An optimal algorithm for constructing the Delaunay triangulation of a set of line segments

Abstract

In this paper, we first define a new Voronoi diagram for the endpoints of a set of line segments in the plane which do not intersect (except possibly at their endpoints), which is called a bounded Voronoi diagram. In this Voronoi diagram, the line segments themselves are regarded as obstacles. We present an optimal Θ(n log n) algorithm to construct it, where n is the number of input line segments.