  We give a deterministic polynomial space construction for nearly optimal
eps-nets with respect to any input n-dimensional convex body K and norm |.|.
More precisely, our algorithm can build and iterate over an eps-net of K with
respect to |.| in time 2^O(n) x (size of the optimal net) using only
poly(n)-space. This improves on previous constructions of Alon et al [STOC
2013] which achieve either a 2^O(n) approximation or an n^O(n) approximation of
the optimal net size using 2^n space and poly(n)-space respectively. As in
their work, our algorithm relies on the mathematically classical approach of
building thin lattice coverings of space, which reduces the task of
constructing eps-nets to the problem of enumerating lattice points. Our main
technical contribution is a deterministic 2^O(n)-time and poly(n)-space
construction of thin lattice coverings of space with respect to any convex
body, where enumeration in these lattices can be efficiently performed using
poly(n)-space. This also yields the first existential construction of
poly(n)-space enumerable thin covering lattices for general convex bodies,
which we believe is of independent interest. Our construction combines the use
of the M-ellipsoid from convex geometry with lattice sparsification and
densification techniques.
  As an application, 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, which nearly matches the lower bounds for volume
estimation in the oracle model (the dependence on eps is larger by a factor 2
in the exponent). This improves on the previous results of Dadush and Vempala
[PNAS 2013], which gave the above result only for symmetric bodies and achieved
a dependence on eps of (1+log^{5/2}(1/eps)/eps^2)^n.
