Next: 5.3 Algorithms for Constructing Up: 5. Delaunay Triangulation Previous: 5.1 Tetrahedralization of a

# 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 be a finite set of points in the -dimensional space and their location vectors . The region given by

is called Voronoi region (Voronoi box) associated with and

is said to be the Voronoi diagram of .

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 .

Criterion 5.1 (Delaunay edge)   Let be a finite set of points in a sub-domain of the -dimensional space . Two points and are connected by a Delaunay edge if and only if there exists a location which is equally close to and and closer to than to any other . The location is the center of an -dimensional sphere which passes through the points and which contains no other points of .

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 be a finite set of points in a sub-domain of the -dimensional space . Three non-collinear points and form a Delaunay triangle if and only if there exists a location which is equally close to and and closer to than to any other . The location is the center of an -dimensional sphere which passes through the points and which contains no other points of . For only one such sphere exists which is the circumcircle of .

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 four5.1 incident Voronoi boxes.

Criterion 5.3 (Delaunay tetrahedron)   Let be a finite set of points in a sub-domain of the -dimensional space , where . Four non-coplanar points and form a Delaunay tetrahedron if and only if there exists a location which is equally close to and and closer to than to any other . The location is the center of an -dimensional sphere which passes through the points and which contains no other points of . For only one such sphere exists which is the circumsphere of .

A Delaunay tetrahedron must consist of Delaunay edges and Delaunay triangles. The edge and triangle criteria are implicit, because the existence of the -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.

Next: 5.3 Algorithms for Constructing Up: 5. Delaunay Triangulation Previous: 5.1 Tetrahedralization of a
Peter Fleischmann
2000-01-20