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

• triangulations
• flip-graph
• rotation distance
• binary tree
• associahedra
• [info.info-dm]computer science [cs]/discrete mathematics [cs.dm]