7 - Counting lattice triangulations

Summary

Abstract

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² 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, 2mn facets/triangles, and 3mn + m + n edges, 2 (m + n) of them on the boundary, the other 3mn – 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.