Computing Simple Circuits from a Set of Line Segments is NP-Complete

DOI10.1137/0218075zbMath0692.68039OpenAlexW2028883079MaRDI QIDQ3034824

David Rappaport

Publication date: 1989

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0218075

zbMATH Keywords

computational geometryHamiltonian pathline segmentscomplexity classesNP-complete problemEuclidean travelling salesman problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computing methodologies and applications (68U99) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (20)

The visibility graph of congruent discs is Hamiltonian ⋮ Reconstruction of Weakly Simple Polygons from Their Edges ⋮ Circumscribing polygons and polygonizations for disjoint line segments ⋮ Segment endpoint visibility graphs are Hamiltonian ⋮ Compatible spanning trees ⋮ Compatible geometric matchings ⋮ Augmenting the connectivity of geometric graphs ⋮ Connectivity augmentation in planar straight line graphs ⋮ On \(k\)-convex point sets ⋮ Hamiltonian triangulations and circumscribing polygons of disjoint line segments ⋮ On a counterexample to a conjecture of Mirzaian ⋮ Angle-restricted tours in the plane. ⋮ Disjoint compatibility graph of non-crossing matchings of points in convex position ⋮ 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 ⋮ Pointed binary encompassing trees: simple and optimal ⋮ Alternating paths through disjoint line segments ⋮ Augmenting the Connectivity of Planar and Geometric Graphs ⋮ Augmenting Geometric Graphs with Matchings

This page was built for publication: Computing Simple Circuits from a Set of Line Segments is NP-Complete