Counting lattice triangulations

Volker Kaibel and Günter M. Ziegler— 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\times 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.

TitelCounting lattice triangulations
VerfasserVolker Kaibel and Günter M. Ziegler
VerlagCambridge University Press
Erschienen inSurveys in Combinatorics 2003, London Math. Society Lecture Notes Series, pages 277-307