Tight lower bounds for the size of epsilon-nets

Pach, János; Tardos, Gábor

doi:10.1090/S0894-0347-2012-00759-0

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

by János Pach and Gábor Tardos;

J. Amer. Math. Soc. 26 (2013), 645-658

DOI: https://doi.org/10.1090/S0894-0347-2012-00759-0

Published electronically: November 7, 2012

PDF

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.