Approximating constrained tetrahedrizations (Q1208496): Difference between revisions

It was shown by \textit{E. Schönhardt} [Mat. Ann. 89, 309-312 (1927; JFM 53.0576.01)] that it is not always possible to turn a given set of points in \(\mathbb{R}^ 3\) into the vertices of a pseudo-manifold simplicial complex and such that a preassigned triangle should appear as a face in the complex. In computer aided design one has the additional problem that one would like to work with Delaunay triangulations for which many procedures are available. \textit{A. K. Cline} and \textit{R. J. Renka} [SIAM J. Numer. Anal. 27, No. 5, 1305-1321 (1990; Zbl 0714.65024)] relaxed the definition of a Delaunay triangulation in the case of two-dimensional problems to give an algorithm that allows the incorporation of pre-assigned segments. The author shows that a three-dimensional analogue of the Cline and Renka definition also leads to problems without solution. She therefore relaxes the conditions still more to obtain an explicit procedure that from a (Delaunay) triangulation \(T'\) of a pointset \(P'\) and a finite collection \(R\) of planar convex polygonal regions returns a set \(P\) and triangulation \(T\) of \(P\) such that \(P\setminus P' \in R\), \(T\) coincides with \(T'\) except for tetrahedra that are intersected (but not in face) by a region in \(R\) and any polygon in \(R\) is the union of faces of tetrahedra in \(T\). The procedure is linear in the number of tetrahedra in \(T'\) but exponential in the number of members of \(R\).