Computing simple circuits from a set of line segments
From MaRDI portal
Recommendations
- Computing Simple Circuits from a Set of Line Segments is NP-Complete
- Complexity of linear circuits and geometry
- On constructing the shortest circuits on a set of line segments
- Intersections and circuits in sets of line segments
- Circuits through prescribed edges
- scientific article; zbMATH DE number 4062595
- Finding all solutions of piecewise-linear circuits
- On computing connected components of line segments
- Circuits including a given set of vertices
Cites work
- scientific article; zbMATH DE number 4062595 (Why is no real title available?)
- scientific article; zbMATH DE number 3557226 (Why is no real title available?)
- Algorithms for Reporting and Counting Geometric Intersections
- An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- An efficient algorithm for determining the convex hull of a finite planar set
- On the Computational Complexity of Combinatorial Problems
- The Planar Hamiltonian Circuit Problem is NP-Complete
- The Ultimate Planar Convex Hull Algorithm?
Cited in
(20)- Hamiltonian triangulations and circumscribing polygons of disjoint line segments
- Compatible spanning trees
- Topics on line segments and polygons
- Reconstruction of weakly simple polygons from their edges
- scientific article; zbMATH DE number 4062595 (Why is no real title available?)
- 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
- scientific article; zbMATH DE number 7559209 (Why is no real title available?)
- On a counterexample to a conjecture of Mirzaian
- Segment endpoint visibility graphs are Hamiltonian
- Augmenting Geometric Graphs with Matchings
- Compatible geometric matchings
- On an estimate of the size of the maximum matching for a family of disjoint compact convex sets in the plane
- Computing Simple Circuits from a Set of Line Segments is NP-Complete
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)
