Geodesic
A combinatorial method to find sharp lower bounds on flip distances
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013) (2013).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2013_special_264_a59,
     author = {Pournin, Lionel},
     title = {A combinatorial method to find sharp lower bounds on flip distances},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)},
     year = {2013},
     doi = {10.46298/dmtcs.12788},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.12788/}
}
TY  - JOUR
AU  - Pournin, Lionel
TI  - A combinatorial method to find sharp lower bounds on flip distances
JO  - Discrete mathematics & theoretical computer science
PY  - 2013
VL  - DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.12788/
DO  - 10.46298/dmtcs.12788
LA  - en
ID  - DMTCS_2013_special_264_a59
ER  - 
%0 Journal Article
%A Pournin, Lionel
%T A combinatorial method to find sharp lower bounds on flip distances
%J Discrete mathematics & theoretical computer science
%D 2013
%V DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.12788/
%R 10.46298/dmtcs.12788
%G en
%F DMTCS_2013_special_264_a59
Pournin, Lionel. A combinatorial method to find sharp lower bounds on flip distances. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013) (2013). doi : 10.46298/dmtcs.12788. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.12788/

Cité par Sources :