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

DOI10.1137/0218075MaRDI QIDQ3034824zbMATH OpenOpenAlexFDO

Authors 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

complexity classescomputational geometryEuclidean travelling salesman problemHamiltonian pathline segmentsNP-complete problem

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 4062595
• Computing simple circuits from a set of line segments
• Contact graphs of line segments are NP-complete
• On non-intersecting Eulerian circuits
• Reconstructing sets of orthogonal line segments in the plane

Cited in

(27)

• Alternating paths through disjoint line segments
• Hamiltonian triangulations and circumscribing polygons of disjoint line segments
• On a counterexample to a conjecture of Mirzaian
• Finding Hamiltonian circuits in arrangements of Jordan curves is NP- complete
• 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
• scientific article; zbMATH DE number 4062595 (Why is no real title available?)
• Augmenting Geometric Graphs with Matchings
• Circumscribing polygons and polygonizations for disjoint line segments
• Augmenting the connectivity of planar and geometric graphs
• Computing simple circuits from a set of line segments
• 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
• Partitioning a planar assembly into two connected parts is NP-complete
• Reconstructing sets of orthogonal line segments in the plane
• On plane cycles in geometric multipartite graphs
• Crossing and independent families among polygons
• Pointed binary encompassing trees: simple and optimal
• Compatible geometric matchings
• Augmenting the connectivity of geometric graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3034824)