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. 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.