Matpic
mathematics, in pictures
Concept

Flip — where it appears

The move that replaces one diagonal of a convex quadrilateral inside a triangulation by the other diagonal. Any two triangulations of a polygon are joined by a chain of flips, and the length of the shortest chain is a distance between them.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

The 14 triangulations, joined by single flips. The flip graph of a 6-gon: 14 triangulations drawn as small polygons and joined by 21 edges, one for each pair differing in a single diagonal.

The solid whose corners are triangulations

Take the triangulations of a hexagon as points and join two of them when a single diagonal can be swapped for another. The result is not merely a graph — it is the edge skeleton of a genuine convex polyhedron, with fourteen corners, three square faces and six pentagonal ones.

discrete · Catalan numbers Seven flips between the octagon's farthest triangulations. A shortest flip path of length 7 between two of the 132 triangulations of the octagon.

How far apart two triangulations can be

Any triangulation of a polygon can be turned into any other by flipping one diagonal at a time. On an octagon seven flips always suffice; on a polygon with m vertices the worst case is 2m − 10 flips once m reaches thirteen, a value Sleator, Tarjan and Thurston proved with hyperbolic geometry in 1988. Breadth-first search over all 58,786 triangulations of the 13-gon finds the sixteen.

discrete · Catalan numbers

Named alongside it

The objects these essays reach for when they reach for this one.

Catalan numbersGraphPolytopeTriangulationAssociativityBinary treesConvex hullEuler formulaExhaustive searchLower bound

All concepts