Discrete Volume Computations for Polyhedra
- Matthias Beck (San Francisco State University, San Francisco, USA)
- #
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.
