{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:34:59Z","timestamp":1750307699028,"version":"3.41.0"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2008,12,1]],"date-time":"2008-12-01T00:00:00Z","timestamp":1228089600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-05-14079"],"award-info":[{"award-number":["CCF-05-14079"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["975\/06155\/05"],"award-info":[{"award-number":["975\/06155\/05"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2008,12]]},"abstract":"<jats:p>\n            We construct weak \u03b5-nets of almost linear size for\ncertain types of point sets. Specifically, for planar point sets in\nconvex position we construct weak 1\/r-nets of size O(r\u03b1(r)),\nwhere \u03b1(r) denotes the inverse Ackermann function. For point\nsets along the moment curve in \u211d\n            <jats:sup>d<\/jats:sup>\n            we construct\nweak 1\/r-nets of size r \u00b7 2\n            <jats:sup>poly(\u03b1(r))<\/jats:sup>\n            ,\nwhere the degree of the polynomial in the exponent depends\n(quadratically) on d.\n          <\/jats:p>\n          <jats:p>\n            Our constructions result from a reduction to a new problem,\nwhich we call stabbing interval chains with j-tuples. Given the\nrange of integers N = [1, n], an interval chain of length k is a\nsequence of k consecutive, disjoint, nonempty intervals contained\nin N. A j-tuple $\\bar{P}$ = (p1,\u2026,pj) is said to stab an\ninterval chain C = I\n            <jats:sub>1<\/jats:sub>\n            \u2026I\n            <jats:sub>k<\/jats:sub>\n            if each\np\n            <jats:sub>i<\/jats:sub>\n            falls on a different interval of C. The problem is to\nconstruct a small-size family Z of j-tuples that stabs all\nk-interval chains in N.\n          <\/jats:p>\n          <jats:p>\n            Let z\n            <jats:sup>(j)<\/jats:sup>\n            <jats:sub>k<\/jats:sub>\n            (n) denote the minimum size of\nsuch a family Z. We derive almost-tight upper and lower bounds for\nz\n            <jats:sup>(j)<\/jats:sup>\n            <jats:sub>k<\/jats:sub>\n            (n) for every fixed j; our bounds\ninvolve functions \u03b1\n            <jats:sub>m<\/jats:sub>\n            (n) of the inverse Ackermann\nhierarchy. Specifically, we show that for j = 3 we have\nz\n            <jats:sup>(3)<\/jats:sup>\n            <jats:sub>k<\/jats:sub>\n            (n) =\n\u0398(n\u03b1\n            <jats:sub>$\\lfloor$k\/2$\\rfloor$<\/jats:sub>\n            (n)) for all k \u2265\n6. For each j\u22654, we construct a pair of functions\nP\u02b9\n            <jats:sub>j<\/jats:sub>\n            (m), Q\u02b9\n            <jats:sub>j<\/jats:sub>\n            (m), almost equal\nasymptotically, such that z\n            <jats:sup>(j)<\/jats:sup>\n            <jats:sub>P\u02b9<\/jats:sub>\n            j(m)(n)\n= O(n\u03b1\n            <jats:sub>m<\/jats:sub>\n            (n)) and\nz\n            <jats:sup>(j)<\/jats:sup>\n            <jats:sub>Q\u02b9<\/jats:sub>\n            j(m)(n) =\n\u03a9(n\u03b1\n            <jats:sub>m<\/jats:sub>\n            (n)).\n          <\/jats:p>","DOI":"10.1145\/1455248.1455252","type":"journal-article","created":{"date-parts":[[2008,12,17]],"date-time":"2008-12-17T13:25:20Z","timestamp":1229520320000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Weak \u03b5-nets and interval chains"],"prefix":"10.1145","volume":"55","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[{"name":"Tel-Aviv University, Tel-Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haim","family":"Kaplan","sequence":"additional","affiliation":[{"name":"Tel-Aviv University, Tel-Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gabriel","family":"Nivasch","sequence":"additional","affiliation":[{"name":"Tel-Aviv University, Tel-Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha","family":"Sharir","sequence":"additional","affiliation":[{"name":"Tel-Aviv University, Tel-Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shakhar","family":"Smorodinsky","sequence":"additional","affiliation":[{"name":"Ben-Gurion University, Be'er Sheva, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,12,17]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300000225"},{"key":"e_1_2_2_2_1","volume-title":"Tech. Rep. 71\/87","author":"Alon N.","year":"1987","unstructured":"Alon , N. , and Schieber , B . 1987 . Optimal preprocessing for answering on-line product queries. Tech. Rep. 71\/87 , The Moise and Frida Eskenasy Institute of Computer Science, Tel-Aviv University, Tel-Aviv, Israel . Alon, N., and Schieber, B. 1987. Optimal preprocessing for answering on-line product queries. Tech. Rep. 71\/87, The Moise and Frida Eskenasy Institute of Computer Science, Tel-Aviv University, Tel-Aviv, Israel."},{"volume-title":"Proceedings of the 17th Canadian Conference on Computational Geometry. 52--56","author":"Aronov B.","key":"e_1_2_2_3_1","unstructured":"Aronov , B. , Aurenhammer , F. , Hurtado , F. , Langerman , S. , Rappaport , D. , Smorodinsky , S. , and Seara , C . 2005. Small weak epsilon nets . In Proceedings of the 17th Canadian Conference on Computational Geometry. 52--56 . Aronov, B., Aurenhammer, F., Hurtado, F., Langerman, S., Rappaport, D., Smorodinsky, S., and Seara, C. 2005. Small weak epsilon nets. In Proceedings of the 17th Canadian Conference on Computational Geometry. 52--56."},{"volume-title":"Proceedings of the 18th Canadian Conference on Computational Geometry. 47--50","author":"Babazadeh M.","key":"e_1_2_2_4_1","unstructured":"Babazadeh , M. , and Zarrabi-Zadeh , H . 2006. Small weak epsilon-nets in three dimensions . In Proceedings of the 18th Canadian Conference on Computational Geometry. 47--50 . Babazadeh, M., and Zarrabi-Zadeh, H. 2006. Small weak epsilon-nets in three dimensions. In Proceedings of the 18th Canadian Conference on Computational Geometry. 47--50."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009309"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90015-7"},{"key":"e_1_2_2_7_1","unstructured":"Chazelle B. Edelsbrunner H. Eppstein D. Grigni M. Guibas L. Sharir M. and Welzl E. 1995a. Algorithms for weak &epsis;-nets. Unpublished manuscript. Available at http:\/\/citeseer.ist.psu.edu\/24190.html.  Chazelle B. Edelsbrunner H. Eppstein D. Grigni M. Guibas L. Sharir M. and Welzl E. 1995a. Algorithms for weak &epsis;-nets. Unpublished manuscript. Available at http:\/\/citeseer.ist.psu.edu\/24190.html."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574025"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195991000049"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2003.09.020"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808731"},{"volume-title":"Lectures on Discrete Geometry","author":"Matou\u0161ek J.","key":"e_1_2_2_12_1","unstructured":"Matou\u0161ek , J. 2002a. Lectures on Discrete Geometry . Springer-Verlag , New York . Matou\u0161ek, J. 2002a. Lectures on Discrete Geometry. Springer-Verlag, New York."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-001-0090-3"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-004-1116-4"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247069.1247113"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215351"},{"key":"e_1_2_2_17_1","unstructured":"Seidel R. 2006. Understanding the inverse ackermann function. PDF presentation. Available at http:\/\/cgi.di.uoa.gr\/~ewcg06\/invited\/Seidel.pdf.  Seidel R. 2006. Understanding the inverse ackermann function. PDF presentation. Available at http:\/\/cgi.di.uoa.gr\/~ewcg06\/invited\/Seidel.pdf."},{"key":"e_1_2_2_18_1","unstructured":"Sharir M. and Agarwal P. K. 1995. Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press Cambridge UK.   Sharir M. and Agarwal P. K. 1995. Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press Cambridge UK."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01191208"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802185"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1455248.1455252","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1455248.1455252","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:30:00Z","timestamp":1750253400000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1455248.1455252"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,12]]},"references-count":20,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2008,12]]}},"alternative-id":["10.1145\/1455248.1455252"],"URL":"https:\/\/doi.org\/10.1145\/1455248.1455252","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2008,12]]},"assertion":[{"value":"2007-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-12-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}