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

https://hal.inria.fr/hal-01229752
Contributor : Alain Monteil <>
Submitted on : Tuesday, November 17, 2015 - 10:21:06 AM
Last modification on : Friday, March 27, 2020 - 3:53:03 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

Collections

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⟩

Share

Metrics

Record views

203

Files downloads

79