Computing the Ehrhart polynomial of a convex lattice polytope (Q1330880): Difference between revisions

For a (convex) polytope \(P \subset \mathbb{R}^ d\) whose vertices belong to the integer lattice \(\mathbb{Z}^ d\) the number of lattice points in \(nP\) can be expressed as a polynomial (in \(n\)) of degree \(d\), the Ehrhart polynomial of \(P\). (The constant coefficient \(e_ 0(P) = 1\), the highest coefficient \(e_ d(P)\) is the volume of \(P\), and \(e_{d - 1}(P)\) is half the volume of the \((d - 1)\)-dimensional `surface'.) Based on some identities of Morelli [\textit{R. Morelli}, Adv. Math. 100, No. 2, 183-231 (1993; Zbl 0797.14018)] it is proved that, if \(P\) is given by \(m\) linear inequalities with input size \(s(P)\), then for any fixed \(k\) the coefficient \(e_{d - k}(P)\) can be computed using \(O(m^ k)\) calls of an oracle returning the volume of a face of \(P\), and both the number of operations necessary and the size of the numbers involved is bounded polynomially in \(s(P)\). This implies that for fixed dimension \(d\) the number of lattice points in a simplex \(\Delta\) can be computed in polynomial time, thus reproving an earlier result of the author [Proc. 34th Symposium on the Foundations of Computer Science New York, 566-572 (1993)] but with a better bound (\({d\cdot s(\Delta)}^{O(d)}\)) on the complexity.