Counting lattice triangulations
Volker Kaibel, Günter M. Ziegler · Cambridge University Press eBooks · 2003
We discuss the problem to count, or, more modestly, to estimate the number f(m, n) of unimodular triangulations of the planar grid of size m × n . Among other tools, we employ recursions that allow one to compute the (huge) number of triangulations for small m and rather large n by dynamic programming; we show that this computation can be done in polynomial time if m is fixed, and present computational results from our implementation of this approach. We also present new upper and lower bounds for large m and n , and we report about results obtained from a computer simulation of the random walk that is generated by flips. Introduction An innocent little combinatorial counting problem asks for the number of triangulations of a finite grid of size m × n . That is, for m,n ≥ 1 we define P m,n := {0,1,…, m } × {0,1,…, n }, “the grid”. Equivalently, the point configuration P m,n consists of all points of the integer lattice Z 2 in the lattice rectangle conv( P m,n ) = [0, m ] × [0, n ] of area mn . Every triangulation of this rectangle point set that uses all the points in P m,n has ( m + 1)( n + 1) = ∣ P m, n ∣ vertices, 2 mn facets/triangles, and 3 mn + m + n edges, 2 ( m + n ) of them on the boundary, the other 3 mn – m – n ones in the interior. All the triangles are minimal lattice triangles of area ½ (that is, of determinant 1), which are referred to as unimodular triangles.