How far apart two triangulations can be

The solid whose corners are triangulations joined two triangulations of a polygon whenever a single diagonal could be swapped for another, and found that the resulting graph is the skeleton of a polytope, the associahedron. Every triangulation of a convex polygon with $m$ vertices has $m - 3$ diagonals, and each can be flipped: removed, leaving a quadrilateral, and replaced by the quadrilateral’s other diagonal. So every corner of the associahedron has $m - 3$ edges, and the solid is connected — any triangulation can be reached from any other by a sequence of flips.

This essay asks how long that sequence has to be. The flip distance between two triangulations is the fewest flips that turn one into the other, and the diameter of the flip graph is the largest flip distance between any two. It is a natural measure of how varied the triangulations of a polygon are, and it is also a classical question in computer science in disguise: triangulations of a polygon are binary trees, a flip is a rotation of a binary tree, and the diameter is the largest number of rotations ever needed to turn one search tree into another. Daniel Sleator, Robert Tarjan and William Thurston studied it for that reason in 1988, and their answer, for large polygons, was exactly $2m - 10$.

A flip is a rotation of a tree #

The equivalence with binary trees is worth making concrete, because it is where the question came from and where most of its applications live. Mark one side of the polygon as the root side. The triangle resting on it is the root of a tree; the two other sides of that triangle each either are sides of the polygon, in which case that branch of the tree ends, or are diagonals with another triangle on their far side, which becomes a child. Continuing outward, every triangulation of a polygon with $m$ vertices becomes a binary tree with $m - 2$ nodes, one per triangle, and every binary tree with $m - 2$ nodes arises from exactly one triangulation — which is one of the bijections one word and four objects used to show that both are counted by the Catalan numbers, and the equation a sequence satisfies solved in closed form.

Under that correspondence a flip is a rotation. Flipping the diagonal between a triangle and its child exchanges which of the two is nearer the root, and in the tree that is the operation of making a child the parent of its former parent while keeping the left-to-right order of everything below. Rotations are what keep a binary search tree balanced as items are inserted and deleted — every self-balancing tree in computing rebalances by rotations — and the flip distance is the fewest rotations needed to turn one search tree into another holding the same keys. Sleator and Tarjan were studying self-adjusting search trees when they asked how large that number can be, and the triangulation picture, with Thurston’s geometry, was the route to the answer.

Searching every triangulation #

The flip graph is finite, so its diameter can be found by brute force: list every triangulation, list every flip, and run a breadth-first search from every triangulation to find the farthest one. The number of triangulations is a Catalan number — 132 for the octagon, 1,430 for the decagon, 58,786 for the 13-gon — as one word and four objects showed by matching triangulations with bracketings and trees. Each triangulation is stored as its set of diagonals, each flip is found by locating the two triangles on either side of a diagonal, and each search visits every triangulation once. For the larger polygons the search is run from only one triangulation in each class of triangulations related by rotating or reflecting the polygon, since a symmetry of the polygon preserves flip distances; for the 13-gon that is 2,282 searches instead of 58,786.

The octagon, in the hero figure, shows the kind of path the search finds. Its start and end share no diagonal, and each of the start’s five diagonals has to be removed, so at least five flips are needed. Seven are, because two of the diagonals inserted along the way are in the way of later ones and have to be flipped again. That excess over a simple count of diagonals is the whole difficulty of the problem, and it is what makes the diameter more than $m - 3$.

Diameter, polygon by polygon #

The next figure shows the diameter for every polygon from four vertices to thirteen.

The diameters are $1, 2, 4, 5, 7, 9, 11, 12, 15, 16$ for polygons with $4$ to $13$ vertices. They grow by one or two at each step, with no simple pattern at small sizes: from 9 to 11 vertices they grow by two each time, from 11 to 12 by three, and the value at 11 vertices, 12, happens to equal $2m - 10$ while the value at 12 vertices, 15, exceeds it. From 13 vertices on the diameter is $2m - 10$ exactly, which the search confirms at $m = 13$ and which is a theorem beyond: Sleator, Tarjan and Thurston proved in 1988 that the diameter is at most $2m - 10$ for every $m$ above 12 and equal to it for all sufficiently large $m$, and Lionel Pournin proved in 2014, by a purely combinatorial argument, that equality holds for every $m$ above 12.

Their proof of the lower bound is one of the famous surprises of combinatorics. They glued the two triangulations together along the polygon’s boundary, one on each side, to form a triangulated sphere, and observed that a short flip sequence gives a way of building that sphere’s interior out of few tetrahedra. They then used the volume of hyperbolic polyhedra to show that some spheres need many tetrahedra, which forces some pairs of triangulations to be far apart. A question about rotating binary trees was answered with hyperbolic geometry in three dimensions, and for twenty-six years nobody found a proof that avoided it.

Every triangulation is near a fan #

The upper bound is elementary, and the next figure shows it exactly.

The fan at a vertex is the triangulation with every diagonal drawn from that vertex. From any triangulation, there is always a diagonal whose flip creates a new diagonal at the chosen vertex: find a triangle touching the vertex whose opposite side is a diagonal, and flip that diagonal. So a triangulation with $j$ of its diagonals at the vertex is at most $m - 3 - j$ flips from the fan, and since no flip can add more than one diagonal at the vertex, it is exactly that far. The search confirms the formula for all 1,430 triangulations of the decagon, with distances from 0, the fan itself, to 7, attained by the 429 triangulations that have no diagonal at the fan’s vertex.

Going through a fan gives the upper bound at once. Any two triangulations are each at most $m - 3$ flips from the same fan, so they are at most $2m - 6$ apart. Choosing the fan’s vertex cleverly — at a vertex where both triangulations already have many diagonals — improves this, and Sleator, Tarjan and Thurston’s upper bound $2m - 10$ comes from a counting argument showing that some vertex always carries enough. The fan route is a long way round in general: two triangulations near each other are usually far from every fan.

Typical pairs are well short of the diameter #

The diameter is a worst case. The next figure counts the distances between all pairs.

Two triangulations chosen at random are typically a little more than half the diameter apart: $4.94$ flips on the nonagon, $6.00$ on the decagon, $7.09$ on the 11-gon, each about $m - 4$, against diameters of $9$, $11$ and $12$. The distribution has a thin upper tail. On the decagon only three pairs in ten thousand are at the full distance of 11, and on the nonagon two in a thousand are at its distance of 9. The pairs that realise the diameter are special, and the lower-bound proofs have to construct them: they do not appear by chance among a few random pairs.

That is also why the diameter is hard to compute in general. Computing the flip distance between two given triangulations is a famous problem whose complexity is unknown — it is in NP, since a short sequence of flips can be checked, but no polynomial-time algorithm is known and no proof that it is hard either. The figures here are exhaustive searches, and their cost grows with the Catalan numbers, by a factor of about four per vertex.

A shared diagonal never needs to move #

One tool makes larger computations and every proof possible: a lemma that cuts a pair of triangulations into smaller pairs.

If two triangulations share a diagonal, that diagonal cuts the polygon into two smaller polygons, and each triangulation restricts to a triangulation of each piece. Flipping only inside the pieces, the pair can be joined in a number of flips equal to the sum of the two pieces’ distances, never flipping the shared diagonal. The lemma, which Sleator, Tarjan and Thurston proved and used, says that this is optimal: there is always a shortest path that never flips a diagonal the two ends share. The figure checks it directly. For every pair of triangulations of polygons up to nine vertices and every diagonal they share — 130,923 comparisons for the nonagon alone, 143,065 in all — the full distance equals the sum of the two pieces’ distances.

The lemma is why the farthest pairs share nothing. A shared diagonal would split the distance into the distances of two smaller polygons, whose diameters are smaller, and the sum of the two smaller diameters falls short of the large one. So a pair at the full distance must have no diagonal in common, and the lower-bound constructions all start from two triangulations that are as different as two triangulations can be.

Two triangulations sixteen flips apart #

The search on the 13-gon produces an explicit pair at the full distance, $2m - 10 = 16$.

Each has ten diagonals, so at least ten flips are needed simply to replace them all, and six more are forced. The extra flips come from crossings. A diagonal of the second triangulation that crosses many diagonals of the first cannot be put in by a single flip until all but one of the diagonals it crosses have been removed, and the replacements made along the way may cross later diagonals in turn. Sleator, Tarjan and Thurston’s hyperbolic argument, and Pournin’s combinatorial one, both amount to showing that for suitable pairs these forced detours add up to $m - 7$ beyond the $m - 3$ that a count of diagonals requires.

The pair drawn here is simply the first that the search finds at distance 16; it is not one of the published constructions, which are described for all $m$ at once and are easier to analyse than to draw. What it shows is that the theorem’s value is attained, at the first size where it holds for good.

A short diameter for a large polytope #

The flip graph is the skeleton of a polytope, and from that side the diameter is remarkably small. The associahedron of the $m$-gon has dimension $m - 3$, and its facets — one for each diagonal, the triangulations containing that diagonal — number $m(m - 3)/2$, which is 65 for the 13-gon. The classical bound conjectured by Warren Hirsch in 1957 for the diameter of any polytope is the number of facets minus the dimension, which for the 13-gon would allow 55 steps. The true diameter is 16, about a third of that, and as $m$ grows the gap widens: the Hirsch bound grows like $m^2/2$, the associahedron’s diameter like $2m$.

Polytope diameters matter because they bound how many steps the simplex method can need with the best possible choice of pivots, which the cube that takes every corner showed can be catastrophically worse with a bad choice. The Hirsch conjecture itself was disproved by Francisco Santos in 2010 with a polytope of dimension 43, and whether every polytope’s diameter is bounded by a polynomial in its number of facets is open; the cheapest way to send met the same question for the polytope of flows. The associahedron is one of the polytopes where the answer is known exactly and is linear, and it is known exactly only because its corners are triangulations, whose structure the lemma above and the hyperbolic argument could exploit.

The growth of the number of corners makes the contrast sharper. The 13-gon’s associahedron has 58,786 corners and diameter 16; the polytope of a 30-gon has about $3 \times 10^{14}$ corners and diameter 50. Small as that is beside the Hirsch bound, it is large beside a random graph with the same number of vertices, each of degree 27, in which distances grow like the logarithm of the size and the diameter would be about ten: the associahedron is spread out in a structured way, and the paths that go wrong in Catalan counting are the same structure seen from the side of enumeration.

What the search cannot show #

The figures are exhaustive for every polygon drawn, and they show the diameter exactly up to 13 vertices. Beyond that they show nothing: the next polygon has 208,012 triangulations, and the one after 742,900, so the brute-force method runs out within a few more vertices. That the diameter stays at $2m - 10$ forever is Pournin’s theorem, and it is the only reason to believe the line in the diameter figure continues.

The figures also say nothing about the distance between two given large triangulations. The lemma and the fan argument give bounds and simplifications; the exact distance, for triangulations of a polygon with a few hundred vertices, is not something any known method computes quickly. That gap between knowing the worst case exactly and not being able to compute a typical case is unusual, and it is the reason the problem is still studied.

Still open: computing one distance #

Whether the flip distance between two triangulations of a convex polygon can be computed in polynomial time is open. It is the same question as computing the rotation distance between two binary trees, and it has been open since Sleator, Tarjan and Thurston raised it. It is known to be fixed-parameter tractable — computable quickly when the distance itself is small — and approximable within a factor of two by simple methods, such as removing shared diagonals and routing through fans. For triangulations of point sets that are not in convex position, and of polygons that are not convex, the problem is known to be NP-hard, which makes the convex case’s status more puzzling rather than less.

The sums a triangulation cannot change found quantities that every triangulation of a cyclic polygon shares, unchanged by any flip. The flip distance is the opposite kind of object: the measure of how much two triangulations differ. A polynomial algorithm for it, if one exists, would have to find in the geometry of the associahedron a structure as clean as those invariants, and nobody has.

A question about trees answered by space #

The flip graph of the 13-gon has 58,786 corners, each with ten edges, and a search through all of it finds that no two triangulations are more than sixteen flips apart, while some are exactly that far. Sixteen is $2 \times 13 - 10$, and the reason that formula holds for this polygon and every larger one is a theorem first proved by building three-dimensional hyperbolic polyhedra from pairs of triangulations. Below thirteen vertices the formula is wrong — fifteen, not fourteen, at twelve vertices — which is why the theorem says “for m above 12”. The search measures where the asymptotic truth takes over, and finds it exactly where the theorem says it does.