Your Search Results

Use this resource - and many more! - in your textbook!

AcademicPub holds over eight million pieces of educational content for you to mix-and-match your way.

Experience the freedom of customizing your course pack with AcademicPub!
Not an educator but still interested in using this content? No problem! Visit our provider's page to contact the publisher and get permission directly.

Computation of the Highest Coefficients of Weighted Ehrhart Quasi-polynomials of Rational Polyhedra

By: N. Berline; V. Baldoni; M. Vergne; M. Köppe; J. Loera;

2012 / Springer Science+Business Media / 1615-3375


This article concerns the computational problem of counting the lattice points inside convex polytopes, when each point must be counted with a weight associated to it. We describe an efficient algorithm for computing the highest degree coefficients of the weighted Ehrhart quasi-polynomial for a rational simple polytope in varying dimension, when the weights of the lattice points are given by a polynomial function ≡1). In contrast to Barvinok’s method, our method is local, obtains an approximation on the level of generating functions, handles the general weighted case, and provides the coefficients in closed form as step polynomials of the dilation. To demonstrate the practicality of our approach, we report on computational experiments which show that even our simple implementation can compete with state-of-the-art software.