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+σ}) spacetime 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., linetetrahedron intersection in ℝ⁴ [Esther Ezra and Micha Sharir, 2022], triangletriangle 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 (d1)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(d1)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^{6o(1)}) for triangletriangle 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:13:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772730},
ISSN = {18688969},
year = {2023},
volume = {258},
editor = {Chambers, Erin W. and Gudmundsson, Joachim},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17853},
URN = {urn:nbn:de:0030drops178536},
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 