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

DOI10.1016/j.comgeo.2014.01.001zbMath1293.65032arXiv1206.3179OpenAlexW3104079118MaRDI 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

triangulationflip distanceAPX-hard problem

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Related Items (16)

Shortest Reconfiguration of Perfect Matchings via Alternating Cycles ⋮ Computing the flip distance between triangulations ⋮ A proof of the orbit conjecture for flipping edge-labelled triangulations ⋮ Flip distance between triangulations of a simple polygon is NP-complete ⋮ 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 ⋮ Arc diagrams, flip distances, and Hamiltonian triangulations ⋮ The rotation distance of brooms ⋮ Flip distance between two triangulations of a point set is NP-complete ⋮ Minimum weight connectivity augmentation for planar straight-line graphs ⋮ Reconstruction of the crossing type of a point set from the compatible exchange graph of noncrossing spanning trees ⋮ Unnamed Item ⋮ Transition operations over plane trees ⋮ An improved FPT algorithm for the flip distance problem ⋮ Introduction to reconfiguration

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

This page was built for publication: Flip distance between triangulations of a planar point set is APX-hard