Computing Simple Circuits from a Set of Line Segments is NP-Complete
From MaRDI portal
Publication:3034824
DOI10.1137/0218075zbMath0692.68039MaRDI QIDQ3034824
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
computational geometry; Hamiltonian path; line segments; complexity classes; NP-complete problem; Euclidean travelling salesman problem
68Q25: Analysis of algorithms and problem complexity
68U99: Computing methodologies and applications
03D15: Complexity of computation (including implicit computational complexity)
Related Items
Unnamed Item, Augmenting Geometric Graphs with Matchings, Augmenting the Connectivity of Planar and Geometric Graphs, 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, Connectivity augmentation in planar straight line graphs, Pointed binary encompassing trees: simple and optimal, Compatible geometric matchings, Augmenting the connectivity of geometric graphs, Alternating paths through disjoint line segments, Hamiltonian triangulations and circumscribing polygons of disjoint line segments, On a counterexample to a conjecture of Mirzaian, Segment endpoint visibility graphs are Hamiltonian, The visibility graph of congruent discs is Hamiltonian, On \(k\)-convex point sets, Disjoint compatibility graph of non-crossing matchings of points in convex position, Compatible spanning trees, Angle-restricted tours in the plane., Circumscribing polygons and polygonizations for disjoint line segments, Reconstruction of Weakly Simple Polygons from Their Edges
