Paper Info
Title
Tight lower bounds for the size of epsilon-nets
Abstract
According to a well known theorem of Haussler and Welzl (1987), any range space of bounded VC-dimension admits an ε-net of size O(1/ε log 1/ε). 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 ε-nets is superlinear in 1/ε, were found by Alon (2010). In his examples, every ε-net is of size Ω(1/εg(1/ε)), where g is an extremely slowly growing function, related to the inverse Ackermann function. We show that there exist geometrically defined range spaces, already of VC-dimension 2, in which the size of the smallest ε-nets is Ω(1/ε log 1/ε). We also construct range spaces induced by axis-parallel rectangles in the plane, in which the size of the smallest ε-nets is Ω(1/ε log log 1/ε). By a theorem of Aronov, Ezra, and Sharir (2010), this bound is tight.
Year
DOI
Venue
2011
10.1145/1998196.1998271
Journal of the American Mathematical Society
Keywords
DocType
Volume
boxes,lower bound,vc dimension,geometry,euclidean space
Conference
abs/1012.1240
Issue
ISSN
Citations 
3
0894-0347
13
PageRank 
References 
Authors
0.70
17
2
Name
Order
Citations
PageRank
János Pach12366292.28
Gábor Tardos21261140.58