Flip Distance Between Triangulations of a Planar Point Set is APX-Hard

Abstract

In this work we consider triangulations of point sets in the Euclidean plane, i.e., maximal straight-line crossing-free graphs on a finite set of points. Given a triangulation of a point set, an edge flip is the operation of removing one edge and adding another one, such that the resulting graph is again a triangulation. Flips are a major way of locally transforming triangular meshes. We show that, given a point set $S$ in the Euclidean plane and two triangulations $T_1$ and $T_2$ of $S$, it is an APX-hard problem to minimize the number of edge flips to transform $T_1$ to $T_2$.

A previous version only showed NP-completeness of the corresponding decision problem. The current version is the one of the accepted manuscript

Cited by in corpus (4)

• Flip Distance Between Triangulations of a Simple Polygon is NP-Complete
• Eccentricities in the flip-graphs of convex polygons
• The rotation distance of brooms
• Gap-planar Graphs