** Next:** Computing the Delaunay complex
** Up:** Voronoi Diagram and Delaunay
** Previous:** What is Voronoi diagram
** Contents**

##

What is the Delaunay triangulation in ?

See also 3.2, 3.1.

Let be a set of points in .
The convex hull
of the nearest neighbor set of a
Voronoi vertex is called the Delaunay cell of .
The Delaunay complex (or triangulation) of
is a partition of the convex hull into
the Delaunay cells of Voronoi vertices together with
their faces.

The Delaunay complex is not in general a triangulation
but becomes a triangulation when the input points are in
*general position* (or *nondegenerate*),
i.e. no points are cospherical or equivalently there is no
point whose nearest neighbor set has more than elements.

The Delaunay complex is dual to the Voronoi diagram 3.2
in the sense that there is a natural bijection between the
two complexes which reverses the face inclusions.

There is a direct way to represent the Delaunay complex, just like
the Voronoi diagram 3.2. In fact, it uses the same
paraboloid in :
.
Let
, and let
for . Then the so-called lower hull of the lifted points
represents the Delaunay complex.
More precisely, let

where is the unit vector in whose last component is .
Thus is the unbounded convex polyhedron
consisting of
and
any nonnegative shifts by the ``upper'' direction .
The nontrivial claim is that the the boundary complex of projects
to the Delaunay complex: any facet of which is not parallel
to the vertical direction is a Delaunay cell once its last coordinate
is ignored, and any Delaunay cell is represented this way.

** Next:** Computing the Delaunay complex
** Up:** Voronoi Diagram and Delaunay
** Previous:** What is Voronoi diagram
** Contents**
Komei Fukuda
2004-08-26