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

   
Mobile Device Pairing
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
Email: barvinok@umich.edu

DOI: http://dx.doi.org/10.1090/S0025-5718-06-01836-9
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