Afshani, Peyman ;
Cheng, Pingan
Lower Bounds for Semialgebraic Range Searching and Stabbing Problems
Abstract
In the semialgebraic range searching problem, we are given a set of n points in ℝ^d and we want to preprocess the points such that for any query range belonging to a family of constant complexity semialgebraic sets (Tarski cells), all the points intersecting the range can be reported or counted efficiently. When the ranges are composed of simplices, then the problem is wellunderstood: it can be solved using S(n) space and with Q(n) query time with S(n)Q^d(n) = Õ(n^d) where the Õ(⋅) notation hides polylogarithmic factors and this tradeoff is tight (up to n^o(1) factors). Consequently, there exists "low space" structures that use O(n) space with O(n^{11/d}) query time and "fast query" structures that use O(n^d) space with O(log^{d+1} n) query time. However, for the general semialgebraic ranges, only "low space" solutions are known, but the best solutions match the same tradeoff curve as the simplex queries, with O(n) space and Õ(n^{11/d}) query time. It has been conjectured that the same could be done for the "fast query" case but this open problem has stayed unresolved.
Here, we disprove this conjecture. We give the first nontrivial lower bounds for semilagebraic range searching and other related problems. More precisely, we show that any data structure for reporting the points between two concentric circles, a problem that we call 2D annulus reporting problem, with Q(n) query time must use S(n) = Ω^o(n³/Q(n)⁵) space where the Ω^o(⋅) notation hides n^o(1) factors, meaning, for Q(n) = O(log^{O(1)}n), Ω^o(n³) space must be used. In addition, we study the problem of reporting the subset of input points between two polynomials of the form Y = ∑_{i=0}^Δ a_i Xⁱ where values a_0,⋯,a_Δ are given at the query time, a problem that we call polynomial slab reporting. For this, we show a space lower bound of Ω^o(n^{Δ+1}/Q(n)^{Δ²+Δ}), which shows for Q(n) = O(log^{O(1)}n), we must use Ω^o(n^{Δ+1}) space. We also consider the dual problems of semialgebraic range searching, semialgebraic stabbing problems, and present lower bounds for them. In particular, we show that in linear space, any data structure that solves 2D annulus stabbing problems must use Ω(n^{2/3}) query time. Note that this almost matches the upper bound obtained by lifting 2D annuli to 3D. Like semialgebraic range searching, we also present lower bounds for general semialgebraic slab stabbing problems. Again, our lower bounds are almost tight for linear size data structures in this case.
BibTeX  Entry
@InProceedings{afshani_et_al:LIPIcs.SoCG.2021.8,
author = {Afshani, Peyman and Cheng, Pingan},
title = {{Lower Bounds for Semialgebraic Range Searching and Stabbing Problems}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {8:18:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771849},
ISSN = {18688969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13807},
URN = {urn:nbn:de:0030drops138072},
doi = {10.4230/LIPIcs.SoCG.2021.8},
annote = {Keywords: Computational Geometry, Data Structures and Algorithms}
}
02.06.2021
Keywords: 

Computational Geometry, Data Structures and Algorithms 
Seminar: 

37th International Symposium on Computational Geometry (SoCG 2021)

Issue date: 

2021 
Date of publication: 

02.06.2021 