Tight lower bounds for the size of epsilon-nets

Pach, János¹ ; Tardos, Gábor²

¹ EPFL, Station 8, CH-1015 Lausanne, Switzerland – and – Hungarian Academy of Science, Rényi Institute, P. O. Box 127, Budapest, 1364 Hungary
² 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

Journal of the American Mathematical Society, Tome 26 (2013) no. 3, pp. 645-658

Résumé

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.

Détail

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

Bibliographie

[1] Alon, Noga A non-linear lower bound for planar epsilon-nets Discrete Comput. Geom. 2012 235 244

[2] Aronov, Boris, Ezra, Esther, Sharir, Micha Small-size 𝜀-nets for axis-parallel rectangles and boxes SIAM J. Comput. 2010 3248 3282

[3] Brã¶Nnimann, H., Goodrich, M. T. Almost optimal set covers in finite VC-dimension Discrete Comput. Geom. 1995 463 479

[4] Chazelle, Bernard The discrepancy method 2000

[5] Chen, Xiaomin, Pach, Jã¡Nos, Szegedy, Mario, Tardos, Gã¡Bor Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles Random Structures Algorithms 2009 11 23

[6] Clarkson, Kenneth L., Varadarajan, Kasturi Improved approximation algorithms for geometric set cover Discrete Comput. Geom. 2007 43 58

[7] Even, Guy, Rawitz, Dror, Shahar, Shimon Hitting sets when the VC-dimension is small Inform. Process. Lett. 2005 358 362

[8] Ezra, Esther A note about weak 𝜀-nets for axis-parallel boxes in 𝑑-space Inform. Process. Lett. 2010 835 840

[9] Ezra, Esther, Aronov, Boris, Sharir, Micha Improved bound for the union of fat triangles 2011 1778 1785

[10] Furstenberg, H., Katznelson, Y. A density version of the Hales-Jewett theorem for 𝑘 Discrete Math. 1989 227 241

[11] Furstenberg, H., Katznelson, Y. A density version of the Hales-Jewett theorem J. Anal. Math. 1991 64 119

[12] Gibson, Matt, Varadarajan, Kasturi Decomposing coverings and the planar sensor cover problem 2009 159 168

[13] Hales, A. W., Jewett, R. I. Regularity and positional games Trans. Amer. Math. Soc. 1963 222 229

[14] Haussler, David, Welzl, Emo 𝜀-nets and simplex range queries Discrete Comput. Geom. 1987 127 151

[15] Kaplan, Haim, Rubin, Natan, Sharir, Micha, Verbin, Elad Efficient colored orthogonal range counting SIAM J. Comput. 2008 982 1011

[16] Komlã³S, Jã¡Nos, Pach, Jã¡Nos, Woeginger, Gerhard Almost tight bounds for 𝜀-nets Discrete Comput. Geom. 1992 163 173

[17] Matouå¡Ek, Jiå™Ã­ Reporting points in halfspaces Comput. Geom. 1992 169 186

[18] Pach, Jã¡Nos, Agarwal, Pankaj K. Combinatorial geometry 1995

[19] Pach, Jã¡Nos, Tardos, Gã¡Bor Coloring axis-parallel rectangles J. Combin. Theory Ser. A 2010 776 782

[20] Pach, Jã¡Nos, Tardos, Gã¡Bor Tight lower bounds for the size of epsilon-nets (extended abstract) 2011 458 463

[21] Pach, Jã¡Nos, Tardos, Gã¡Bor, Tã³Th, Gã©Za Indecomposable coverings Canad. Math. Bull. 2009 451 463

[22] Polymath, D. H. J. A new proof of the density Hales-Jewett theorem Ann. of Math. (2) 2012 1283 1327

[23] Polymath, D. H. J. Density Hales-Jewett and Moser numbers 2010 689 753

[24] Pyrga, Evangelia, Ray, Saurabh New existence proofs for 𝜀-nets 2008 199 207