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,
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
: