** 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