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], https://doi.org/10.6028/NIST.TN.1252
(Accessed October 23, 2025)
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
Published
Author(s)
Abstract
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.Citation
Technical Note (NIST TN) - 1252
Report Number
1252
NIST Pub Series
Pub Type
NIST Pubs
Download Paper
Keywords
algorithm, computational complexity, computational geometry, constrained Delaunay triangulation, expected time analysis, multiply-connected polygonal regions, Voronoi diagram
Citation
Issues
If you have any questions about this publication or are having problems accessing it, please contact [email protected].
Created September 1, 1988, Updated November 10, 2018