2005/04/21 by Alexander Barvinok, Barvinok, Alexander
Mathematics · #05A15 #52C07 #68R05 #Combinatorics (math.CO) #FOS: Mathematics #Metric Geometry (math.MG) #math.CO #math.MG #msc:05A15 #msc:52C07 #msc:68R05
paper · pdf · doi:10.48550/arxiv.math/0504444
21 pages
arxiv created 2005/04/21 · arxiv updated 2009/12/01
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 kth 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.