Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

Remote Access
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)


Computing the Ehrhart quasi-polynomial of a rational simplex

Author: Alexander Barvinok
Journal: Math. Comp. 75 (2006), 1449-1466
MSC (2000): Primary 52C07; Secondary 05A15, 68R05
Published electronically: March 10, 2006
MathSciNet review: 2219037
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We present a polynomial time algorithm to compute any fixed number of the highest coefficients of the Ehrhart quasi-polynomial of a rational simplex. Previously such algorithms were known for integer simplices and for rational polytopes of a fixed dimension. The algorithm is based on the formula relating the $ k$th coefficient of the Ehrhart quasi-polynomial of a rational polytope to volumes of sections of the polytope by affine lattice subspaces parallel to $ k$-dimensional faces of the polytope. We discuss possible extensions and open questions.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 52C07, 05A15, 68R05

Retrieve articles in all journals with MSC (2000): 52C07, 05A15, 68R05

Additional Information

Alexander Barvinok
Affiliation: Department of Mathematics, University of Michigan, Ann Arbor, Michigan 48109-1043

PII: S 0025-5718(06)01836-9
Keywords: Ehrhart quasi-polynomial, rational polytope, valuation, algorithm
Received by editor(s): April 29, 2005
Published electronically: March 10, 2006
Additional Notes: This research was partially supported by NSF Grant DMS 0400617
Article copyright: © Copyright 2006 American Mathematical Society

Comments: Email Webmaster

© Copyright , American Mathematical Society
Contact Us · Sitemap · Privacy Statement

Connect with us Facebook Twitter Google+ LinkedIn Instagram RSS feeds Blogs YouTube Podcasts Wikipedia