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.2023.3
URN: urn:nbn:de:0030-drops-178536
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17853/
Afshani, Peyman ;
Cheng, Pingan
Lower Bounds for Intersection Reporting Among Flat Objects
Abstract
Recently, Ezra and Sharir [Esther Ezra and Micha Sharir, 2022] showed an O(n^{3/2+σ}) space and O(n^{1/2+σ}) query time data structure for ray shooting among triangles in ℝ³. This improves the upper bound given by the classical S(n)Q(n)⁴ = O(n^{4+σ}) space-time tradeoff for the first time in almost 25 years and in fact lies on the tradeoff curve of S(n)Q(n)³ = O(n^{3+σ}). However, it seems difficult to apply their techniques beyond this specific space and time combination. This pheonomenon appears persistently in almost all recent advances of flat object intersection searching, e.g., line-tetrahedron intersection in ℝ⁴ [Esther Ezra and Micha Sharir, 2022], triangle-triangle intersection in ℝ⁴ [Esther Ezra and Micha Sharir, 2022], or even among flat semialgebraic objects [Agarwal et al., 2022].
We give a timely explanation to this phenomenon from a lower bound perspective. We prove that given a set ? of (d-1)-dimensional simplicies in ℝ^d, any data structure that can report all intersections with a query line in small (n^o(1)) query time must use Ω(n^{2(d-1)-o(1)}) space. This dashes the hope of any significant improvement to the tradeoff curves for small query time and almost matches the classical upper bound. We also obtain an almost matching space lower bound of Ω(n^{6-o(1)}) for triangle-triangle intersection reporting in ℝ⁴ when the query time is small. Along the way, we further develop the previous lower bound techniques by Afshani and Cheng [Afshani and Cheng, 2021; Afshani and Cheng, 2022].
BibTeX - Entry
@InProceedings{afshani_et_al:LIPIcs.SoCG.2023.3,
author = {Afshani, Peyman and Cheng, Pingan},
title = {{Lower Bounds for Intersection Reporting Among Flat Objects}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {3:1--3:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-273-0},
ISSN = {1868-8969},
year = {2023},
volume = {258},
editor = {Chambers, Erin W. and Gudmundsson, Joachim},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17853},
URN = {urn:nbn:de:0030-drops-178536},
doi = {10.4230/LIPIcs.SoCG.2023.3},
annote = {Keywords: Computational Geometry, Intersection Searching, Data Structure Lower Bounds}
}
|
Keywords: |
|
Computational Geometry, Intersection Searching, Data Structure Lower Bounds |
|
Collection: |
|
39th International Symposium on Computational Geometry (SoCG 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
09.06.2023 |
