Flip distance between triangulations of a planar point set is APX-hard
From MaRDI portal
Publication:2444311
DOI10.1016/j.comgeo.2014.01.001zbMath1293.65032arXiv1206.3179MaRDI QIDQ2444311
Publication date: 9 April 2014
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1206.3179
65D18: Numerical aspects of computer graphics, image analysis, and computational geometry
Related Items
Unnamed Item, Shortest Reconfiguration of Perfect Matchings via Alternating Cycles, Transition operations over plane trees, On the longest flip sequence to untangle segments in the plane, Complexity results on untangling red-blue matchings, A survey of parameterized algorithms and the complexity of edge modification, Flip distance between triangulations of a simple polygon is NP-complete, Flip distance between two triangulations of a point set is NP-complete, Arc diagrams, flip distances, and Hamiltonian triangulations, Reconstruction of the crossing type of a point set from the compatible exchange graph of noncrossing spanning trees, An improved FPT algorithm for the flip distance problem, Minimum weight connectivity augmentation for planar straight-line graphs, Introduction to reconfiguration, Computing the flip distance between triangulations, A proof of the orbit conjecture for flipping edge-labelled triangulations
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Every large point set contains many collinear points or an empty pentagon
- On the hardness of approximating minimum vertex cover
- Flip distance between triangulations of a simple polygon is NP-complete
- Flips in planar graphs
- Rotation distance is fixed-parameter tractable
- A note on some tree similarity measures
- Optimization, approximation, and complexity classes
- Some APX-completeness results for cubic graphs
- Flipping edges in triangulations
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Transforming triangulations
- Happy endings for flip graphs
- Rotation Distance, Triangulations, and Hyperbolic Geometry
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Approximation algorithms for NP-complete problems on planar graphs
- Elliptic Curves
- Automata, Languages and Programming