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