    Next: What is the Delaunay Up: Voronoi Diagram and Delaunay Previous: What is cell complex?   Contents

## What is Voronoi diagram in ?

See also 3.3.

Given a set of distinct points in , Voronoi diagram is the partition of into polyhedral regions ( ). Each region , called the Voronoi cell of , is defined as the set of points in which are closer to than to any other points in , or more precisely, where is the Euclidean distance function. (One can use different distance functions to define various variations of Voronoi diagrams, but we do not discuss them here.) The set of all Voronoi cells and their faces forms a cell complex. The vertices of this complex are called the Voronoi vertices, and the extreme rays (i.e. unbounded edges) are the Voronoi rays. For each point , the nearest neighbor set of in is the set of points which are closest to in Euclidean distance. Alternatively, one can define a point to be a Voronoi vertex of if is maximal over all nearest neighbor sets.

In order to compute the Voronoi diagram, the following construction is very important. For each point in , consider the hyperplane tangent to the paraboloid in at : . This hyperplane is represented by : By replacing the equality with inequality above for each point , we obtain the system of inequalities, which we denote by . The polyhedron in of all solutions to the system of inequalities is a lifting of the Voronoi diagram to one higher dimensional space. In other words, by projecting the polyhedron onto the original space, we obtain the Voronoi diagram in the sense that the projection of each facet of associated with is exactly the voronoi cell . The vertices and the extreme rays of project exactly to the Voronoi vertices and the rays, respectively.     Next: What is the Delaunay Up: Voronoi Diagram and Delaunay Previous: What is cell complex?   Contents
Komei Fukuda 2004-08-26