Return to Colloquia & Seminar listing
Irrational decompositions of polyhedra and the computation of Ehrhart polynomials
Student-Run Geometry/Topology Seminar| Speaker: | Matthias Koeppe, UC Davis |
| Location: | 1147 MSB |
| Start time: | Tue, Oct 28 2008, 1:10PM |
A very powerful algorithmic technique in discrete geometry is A. Barvinok's (1994) calculus of "short" rational generating functions. It allows to efficiently compute the number of lattice points in rational polytopes, and thus parametric lattice-point counting functions like Ehrhart functions.
Beck and Sottile (2006/2007) introduced "irrational" decompositions of polyhedral cones as a proof technique, simplifying the proofs of a number of classic theorems on rational generating functions. A surprising fact is that irrational decompositions can also be used algorithmically. I illustrate this on practical computations with my state-of-the-art software "LattE macchiato", where computation times are reduced quite dramatically compared to previously known methods.
The method also gives rise to new results in computational complexity. We show the polynomial-time computability of Ehrhart polynomials for matroid polytopes, matroid base polytopes, and polymatroids, whenever the rank function is bounded by an arbitrary constant.