Remote Access Journal of the American Mathematical Society
Green Open Access

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
MathSciNet review: 3037784
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?)

  • [Al12] Noga Alon, A non-linear lower bound for planar epsilon-nets, Discrete Comput. Geom. 47 (2012), no. 2, 235-244. MR 2872535,
  • [ArES10] Boris Aronov, Esther Ezra, and Micha Sharir, Small-size $ \epsilon $-nets for axis-parallel rectangles and boxes, SIAM J. Comput. 39 (2010), no. 7, 3248-3282. MR 2678074 (2012h:68259),
  • [BrG95] H. Brönnimann and M. T. Goodrich, Almost optimal set covers in finite VC-dimension, Discrete Comput. Geom. 14 (1995), no. 4, 463-479. ACM Symposium on Computational Geometry (Stony Brook, NY, 1994). MR 1360948 (96j:68170),
  • [Ch00] Bernard Chazelle, The discrepancy method, Cambridge University Press, Cambridge, 2000. Randomness and complexity. MR 1779341 (2002c:68002)
  • [ChPS09] Xiaomin Chen, János Pach, Mario Szegedy, and Gábor Tardos, Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles, Random Structures Algorithms 34 (2009), no. 1, 11-23. MR 2478536 (2009k:52031),
  • [ClV07] Kenneth L. Clarkson and Kasturi Varadarajan, Improved approximation algorithms for geometric set cover, Discrete Comput. Geom. 37 (2007), no. 1, 43-58. MR 2279863 (2008a:68216),
  • [EvRS05] Guy Even, Dror Rawitz, and Shimon Shahar, Hitting sets when the VC-dimension is small, Inform. Process. Lett. 95 (2005), no. 2, 358-362. MR 2149262 (2005m:68253),
  • [Ez10] Esther Ezra, A note about weak $ \epsilon $-nets for axis-parallel boxes in $ d$-space, Inform. Process. Lett. 110 (2010), no. 18-19, 835-840. MR 2676041 (2011e:68161),
  • [EzAS11] Esther Ezra, Boris Aronov, and Micha Sharir, Improved bound for the union of fat triangles, Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 2011, pp. 1778-1785. MR 2858435 (2012j:68286)
  • [FuK89] H. Furstenberg and Y. Katznelson, A density version of the Hales-Jewett theorem for $ k=3$, Discrete Math. 75 (1989), no. 1-3, 227-241. Graph theory and combinatorics (Cambridge, 1988). MR 1001397 (90k:05003),
  • [FuK91] H. Furstenberg and Y. Katznelson, A density version of the Hales-Jewett theorem, J. Anal. Math. 57 (1991), 64-119. MR 1191743 (94f:28020),
  • [GiV09] Matt Gibson and Kasturi Varadarajan, Decomposing coverings and the planar sensor cover problem, 2009 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), IEEE Computer Soc., Los Alamitos, CA, 2009, pp. 159-168. MR 2648398 (2011g:68279),
  • [HaJ63] A. W. Hales and R. I. Jewett, Regularity and positional games, Trans. Amer. Math. Soc. 106 (1963), 222-229. MR 0143712 (26 #1265)
  • [HaW87] David Haussler and Emo Welzl, $ \epsilon $-nets and simplex range queries, Discrete Comput. Geom. 2 (1987), no. 2, 127-151. MR 884223 (88d:68099),
  • [KaRS08] Haim Kaplan, Natan Rubin, Micha Sharir, and Elad Verbin, Efficient colored orthogonal range counting, SIAM J. Comput. 38 (2008), no. 3, 982-1011. MR 2421075 (2010g:68124),
  • [KoPW92] János Komlós, János Pach, and Gerhard Woeginger, Almost tight bounds for $ \epsilon $-nets, Discrete Comput. Geom. 7 (1992), no. 2, 163-173. MR 1139078 (93a:52013),
  • [Ma92] Jiří Matoušek, Reporting points in halfspaces, Comput. Geom. 2 (1992), no. 3, 169-186. MR 1190599 (93i:68181),
  • [MaSW90] J. Matoušek, R. Seidel and E. Welzl, How to net a lot with little: Small $ \varepsilon $-nets for disks and halfspaces, In: Proc. 6th Ann. ACM Symposium on Computational Geometry, ACM Press, New York, 1990, 16-22.
  • [PaA95] János Pach and Pankaj K. Agarwal, Combinatorial geometry, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons Inc., New York, 1995. A Wiley-Interscience Publication. MR 1354145 (96j:52001)
  • [PaT10] János Pach and Gábor Tardos, Coloring axis-parallel rectangles, J. Combin. Theory Ser. A 117 (2010), no. 6, 776-782. MR 2645191 (2011h:05183),
  • [PaT11] János Pach and Gábor Tardos, Tight lower bounds for the size of epsilon-nets (extended abstract), Computational geometry (SCG'11), ACM, New York, 2011, pp. 458-463. MR 2919638,
  • [PaTT09] János Pach, Gábor Tardos, and Géza Tóth, Indecomposable coverings, Canad. Math. Bull. 52 (2009), no. 3, 451-463. MR 2547811 (2011a:52037),
  • [PaW90] J. Pach and G. Woeginger, Some new bounds for $ \varepsilon $-nets, in: Proc. 6th Ann. Symp. on Computat. Geom., ACM Press, New York, 1990, 10-15.
  • [Po09] D. H. J. Polymath, A new proof of the density Hales-Jewett theorem, Ann. of Math. (2) 175 (2012), no. 3, 1283-1327. MR 2912706,
  • [Po10] D. H. J. Polymath, Density Hales-Jewett and Moser numbers, An irregular mind, Bolyai Soc. Math. Stud., vol. 21, János Bolyai Math. Soc., Budapest, 2010, pp. 689-753. MR 2815620,
  • [PyR08] Evangelia Pyrga and Saurabh Ray, New existence proofs for $ \epsilon $-nets, Computational geometry (SCG'08), ACM, New York, 2008, pp. 199-207. MR 2504287 (2010f:05130),
  • [VaC71] V. N. Vapnik and A. Ya. Chervonenkis, On the uniform convergence of relative frequencies of events to their probabilities, Theory Probab. Appl. 16 (1971), 264-280.
  • [Va09] K. R. Varadarajan, Epsilon nets and union complexity, in: Proc. 25th Ann. ACM Sympos. Comput. Geom., ACM Press, New York, 2009, 11--16.

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

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

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

American Mathematical Society