Abstract
We give a 2^{O(n)}(1+1/eps)^n time and poly(n)space deterministic algorithm for computing a (1+eps)^n approximation to the volume of a general convex body K, which comes close to matching the (1+c/eps)^{n/2} lower bound for volume estimation in the oracle model by Barany and Furedi (STOC 1986, Proc. Amer. Math. Soc. 1988). This improves on the previous results of Dadush and Vempala (Proc. Nat'l Acad. Sci. 2013), which gave the above result only for symmetric bodies and achieved a dependence of 2^{O(n)}(1+log^{5/2}(1/eps)/eps^3)^n.
For our methods, we reduce the problem of volume estimation in K to counting lattice points in K subseteq R^n (via enumeration) for a specially constructed lattice L: a socalled thin covering of space with respect to K (more precisely, for which L + K = R^n and vol_n(K)/det(L) = 2^{O(n)}). The trade off between time and approximation ratio is achieved by scaling down the lattice.
As our main technical contribution, we give the first deterministic 2^{O(n)}time and poly(n)space construction of thin covering lattices for general convex bodies. This improves on a recent construction of Alon et al (STOC 2013) which requires exponential space and only works for symmetric bodies. For our construction, we combine the use of the Mellipsoid from convex geometry (Milman, C.R. Math. Acad. Sci. Paris 1986) together with lattice sparsification and densification techniques (Dadush and Kun, SODA 2013; Rogers, J. London Math. Soc. 1950).
BibTeX  Entry
@InProceedings{dadush:LIPIcs:2015:5116,
author = {Daniel Dadush},
title = {{Faster Deterministic Volume Estimation in the Oracle Model via Thin Lattice Coverings}},
booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)},
pages = {704718},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897835},
ISSN = {18688969},
year = {2015},
volume = {34},
editor = {Lars Arge and J{\'a}nos Pach},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5116},
URN = {urn:nbn:de:0030drops51168},
doi = {10.4230/LIPIcs.SOCG.2015.704},
annote = {Keywords: Deterministic Volume Estimation, Convex Geometry, Lattice Coverings of Space, Lattice Point Enumeration}
}
Keywords: 

Deterministic Volume Estimation, Convex Geometry, Lattice Coverings of Space, Lattice Point Enumeration 
Collection: 

31st International Symposium on Computational Geometry (SoCG 2015) 
Issue Date: 

2015 
Date of publication: 

12.06.2015 