2026-08-17T08:39:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16012 2024-03-06T10:56:44Z ddc:004 open_access

Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems Agarwal, Pankaj K. Aronov, Boris Ezra, Esther Katz, Matthew J. Sharir, Micha Intersection searching Semi-algebraic range searching Point-enclosure queries Ray-shooting queries Polynomial partitions Cylindrical algebraic decomposition Multi-level partition trees Collision detection Let 𝒯 be a set of n planar semi-algebraic regions in ℝ³ of constant complexity (e.g., triangles, disks), which we call plates. We wish to preprocess 𝒯 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 𝒯, 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 ℝ³ (arcs, for short), or (ii) the input objects are arcs and the query objects are plates in ℝ³. 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 𝒯 is a set of plates and the query objects are arcs, we obtain a data structure that uses O^*(n^{4/3}) storage (where the O^*(⋅) notation hides subpolynomial factors) and answers an intersection query in O^*(n^{2/3}) time. Alternatively, by increasing the storage to O^*(n^{3/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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pankaj K. Agarwal and Boris Aronov and Esther Ezra and Matthew J. Katz and Micha Sharir 2022 Is Part Of LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2022.4 urn:nbn:de:0030-drops-160126 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.4 eng https://creativecommons.org/licenses/by/4.0/legalcode