APPROXIMATING CONSTRAINED TETRAHEDRIZATIONS

The facets of a Delaunay tetrahedrization of a set of points in three-dimensional Euclidean space are determined except in the presence of cospherical points. Since it is not always possible to construct in three-dimensional Euclidean space a tetrahedrization that contains prespecified facets, we describe an algorithm to construct a tetrahedrization that incorporates specified convex, planar, polygonal regions, including triangles, as unions of facets of tetrahedra. Points added to the original set lie within the specified regions. The resulting tetrahedrization coincides with the original tetrahedrization except in the vicinity of the specified regions. The worst case behavior of the algorithm is linear in the number of original tetrahedra but exponential in the number of specified regions. Measurement of performance on data generated by applications awaits an implementation.