5.5 Boundary Integrity

Constraining boundaries are usually defined as a set $I$ of vertices, edges, and facets which are closed under intersection. All intersections between entities in $I$ must be present in $I$. The facets are bounded by edges of $I$. All vertices of facets and edges must be contained in $I$. In two dimensions such a set is called a planar straight line graph (PSLG) and in higher dimensions piecewise linear complex (PLC). A Delaunay Triangulation of the vertices of $I$ will generally not be conform with the edges and facets of $I$ (Fig. 5.3-a). Special means are required to incorporate $I$ into the Delaunay Triangulation. Two different theoretical concepts exist which extend the definition of the Delaunay Triangulation for boundaries. Furthermore, two different approaches exist when to incorporate the boundaries from an algorithmic point of view.

Figure 5.3: (a) Boundaries which are not conform with the Delaunay Triangulation (b) A constrained Delaunay Triangulation (c) A conforming Delaunay Triangulation