How to Integrate a Polynomial over a Simplex

Abstract

This paper settles the computational complexity of the problem of integrating a polynomial function f over a rational simplex. We prove that the problem is NP-hard for arbitrary polynomials via a generalization of a theorem of Motzkin and Straus. On the other hand, if the polynomial depends only on a fixed number of variables, while its degree and the dimension of the simplex are allowed to vary, we prove that integration can be done in polynomial time. As a consequence, for polynomials of fixed total degree, there is a polynomial time algorithm as well. We conclude the article with extensions to other polytopes, discussion of other available methods and experimental results.

Tables added with new experimental results. References added

Cited by in corpus (12)

• The inverse moment problem for convex polytopes
• Exploiting Polyhedral Symmetries in Social Choice
• Intermediate Sums on Polyhedra: Computation and Real Ehrhart Theory
• Multi-Collinear Splitting Kernels for Track Function Evolution
• On fundamental domains and volumes of hyperbolic Coxeter-Weyl groups
• On moments of a polytope
• Accelerating Performance Inference over Closed Systems by Asymptotic Methods
• Intermediate Sums on Polyhedra II: Bidegree and Poisson Formula
• Weighted Ehrhart Theory: Extending Stanley's nonnegativity theorem
• Average Weights and Power in Weighted Voting Games
• Weighted Ehrhart functions
• Ehrhart Functions of Weighted Lattice Points