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 distancesArticle

Authors: Lionel Pournin 1,2,3

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.


Volume: DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)
Section: Proceedings
Published on: January 1, 2013
Imported on: November 21, 2016
Keywords: Triangulations,Flip-graph,Rotation distance,Binary tree,Associahedra,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 26 times.
This article's PDF has been downloaded 15 times.