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

DOI10.1007/s00454-015-9709-7zbMath1331.68240arXiv1209.0579OpenAlexW3102370784MaRDI QIDQ894685

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)

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

zbMATH Keywords

triangulationssimple polygonflip distance

Mathematics Subject Classification ID

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

Related Items (24)

Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas ⋮ Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas ⋮ 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 ⋮ Flip paths between lattice triangulations ⋮ On the longest flip sequence to untangle segments in the plane ⋮ Complexity results on untangling red-blue matchings ⋮ An improved kernel for the flip distance problem on simple convex polygons ⋮ The rotation distance of brooms ⋮ Flip distance between two triangulations of a point set is NP-complete ⋮ Flip distance between triangulations of a planar point set is APX-hard ⋮ Flipping in spirals ⋮ Disjoint compatibility graph of non-crossing matchings of points in convex position ⋮ On flips in planar matchings ⋮ Unnamed Item ⋮ Flip distances between graph orientations ⋮ An improved FPT algorithm for the flip distance problem ⋮ The Perfect Matching Reconfiguration Problem ⋮ Convex dominating sets in maximal outerplanar graphs ⋮ Planar 3-SAT with a clause/variable cycle ⋮ Flip distance to some plane configurations ⋮ Flip Distance to some Plane Configurations.

Cites Work

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

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