Discrete Volume Computations for Polyhedra
- Matthias Beck (San Francisco State University)
Abstract
Our goal is to compute volumes of polyhedra, which are fundamental in many areas of mathematics. Although polyhedra have an easy description, e.g., using a linear system of equalities and inequalities, volume computation (at least in general dimension) is hard even for these basic objects. Our approach is to compute the discrete volume of a polyhedron P, namely, the number of grid points that lie inside P, given a fixed grid in Euclidean space such as the set of all integer points. A theory initiated by Eugene Ehrhart implies that the discrete volume of a polytope has some remarkable properties. We will exemplify Ehrhart theory with the help of several interesting families of polyhedra, and give applications to areas beyond computational geometry.
