Hamiltonian triangulations and circumscribing polygons of disjoint line segments (Q1200910)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Hamiltonian triangulations and circumscribing polygons of disjoint line segments |
scientific article |
Statements
Hamiltonian triangulations and circumscribing polygons of disjoint line segments (English)
0 references
16 January 1993
0 references
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.
0 references
\(n\) disjoint line segments in the plane
0 references
circumscribing polygon
0 references
algorithm
0 references
0 references