Lionel Pournin
-
A combinatorial method to find sharp lower bounds on flip distances
dmtcs:12788 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2013,
DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)
-
https://doi.org/10.46298/dmtcs.12788
A combinatorial method to find sharp lower bounds on flip distancesConference paper
Consider the triangulations of a convex polygon with n vertices. In 1988, Daniel Sleator, Robert Tarjan, and William Thurston have shown that the flip distance of two such triangulations is at most 2n−10 when n is greater than 12 and that this bound is sharp when n is large enough. They also conjecture that `"large enough'' means greater than 12. A proof of this conjecture was recently announced by the author. A sketch of this proof is given here, with emphasis on the intuitions underlying the construction of lower bounds on the flip distance of two triangulations.