General-dimensional constrained delaunay and constrained regular triangulations I: Combinatorial properties, Discrete Comput

Two-dimensional constrained Delaunay triangulations are geometric structures that are popular for interpo-lation and mesh generation because they respect the shapes of planar domains, they have “nicely shaped” triangles that optimize several criteria, and they are easy to construct and update. The present work gener-alizes constrained Delaunay triangulations (CDTs) to higher dimensions and describes constrained variants of regular triangulations, here christened weighted CDTs and constrained regular triangulations. CDTs and weighted CDTs are powerful and practical models of geometric domains, especially in two and three dimensions. The main contributions are rigorous, theory-tested definitions of constrained Delaunay triangulations and piecewise linear complexes (geometric domains that incorporate nonconvex faces with “internal ” bound-aries), a characterization of the combinatorial properties of CDTs and weighted CDTs (including a general-ization of the Delaunay Lemma), the proof of several optimality properties of CDTs when they are used for piecewise linear interpolation, and a simple and useful condition that guarantees that a domain has a CDT. These results provide foundations for reasoning about CDTs and proving the correctness of algorithms