Springe direkt zu Inhalt

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.

Counting lattice triangulations
Volker Kaibel and Günter M. Ziegler
Cambridge University Press
Erschienen in
Surveys in Combinatorics 2003, London Math. Society Lecture Notes Series, pages 277-307