Speaker:
Mary C. Krembs
Title:
Classification and Approximation of Voronoi Nets
Abstract:
Determining the Voronoi diagram for a set of points in the plane is a well studied computational geometry topic. This talk focuses on the inverse problem and related questions.
The definition of 'net' is formalized and topological, graph theoretic and geometric properties of a net are discussed. A new definition of a Voronoi diagram is provided that admits multiple sets of sites. A complete theoretical solution is presented to the inverse problem of "Given an arbitrary net, determine whether or not it is a Voronoi net. If it is, find all sets of sites that generate the net."
Several notions of a net being "close" to a Voronoi net are provided. A data structure for representing an arbitrary net is given. This data structure allows the graph theoretic and topological properties of the net to be abstracted. Using the data structure, all possible (topologically distinct) Voronoi nets resulting from n sites for n =2..6 are listed. A set of necessary topological and graph theoretic properties for an arbitrary abstract net to be realizable as a Voronoi net is given. Applications for this work, and open problems resulting from this work are discussed.
Audience:
The talk will be accessible to math majors.
[Program
Information | Faculty | Mathematics Seminar | Mathematics Links]
[Math Department Home Page | Marist College]