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

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

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 triangulations of a simple polygon is NP-complete
• 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
• Happy endings for flip graphs
• 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 * 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?)
• Flip distance between triangulations of a simple polygon is NP-complete

Cited In (25)

• Flipping in spirals
• Planar 3-SAT with a clause/variable cycle
• Flip distance between two triangulations of a point set is NP-complete
• A proof of the orbit conjecture for flipping edge-labelled triangulations
• Short flip sequences to untangle segments in the plane
• Flip Distance to some Plane Configurations.
• On flips in planar matchings
• Flip paths between lattice triangulations
• Title not available (Why is that?)
• Disjoint compatibility graph of non-crossing matchings of points in convex position
• Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas
• Flip distance between triangulations of a simple polygon is NP-complete
• The rotation distance of brooms
• An improved kernel for the flip distance problem on simple convex polygons
• On the longest flip sequence to untangle segments in the plane
• Complexity results on untangling red-blue matchings
• Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas
• Flip distance to some plane configurations
• An improved FPT algorithm for the flip distance problem
• Convex dominating sets in maximal outerplanar graphs
• Shortest Reconfiguration of Perfect Matchings via Alternating Cycles
• Flip distance between triangulations of a planar point set is APX-hard
• The Perfect Matching Reconfiguration Problem
• Flip distances between graph orientations
• Computing the flip distance between triangulations

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)