Constructing Delaunay Triangulations for Sets Constrained by Line Segments

摘要

In the paper, the authors 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. The 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.