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.

On constructing Delaunay triangulations for sets constrained by line segments



Javier Bernal


In this paper, we propose a simple algorithm for constructing a Delaunay triangulation for a finite set of points in the plane constrained by a finite collection of line segments. This algorithm constructs first a Delaunay triangulation for the set, and then generates from it a sequence of triangulations as each line segment is incorporated into the previously obtained triangulation. An expected time analysis shows the algorithm to be linear if the number of line segments is kept constant.
Technical Note (NIST TN) - 1252
Report Number


algorithm, computational complexity, computational geometry, constrained Delaunay triangulation, expected time analysis, multiply-connected polygonal regions, Voronoi diagram


Bernal, J. (1988), On constructing Delaunay triangulations for sets constrained by line segments, Technical Note (NIST TN), National Institute of Standards and Technology, Gaithersburg, MD, [online], (Accessed April 16, 2024)
Created September 1, 1988, Updated November 10, 2018