Skip to Main content Skip to Navigation
Conference papers

A combinatorial method to find sharp lower bounds on flip distances

Abstract : 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download
Contributor : Alain Monteil Connect in order to contact the contributor
Submitted on : Tuesday, November 17, 2015 - 10:21:06 AM
Last modification on : Saturday, November 20, 2021 - 3:49:40 AM
Long-term archiving on: : Friday, April 28, 2017 - 3:15:07 PM


Publisher files allowed on an open archive


  • HAL Id : hal-01229752, version 1



Lionel Pournin. A combinatorial method to find sharp lower bounds on flip distances. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. pp.1-12. ⟨hal-01229752⟩



Record views


Files downloads