{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:16:36Z","timestamp":1750220196944,"version":"3.41.0"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2022,10,27]],"date-time":"2022-10-27T00:00:00Z","timestamp":1666828800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Unions Horizon 2020","award":["678765"],"award-info":[{"award-number":["678765"]}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["2891\/21"],"award-info":[{"award-number":["2891\/21"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2022,10,31]]},"abstract":"<jats:p>\n            We show that for any finite point set\n            <jats:italic>P<\/jats:italic>\n            in the plane and\n            <jats:italic>\u03f5 &gt; 0<\/jats:italic>\n            there exist\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( O(\\tfrac{1}{{\\epsilon }^{3\/2+\\gamma }}) \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            points in \u211d\n            <jats:sup>2<\/jats:sup>\n            , for arbitrary small \u03b3 &gt; 0, that pierce every convex set\n            <jats:italic>K<\/jats:italic>\n            with |\n            <jats:italic>K<\/jats:italic>\n            \u2229\n            <jats:italic>P<\/jats:italic>\n            |&gt; \u03f5 |\n            <jats:italic>P<\/jats:italic>\n            |. This is the first improvement of the bound of\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( O(\\tfrac{1}{{\\epsilon }^2}) \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            that was obtained in 1992 by Alon, B\u00e1r\u00e1ny, F\u00fcredi, and Kleitman for general point sets in the plane.\n          <\/jats:p>","DOI":"10.1145\/3555985","type":"journal-article","created":{"date-parts":[[2022,8,10]],"date-time":"2022-08-10T12:20:09Z","timestamp":1660134009000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["An Improved Bound for Weak Epsilon-nets in the Plane"],"prefix":"10.1145","volume":"69","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7463-6728","authenticated-orcid":false,"given":"Natan","family":"Rubin","sequence":"first","affiliation":[{"name":"Department of Computer Science, Ben-Gurion University of The Negev, Beer-Sheva, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,10,27]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574015"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300000225"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.5555\/3115956.3116028"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574042"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-8858(02)00003-9"},{"key":"e_1_3_2_7_2","first-page":"175","volume":"10","author":"Alon N.","year":"2008","unstructured":"N. Alon, H. Kaplan, G. Nivasch, M. Sharir, and S. Smorodinsky. 2008. Weak \\( {\\epsilon } \\) -nets and interval chains. Combinatorica 10 (1990), 175\u2013183.","journal-title":"Combinatorica"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(92)90052-M"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/090762968"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189317"},{"key":"e_1_3_2_11_2","first-page":"669","article-title":"Independent sets in hypergraphs.","volume":"28","author":"Balogh J.","year":"2015","unstructured":"J. Balogh, R. Morris, and W. Samotij. 2015. Independent sets in hypergraphs. J. AMS 28 (2015), 669\u2013709.","journal-title":"J. AMS"},{"key":"e_1_3_2_12_2","first-page":"1","article-title":"On the number of points in general position in the plane.","volume":"16","author":"Balogh J.","year":"2018","unstructured":"J. Balogh and J. Solymosi. 2018. On the number of points in general position in the plane. Disc. Anal. 16 (2018), 1\u201320.","journal-title":"Disc. Anal."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-007-1331-x"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02570718"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-011-0029-1"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009309"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.5555\/3116278.3116568"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187743"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511626371"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574025"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122778"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009449"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187783"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-006-1273-8"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.03.010"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF03041066"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58043-7_8"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01898794"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574383"},{"key":"e_1_3_2_30_2","volume-title":"Proceedings of the 35th International Symposium Computational Geometry (SOCG\u201919)","author":"Har-Peled S.","year":"2019","unstructured":"S. Har-Peled and M. Jones. 2019. Journey to the center of the point set. In Proceedings of the 35th International Symposium Computational Geometry (SOCG\u201919). Article 41."},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187876"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.70"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-018-1685-1"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187833"},{"key":"e_1_3_2_36_2","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1007\/978-3-642-58043-7_4","volume-title":"New Trends in Discrete Computational Geometry","author":"Matou\u0161ek. J.","year":"1993","unstructured":"J. Matou\u0161ek. 1993. Epsilon-nets and computational geometry. In New Trends in Discrete Computational Geometry, J. Pach (Ed.). Springer, Berlin, 69\u201389."},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.5555\/581165"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02293051"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.5555\/3115953.3116001"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/98524.98530"},{"key":"e_1_3_2_41_2","author":"Mulmuley K.","year":"1993","unstructured":"K. Mulmuley. 1993. Computational Geometry: An Introduction through Randomized Algorithms, (1st ed.). Prentice Hall.","journal-title":"Computational Geometry: An Introduction through Randomized Algorithms"},{"key":"e_1_3_2_42_2","first-page":"84","volume-title":"Comput. Geom.","volume":"40","author":"Mustafa N. H.","year":"2008","unstructured":"N. H. Mustafa and S. Ray. 2008. Weak \\( \\varepsilon \\) -nets have a basis of size \\( O(1\/\\varepsilon \\log 1\/\\varepsilon) \\) . Comput. Geom. 40 (2008), 84\u201391."},{"key":"e_1_3_2_43_2","volume-title":"Handbook of Discrete and Computational Geometry","author":"Mustafa N. H.","year":"2017","unstructured":"N. H. Mustafa and K. Varadarajan. 2017. Epsilon-approximations and epsilon-nets. In Handbook of Discrete and Computational Geometry, J. E. Goodman, J. O\u2019Rourke, and C. D. T\u00f3th (Eds.), (3rd ed.). CRC Press, Boca Raton, FL."},{"key":"e_1_3_2_44_2","first-page":"645","article-title":"Tight lower bounds for the size of epsilon-nets.","volume":"26","author":"Pach J.","year":"2013","unstructured":"J. Pach and G. Tardos. 2013. Tight lower bounds for the size of epsilon-nets. J. AMS 26 (2013), 645\u2013658.","journal-title":"J. AMS"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451062"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-014-0562-8"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574384"},{"key":"e_1_3_2_48_2","author":"Sharir M.","year":"1995","unstructured":"M. Sharir and P. K. Agarwal. 1995. Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, New York, NY.","journal-title":"Davenport-Schinzel Sequences and Their Geometric Applications"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579194"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1137\/1116025"},{"key":"e_1_3_2_51_2","article-title":"Helly-type theorems and geometric transversals. In","author":"Wenger R.","year":"2004","unstructured":"R. Wenger. 2004. Helly-type theorems and geometric transversals. In Handbook of Discrete and Computational Geometry, (2nd Ed.), J. E. Goodman and J. O\u2019Rourke (Eds.). Chapman & Hall\/CRC Press, New York, NY.","journal-title":"Handbook of Discrete and Computational Geometry"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3555985","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3555985","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:02:41Z","timestamp":1750186961000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3555985"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,27]]},"references-count":50,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,10,31]]}},"alternative-id":["10.1145\/3555985"],"URL":"https:\/\/doi.org\/10.1145\/3555985","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2022,10,27]]},"assertion":[{"value":"2020-01-02","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-05-31","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}