Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Journal of the American Mathematical Society
Journal of the American Mathematical Society
ISSN 1088-6834(online) ISSN 0894-0347(print)

   

 

Tight lower bounds for the size of epsilon-nets


Authors: János Pach and Gábor Tardos
Journal: J. Amer. Math. Soc. 26 (2013), 645-658
MSC (2010): Primary 52C10; Secondary 05D15
Published electronically: November 7, 2012
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: According to a well known theorem of Haussler and Welzl (1987), any range space of bounded VC-dimension admits an $ \varepsilon $-net of size $ O\!\left (\frac {1}{\varepsilon }\log \frac 1{\varepsilon }\right )$. 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 $ \varepsilon $-nets is superlinear in $ \frac 1{\varepsilon }$, were found by Alon (2010). In his examples, every $ \varepsilon $-net is of size $ \Omega \left (\frac {1}{\varepsilon }g(\frac {1}{\varepsilon })\right )$, 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 $ \varepsilon $-nets is $ \Omega \left (\frac {1}{\varepsilon }\log \frac {1}{\varepsilon }\right )$. We also construct range spaces induced by axis-parallel rectangles in the plane, in which the size of the smallest $ \varepsilon $-nets is $ \Omega \left (\frac {1}{\varepsilon }\log \log \frac {1}{\varepsilon }\right )$. By a theorem of Aronov, Ezra, and Sharir (2010), this bound is tight.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2010): 52C10, 05D15

Retrieve articles in all journals with MSC (2010): 52C10, 05D15


Additional Information

János Pach
Affiliation: EPFL, Station 8, CH-1015 Lausanne, Switzerland – and – Hungarian Academy of Science, Rényi Institute, P. O. Box 127, Budapest, 1364 Hungary
Email: pach@cims.nyu.edu

Gábor Tardos
Affiliation: Department of Computer Science, Simon Fraser University, Burnaby, BC, Canada V5A 1S6 – and – Hungarian Academy of Science, Rényi Institute, P. O. Box 127, Budapest, 1364 Hungary
Email: tardos@cs.sfu.edu

DOI: http://dx.doi.org/10.1090/S0894-0347-2012-00759-0
PII: S 0894-0347(2012)00759-0
Received by editor(s): April 26, 2011
Received by editor(s) in revised form: January 7, 2012, and July 30, 2012
Published electronically: November 7, 2012
Additional Notes: The first author was supported by Hungarian Science Foundation EuroGIGA grant OTKA NN-102029, by Swiss National Science Foundation grant 200021-125287/1, and by NSF grant CCF-08-30272
The second author was supported by NSERC grant 329527, OTKA grants T-046234, AT-048826, and NK-62321, and by the Bernoulli Center at EPFL
Article copyright: © Copyright 2012 Pach and Tardos