Abstract
We show that the minimum possible size of an ε-net for point objects and line (or rectangle)-ranges in the plane is (slightly) bigger than linear in \(\frac{1}{\epsilon}\). This settles a problem raised by Matoušek, Seidel and Welzl (Proc. 6th Annu. ACM Sympos. Comput. Geom., pp. 16–22, 1990).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Agarwal, P.K.: Partitioning arrangements of lines I. Discrete Comput. Geom. 5, 449–483 (1990)
Agarwal, P.K.: Partitioning arrangements of lines II. Discrete Comput. Geom. 5, 553–573 (1990)
Alon, N., Spencer, J.H.: The Probabilistic Method, 3rd edn. Wiley, New York (2008). xv+352 pp.
Alon, N., Haussler, D., Welzl, E.: Partitioning and geometric embedding of range spaces of finite Vapnik–Chervonenkis dimension. In: Proc. of the Third Annual Symposium on Computational Geometry, Waterloo, Canada, pp. 331–340. ACM, New York (1987)
Alon, N., Bárány, I., Füredi, Z., Kleitman, D.J.: Point selections and weak ε-nets for convex hulls. Comb. Probab. Comput. 1, 189–200 (1992)
Alon, N., Kalai, G., Matoušek, J., Meshulam, R.: Transversal numbers for hypergraphs arising in geometry. Adv. Appl. Math. 29, 79–101 (2002)
Aronov, B., Ezra, E., Sharir, M.: Small-size epsilon-nets for axis-parallel rectangles and boxes. In: Proc. STOC 09, pp. 639–648
Brönnimann, H., Goodrich, M.T.: Almost optimal set covers in finite VC dimensions. Discrete Comput. Geom. 14, 463–479 (1995)
Bukh, B., Matoušek, J., Nivasch, G.: Lower bounds for weak epsilon-nets and stair-convexity. In: Proc. 25th ACM Symp. on Computational Geometry (SoCG 2009), pp. 1–10 (2009)
Chazelle, B., Friedman, J.: A deterministic view of random sampling and its use in geometry. Combinatorica 10, 229–249 (1990)
Chazelle, B., Edelsbrunner, H., Grigni, M., Guibas, L.J., Sharir, M., Welzl, E.: Improved bounds on weak ε-nets for convex sets. Discrete Comput. Geom. 13, 1–15 (1995)
Clarkson, K.: New applications of random sampling in computational geometry. Discrete Comput. Geom. 2, 195–222 (1987)
Clarkson, K.L., Varadarajan, K.: Improved approximation algorithms for geometric set cover. Discrete Comput. Geom. 37, 43–58 (2007)
Even, G., Rawitz, D., Shahar, S.: Hitting sets when the VC-dimension is small. Inf. Process. Lett. 95, 358–362 (2005)
Füredi, Z., Pach, J.: Traces of finite sets: extremal problems and geometric applications. In: Extremal problems for finite sets, Visegrád, 1991. Bolyai Soc. Math. Stud., vol. 3, pp. 251–282. János Bolyai Math. Soc., Budapest (1994)
Furstenberg, H., Katznelson, Y.: A density version of the Hales–Jewett theorem for k=3. In: Graph Theory and Combinatorics, Cambridge, 1988. Discrete Math., vol. 75, pp. 227–241 (1989)
Furstenberg, H., Katznelson, Y.: A density version of the Hales–Jewett theorem. J. Anal. Math. 57, 64–119 (1991)
Hales, A.W., Jewett, R.I.: Regularity and positional games. Trans. Am. Math. Soc. 106, 222–229 (1963)
Har-Peled, S., Kaplan, H., Sharir, M., Smorodinsky, S.: ε-nets for half-spaces revisited. Manuscript (2008)
Haussler, D., Welzl, E.: ε-nets and simplex range queries. Discrete Comput. Geom. 2, 127–151 (1987)
King, J., Kirkpatrick, D.G.: Improved approximation for guarding simple galleries from the perimeter. arXiv:1001.4231 (2010)
Komlós, J., Pach, J., Woeginger, G.: Almost tight bounds for epsilon nets. Discrete Comput. Geom. 7, 163–173 (1992)
Matoušek, J.: Reporting points in half-spaces. Comput. Geom. 2, 169–186 (1992)
Matoušek, J.: Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol. 212. Springer, New York (2002). xvi+481 pp.
Matoušek, J., Wagner, U.: New constructions of weak ε-nets. Discrete Comput. Geom. 32, 195–206 (2004)
Matoušek, J., Seidel, R., Welzl, E.: How to net a lot with little: small ε-nets for disks and halfspaces. In: Proc. 6th Annu. ACM Sympos. Comput. Geom., pp. 16–22 (1990). Revised version at http://kam.mff.cuni.cz/matousek/enets3.ps.gz
Pach, J., Agarwal, P.K.: Combinatorial Geometry. Wiley-Interscience Series in Discrete Mathematics and Optimization, A Wiley-Interscience Publication. Wiley, New York (1995). xiv+354 pp.
Pach, J., Woeginger, G.: Some new bounds for ε-nets. In: Proc. 6th Annual Symposium on Computational Geometry, pp. 10–15. ACM, New York (1990)
Pach, J., Tardos, G., Tóth, G.: Indecomposable coverings. Can. Math. Bull. 52(3), 451–463 (2009)
Polymath, D.H.J.: A new proof of the density Hales–Jewett theorem. arXiv:0910.3926
Polymath, D.H.J.: Density Hales–Jewett and Moser numbers. arXiv:1002.0374
Pyrga, E., Ray, S.: New existence proofs for ε-nets. In: Proc. 24th Annu. ACM Sympos. Comput. Geom., pp. 199–207 (2008)
Schwartz, J.: Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 701–717 (1980)
Vapnik, V.N., Chervonenkis, A.Yu.: On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl. 16, 264–280 (1971)
Varadarajan, K.R.: Epsilon nets and union complexity. In: Symposium on Computational Geometry, pp. 11–16 (2009)
Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Symbolic and Algebraic Computation (EUROSAM’79, Internat. Sympos.), Marseille, 1979. Lecture Notes in Comput. Sci., vol. 72, pp. 216–226. Springer, Berlin (1979)
Author information
Authors and Affiliations
Corresponding author
Additional information
A preliminary version of this paper appeared in the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010).
Research supported in part by an ERC Advanced grant, by the Hermann Minkowski Minerva Center for Geometry in Tel Aviv University, by the Oswald Veblen Fund and by the Bell Companies Fellowship.
Rights and permissions
About this article
Cite this article
Alon, N. A Non-linear Lower Bound for Planar Epsilon-nets. Discrete Comput Geom 47, 235–244 (2012). https://doi.org/10.1007/s00454-010-9323-7
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-010-9323-7