Flip Distance of Triangulations of Convex Polygons / Rotation Distance of Binary Trees is NP-complete
Summary
The arXiv paper proves that computing the minimum number of flips between triangulations of convex polygons is NP-hard, which in turn makes the rotation distance of binary trees NP-hard. It develops techniques for flip sequences and situates the result in the broader context of computational geometry and discrete math, drawing on related work in flip sequences and non-crossing structures.