Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Inserting line segments into triangulations and tetrahedralizations



Javier Bernal


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.
NIST Interagency/Internal Report (NISTIR) - 5596
Report Number


computational geometry, constrained Delaunay tri angulation, edge-swapping, empty circle criterion, locally equiangular, segment insertion, Voronoi diagram


Bernal, J. (1995), Inserting line segments into triangulations and tetrahedralizations, NIST Interagency/Internal Report (NISTIR), National Institute of Standards and Technology, Gaithersburg, MD, [online], (Accessed July 15, 2024)


If you have any questions about this publication or are having problems accessing it, please contact

Created March 1, 1995, Updated November 10, 2018