A Deterministic Polynomial Space Construction for eps-nets under any Norm

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