Counting Lattice Triangulations
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
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.
30 pages, to appear in: ``British Combinatorial Surveys'' (C. D. Wensley, ed.), Cambridge University Press, 2003. This is an updated version containing minor changes suggested by the referee
30 pages, to appear in: ``British Combinatorial Surveys'' (C. D. Wensley, ed.), Cambridge University Press, 2003. This is an updated version containing minor changes suggested by the referee