Flip distance between triangulations of a simple polygon is NP-complete

DOI10.1007/978-3-642-40450-4_2zbMATH Open1331.68240arXiv1209.0579OpenAlexW3102370784MaRDI QIDQ894685FDOQ894685

Authors: Wolfgang Mulzer, Alexander Pilz, Oswin Aichholzer 

Publication date: 2 December 2015

Published in: Lecture Notes in Computer Science, Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: Let T be a triangulation of a simple polygon. A flip in T is the operation of removing one diagonal of T and adding a different one such that the resulting graph is again a triangulation. The flip distance between two triangulations is the smallest number of flips required to transform one triangulation into the other. For the special case of convex polygons, the problem of determining the shortest flip distance between two triangulations is equivalent to determining the rotation distance between two binary trees, a central problem which is still open after over 25 years of intensive study. We show that computing the flip distance between two triangulations of a simple polygon is NP-complete. This complements a recent result that shows APX-hardness of determining the flip distance between two triangulations of a planar point set.

Full work available at URL: https://arxiv.org/abs/1209.0579

Recommendations

• Flip distance between two triangulations of a point set is NP-complete
• Flipping edges in triangulations
• Computing the flip distance between triangulations
• Flip distance is in FPT time \(O(n+ k \cdot c^k)\)

zbMATH Keywords

triangulationssimple polygonflip distance

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Flipping edges in triangulations
• The power of geometric duality
• The Steiner tree problem
• Rotation Distance, Triangulations, and Hyperbolic Geometry
• Constructing Arrangements of Lines and Hyperplanes with Applications
• Transforming triangulations
• The rectilinear Steiner arborescence problem
• Title not available (Why is that?)
• Flips in planar graphs
• A note on some tree similarity measures
• Every large point set contains many collinear points or an empty pentagon
• Polynomial time approximation scheme for the rectilinear Steiner arborescence problem
• Flip distance is in FPT time \(O(n+ k \cdot c^k)\)
• Flip distance between two triangulations of a point set is NP-complete
• Title not available (Why is that?)
• Flip distance between triangulations of a planar point set is APX-hard
• Subclass of the Steiner problems on a plane with rectilinear metric
• Title not available (Why is that?)

This page was built for publication: Flip distance between triangulations of a simple polygon is NP-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q894685)