next up previous contents
Next: Computing the Delaunay complex Up: Voronoi Diagram and Delaunay Previous: What is Voronoi diagram   Contents


What is the Delaunay triangulation in $ R^d$?

See also 3.2, 3.1.

Let $ S$ be a set of $ n$ points in $ R^d$. The convex hull $ conv(nb(S, v))$ of the nearest neighbor set of a Voronoi vertex $ v$ is called the Delaunay cell of $ v$. The Delaunay complex (or triangulation) of $ S$ is a partition of the convex hull $ conv(S)$ into the Delaunay cells of Voronoi vertices together with their faces.


\includegraphics[height=40mm]{vtest_draw_vode}

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 $ d+2$ points are cospherical or equivalently there is no point $ c\in R^d$ whose nearest neighbor set has more than $ d+1$ 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 $ R^{d+1}$: $ x_{d+1} = x_1^2 + \cdots + x_d^2$. Let $ f(x) = x_1^2 + \cdots + x_d^2$, and let $ \tilde{p}= (p, f(x)) \in R^{d+1}$ for $ p \in S$. Then the so-called lower hull of the lifted points $ \tilde{S}:=\{\tilde{p}: p\in S\}$ represents the Delaunay complex. More precisely, let

$\displaystyle P = conv(\tilde{S}) + nonneg(e^{d+1})
$

where $ e^{d+1}$ is the unit vector in $ R^{d+1}$ whose last component is $ 1$. Thus $ P$ is the unbounded convex polyhedron consisting of $ conv(\tilde{S})$ and any nonnegative shifts by the ``upper'' direction $ r$. The nontrivial claim is that the the boundary complex of $ P$ projects to the Delaunay complex: any facet of $ P$ which is not parallel to the vertical direction $ r$ is a Delaunay cell once its last coordinate is ignored, and any Delaunay cell is represented this way.


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