TY - GEN

T1 - Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems

AU - Agarwal, Pankaj K.

AU - Aronov, Boris

AU - Ezra, Esther

AU - Katz, Matthew J.

AU - Sharir, Micha

N1 - Funding Information:
Funding Pankaj K. Agarwal: Work partially supported by NSF grants IIS-18-14493 and CCF-20-07556. Boris Aronov: Work partially supported by NSF Grants CCF-15-40656 and CCF-20-08551, and by Grant 2014/170 from the US-Israel Binational Science Foundation. Esther Ezra: Work partially supported by NSF CAREER under Grant CCF:AF-1553354 and by Grant 824/17 from the Israel Science Foundation. Matthew J. Katz: Work partially supported by Grant 1884/16 from the Israel Science Foundation, and by Grant 2019715/CCF-20-08551 from the US-Israel Binational Science Foundation/US National Science Foundation. Micha Sharir: Work partially supported by Grant 260/18 from the Israel Science Foundation.
Publisher Copyright:
© Pankaj K. Agarwal, Boris Aronov, Esther Ezra, Matthew J. Katz, and Micha Sharir; licensed under Creative Commons License CC-BY 4.0

PY - 2022/6/1

Y1 - 2022/6/1

N2 - Let T be a set of n planar semi-algebraic regions in R3 of constant complexity (e.g., triangles, disks), which we call plates. We wish to preprocess T into a data structure so that for a query object ?, which is also a plate, we can quickly answer various intersection queries, such as detecting whether ? intersects any plate of T, reporting all the plates intersected by ?, or counting them. We focus on two simpler cases of this general setting: (i) the input objects are plates and the query objects are constant-degree algebraic arcs in R3 (arcs, for short), or (ii) the input objects are arcs and the query objects are plates in R3. These interesting special cases form the building blocks for the general case. By combining the polynomial-partitioning technique with additional tools from real algebraic geometry, we obtain a variety of results with different storage and query-time bounds, depending on the complexity of the input and query objects. For example, if T is a set of plates and the query objects are arcs, we obtain a data structure that uses O*(n4/3) storage (where the O*(·) notation hides subpolynomial factors) and answers an intersection query in O*(n2/3) time. Alternatively, by increasing the storage to O*(n3/2), the query time can be decreased to O*(n?), where ? = (2t - 3)/3(t - 1) < 2/3 and t = 3 is the number of parameters needed to represent the query arcs.

AB - Let T be a set of n planar semi-algebraic regions in R3 of constant complexity (e.g., triangles, disks), which we call plates. We wish to preprocess T into a data structure so that for a query object ?, which is also a plate, we can quickly answer various intersection queries, such as detecting whether ? intersects any plate of T, reporting all the plates intersected by ?, or counting them. We focus on two simpler cases of this general setting: (i) the input objects are plates and the query objects are constant-degree algebraic arcs in R3 (arcs, for short), or (ii) the input objects are arcs and the query objects are plates in R3. These interesting special cases form the building blocks for the general case. By combining the polynomial-partitioning technique with additional tools from real algebraic geometry, we obtain a variety of results with different storage and query-time bounds, depending on the complexity of the input and query objects. For example, if T is a set of plates and the query objects are arcs, we obtain a data structure that uses O*(n4/3) storage (where the O*(·) notation hides subpolynomial factors) and answers an intersection query in O*(n2/3) time. Alternatively, by increasing the storage to O*(n3/2), the query time can be decreased to O*(n?), where ? = (2t - 3)/3(t - 1) < 2/3 and t = 3 is the number of parameters needed to represent the query arcs.

KW - Collision detection

KW - Cylindrical algebraic decomposition

KW - Intersection searching

KW - Multilevel partition trees

KW - Point-enclosure queries

KW - Polynomial partitions

KW - Ray-shooting queries

KW - Semi-algebraic range searching

UR - http://www.scopus.com/inward/record.url?scp=85134335799&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85134335799&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.SoCG.2022.4

DO - 10.4230/LIPIcs.SoCG.2022.4

M3 - Conference contribution

AN - SCOPUS:85134335799

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 38th International Symposium on Computational Geometry, SoCG 2022

A2 - Goaoc, Xavier

A2 - Kerber, Michael

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 38th International Symposium on Computational Geometry, SoCG 2022

Y2 - 7 June 2022 through 10 June 2022

ER -