Inserting line segments into triangulations and tetrahedralizations
In this paper, we further develop an algorithm by Bernal, De Floriani, and Puppo, for inserting a line segment into a Constrained Delaunay triangulation. The new version of the algorithm inserts the line segment in exactly the same manner in which the old version does but has the additional capability that it does not delete the triangles intersected by the line segment but transforms them through edge-swapping. Since the concept of edge-swapping generalizes to 3 dimensional space, a 3 dimensional version of the algorithm without the optimization step for the Delaunay property is also presented for attempting to insert a line segment into a tetrahedralization. It is shown that for certain cases the failure of the 3 dimensional algorithm to insert a line segment is an indication that it can not be done. Finally, 3 dimensional problems that can be approached algorithmically as 2 dimensional problems are identified.
computational geometry, constrained Delaunay tri angulation, edge-swapping, empty circle criterion, locally equiangular, segment insertion, Voronoi diagram
Inserting line segments into triangulations and tetrahedralizations, NIST Interagency/Internal Report (NISTIR), National Institute of Standards and Technology, Gaithersburg, MD, [online], https://doi.org/10.6028/NIST.IR.5596
(Accessed March 1, 2024)