By: Dr. Meera Sitharam
Abstract:
Given a triangulation of points in the plane, a flip deletes an edge e whose removal leaves a convex quadrilateral and replaces e by the opposite diagonal of the quadrilateral. In the topological setting, a triangulation of a closed surface is an equivalence class permitting points to be moved freely and edges to be bent using homeomorphisms, so the convexity condition does not apply. Flip paths between triangulations in the geometric and topological settings have been studied since Lawson in the 1970s and Wagner in the 1930s respectively.
It is well known that any triangulation of a point set (resp. of a closed surface) can be reconfigured to any other triangulation by some sequence of flips. The problem of finding the shortest such flip path is in general NP-complete. However, for lattice triangulations, this problem and many of its variants have a polynomial-time algorithm. By using the concept of Farey sequences in elementary number theory and the flip structure of lattice triangulations, we structurally elucidate and improve the complexity of these algorithms by a linear factor.
This​ is a friendly survey of the topic. What he calls “combinatorial” is the topological setting.