×

A simple proof of optimal epsilon nets. (English) Zbl 1424.52020

Given a set system \((X,\mathcal{R})\) and any \(Y \subseteq X\), \(\mathcal{R} \vert_Y\) is defined to be \(\{ Y \cap R \mid R \in \mathcal{R}\}\). The VC-dimension VC-\(\dim (\mathcal{R})\) of \(\mathcal{R}\) is the size of the largest \(Y \subseteq X\) for which \(\mathcal{R} \vert_Y =2^Y\).
For \(\varepsilon > 0\), an \(\varepsilon\)-net for a set system \((X,\mathcal{R})\) is a set \(N \subseteq X\) such that \(N \cap R \ne \emptyset\) for all \(R \in \mathcal{R}\) with \(\vert R\vert \geq \varepsilon \vert X\vert \).
A set system \((X,\mathcal{R})\) has shallow-cell complexity \(\varphi_{\mathcal{R}}(\cdot,\cdot)\) if for any \(Y \subseteq X\), the number of subsets in \(\mathcal{R}\vert_Y\) of size at most \(\ell\) is \(\vert Y\vert \cdot \varphi_{\mathcal{R}}(\vert Y\vert ,\ell)\).
The size of the smallest \(\varepsilon\)-nets for set systems has been settled in terms of shallow-cell complexity. The authors give a short proof of this result based on the \(\varepsilon\)-net bound of D. Haussler and E. Welzl [Discrete Comput. Geom. 2, 127–151 (1987; Zbl 0619.68056)] together with the packing lemma of D. Haussler [J. Comb. Theory, Ser. A 69, No. 2, 217–232 (1995; Zbl 0818.60005)]. More precisely, the authors prove the following. Let \((X,\mathcal{R})\), \(\vert X\vert = n\), be a set system with VC-\(\dim (\mathcal{R}) = d\) and shallow-cell complexity \(\varphi_{\mathcal{R}}(\cdot,\cdot)\), where \(\varphi_{\mathcal{R}}(\cdot,\cdot)\) is a non-decreasing function in the first variable. Then there exists an \(\varepsilon\)-net for \(\mathcal{R}\) of size \(O(\frac{1}{\varepsilon} \log \varphi(\frac{8d}{\varepsilon},24d) + \frac{d}{\varepsilon})\).

MSC:

52C45 Combinatorial complexity of geometric structures
05D15 Transversal (matching) theory
52B55 Computational aspects related to convexity
PDFBibTeX XMLCite
Full Text: DOI HAL

References:

[1] N. Alon: A non-linear lower bound for planar epsilon-nets, Discrete &amp · doi:10.1007/s00454-010-9323-7
[2] B. Aronov, E. Ezra and M. Sharir: Small-size \({\in}\)-nets for axis-parallel rectangles and boxes, S · doi:10.1137/090762968
[3] N. Bus, S. Garg, N. H. Mustafa and S. Ray: Tighter estimates for \({\in}\)-nets for disks, Computational Geometry: · doi:10.1016/j.comgeo.2015.12.002
[4] T. M. Chan, E. Grant, J. Könemann and M. Sharpe: Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling, in: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1576–1585, 2012.
[5] B. Chazelle: A note on Haussler’s packing lemma, 1992, See Section 5.3 from Geometric Discrepancy: An Illustrated Guide by J. Matoušek.
[6] B. Chazelle: The Discrepancy Method: Randomness and Complexity, Cambridge University Press, 2000.
[7] B. Chazelle and J. Friedman: A deterministic view of random sampling and its use in · doi:10.1007/BF02122778
[8] K. L. Clarkson and P. W. Shor: Application of random sampling in computational geometry, II, Discrete &amp · doi:10.1007/BF02187740
[9] K. L. Clarkson and K. R. Varadarajan: Improved approximation algorithms for geometric set cover, Discrete &amp · doi:10.1007/s00454-006-1273-8
[10] K. Dutta, E. Ezra and A. Ghosh: Two proofs for shallow packings, in: Proceedings of the 31st Annual Symposium on Computational Geometry (SoCG), 96–110, 2015.
[11] E. Ezra: A size-sensitive discrepancy bound for set systems of bounded primal shatter dimension, in: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1378–1388, 2014.
[12] S. Har-Peled, H. Kaplan, M. Sharir and S. Smorodinsky: Epsilon-nets for halfspaces revisited, CoRR, abs/1410.3154, 2014.
[13] S. Har-Peled and M. Sharir: Relative (p, \({\in}\))-approximations in geometry, Discrete &amp · doi:10.1007/s00454-010-9248-1
[14] D. Haussler: Sphere packing numbers for subsets of the boolean n-cube with bounded Vapnik-Chervonenkis dimension, Journal of Combin · doi:10.1016/0097-3165(95)90052-7
[15] D. Haussler and E. Welzl: Epsilon-nets and simplex range queries, Discrete &amp · doi:10.1007/BF02187876
[16] J. Komlós, J. Pach and G. Woeginger: Almost tight bounds for \({\in}\)-nets, Discrete &amp · doi:10.1007/BF02187833
[17] A. Kupavskii, N. H. Mustafa and J. Pach: New lower bounds for epsilon-nets, in: Proceedings of the 32nd International Symposium on Computational Geometry, SoCG 2016, 54:1–54:16, 2016.
[18] J. Matoušek: On constants for cuttings in the plane, Discrete &amp · doi:10.1007/PL00009394
[19] J. Matoušek: Geometric Discrepancy: An Illustrated Guide, Springer, 1999.
[20] J. Matoušek: Lectures in Discrete Geometry, Springer, 2002.
[21] J. Matoušek, R. Seidel and E. Welzl: How to net a lot with little: Small epsilonnets for disks and halfspaces, in: Proceedings of the 6th Annual ACM Symposium on Computational Geometry (SoCG), 16–22, 1990.
[22] J. Matoušek: Reporting points in halfspaces, Computational Geometry: · doi:10.1016/0925-7721(92)90006-E
[23] J. Matoušek: Derandomization in Computational Geometr · doi:10.1006/jagm.1996.0027
[24] N. H. Mustafa: A simple proof of the shallow packing lemma, Discrete &amp · doi:10.1007/s00454-016-9767-5
[25] N. H. Mustafa and S. Ray: Near-optimal generalisations of a theorem of Macbeath, in: Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS), 578–589, 2014.
[26] J. Pach and P. K. Agarwal: Combinatorial Geometry, John Wiley & Sons, 1995.
[27] J. Pach and G. Tardos: Tight lower bounds for the size of epsilon-
[28] E. Pyrga and S. Ray: New existence proofs for \({\in}\)-nets, in: Proceedings of the 24th Annual ACM Symposium on Computational Geometry (SoCG), 199–207, 2008.
[29] N. Sauer: On the density of families of sets, Journal of Combin · doi:10.1016/0097-3165(72)90019-2
[30] S. Shelah: A combinatorial problem, stability and order for models and theories in infinitary languages, Pacifi
[31] V. N. Vapnik and A. Y. Chervonenkis: On the uniform convergence of relative frequencies of events to their probabilities, Theory of Probabil · doi:10.1137/1116025
[32] K. R. Varadarajan: Epsilon nets and union complexity, in: Proceedings of the 25th Annual ACM Symposium on Computational Geometry (SoCG), 11–16, 2009.
[33] K. R. Varadarajan: Weighted geometric set cover via quasi-uniform sampling, in: Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC), 641–648, 2010.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.