License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SOCG.2015.704
URN: urn:nbn:de:0030-drops-51168
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5116/
Go to the corresponding LIPIcs Volume Portal

Dadush, Daniel

Faster Deterministic Volume Estimation in the Oracle Model via Thin Lattice Coverings

pdf-format:
33.pdf (0.4 MB)

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 so-called 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 M-ellipsoid 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 =	{704--718},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Lars Arge and J{\'a}nos Pach},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5116},
  URN =		{urn:nbn:de:0030-drops-51168},
  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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI