An Introduction to Algorithms for Constructing Conforming Delaunay Tetrahedrizations

In many computational applications involving 3D geometric modeling, a space decomposition of the problem domain whose elements satisfy some quality constraints is often required. The Delaunay tetrahedrization is a popular choice due to its many important geometric properties and to the existence of efficient algorithms to compute and to maintain it. However, the Delaunay tetrahedrization has a serious limitation: Its underlying space is convex, and thus it can only induce a space subdivision of convex domains. The adaptation of the Delaunay tetrahedrization, defined over a finite set of points, to more complicated domains, such as arbitrary polyhedra, has proven to be a major challenge for both the mesh generation and computational geometry communities. The conforming Delaunay tetrahedrization is such an adaptation. A conforming Delaunay tetrahedrization of an arbitrary polyhedron is the Delaunay tetrahedrization of some finite set of points in which the boundary of the polyhedron is represented by the vertices, edges, and facets of the tetrahedrization. The primary goal of any algorithm for constructing such a tetrahedrization is to find an appropriate set of points for which the Delaunay tetrahedrization conforms to the boundary of the input domain. It turns out that this goal poses many algorithmic challenges. For instance, it is not known if there is a polynomial upper bound for the size of the set of vertices of the tetrahedrization with respect to the number of vertices of the input polyhedron. Furthermore, there is no known solution that can fully reconcile boundary conformity and quality constraints for some of the most common quality metrics. In this paper we review four algorithms for constructing a Delaunay tetrahedrization that conforms to the boundary of an arbitrary polyhedron and to an optional set of isolated vertices, edges, and facets lying in the interior of the polyhedron. All these algorithms are provably guaranteed to terminate and to satisfy some quality constraints. We present the proofs of correctness and termination of the algorithms, compare their contributions, advantages and weaknesses, report on their complexity issues, and highlight some of the most important unsolved questions related to the problem of obtaining a conforming Delaunay tetrahedrization.