Remote Access Mathematics of Computation
Green Open Access

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?)

  • 1. W. Banaszczyk, New bounds in some transference theorems in the geometry of numbers, Math. Ann. 296 (1993), 625-635. MR 1233487 (94k:11075)
  • 2. A. Barvinok, Computing the Ehrhart polynomial of a convex lattice polytope, preprint TRITA-MAT-1992-0036 (1992), Royal Institute of Technology, Stockholm.
  • 3. A. Barvinok, Computing the volume, counting integral points, and exponential sums, Discrete Comput. Geom. 10 (1993), 123-141. MR 1220543 (94d:52005)
  • 4. A. Barvinok, A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed, Math. Oper. Res. 19 (1994), 769-779. MR 1304623 (96c:52026)
  • 5. A. Barvinok, Computing the Ehrhart polynomial of a convex lattice polytope, Discrete Comput. Geom. 12 (1994), 35-48. MR 1280575 (95e:52015)
  • 6. A. Barvinok and J. Pommersheim, An algorithmic theory of lattice points in polyhedra, New perspectives in algebraic combinatorics (Berkeley, CA, 1996-97), Math. Sci. Res. Inst. Publ., vol. 38, Cambridge Univ. Press, Cambridge, 1999, pp. 91-147.MR 1731815 (2000k:52014)
  • 7. A. Barvinok and K. Woods, Short rational generating functions for lattice point problems, J. Amer. Math. Soc. 16 (2003), 957-979. MR 1992831 (2004e:05009)
  • 8. M. Beck and F. Sottile, Irrational proofs for three theorems of Stanley, preprint arXiv math.CO/0501359, 2005.
  • 9. R. Bellman, A Brief Introduction to Theta Functions, Athena Series: Selected Topics in Mathematics, Holt Rinehart and Winston, New York, 1961.MR 0125252 (23:A2556)
  • 10. K. Beyls, M. Bruynooghe, V. Loechner, R. Seghir, and S. Verdoolaege Analytical computation of Ehrhart polynomials: Enabling more compiler analyses and optimizations, Proceedings of the 2004 International Conference on Compilers, Architecture, and Synthesis for Embedded Systems, ACM Press, New York, 2004 pp. 248-258; see also http://$ ^\sim$skimo/barvinok.
  • 11. J. A. De Loera, R. Hemmecke, J. Tauzer, and R. Yoshida, Effective lattice point counting in rational convex polytopes, J. Symbolic Comput. 38(2004), 1273-1302; see also http://$ ^\sim$latte. MR 2094541 (2005i:52020)
  • 12. J. A. De Loera, R. Hemmecke, M. Köppe, and R. Weismantel, Integer polynomial optimization in fixed dimension, preprint, arXiv: math.OC/0410111, 2004.
  • 13. R. Diaz and S. Robins, Solid angles, lattice points, and the Fourier decomposition of polytopes, manuscript, 1994.
  • 14. R. Diaz and S. Robins, The Ehrhart polynomial of a lattice polytope, Ann. of Math. (2) 145 (1997), 503-518; Erratum: 146 (1997), no. 1, 237.MR 1454701 (98e:11117a), MR 1469320 (98e:11117b)
  • 15. P. Gritzmann and V. Klee, On the complexity of some basic problems in computational convexity. II. Volume and mixed volumes, Polytopes: Abstract, Convex and Computational (Scarborough, ON, 1993), NATO Adv. Sci. Inst. Ser. C. Math. Phys. Sci., vol. 440, Kluwer Acad. Publ., Dordrecht, 1994, pp. 373-466. MR 1322071 (96k:52012)
  • 16. M. Grötschel, L. Lovász, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization. Second edition, Algorithms and Combinatorics, vol. 2, Springer-Verlag, Berlin, 1993. MR 1261419 (95e:90001)
  • 17. P. D. Lax, Functional Analysis, Pure and Applied Mathematics, Wiley-Interscience, New York, 2002. MR 1892228 (2003a:47001)
  • 18. J. Matoušek, Lectures on Discrete Geometry, Graduate Texts in Mathematics, vol. 212, Springer-Verlag, New York, 2002. MR 1899299 (2003f:52011)
  • 19. P. McMullen, Lattice invariant valuations on rational polytopes, Arch. Math. (Basel) 31 1978/79, 509-516. MR 0526617 (80d:52011)
  • 20. P. McMullen, Valuations and dissections, Handbook of Convex Geometry, vol. B, North-Holland, Amsterdam, 1993, pp. 933-988.MR 1243000 (95f:52018)
  • 21. P. McMullen and R. Schneider, Valuations on convex bodies, Convexity and its Applications, Birkhäuser, Basel, 1983, pp. 170-247. MR 0731112 (85e:52001)
  • 22. R. Morelli, Pick's theorem and the Todd class of a toric variety, Adv. Math. 100 (1993), 183-231. MR 1234309 (94j:14048)
  • 23. J. Pommersheim and H. Thomas, Cycles representing the Todd class of a toric variety, J. Amer. Math. Soc. 17 (2004), 983-994. MR 2083474 (2005h:14124)
  • 24. R. Schneider, Convex Bodies: The Brunn-Minkowski Theory, Encyclopedia of Mathematics and its Applications, vol. 44, Cambridge University Press, Cambridge, 1993. MR 1216521 (94d:52007)
  • 25. A. Schrijver, Theory of Linear and Integer Programming, Wiley-Interscience Series in Discrete Mathematics, John Wiley $ \&$ Sons, Ltd., Chichester, 1986. MR 0874114 (88m:90090)
  • 26. V. N. Shevchenko, Qualitative Topics in Integer Linear Programming, Translated from the Russian by H. H. McFaden. Translations of Mathematical Monographs, vol. 156, American Mathematical Society, Providence, RI, 1997.MR 1414900 (97m:90001)
  • 27. R. P. Stanley, Enumerative Combinatorics. Vol. 1, corrected reprint of the 1986 original. Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 1997.MR 1442260 (98a:05001)

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

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

American Mathematical Society