Tight lower bounds for the size of epsilon-nets

According to a well known theorem of Haussler and Welzl (1987), any range space of bounded VC-dimension admits an epsilon-net of size O (1/epsilon log 1/epsilon). Using probabilistic techniques, Pach and Woeginger (1990) showed that there exist range spaces of VC-dimension 2, for which the above bound is sharp. The only known range spaces of small VC-dimension, in which the ranges are geometric objects in some Euclidean space and the size of the smallest epsilon-nets is superlinear in 1/epsilon, were found by Alon (2010). In his examples, every epsilon-net is of size Omega (1/epsilon g(1/epsilon)), where g is an extremely slowly growing function, related to the inverse Ackermann function.

Published in:
Proc. 27th Annual ACM Symposium on Computational Geometry , 458-463
Presented at:
27th Annual ACM Symposium on Computational Geometry , Paris, France
Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa

 Record created 2011-12-12, last modified 2018-03-17

Rate this document:

Rate this document:
(Not yet reviewed)