3D Conforming Delaunay Triangulation

A three-dimensional domain with piecewise linear boundary elements can be represented as a piecewise linear complex (PLC) of linear cells – vertices, edges, polygons, and polyhedra – that satisfy the following properties [4]. First, no vertex lies in the interior of an edge and every two edges are interior-disjoint. Second, the boundary of a polygon or polyhedra are union of cells in the PLC. Third, if two cells f and g intersect, the intersection is a union of cells in the PLC with dimensions lower than f or g. A triangulation of an input PLC is conforming if every edge and polygon appear as a union of segments and triangles in the triangulation. Additional Steiner vertices are often necessary. The 3D conforming Delaunay triangulation problem is to construct a triangulation of an input PLC that is both conforming and Delaunay. Figure 1a, b shows an input PLC and its conforming Delaunay triangulation. In many applications, it is often desired that the triangulation is not unnecessarily dense and the resulting tetrahedra are of bounded aspect ratio. Another popular shape measure is the radius-edge ratio, which is the ratio of the circumradius of the tetrahedron to its shortest edge length. Tetrahedra with bounded radius-edge ratio may still have negligible volume, and they are known as slivers. Figure 1c shows a sliver