{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T10:01:14Z","timestamp":1777975274436,"version":"3.51.4"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2011,1,5]],"date-time":"2011-01-05T00:00:00Z","timestamp":1294185600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2012,3]]},"DOI":"10.1007\/s00454-010-9323-7","type":"journal-article","created":{"date-parts":[[2011,1,4]],"date-time":"2011-01-04T15:14:14Z","timestamp":1294154054000},"page":"235-244","source":"Crossref","is-referenced-by-count":19,"title":["A Non-linear Lower Bound for Planar Epsilon-nets"],"prefix":"10.1007","volume":"47","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,1,5]]},"reference":[{"key":"9323_CR1","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1007\/BF02187805","volume":"5","author":"P.K. Agarwal","year":"1990","unstructured":"Agarwal, P.K.: Partitioning arrangements of lines I. Discrete Comput. Geom. 5, 449\u2013483 (1990)","journal-title":"Discrete Comput. Geom."},{"key":"9323_CR2","first-page":"553","volume":"5","author":"P.K. Agarwal","year":"1990","unstructured":"Agarwal, P.K.: Partitioning arrangements of lines\u00a0II. Discrete Comput. Geom. 5, 553\u2013573 (1990)","journal-title":"Discrete Comput. Geom."},{"key":"9323_CR3","doi-asserted-by":"crossref","DOI":"10.1002\/9780470277331","volume-title":"The Probabilistic Method","author":"N. Alon","year":"2008","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method, 3rd edn. Wiley, New York (2008). xv+352\u00a0pp.","edition":"3"},{"key":"9323_CR4","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1145\/41958.41994","volume-title":"Proc. of the Third Annual Symposium on Computational Geometry","author":"N. Alon","year":"1987","unstructured":"Alon, N., Haussler, D., Welzl, E.: Partitioning and geometric embedding of range spaces of finite Vapnik\u2013Chervonenkis dimension. In: Proc. of the Third Annual Symposium on Computational Geometry, Waterloo, Canada, pp. 331\u2013340. ACM, New York (1987)"},{"key":"9323_CR5","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1017\/S0963548300000225","volume":"1","author":"N. Alon","year":"1992","unstructured":"Alon, N., B\u00e1r\u00e1ny, I., F\u00fcredi, Z., Kleitman, D.J.: Point selections and weak \u03b5-nets for convex hulls. Comb. Probab. Comput. 1, 189\u2013200 (1992)","journal-title":"Comb. Probab. Comput."},{"key":"9323_CR6","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/S0196-8858(02)00003-9","volume":"29","author":"N. Alon","year":"2002","unstructured":"Alon, N., Kalai, G., Matou\u0161ek, J., Meshulam, R.: Transversal numbers for hypergraphs arising in geometry. Adv. Appl. Math. 29, 79\u2013101 (2002)","journal-title":"Adv. Appl. Math."},{"key":"9323_CR7","doi-asserted-by":"crossref","unstructured":"Aronov, B., Ezra, E., Sharir, M.: Small-size epsilon-nets for axis-parallel rectangles and boxes. In: Proc. STOC 09, pp. 639\u2013648","DOI":"10.1145\/1536414.1536501"},{"key":"9323_CR8","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1007\/BF02570718","volume":"14","author":"H. Br\u00f6nnimann","year":"1995","unstructured":"Br\u00f6nnimann, H., Goodrich, M.T.: Almost optimal set covers in finite VC dimensions. Discrete Comput. Geom. 14, 463\u2013479 (1995)","journal-title":"Discrete Comput. Geom."},{"key":"9323_CR9","first-page":"1","volume-title":"Proc. 25th ACM Symp. on Computational Geometry (SoCG 2009)","author":"B. Bukh","year":"2009","unstructured":"Bukh, B., Matou\u0161ek, J., Nivasch, G.: Lower bounds for weak epsilon-nets and stair-convexity. In: Proc. 25th ACM Symp. on Computational Geometry (SoCG 2009), pp.\u00a01\u201310 (2009)"},{"key":"9323_CR10","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/BF02122778","volume":"10","author":"B. Chazelle","year":"1990","unstructured":"Chazelle, B., Friedman, J.: A deterministic view of random sampling and its use in geometry. Combinatorica 10, 229\u2013249 (1990)","journal-title":"Combinatorica"},{"key":"9323_CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02574025","volume":"13","author":"B. Chazelle","year":"1995","unstructured":"Chazelle, B., Edelsbrunner, H., Grigni, M., Guibas, L.J., Sharir, M., Welzl, E.: Improved bounds on weak \u03b5-nets for convex sets. Discrete Comput. Geom. 13, 1\u201315 (1995)","journal-title":"Discrete Comput. Geom."},{"key":"9323_CR12","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF02187879","volume":"2","author":"K. Clarkson","year":"1987","unstructured":"Clarkson, K.: New applications of random sampling in computational geometry. Discrete Comput. Geom. 2, 195\u2013222 (1987)","journal-title":"Discrete Comput. Geom."},{"key":"9323_CR13","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/s00454-006-1273-8","volume":"37","author":"K.L. Clarkson","year":"2007","unstructured":"Clarkson, K.L., Varadarajan, K.: Improved approximation algorithms for geometric set cover. Discrete Comput. Geom. 37, 43\u201358 (2007)","journal-title":"Discrete Comput. Geom."},{"key":"9323_CR14","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1016\/j.ipl.2005.03.010","volume":"95","author":"G. Even","year":"2005","unstructured":"Even, G., Rawitz, D., Shahar, S.: Hitting sets when the VC-dimension is small. Inf. Process. Lett. 95, 358\u2013362 (2005)","journal-title":"Inf. Process. Lett."},{"key":"9323_CR15","series-title":"Bolyai Soc. Math. Stud.","first-page":"251","volume-title":"Extremal problems for finite sets","author":"Z. F\u00fcredi","year":"1994","unstructured":"F\u00fcredi, Z., Pach, J.: Traces of finite sets: extremal problems and geometric applications. In: Extremal problems for finite sets, Visegr\u00e1d, 1991. Bolyai Soc. Math. Stud., vol. 3, pp. 251\u2013282. J\u00e1nos Bolyai Math. Soc., Budapest (1994)"},{"key":"9323_CR16","series-title":"Discrete Math.","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/S0167-5060(08)70577-6","volume-title":"Graph Theory and Combinatorics","author":"H. Furstenberg","year":"1989","unstructured":"Furstenberg, H., Katznelson, Y.: A density version of the Hales\u2013Jewett theorem for k=3. In: Graph Theory and Combinatorics, Cambridge, 1988. Discrete Math., vol. 75, pp. 227\u2013241 (1989)"},{"key":"9323_CR17","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1007\/BF03041066","volume":"57","author":"H. Furstenberg","year":"1991","unstructured":"Furstenberg, H., Katznelson, Y.: A density version of the Hales\u2013Jewett theorem. J. Anal. Math. 57, 64\u2013119 (1991)","journal-title":"J. Anal. Math."},{"key":"9323_CR18","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1090\/S0002-9947-1963-0143712-1","volume":"106","author":"A.W. Hales","year":"1963","unstructured":"Hales, A.W., Jewett, R.I.: Regularity and positional games. Trans. Am. Math. Soc. 106, 222\u2013229 (1963)","journal-title":"Trans. Am. Math. Soc."},{"key":"9323_CR19","unstructured":"Har-Peled, S., Kaplan, H., Sharir, M., Smorodinsky, S.: \u03b5-nets for half-spaces revisited. Manuscript (2008)"},{"key":"9323_CR20","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D. Haussler","year":"1987","unstructured":"Haussler, D., Welzl, E.: \u03b5-nets and simplex range queries. Discrete Comput. Geom. 2, 127\u2013151 (1987)","journal-title":"Discrete Comput. Geom."},{"key":"9323_CR21","doi-asserted-by":"crossref","unstructured":"King, J., Kirkpatrick, D.G.: Improved approximation for guarding simple galleries from the perimeter. arXiv:1001.4231 (2010)","DOI":"10.1007\/s00454-011-9352-x"},{"key":"9323_CR22","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/BF02187833","volume":"7","author":"J. Koml\u00f3s","year":"1992","unstructured":"Koml\u00f3s, J., Pach, J., Woeginger, G.: Almost tight bounds for epsilon nets. Discrete Comput. Geom. 7, 163\u2013173 (1992)","journal-title":"Discrete Comput. Geom."},{"key":"9323_CR23","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0925-7721(92)90006-E","volume":"2","author":"J. Matou\u0161ek","year":"1992","unstructured":"Matou\u0161ek, J.: Reporting points in half-spaces. Comput. Geom. 2, 169\u2013186 (1992)","journal-title":"Comput. Geom."},{"key":"9323_CR24","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry","author":"J. Matou\u0161ek","year":"2002","unstructured":"Matou\u0161ek, J.: Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol.\u00a0212. Springer, New York (2002). xvi+481\u00a0pp."},{"key":"9323_CR25","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/s00454-004-1116-4","volume":"32","author":"J. Matou\u0161ek","year":"2004","unstructured":"Matou\u0161ek, J., Wagner, U.: New constructions of weak \u03b5-nets. Discrete Comput. Geom. 32, 195\u2013206 (2004)","journal-title":"Discrete Comput. Geom."},{"key":"9323_CR26","first-page":"16","volume-title":"Proc. 6th Annu. ACM Sympos. Comput. Geom.","author":"J. Matou\u0161ek","year":"1990","unstructured":"Matou\u0161ek, J., Seidel, R., Welzl, E.: How to net a lot with little: small \u03b5-nets for disks and halfspaces. In: Proc. 6th Annu. ACM Sympos. Comput. Geom., pp. 16\u201322 (1990). Revised version at http:\/\/kam.mff.cuni.cz\/matousek\/enets3.ps.gz"},{"key":"9323_CR27","series-title":"Wiley-Interscience Series in Discrete Mathematics and Optimization, A Wiley-Interscience Publication","doi-asserted-by":"crossref","DOI":"10.1002\/9781118033203","volume-title":"Combinatorial Geometry","author":"J. Pach","year":"1995","unstructured":"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."},{"key":"9323_CR28","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1145\/98524.98529","volume-title":"Proc. 6th Annual Symposium on Computational Geometry","author":"J. Pach","year":"1990","unstructured":"Pach, J., Woeginger, G.: Some new bounds for \u03b5-nets. In: Proc. 6th Annual Symposium on Computational Geometry, pp. 10\u201315. ACM, New York (1990)"},{"issue":"3","key":"9323_CR29","doi-asserted-by":"crossref","first-page":"451","DOI":"10.4153\/CMB-2009-048-x","volume":"52","author":"J. Pach","year":"2009","unstructured":"Pach, J., Tardos, G., T\u00f3th, G.: Indecomposable coverings. Can. Math. Bull. 52(3), 451\u2013463 (2009)","journal-title":"Can. Math. Bull."},{"key":"9323_CR30","unstructured":"Polymath, D.H.J.: A new proof of the density Hales\u2013Jewett theorem. arXiv:0910.3926"},{"key":"9323_CR31","unstructured":"Polymath, D.H.J.: Density Hales\u2013Jewett and Moser numbers. arXiv:1002.0374"},{"key":"9323_CR32","first-page":"199","volume-title":"Proc. 24th Annu. ACM Sympos. Comput. Geom.","author":"E. Pyrga","year":"2008","unstructured":"Pyrga, E., Ray, S.: New existence proofs for \u03b5-nets. In: Proc. 24th Annu. ACM Sympos. Comput. Geom., pp. 199\u2013207 (2008)"},{"key":"9323_CR33","doi-asserted-by":"crossref","unstructured":"Schwartz, J.: Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 701\u2013717 (1980)","DOI":"10.1145\/322217.322225"},{"key":"9323_CR34","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"V.N. Vapnik","year":"1971","unstructured":"Vapnik, V.N., Chervonenkis, A.Yu.: On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl. 16, 264\u2013280 (1971)","journal-title":"Theory Probab. Appl."},{"key":"9323_CR35","first-page":"11","volume-title":"Symposium on Computational Geometry","author":"K.R. Varadarajan","year":"2009","unstructured":"Varadarajan, K.R.: Epsilon nets and union complexity. In: Symposium on Computational Geometry, pp. 11\u201316 (2009)"},{"key":"9323_CR36","series-title":"Lecture Notes in Comput. Sci.","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1007\/3-540-09519-5_73","volume-title":"Symbolic and Algebraic Computation (EUROSAM\u201979, Internat. Sympos.)","author":"R. Zippel","year":"1979","unstructured":"Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Symbolic and Algebraic Computation (EUROSAM\u201979, Internat. Sympos.), Marseille, 1979. Lecture Notes in Comput. Sci., vol. 72, pp.\u00a0216\u2013226. Springer, Berlin (1979)"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-010-9323-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-010-9323-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-010-9323-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T11:22:39Z","timestamp":1740828159000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-010-9323-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1,5]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,3]]}},"alternative-id":["9323"],"URL":"https:\/\/doi.org\/10.1007\/s00454-010-9323-7","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1,5]]}}}