Flip Distance Between Triangulations of Convex Polygons is NP-Complete

Abstract

The complexity of determining the minimum number of flips that transform one triangulation of a convex polygon into another has been raised as an open problem by Culik and Wood [Inf. Proc. Letters 1982] and has been popularized through the study of extremal pairs of triangulations by Sleator, Tarjan, and Thurston [STOC 1986 & J. Am. Math. Society 1988]. The search for a hardness proof for the flip distance problem has yielded many (weaker) hardness-results in more general settings. Lubiw and Pathak [CCCG 2012, Comp. Geom. 2014] and Pilz [Comp. Geom. 2014] proved that computing the flip distance between triangulations of point sets in general position is NP-complete. Further, Aichholzer, Mulzer, and Pilz [ESA 2013, DCG 2015] proved that computing the flip distance between triangulations of simple polygons is NP-complete. The methods used to obtain these previous hardness results rely heavily on the geometric positioning of the vertices of the point set or the vertices of the polygon and are thus not feasible to prove NP-hardness for the flip distance problem of triangulations of convex polygons, where vertices are placed on a circle. We formulate a notion of conflict graphs for flip sequences between triangulations of convex polygons that allows us to use both geometric and combinatorial tools to study flip sequences. Large acyclic subsets of the conflict graph will correspond to short flip sequences. We show NP-completeness of the flip distance problem by proving that finding the largest acyclic subset of our conflict graphs is NP-complete.