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

## What is the Delaunay triangulation in ?

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