Vinayak Pathak
The problem of computing the minimum number of flips to transform one triangulation of a convex polygon to another is not known to be in P or NP-complete. A flip sequence determines a one-to-one correspondence between the edges of the two triangulations. As a step towards understanding the source of difficulty, we investigate the case when this edge correspondence is given, i.e., we want the flip distance between two edge-labelled triangulations of a convex polygon.
We give tight worst case bounds of Θ(n log n) on the flip distance between edge-labelled triangulations of a convex polygon, and edge-labelled combinatorial triangulations, in contrast to the Θ(n) bounds for the unlabelled case. Our method is to reduce to sorting with restricted operations, similar to the length-weighted reversals relevant in comparative genomics. Our bounds imply a lower bound on a very general model of sorting that subsumes a previously known lower bound. Using our upper bound we give an O(log n)-factor approximation algorithm for computing the flip distance between edge-labelled triangulations of a convex polygon.
We also consider simultaneous flips on edge-labelled triangulations. We prove an O(log2 n) upper bound and an Ω(log n) lower bound on the worst case number of simultaneous flips, in contrast with the tight bound of Θ(log n) for the unlabelled case proved in SODA '06.