next up previous contents
Next: 5.4 Non-Uniqueness Up: 5.3 Algorithms for Constructing Previous: 5.3.4 Incremental Search

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

\tilde{x} & = & x \\
\tilde{y} & = & y \\
\tilde{z} & = & x^{2}+y^{2}

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

Peter Fleischmann