×

zbMATH — the first resource for mathematics

Counting lattice triangulations. (English) Zbl 1031.05011
Wensley, C. D. (ed.), Surveys in combinatorics, 2003. Proceedings of the 19th British combinatorial conference, University of Wales, Bangor, UK, June 29-July 04, 2003. Cambridge: Cambridge University Press. Lond. Math. Soc. Lect. Note Ser. 307, 277-307 (2003).
Let \(P_{m,n}\) be the planar point configuration \([0,m]\times [0,n]\), “the grid”. The authors discuss the problem of counting the number \(f(m,n)\) of unimodular triangulations of \(P_{m,n}\). This means that a triangulation uses all the points of \(P_{m,n}\) or, equivalently, that each triangle has area 1/2. It is known that triangulations of lattice polygons are related to (i) the theory of plane algebraic curves, via Viro’s construction, (ii) Gelfand-Kapranov-Zelevinsky’s theory of determinants, and (iii) resolutions of singularities of toric threefolds.
These connections also pose the problem of counting the number \(f^{reg}(m,n)\) of regular triangulations of \(P_{m,n}\). A triangulation is regular, if the triangles in it are the domains of linearity of a piecewise linear convex function.
The authors suggest recursions that allow to compute \(f(m,n)\) for small \(m\) and rather large \(n\) by dynamic programming. This computation can be done in a polynomial time in \(n\), if \(m\) is fixed. Some new lower and upper bounds for \(f(m,n)\) and \(f^{reg}(m,n)\) are presented. A considerable part of the paper is devoted to the presentation of computational results and informal discussions of various computer procedures and algorithms.
For the entire collection see [Zbl 1020.00011].

MSC:
05A15 Exact enumeration problems, generating functions
PDF BibTeX XML Cite
Full Text: arXiv