{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:22:09Z","timestamp":1750220529151,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":49,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["678765"],"award-info":[{"award-number":["678765"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451062","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"989-1002","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Stronger bounds for weak epsilon-nets in higher dimensions"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7463-6728","authenticated-orcid":false,"given":"Natan","family":"Rubin","sequence":"first","affiliation":[{"name":"Ben-Gurion University of the Negev, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300000225"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-010-9323-7"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574042"},{"key":"e_1_3_2_1_4_1","first-page":"79","volume-title":"Adv. Appl. Math 29 ( 2001 )","author":"Alon N.","unstructured":"N. Alon, G. Kalai, R. Meshulam, and J. Matou\u0161ek. Transversal numbers for hypergraphs arising in geometry, Adv. Appl. Math 29 ( 2001 ), 79-101."},{"key":"e_1_3_2_1_5_1","volume":"55","author":"Alon N.","unstructured":"N. Alon, H. Kaplan, G. Nivasch, M. Sharir and S. Smorodinsky, Weak \u03f5-nets and interval chains, J. ACM 55 ( 6 ) ( 2008 ), Article 28.","journal-title":"Weak \u03f5-nets and interval chains, J. ACM"},{"key":"e_1_3_2_1_6_1","first-page":"103","volume-title":"Adv. Math. 96 ( 1 ) ( 1992 )","author":"Alon N.","unstructured":"N. Alon and D. J. Kleitman, Piercing convex sets and the Hadwiger-Debrunner (p,q)-problem, Adv. Math. 96 ( 1 ) ( 1992 ), 103-112."},{"key":"e_1_3_2_1_7_1","first-page":"3248","volume":"39","author":"Aronov B.","unstructured":"B. Aronov, E. Ezra and M. Sharir, Small-size epsilon nets for axis-parallel rectangles and boxes, SIAM J. Comput. 39 ( 2010 ), 3248-3282.","journal-title":"Comput."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(94)90027-2"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-003-0854-z"},{"key":"e_1_3_2_1_10_1","first-page":"1","volume":"16","author":"Balogh J.","unstructured":"J. Balogh and J. Solymosi, On the number of points in general position in the plane, Disc. Analysis 16 ( 2018 ), 1-20.","journal-title":"Analysis"},{"key":"e_1_3_2_1_11_1","first-page":"175","volume":"10","author":"B\u00e1r\u00e1ny I.","unstructured":"I. B\u00e1r\u00e1ny, Z. F\u00fcredi and L. Lov\u00e1sz, On the number of halving planes, Discrete Comput. Geom. 10 ( 2 ) ( 1990 ), 175-183.","journal-title":"On the number of halving planes, Discrete Comput. Geom."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.4171\/JEMS\/516"},{"key":"e_1_3_2_1_13_1","first-page":"463","volume":"14","author":"Br\u00f6nnimann H.","unstructured":"H. Br\u00f6nnimann and M. T. Goodrich, Almost optimal set covers in finite VCdimension, Discrete Comput. Geom. 14 ( 4 ) ( 1995 ), 463-479.","journal-title":"Geom."},{"key":"e_1_3_2_1_14_1","first-page":"199","volume":"182","author":"Bukh B.","unstructured":"B. Bukh, J. Matousek, and G. Nivasch, Lower bounds for weak epsilon-nets and stair-convexity, Israel J. Math. 182 ( 2011 ), 199-228.","journal-title":"Math."},{"key":"e_1_3_2_1_15_1","first-page":"83","volume":"18","author":"Bradford Ph. G.","unstructured":"Ph. G. Bradford and V. Capoyleas, Weak epsilon-nets for points on a hypersphere, Discrete Comput. Geom. 18 ( 1 ) ( 1997 ), 83-91.","journal-title":"Geom."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-012-9410-z"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511626371"},{"key":"e_1_3_2_1_18_1","volume-title":"Also in Proc. 25th ACM Sympos. Theory Comput. (STOC)","author":"Chazelle B.","year":"1993","unstructured":"B. Chazelle, H. Edelsbrunner, M. Grigni, L. J. Guibas, M. Sharir and E. Welzl, Improved bounds on weak epsilon-nets for convex sets, Discrete Comput. Geom. 13 ( 1995 ), 1-15. Also in Proc. 25th ACM Sympos. Theory Comput. (STOC), 1993."},{"key":"e_1_3_2_1_19_1","first-page":"229","volume-title":"Combinatorica 10 ( 3 ) ( 1990 )","author":"Chazelle B.","unstructured":"B. Chazelle and J. Friedman, A deterministic view of random sampling and its use in geometry, Combinatorica 10 ( 3 ) ( 1990 ), 229-249."},{"key":"e_1_3_2_1_20_1","first-page":"430","volume":"37","author":"Clarkson K. L.","unstructured":"K. L. Clarkson and K. R. Varadarajan, Improved approximation algorithms for geometric set cover, Discrete Comput. Geom. 37 ( 1 ) ( 2007 ), 430-58.","journal-title":"Geom."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/77635.77639"},{"key":"e_1_3_2_1_22_1","first-page":"181","volume":"3","author":"Erd\u0151s P.","unstructured":"P. Erd\u0151s and M. Simonovits, Supersaturated graphs and hypergraphs, Combinatorica 3 ( 2 ) ( 1983 ), 181-192.","journal-title":"Supersaturated graphs and hypergraphs, Combinatorica"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(93)90082-J"},{"key":"e_1_3_2_1_24_1","first-page":"358","volume":"95","author":"Even G.","unstructured":"G. Even, D. Rawitz and S. Shahar, Hitting sets when the VC-dimension is small, Inf. Process. Lett. 95 ( 2 ) ( 2005 ), 358-362.","journal-title":"Hitting sets when the VC-dimension is small, Inf. Process. Lett."},{"key":"e_1_3_2_1_25_1","first-page":"49","volume":"671","author":"Fox J.","unstructured":"J. Fox, M. Gromov, V. Laforgue, A. Naor, and J. Pach, Overlap properties of geometric expanders, Journal f\u00fcr die reine und angewandte Mathematik (Crelle's Journal) 671 ( 2012 ), 49-83.","journal-title":"Overlap properties of geometric expanders, Journal f\u00fcr die reine und angewandte Mathematik (Crelle's Journal)"},{"key":"e_1_3_2_1_26_1","first-page":"2199","volume":"45","author":"Fox J.","unstructured":"J. Fox, J. Pach, and A. Suk, A polynomial regularity lemma for semialgebraic hypergraphs and Its applications in geometry and property testing, SIAM J. Comput. 45 ( 6 ) ( 2016 ), 2199-2223.","journal-title":"Comput."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF03041066"},{"key":"e_1_3_2_1_28_1","first-page":"309","volume-title":"Archiv der Mathematik, 8 ( 4 ) ( 1957 )","author":"Hadwiger H.","unstructured":"H. Hadwiger and H. Debrunner, \u00dcber eine variante zum Hellyschen satz, Archiv der Mathematik, 8 ( 4 ) ( 1957 ), 309-313."},{"key":"e_1_3_2_1_29_1","first-page":"127","volume-title":"Discrete Comput. Geom. 2 ( 1987 )","author":"Haussler D.","unstructured":"D. Haussler and E. Welzl, \u03b5-nets and simplex range queries, Discrete Comput. Geom. 2 ( 1987 ), 127-151."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"crossref","unstructured":"A. Holmsen Large cliques in hypergraphs with forbidden substructures to appear in Discrete Comput. Geom. ( 2020 ).","DOI":"10.1007\/s00493-019-4169-y"},{"key":"e_1_3_2_1_31_1","volume-title":"Radon numbers and the fractional Helly theorem, arXiv","author":"Holmsen A.","year":"1903","unstructured":"A. Holmsen, D.-G. Lee, Radon numbers and the fractional Helly theorem, arXiv: 1903.01068, priprint, 2019."},{"key":"e_1_3_2_1_32_1","first-page":"1155","volume-title":"Proc. 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA 2020 )","author":"Keller C.","unstructured":"C. Keller and S. Smorodinsky, A New Lower Bound on Hadwiger-Debrunner Numbers in the Plane, in Proc. 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA 2020 ), pp. 1155-1169."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-018-1685-1"},{"key":"e_1_3_2_1_34_1","first-page":"163","volume":"7","author":"Kolm\u00f3s J.","unstructured":"J. Kolm\u00f3s, J. Pach and G. J. Woeginger, Almost tight bounds for epsilon-Nets, Discrete Comput. Geom. 7 ( 1992 ), 163-173.","journal-title":"Almost tight bounds for epsilon-Nets, Discrete Comput. Geom."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58043-7_4"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/581165"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02293051"},{"key":"e_1_3_2_1_38_1","first-page":"195","volume":"32","author":"Matousek J.","unstructured":"J. Matousek and U. Wagner, New constructions of weak epsilon-nets, Discrete Comput. Geom. 32 ( 2 ) ( 2004 ), 195-206.","journal-title":"New constructions of weak epsilon-nets, Discrete Comput. Geom."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/98524.98530"},{"key":"e_1_3_2_1_40_1","volume-title":"Chap. 47 in Handbook of Discrete and Computational Geometry, J.E. Goodman, J. O'Rourke, and C","author":"Mustafa N. H.","year":"2017","unstructured":"N. H. Mustafa and K. Varadarajan, Epsilon-approximations and epsilon-nets, Chap. 47 in Handbook of Discrete and Computational Geometry, J.E. Goodman, J. O'Rourke, and C. D. T\u00f3th (ed.), 3rd edition, CRC Press, Boca Raton, FL, 2017.","edition":"3"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2008.07.003"},{"key":"e_1_3_2_1_42_1","first-page":"645","volume":"26","author":"Pach J.","unstructured":"J. Pach and G. Tardos, Tight lower bounds for the size of epsilon-nets, J. AMS 26 ( 2013 ), 645-658.","journal-title":"AMS"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00030"},{"key":"e_1_3_2_1_44_1","volume-title":"Stronger bounds for weak Epsilon-nets in higher dimensions, https:\/\/arxiv.org\/abs\/2104.12654","author":"Rubin N.","year":"2021","unstructured":"N. Rubin, Stronger bounds for weak Epsilon-nets in higher dimensions, https:\/\/arxiv.org\/abs\/2104.12654, 2021."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574384"},{"key":"e_1_3_2_1_46_1","volume-title":"Davenport-Schinzel Sequences and Their Geometric Applications","author":"Sharir M.","year":"1995","unstructured":"M. Sharir and P. K. Agarwal, Davenport-Schinzel Sequences and Their Geometric Applications, Cambridge University Press, New York, 1995."},{"key":"e_1_3_2_1_47_1","first-page":"3","volume":"3","author":"Szemer\u00e9di E.","year":"1983","unstructured":"E. Szemer\u00e9di and W. T. Trotter, Extremal problems in discrete geometry, Combinatorica 3 ( 3-4) ( 1983 ), 381-392.","journal-title":"Extremal problems in discrete geometry, Combinatorica"},{"key":"e_1_3_2_1_48_1","first-page":"264","volume":"16","author":"Vapnik V. N.","unstructured":"V. N. Vapnik and A. Y. Chervonenkis, On the uniform convergence of relative frequencies of events to their probabilities, Theory Prob. Appls. 16 ( 1971 ), 264-280.","journal-title":"Appls."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(92)90028-S"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Virtual Italy","acronym":"STOC '21"},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451062","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451062","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:53Z","timestamp":1750195493000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451062"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":49,"alternative-id":["10.1145\/3406325.3451062","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451062","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}