Skip to Main Content

Journal of the American Mathematical Society

Published by the American Mathematical Society, the Journal of the American Mathematical Society (JAMS) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6834 (online) ISSN 0894-0347 (print)

The 2020 MCQ for Journal of the American Mathematical Society is 4.79.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Tight lower bounds for the size of epsilon-nets
HTML articles powered by AMS MathViewer

by János Pach and Gábor Tardos PDF
J. Amer. Math. Soc. 26 (2013), 645-658

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
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
  • 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
  • © Copyright 2012 Pach and Tardos
  • Journal: J. Amer. Math. Soc. 26 (2013), 645-658
  • MSC (2010): Primary 52C10; Secondary 05D15
  • DOI: https://doi.org/10.1090/S0894-0347-2012-00759-0
  • MathSciNet review: 3037784