Grid flip graphs are partial cubes

The labeling scheme I described for the 3x3 grid appears to generalize to show that any grid has a flip graph that embeds isometrically into a hypercube.

Some properties of (maximal) integer grid triangulations and their flips:

All triangles in a triangulation have area 1/2.

Proof sketch: By Pick's formula, any larger triangle would have an interior or boundary grid point through which it could be subdivided.

An edge from (a,b) to (a+x,b+y) can be part of a triangulation if and only if gcd(x,y) = 1.

Proof sketch: Any grid line segment passes through gcd(x,y)-1 integer points, so by Pick's formula any triangle formed from an edge with gcd(x,y) > 1 would have area greater than 1/2.

Two triangles can be flipped if and only if they form a parallelogram.

Proof sketch: In one direction, it is clear that any parallelogram is flippable. In the other, suppose we have a flippable pair of triangles. We can transform the integer lattice by an appropriate transformation (derived from the extended Euclidean algorithm) so that the shared edge has length one, so that the two triangles have apexes on the two grid lines parallel to and nearest the shared edge, and so that one of the two triangles is right isosceles. Then the other triangle must also be right isosceles, forming a parallelogram, because no other point on the grid line containing the other triangle's apex is visible to the first apex.

For any edge of length ≥ sqrt(2), there is a unique pair of triangles that, when flipped, leads to a new edge of equal or shorter length. The length of the new edge is equal to the length of the old one if and only if the length of both edges is sqrt(2).

Proof sketch: let the edge be pq, and its length be L. Then the triangles that can flip pq have apexes on lines parallel to pq at distance 1/L from it. By the translation symmetry of the lattice and the absence of a grid point between pq, the points on these two lines are spaced at distance L apart. If an apex is outside the slab with boundary lines through p and q perpendicular to pq, its flip will definitely lead to a longer edge. No apex can be on the boundary of this slab, because then it would be at distance 1/L from p or q violating the unit spacing of grid points; therefore there is a unique apex on each side of pq within the slab. From the unit spacing of grid points and the 1/L distance of the apex from line pq we can calculate the conditions on the length of the new edge.

Let T1 and T2 be two triangulations, and e be the longest edge that belongs to exactly one of T1 or T2. Then e can be flipped.

Proof sketch: Assume without loss of generality that e belongs to T1. If one of the edges of a triangle adjacent to e is longer than e, then that edge belongs to both T1 and T2, and the triangle in T2 based on that edge would have an edge longer than e (by an argument similar to the one for uniqueness of length-reducing flips), so e could not be the longest edge belonging to both triangultaions. On the other hand if all edges adjacent to e are of lesser or equal length, then e can be flipped.

Define the content of an edge to be the set of edges that can be reached by length-reducing flips from it (including the edge itself) and define the content of a triangulation to be the union of the contents of its edges. Then any flip of an edge with length ≠ sqrt(2) changes the content by a single edge.

Proof sketch: This follows immediately from the uniqueness of length-reducing flips.

For each triangulation T, and each pair of crossing length-sqrt(2) edges, exactly one edge from the pair belongs to the content of T.

Proof sketch: By induction on the number of edges longer than sqrt(2) in T. If there are none, the result is immediate. Otherwise, flip the longest edge in T.

Define a bitvector label for each triangulation T as follows: for each possible edge e with length greater than sqrt(2), form a bit that is 1 if e belongs to the content of T, and zero otherwise. Additionally, for each pair of crossing edges with length sqrt(2), form a bit that is 0 if the positive-slope edge is in the content of T, and 1 if the negative-slope edge is in the content of T. Then these labels form an isometric embedding of the flip graph of triangulations into a hypercube.

Proof sketch: Each flip changes one bit of the labeling, so the flip distance is at least equal to the Hamming distance between labels. To find a flip sequence with length at most the Hamming distance, flip the largest differing edge between the two triangulations and continue recursively with the resulting flipped triangulation.

Note that the number of bits in these labels, for an n×n grid, is Θ(n⁴), so this doesn't contradict Emo's argument that the flip graph has diameter Θ(n³).

Comments: