Flip Distance of Convex Triangulations and Tree Rotation Is NP-Complete

4 days ago

Flips in triangulations of convex polygons are isomorphic to rotations in binary trees and define edges in the 1-skeleton of the Associahedron.
The complexity of determining the minimum number of flips between triangulations of convex polygons was an open question for decades.
The paper proves that computing shortest flip sequences between triangulations of convex polygons is NP-hard.
The proof uses techniques developed for studying flip sequences of non-crossing spanning trees.
The result also implies that computing the rotation distance of binary trees is NP-hard.

Hasty Briefsbeta