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.

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