Flip distance between triangulations of a planar point set is APX-hard

DOI10.1016/j.comgeo.2014.01.001zbMath1293.65032arXiv1206.3179MaRDI QIDQ2444311

Alexander Pilz

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

zbMATH Keywords

triangulation; flip distance; APX-hard problem

Mathematics Subject Classification ID

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