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 &THgr;(n log n) algorithm to construct it, where n is the number of input line segments.We then show that the straight-line dual of the bounded Voronoi diagram of a set of non-intersecting line segments is the Delaunay triangulation of that set. And the straight-line dual can be obtained in time proportional to the number of input line segments when the corresponding bounded Voronoi diagram is available. Consequently, we obtain an optimal &THgr;(n log n) algorithm to construct the Delaunay triangulation of a set of n non-intersecting line segments in the plane. Our algorithm improves the time bound &Ogr;(n2) of the previous best algorithm.