5.3.5 Convex Hull

An $n$-dimensional Delaunay Triangulation can be deduced from a computation of the convex hull in $(n+1)$ dimensions. For example a two-dimensional Delaunay Triangulation of a point set $P$ is equivalent to the projection of the convex hull of a three-dimensional point set $\tilde{P}$ which is derived from $P$ through a lifting transformation [15,114].

$$\begin{eqnarray*} \tilde{x} & = & x \\ \tilde{y} & = & y \\ \tilde{z} & = & x^{2}+y^{2} \end{eqnarray*}$$

A detailed discussion of convex hull algorithms can be found in [123].