Hamiltonian triangulations and circumscribing polygons of disjoint line segments

DOI10.1016/0925-7721(92)90018-NzbMath0761.52005MaRDI QIDQ1200910

Andranik Mirzaian

Publication date: 16 January 1993

Published in: Computational Geometry (Search for Journal in Brave)

zbMATH Keywords

algorithm\(n\) disjoint line segments in the planecircumscribing polygon

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Paths and cycles (05C38) Convex sets in (2) dimensions (including convex curves) (52A10)

Related Items (12)

The visibility graph of congruent discs is Hamiltonian ⋮ Two segment classes with Hamiltonian visibility graphs ⋮ Circumscribing polygons and polygonizations for disjoint line segments ⋮ On circumscribing polygons for line segments ⋮ Segment endpoint visibility graphs are Hamiltonian ⋮ Compatible spanning trees ⋮ Compatible geometric matchings ⋮ On a counterexample to a conjecture of Mirzaian ⋮ Unnamed Item ⋮ On the visibility graph of convex translates ⋮ On an estimate of the size of the maximum matching for a family of disjoint compact convex sets in the plane ⋮ On the perfect matching of disjoint compact sets by noncrossing line segments in \(\mathbb R^n\)

Cites Work

• Unnamed Item
• Unnamed Item
• Computing simple circuits from a set of line segments
• A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• Traveling salesman cycles are not always subgraphs of Voronoi duals
• Traveling salesman cycles are not always subgraphs of Delaunay triangulations or of minimum weight triangulations
• A linear-time algorithm for finding a minimum spanning pseudoforest
• Triangulating a simple polygon in linear time
• An efficient algorithm for determining the convex hull of a finite planar set
• The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs
• Computing Simple Circuits from a Set of Line Segments is NP-Complete
• Geometry Helps in Matching
• A Theorem on Planar Graphs
• Hamiltonian cycles in planar triangulations with no separating triangles

This page was built for publication: Hamiltonian triangulations and circumscribing polygons of disjoint line segments