# 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.
Keywords :
Document type :
Conference papers

Cited literature [7 references]

https://hal.inria.fr/hal-01229752
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

### File

dmAS0101.pdf
Publisher files allowed on an open archive

### Identifiers

• HAL Id : hal-01229752, version 1

### Citation

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