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.

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

$$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.