Hamiltonian triangulations and circumscribing polygons of disjoint line segments (Q1200910)

Let a set of \(n\) disjoint line segments in the plane be given. If all segments have at least one end point on the boundary of the convex hull of the segments, then it is shown that there is a circumscribing polygon \(P\), i.e. a simple polygon having all endpoints as its vertices such that each segment is an edge or an interval diagonal of \(P\). There is an algorithm that gives this polygon in \(0(n\log n)\) time. The conjecture that \(P\) exists without the convex hull assumption is disproved in the paper reviewed below.