Computing simple circuits from a set of line segments
From MaRDI portal
Publication:583232
DOI10.1007/BF02187791zbMath0692.05042MaRDI QIDQ583232
Godfried T. Toussaint, Hiroshi 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
Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Other problems of combinatorial convexity (52A37)
Related Items
Two segment classes with Hamiltonian visibility graphs ⋮ Finding Hamiltonian circuits in arrangements of Jordan curves is NP- complete ⋮ Polygonizations of point sets in the plane ⋮ Topics on line segments and polygons ⋮ Circumscribing polygons and polygonizations for disjoint line segments ⋮ Segment endpoint visibility graphs are Hamiltonian ⋮ Compatible spanning trees ⋮ Compatible geometric matchings ⋮ Hamiltonian triangulations and circumscribing polygons of disjoint line segments ⋮ On a counterexample to a conjecture of Mirzaian ⋮ Disjoint compatibility graph of non-crossing matchings of points in convex position ⋮ Unnamed Item ⋮ 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 ⋮ Intersections and circuits in sets of line segments ⋮ Augmenting Geometric Graphs with Matchings
Cites Work
- Unnamed Item
- Unnamed Item
- An efficient algorithm for determining the convex hull of a finite planar set
- Algorithms for Reporting and Counting Geometric Intersections
- The Ultimate Planar Convex Hull Algorithm?
- An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
- On the Computational Complexity of Combinatorial Problems
- The Planar Hamiltonian Circuit Problem is NP-Complete
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
This page was built for publication: Computing simple circuits from a set of line segments
