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(log^{2} *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.