The inverse problem to the Voronoi diagram

The primary purpose of this thesis is to address the problem of solving the Inverse Problem for the Voronoi Diagram where the Inverse Problem is: Given a diagram that is in fact a Voronoi Diagram find the set of points X = {x1, x2, x3,…,x n} in R2 that will generate the diagram. In formulating a solution to the Inverse Problem it was necessary that we consider the problem of characterizing Voronoi Diagrams. In developing an algorithm for determining the generating set we considered questions of the form: Is the solution to the Inverse Problem unique? If the solution to the Inverse Problem is not unique, then what properties characterize the Voronoi Diagram? In addition we will develop solutions to a set of problems related to Voronoi Diagrams. These problems are related to: Given a finite set of points X = {x1, x2, x3,…,x n} in R2 find the domain of points Nk such that for every x &egr; N k, xk is the nearest point to x, that is,

x − xk

£

x − xj

for every j ≠ k.