TY - JOUR
T1 - Lower Bounds for Semialgebraic Range Searching and Stabbing Problems
AU - Afshani, Peyman
AU - Cheng, Pingan
N1 - Publisher Copyright:
© 2023 Association for Computing Machinery.
PY - 2023/4
Y1 - 2023/4
N2 - 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, the problem is well-understood: It can be solved using S(n) space and with Q(n) query time with where the notation hides polylogarithmic factors and this trade-off is tight (up to no(1) factors). In particular, there exist "low space"structures that use O(n) space with O(n1-1/d}) query time [8, 25] and "fast query"structures that use O(nd) space with O(log n) query time [9]. However, for general semialgebraic ranges, only "low space"solutions are known, but the best solutions [7] match the same trade-off curve as simplex queries, with O(n) space and 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 semialgebraic 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, with Q(n) query time must use space, where the notation hides factors, meaning, for , space must be used. In addition, we study the problem of reporting the subset of input points in a polynomial slab defined by , where is a univariate polynomial of degree Δand are given at the query time, a problem that we call polynomial slab reporting. For this, we show a space lower bound of , which implies that for , we must use space. We also consider the dual semialgebraic stabbing problems of semialgebraic range searching 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 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 polynomial slab stabbing problems. Again, our lower bounds are almost tight for linear size data structures in this case.
AB - 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, the problem is well-understood: It can be solved using S(n) space and with Q(n) query time with where the notation hides polylogarithmic factors and this trade-off is tight (up to no(1) factors). In particular, there exist "low space"structures that use O(n) space with O(n1-1/d}) query time [8, 25] and "fast query"structures that use O(nd) space with O(log n) query time [9]. However, for general semialgebraic ranges, only "low space"solutions are known, but the best solutions [7] match the same trade-off curve as simplex queries, with O(n) space and 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 semialgebraic 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, with Q(n) query time must use space, where the notation hides factors, meaning, for , space must be used. In addition, we study the problem of reporting the subset of input points in a polynomial slab defined by , where is a univariate polynomial of degree Δand are given at the query time, a problem that we call polynomial slab reporting. For this, we show a space lower bound of , which implies that for , we must use space. We also consider the dual semialgebraic stabbing problems of semialgebraic range searching 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 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 polynomial slab stabbing problems. Again, our lower bounds are almost tight for linear size data structures in this case.
KW - computational geometry
KW - lower bound
KW - Semialgebraic range searching
UR - http://www.scopus.com/inward/record.url?scp=85158113064&partnerID=8YFLogxK
U2 - 10.1145/3578574
DO - 10.1145/3578574
M3 - Journal article
AN - SCOPUS:85158113064
SN - 0004-5411
VL - 70
SP - 1
EP - 26
JO - Journal of the ACM
JF - Journal of the ACM
IS - 2
M1 - 16
ER -