Computing simple circuits from a set of line segments

DOI10.1007/BF02187791zbMATH Open0692.05042MaRDI QIDQ583232FDOQ583232

Godfried Toussaint, Hideki Imai, David Rappaport

Publication date: 1990

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131118

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Other problems of combinatorial convexity (52A37)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• An efficient algorithm for determining the convex hull of a finite planar set
• The Planar Hamiltonian Circuit Problem is NP-Complete
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Algorithms for Reporting and Counting Geometric Intersections
• On the Computational Complexity of Combinatorial Problems
• The Ultimate Planar Convex Hull Algorithm?
• An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon

Cited In (17)

• Hamiltonian triangulations and circumscribing polygons of disjoint line segments
• Compatible spanning trees
• Topics on line segments and polygons
• Circumscribing polygons and polygonizations for disjoint line segments
• Pointed binary encompassing trees: simple and optimal
• Finding Hamiltonian circuits in arrangements of Jordan curves is NP- complete
• Disjoint compatibility graph of non-crossing matchings of points in convex position
• Two segment classes with Hamiltonian visibility graphs
• Alternating paths through disjoint line segments
• Intersections and circuits in sets of line segments
• Polygonizations of point sets in the plane
• Title not available (Why is that?)
• Augmenting Geometric Graphs with Matchings
• On a counterexample to a conjecture of Mirzaian
• Segment endpoint visibility graphs are Hamiltonian
• On an estimate of the size of the maximum matching for a family of disjoint compact convex sets in the plane
• Compatible geometric matchings

   Recommendations

• Computing Simple Circuits from a Set of Line Segments is NP-Complete 👍 👎
• Complexity of linear circuits and geometry 👍 👎
• Title not available (Why is that?) 👍 👎
• Intersections and circuits in sets of line segments 👍 👎
• Circuits through prescribed edges 👍 👎
• Title not available (Why is that?) 👍 👎
• Finding all solutions of piecewise-linear circuits 👍 👎
• On computing connected components of line segments 👍 👎
• Circuits including a given set of vertices 👍 👎

This page was built for publication: Computing simple circuits from a set of line segments

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