5.2 Definition and Delaunay Properties

The definition of the Delaunay Triangulation is based on the Voronoi diagram through the principle of duality (Fig. 5.1). Voronoi diagrams and their application in an enormous amount of fields are described in detail with many original references in [117].

Definition 5.1 (Voronoi)   Let $P=\{p_{1},\ldots ,p_{k}\}$ be a finite set of points in the $n$-dimensional space $R^{n}$ and their location vectors $\mathbf{x}_{i}\not = \mathbf{x}_{j} \ \forall \:i\not =j$. The region given by

$$V(p_{i})= \{\mathbf{x}\mid \Vert\mathbf{x}-\mathbf{x}_{i}\Vert \leq \Vert \mathbf{x-x}_{j}\Vert \ \forall \:j \not = i \}$$

is called Voronoi region (Voronoi box) associated with $p_{i}$ and

$$\mathcal{V}(P) = \bigcup_{i=1}^{k} V(p_{i})$$

is said to be the Voronoi diagram of $P$.

A Voronoi box is formed through the intersection of planes and is therefore a general irregular polyhedron. The facets of the Voronoi boxes correspond in the dual graph to the Delaunay edges which connect the points of $P$.

Figure 5.1: Each Voronoi box associated with a point is differently shaded. Two triangles $t_{1}, t_{2}$ with their circumcenters $M_{1}, M_{2}$ which are the vertices of the Voronoi boxes are depicted for the correct Delaunay case and for the non-Delaunay case. Incorrect Voronoi boxes which are derived from non-Delaunay triangles overlap.

Criterion 5.1 (Delaunay edge)   Let $P$ be a finite set of points in a sub-domain $\Omega^{n}$ of the $n$-dimensional space $R^{n}$. Two points $p_{i}$ and $p_{j}$ are connected by a Delaunay edge $e$ if and only if there exists a location $x \in \Omega^{n}$ which is equally close to $p_{i}$ and $p_{j}$ and closer to $p_{i}, p_{j}$ than to any other $p_{k} \in P$. The location $x$ is the center of an $n$-dimensional sphere which passes through the points $p_{i}, p_{j}$ and which contains no other points $p_{k}$ of $P$.

$$\begin{eqnarray*} e_{\mathit{Delaunay}}(p_{i},p_{j}) \Longleftrightarrow \exist... ...l \:k \not = i,j \ \ \Vert x - p_{i}\Vert<\Vert x - p_{k}\Vert \end{eqnarray*}$$

Combining this criterion for the three edges of a triangle and furthermore for the four triangles of a tetrahedron leads to the following criteria for Delaunay simplices. A Delaunay triangle is thereby the dual of a Voronoi edge.

Criterion 5.2 (Delaunay triangle)   Let $P$ be a finite set of points in a sub-domain $\Omega^{n}$ of the $n$-dimensional space $R^{n}$. Three non-collinear points $p_{i}, p_{j}$ and $p_{k}$ form a Delaunay triangle $t$ if and only if there exists a location $x \in \Omega^{n}$ which is equally close to $p_{i}, p_{j}$ and $p_{k}$ and closer to $p_{i}, p_{j}, p_{k}$ than to any other $p_{m} \in P$. The location $x$ is the center of an $n$-dimensional sphere which passes through the points $p_{i}, p_{j}, p_{k}$ and which contains no other points $p_{m}$ of $P$. For $n=2$ only one such sphere exists which is the circumcircle of $t$.

$$\begin{eqnarray*} t_{\mathit{Delaunay}}(p_{i},p_{j},p_{k}) \Longleftrightarrow ... ...\:m \not = i,j,k \ \ \Vert x - p_{i}\Vert<\Vert x - p_{m}\Vert \end{eqnarray*}$$

Figure 5.2: The Delaunay edge (a) and Delaunay triangle (b) criteria.

Crit. 5.2 implies that an empty circumcircle is necessary but not sufficient for Delaunay surface triangles in three dimensions. This is the reason why a two-dimensional Delaunay Triangulation code is of limited use to construct a three-dimensional Delaunay surface triangulation. The Delaunay edge and Delaunay triangle criteria are depicted in Fig. 5.2. A Delaunay tetrahedron corresponds to a point in the Voronoi diagram, which is the vertex of four^5.1 incident Voronoi boxes.

Criterion 5.3 (Delaunay tetrahedron)   Let $P$ be a finite set of points in a sub-domain $\Omega^{n}$ of the $n$-dimensional space $R^{n}$, where $n\geq3$. Four non-coplanar points $p_{i}, p_{j}, p_{k}$ and $p_{l}$ form a Delaunay tetrahedron $T$ if and only if there exists a location $x \in \Omega^{n}$ which is equally close to $p_{i}, p_{j}, p_{k}$ and $p_{l}$ and closer to $p_{i}, p_{j}, p_{k}, p_{l}$ than to any other $p_{m} \in P$. The location $x$ is the center of an $n$-dimensional sphere which passes through the points $p_{i}, p_{j}, p_{k}, p_{l}$ and which contains no other points $p_{m}$ of $P$. For $n=3$ only one such sphere exists which is the circumsphere of $T$.

$$\begin{eqnarray*} T_{\mathit{Delaunay}}(p_{i},p_{j},p_{k},p_{l}) \Longleftright... ...m \not = i,j,k,l \ \ \Vert x - p_{i}\Vert<\Vert x - p_{m}\Vert \end{eqnarray*}$$

A Delaunay tetrahedron must consist of Delaunay edges and Delaunay triangles. The edge and triangle criteria are implicit, because the existence of the $n$-dimensional sphere in Crit. 5.1 and in Crit. 5.2 is guaranteed by the sphere in Crit. 5.3.

An anisotropic Delaunay Triangulation [20] can be defined through a simple linear transformation. The empty circumcircle criterion is applied in the transformed space and results in an empty ellipse in the mesh space. The transformation must be allowed to change over the domain to be practically useful. This leads to difficulties in the grading of the mesh. For an extremely inhomogeneous transformation the Delaunay Triangulation cannot be applied in a consistent way and the excellent property to always guarantee a valid tessellation without special consistency checks is lost.