## 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

- Noga Alon,
*A non-linear lower bound for planar epsilon-nets*, Discrete Comput. Geom.**47**(2012), no. 2, 235–244. MR**2872535**, DOI 10.1007/s00454-010-9323-7 - 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**, DOI 10.1137/090762968 - 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**, DOI 10.1007/BF02570718 - Bernard Chazelle,
*The discrepancy method*, Cambridge University Press, Cambridge, 2000. Randomness and complexity. MR**1779341**, DOI 10.1017/CBO9780511626371 - 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**, DOI 10.1002/rsa.20246 - Kenneth L. Clarkson and Kasturi Varadarajan,
*Improved approximation algorithms for geometric set cover*, Discrete Comput. Geom.**37**(2007), no. 1, 43–58. MR**2279863**, DOI 10.1007/s00454-006-1273-8 - 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**, DOI 10.1016/j.ipl.2005.03.010 - 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**, DOI 10.1016/j.ipl.2010.06.005 - 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** - 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**, DOI 10.1016/0012-365X(89)90089-7 - H. Furstenberg and Y. Katznelson,
*A density version of the Hales-Jewett theorem*, J. Anal. Math.**57**(1991), 64–119. MR**1191743**, DOI 10.1007/BF03041066 - 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**, DOI 10.1109/FOCS.2009.54 - A. W. Hales and R. I. Jewett,
*Regularity and positional games*, Trans. Amer. Math. Soc.**106**(1963), 222–229. MR**143712**, DOI 10.1090/S0002-9947-1963-0143712-1 - David Haussler and Emo Welzl,
*$\epsilon$-nets and simplex range queries*, Discrete Comput. Geom.**2**(1987), no. 2, 127–151. MR**884223**, DOI 10.1007/BF02187876 - 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**, DOI 10.1137/070684483 - 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**, DOI 10.1007/BF02187833 - Jiří Matoušek,
*Reporting points in halfspaces*, Comput. Geom.**2**(1992), no. 3, 169–186. MR**1190599**, DOI 10.1016/0925-7721(92)90006-E - 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. - 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**, DOI 10.1002/9781118033203 - János Pach and Gábor Tardos,
*Coloring axis-parallel rectangles*, J. Combin. Theory Ser. A**117**(2010), no. 6, 776–782. MR**2645191**, DOI 10.1016/j.jcta.2009.04.007 - 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**, DOI 10.1145/1998196.1998271 - János Pach, Gábor Tardos, and Géza Tóth,
*Indecomposable coverings*, Canad. Math. Bull.**52**(2009), no. 3, 451–463. MR**2547811**, DOI 10.4153/CMB-2009-048-x - 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. - 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**, DOI 10.4007/annals.2012.175.3.6 - 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**, DOI 10.1007/978-3-642-14444-8_{2}2 - Evangelia Pyrga and Saurabh Ray,
*New existence proofs for $\epsilon$-nets*, Computational geometry (SCG’08), ACM, New York, 2008, pp. 199–207. MR**2504287**, DOI 10.1145/1377676.1377708 - 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. - K. R. Varadarajan, Epsilon nets and union complexity, in:
*Proc. 25th Ann. ACM Sympos. Comput. Geom.*, ACM Press, New York, 2009, 11–16.

## 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