General-dimensional constrained Delaunay and constrained regular triangulations. I: Combinatorial properties (Q2482216)

The definition of Delaunay triangulation is too restrictive to comply with constraints such as discontinuity of boundary in objects rendering. In the two-dimensional case, several options are available. One can, for instance, augment the number of points and then construct the Delaunay triangulation of the enlarged vertex set, or relax the requirements for the triangles determined by the initial points. The former idea leads to the notion of conforming Delaunay triangulation; the latter to what it is improperly called constrained Delaunay triangulation (CDT). The author of the paper at hand proposes a recursive definition of CDT in higher dimensions. The motivation for choosing the properties retained in the definition, as well as the geometric justification, is carefully explained. Variants of regular triangulations are considered under the name weighted CDTs and constrained regular triangulations. As a first test of the usefulness of these notions, many basic properties are shown to be similar to well-known combinatorial properties of Delaunay triangulations. In order to verify that a triangulation is or remains a CDT, one may use the fact that the definition of CDT is local in the sense that a triangulation of a vertex set is Delaunay if and only if its facets are locally Delaunay. Additional evidence in favour of the pertinence and usefulness of the notions introduced in this paper is provided in Section 4. Here it is proved that CDTs are optimal by several criteria when used for piecewise linear interpolation. Even when it lacks such optimality, a CDT is a good starting point for mesh improvements algorithms. The paper ends with the difficult proof of a result that points out a sufficient condition for the existence of a CDT. However, this condition is relatively easy to enforce in three dimensions, so it is valuable in geometric modeling of three-dimensional objects. The results proved in this article provide foundations for correctness of algorithms for constructing and updating higher-dimensional CDTs, algorithms that will be described in later work.