{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T14:30:40Z","timestamp":1753885840446,"version":"3.41.2"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2025,3,11]],"date-time":"2025-03-11T00:00:00Z","timestamp":1741651200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"abstract":"\n Let\n \n \\(\\mathcal{T}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n be a set of\n \n \\(n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n flat (planar) semi-algebraic regions in\n \n \\(\\mathbb{R}^{3}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n of constant complexity (e.g., triangles, disks), which we call\n plates<\/jats:italic>\n . We wish to preprocess\n \n \\(\\mathcal{T}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n into a data structure so that for a query object\n \n \\(\\gamma\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , which is also a plate, we can quickly answer various\n intersection queries<\/jats:italic>\n , such as detecting whether\n \n \\(\\gamma\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n intersects any plate of\n \n \\(\\mathcal{T}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , reporting all the plates intersected by\n \n \\(\\gamma\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , or counting them. We also consider two simpler cases of this general setting: (i) the input objects are plates and the query objects are constant-degree parametrized algebraic arcs in\n \n \\(\\mathbb{R}^{3}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n (\n arcs<\/jats:italic>\n , for short), or (ii) the input objects are arcs and the query objects are plates in\n \n \\(\\mathbb{R}^{3}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . Besides being interesting in their own right, the data structures for these two special cases form the building blocks for handling the general case.\n <\/jats:p>\n \n By combining the polynomial-partitioning technique with additional tools from real algebraic geometry, we present many different data structures for intersection queries, which also provide trade-offs between their size and query time. For example, if\n \n \\(\\mathcal{T}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is a set of plates and the query objects are algebraic arcs, we obtain a data structure that uses\n \n \\(O^{*}(n^{4\/3})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n storage (where the\n \n \\(O^{*}(\\cdot)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n notation hides factors of the form\n \n \\(n^{\\varepsilon}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , for an arbitrarily small\n \n \\(\\varepsilon>0\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n ) and answers an arc-intersection query in\n \n \\(O^{*}(n^{2\/3})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n time. This result is significant since the exponents do not depend on the specific shape of the input and query objects. We generalize and slightly improve this result: for a parameter\n \n \\(s\\in[n^{4\/3},n^{t_{q}}]\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , where\n \n \\({t_{q}}\\geq 3\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is the number of real parameters needed to specify a query arc, the query time can be decreased to\n \n \\(O^{*}((n\/s^{1\/{t_{q}}})^{\\tfrac{2\/3}{1-1\/{t_{q}}}})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n by increasing the storage to\n \n \\(O^{*}(s)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . Our approach can be extended to many additional intersection-searching problems in three dimensions, even when the input or query objects are not flat.\n <\/jats:p>","DOI":"10.1145\/3721290","type":"journal-article","created":{"date-parts":[[2025,3,11]],"date-time":"2025-03-11T16:51:38Z","timestamp":1741711898000},"update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9439-181X","authenticated-orcid":false,"given":"Pankaj K.","family":"Agarwal","sequence":"first","affiliation":[{"name":"Department of Computer Science, Duke University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3110-4702","authenticated-orcid":false,"given":"Boris","family":"Aronov","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Tandon School of Engineering, New York University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8133-1335","authenticated-orcid":false,"given":"Esther","family":"Ezra","sequence":"additional","affiliation":[{"name":"School of Computer Science, Bar Ilan University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5971-6746","authenticated-orcid":false,"given":"Matthew J.","family":"Katz","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Ben Gurion University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2541-3763","authenticated-orcid":false,"given":"Micha","family":"Sharir","sequence":"additional","affiliation":[{"name":"School of Computer Science, Tel Aviv University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,3,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8396(88)90011-8"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/77269.77273"},{"key":"e_1_2_1_3_1","first-page":"15","volume-title":"Proc. 37th Intl. Sympos. Comput. Geom.","author":"Afshani P.","year":"2021","unstructured":"P. Afshani and P. Cheng. Lower bounds for semialgebraic range searching and stabbing problems. In Proc. 37th Intl. Sympos. Comput. Geom., pages 8:1\u20138:15, 2021."},{"key":"e_1_2_1_4_1","first-page":"14","volume-title":"Proc. 38th Intl. Sympos. Comput. Geom.","author":"Afshani P.","year":"2022","unstructured":"P. Afshani and P. Cheng. On semialgebraic range reporting. In Proc. 38th Intl. Sympos. Comput. Geom., pages 3:1\u20133:14, 2022."},{"key":"e_1_2_1_5_1","first-page":"16","volume-title":"Proc. 39th Intl. Sympos. Comput. Geom.","author":"Afshani P.","year":"2023","unstructured":"P. Afshani and P. Cheng. Lower bounds for intersection reporting among flat objects. In Proc. 39th Intl. Sympos. Comput. Geom., pages 3:1\u20133:16, 2023."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221035"},{"key":"e_1_2_1_7_1","volume-title":"Springer","author":"Agarwal P. K.","year":"2017","unstructured":"P. K. Agarwal. Simplex range searching and its variants: A review. In Journey through Discrete Mathematics: A Tribute to Ji\u0159\u00ed Matou\u0161ek, pages 1\u201330. Springer, Berlin, 2017."},{"key":"e_1_2_1_8_1","first-page":"14","volume-title":"Proc. 38th Intl. Sympos. Comput. Geom.","author":"Agarwal P. K.","year":"2022","unstructured":"P. K. Agarwal, B. Aronov, E. Ezra, M. J. Katz, and M. Sharir. Intersection queries for flat semi-algebraic objects in three dimensions and related problems. In Proc. 38th Intl. Sympos. Comput. Geom., pages 4:1\u20134:14, 2022."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M1268550"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/220279.220308"},{"key":"e_1_2_1_11_1","series-title":"Contemp","first-page":"56","volume-title":"Advances in Discrete and Computational Geometry","author":"Agarwal P. K.","unstructured":"P. K. Agarwal and J. Erickson. Geometric range searching and its relatives. In Advances in Discrete and Computational Geometry, volume 223 of Contemp. Math., pages 1\u201356. AMS Press, Providence, RI, 1999."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574015"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222051"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/120890855"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793244368"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-002-0727-x"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009500"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M1257548"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009436"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-020-00221-z"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-05355-3"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/358841.358850"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-4049(97)00005-4"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-15198-2_9"},{"key":"e_1_2_1_25_1","first-page":"183","volume-title":"Proc. 2nd GI Conf. Automata Theory and Formal Languages","author":"Collins G. E.","year":"1975","unstructured":"G. E. Collins. Quantifier elimination for the elementary theory of real closed fields by cylindrical algebraic decomposition. In Proc. 2nd GI Conf. Automata Theory and Formal Languages, pages 134\u2013183, 1975."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-16721-3"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1370949"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01377182"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90015-0"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90120-7"},{"key":"e_1_2_1_31_1","first-page":"17","volume-title":"Proc. 30th Annual European Symposium on Algorithms","author":"Ezra E.","year":"2022","unstructured":"E. Ezra and M. Sharir. Intersection searching amid tetrahedra in 4-space and efficient continuous collision detection. In Proc. 30th Annual European Symposium on Algorithms, pages 51:1\u201351:17, 2022."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/21M1408245"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1995.1007"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004115000468"},{"key":"e_1_2_1_35_1","volume-title":"Springer","author":"Guth L.","year":"2017","unstructured":"L. Guth. Ruled Surface Theory and Incidence Geometry, pages 449\u2013466. Springer, Berlin, 2017."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2015.181.1.2"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1017"},{"key":"e_1_2_1_38_1","volume-title":"Oxford University Press","author":"Hilton H.","year":"1920","unstructured":"H. Hilton. Plane Algebraic Curves. Oxford University Press, 1920."},{"key":"e_1_2_1_39_1","first-page":"313","volume-title":"Proc. 1st Latin American Sympos. Theoretical Informatics","author":"Kaltofen E.","year":"1992","unstructured":"E. Kaltofen. Polynomial factorization 1987\u20131991. In Proc. 1st Latin American Sympos. Theoretical Informatics, pages 294\u2013313, 1992."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02573972"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/197405.197408"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90177-J"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-015-9701-2"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01298184"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1515\/9781400881802"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793252080"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01187036"},{"key":"e_1_2_1_48_1","first-page":"1112","volume-title":"J. E. Goodman, J. O\u2019Rourke, and C","author":"Pellegrini M.","unstructured":"M. Pellegrini. Ray shooting and lines in space. In J. E. Goodman, J. O\u2019Rourke, and C. D. T\u00f3th, editors, Handbook on Discrete and Computational Geometry, pages 1093\u20131112. CRC Press, Boca Raton, Florida, 3rd edition, 2017."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2009.12.002"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/4333"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-8858(83)90014-3"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.5555\/2007509.2007760"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.5555\/1066372.1646488"},{"key":"e_1_2_1_54_1","unstructured":"R. J. Walker. Algebraic Curves. Dover Books New York 1962."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/22145.22163"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3721290","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3721290","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:57:39Z","timestamp":1750298259000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3721290"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,11]]},"references-count":55,"alternative-id":["10.1145\/3721290"],"URL":"https:\/\/doi.org\/10.1145\/3721290","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2025,3,11]]},"assertion":[{"value":"2023-08-17","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-24","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"3721290"}}