Loading [MathJax]/jax/output/HTML-CSS/jax.js

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

Authors: Lionel Pournin 1,2,3,4

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 2n10 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 126 times.
This article's PDF has been downloaded 125 times.