The beta version of DROPS 2 is now publicly available! Check this page out at DROPS 2 now!


License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2022.4
URN: urn:nbn:de:0030-drops-160126
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16012/
Go to the corresponding LIPIcs Volume Portal

Agarwal, Pankaj K. ; Aronov, Boris ; Ezra, Esther ; Katz, Matthew J. ; Sharir, Micha

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

pdf-format:
LIPIcs-SoCG-2022-4.pdf (0.7 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{agarwal_et_al:LIPIcs.SoCG.2022.4,
  author =	{Agarwal, Pankaj K. and Aronov, Boris and Ezra, Esther and Katz, Matthew J. and Sharir, Micha},
  title =	{{Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{4:1--4:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16012},
  URN =		{urn:nbn:de:0030-drops-160126},
  doi =		{10.4230/LIPIcs.SoCG.2022.4},
  annote =	{Keywords: Intersection searching, Semi-algebraic range searching, Point-enclosure queries, Ray-shooting queries, Polynomial partitions, Cylindrical algebraic decomposition, Multi-level partition trees, Collision detection}
}

Keywords: Intersection searching, Semi-algebraic range searching, Point-enclosure queries, Ray-shooting queries, Polynomial partitions, Cylindrical algebraic decomposition, Multi-level partition trees, Collision detection
Collection: 38th International Symposium on Computational Geometry (SoCG 2022)
Issue Date: 2022
Date of publication: 01.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI