{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T02:41:35Z","timestamp":1770777695774,"version":"3.50.0"},"reference-count":69,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,6,21]],"date-time":"2024-06-21T00:00:00Z","timestamp":1718928000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-1814026, CCF-2224271"],"award-info":[{"award-number":["CCF-1814026, CCF-2224271"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2024,7,31]]},"abstract":"<jats:p>\n            We revisit Hopcroft\u2019s problem and related fundamental problems about geometric range searching. Given\n            <jats:italic>n<\/jats:italic>\n            points and\n            <jats:italic>n<\/jats:italic>\n            lines in the plane, we show how to count the number of point-line incidence pairs or the number of point-above-line pairs in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>4\/3<\/jats:sup>\n            ) time, which matches the conjectured lower bound and improves the best previous time bound of\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(n^{4\/3}2^{O(\\log ^*n)}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            obtained almost 30 years ago by Matou\u0161ek\u00a0[\n            <jats:xref ref-type=\"bibr\">58<\/jats:xref>\n            ].\n          <\/jats:p>\n          <jats:p>We describe two interesting and different ways to achieve the result: The first is randomized and uses a new two-dimensional version of fractional cascading for arrangements of lines; the second is deterministic and uses decision trees in a manner inspired by the sorting technique of Fredman [42]. The second approach extends to any constant dimension.<\/jats:p>\n          <jats:p>\n            Many consequences follow from these new ideas: For example, we obtain an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>4\/3<\/jats:sup>\n            )-time algorithm for line segment intersection counting in the plane,\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>4\/3<\/jats:sup>\n            )-time randomized algorithms for distance selection in the plane and bichromatic closest pair and Euclidean minimum spanning tree in three or four dimensions, and a randomized data structure for halfplane range counting in the plane with\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>4\/3<\/jats:sup>\n            ) preprocessing time and space and\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(O(n^{1\/3})\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            query time.\n          <\/jats:p>","DOI":"10.1145\/3591357","type":"journal-article","created":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T13:31:01Z","timestamp":1681219861000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Hopcroft\u2019s Problem, Log* Shaving, Two-dimensional Fractional Cascading, and Decision Trees"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8093-0675","authenticated-orcid":false,"given":"Timothy M.","family":"Chan","sequence":"first","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0844-9457","authenticated-orcid":false,"given":"Da Wei","family":"Zheng","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, USA"}]}],"member":"320","published-online":{"date-parts":[[2024,6,21]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00072"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187809"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01187037"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574698"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/223\/03131"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044482537-7\/50003-6"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9036-3"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-7091-9459-1_17"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-33099-2"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40273-9_10"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796260321"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009478"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195901000511"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970343912X"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-012-9410-z"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.51"},{"key":"e_1_3_2_19_2","unstructured":"Timothy M. Chan Qizheng He and Yakov Nekrich. 2020. Further results on colored range searching. Retrieved from https:\/\/arXiv:2003.11604."},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1066506"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-016-9784-4"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90025-5"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-1989-1001852-0"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189314"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02770864"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01182771"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01955043"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122778"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840440"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840441"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.07.003"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187879"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1137\/0217052"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187740"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187784"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1137\/0215024"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1137\/0222031"},{"key":"e_1_3_2_39_2","first-page":"85","volume-title":"Proceedings of the 7th Canadian Conference on Computational Geometry (CCCG\u201995)","author":"Erickson Jeff","year":"1995","unstructured":"Jeff Erickson. 1995. On the relative complexities of some geometric problems. In Proceedings of the 7th Canadian Conference on Computational Geometry (CCCG\u201995). 85\u201390. Retrieved from http:\/\/jeffe.cs.illinois.edu\/pubs\/relative.html."},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02712875"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797315410"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/360680.360691"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90078-5"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1137\/0205006"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00022-2"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187696"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/3185378"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-19487-8_7"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/3285953"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794268649"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1979.15"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1137\/0212002"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.06.032"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90084-B"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1109\/12.376174"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02293051"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90177-J"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(92)90006-E"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02573972"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1018"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1964-0161339-9"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1145\/505241.505243"},{"key":"e_1_3_2_63_2","doi-asserted-by":"publisher","DOI":"10.1145\/304893.304993"},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12172"},{"key":"e_1_3_2_65_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00201-9"},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579194"},{"key":"e_1_3_2_67_2","volume-title":"Differential and Combinatorial Topology","author":"Thom Ren\u00e9","year":"1965","unstructured":"Ren\u00e9 Thom. 1965. Sur l\u2019homologie des vari\u00e9t\u00e9s alg\u00e9briques re\u00e9lles. In Differential and Combinatorial Topology, S. S. Cairns (Ed.). Princeton University Press, Princeton, NJ."},{"key":"e_1_3_2_68_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2020.69"},{"key":"e_1_3_2_69_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SWAT.2022.32"},{"key":"e_1_3_2_70_2","doi-asserted-by":"publisher","DOI":"10.1137\/0211059"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3591357","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3591357","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:21Z","timestamp":1750178841000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3591357"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,21]]},"references-count":69,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,7,31]]}},"alternative-id":["10.1145\/3591357"],"URL":"https:\/\/doi.org\/10.1145\/3591357","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,21]]},"assertion":[{"value":"2022-06-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-04-04","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}