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].

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].

Reviewer: Dmitri Panyushev (Moskva)

##### MSC:

05A15 | Exact enumeration problems, generating functions |