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
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references