Rectangle stabbing and orthogonal range reporting lower bounds in moderate dimensions

TY - JOUR

T1 - Rectangle stabbing and orthogonal range reporting lower bounds in moderate dimensions

AU - Afshani, Peyman

AU - Killmann, Rasmus

N1 - Publisher Copyright: © 2022

PY - 2023/4

Y1 - 2023/4

N2 - We study the orthogonal range reporting and rectangle stabbing problems in moderate dimensions, i.e., when the dimension is clog⁡(n) for some constant c. In orthogonal range reporting, the input is a set of n points in d dimensions, and the goal is to store these n points in a data structure such that given a query rectangle, we can report all the input points contained in the rectangle. The rectangle stabbing problem is the “dual” problem where the input is a set of rectangles, and the query is a point. Our main result is the following: assume using S(n) space, we can solve either problem in d=clog⁡n dimensions, c≥4, using Q(n)+O(t) time in the pointer machine model of computation where t is the output size. Then, we show that if the query time is small, that is, Q(n)=n1−γ, for [Formula presented], then the space must be Ω(n1−γncγ/e−o(cγ)). Interestingly, we obtain this lower bound using a non-constructive method, and we show the existence of some codes that generalize a specific aspect of error correction codes. Our result overcomes the shortcomings of the previous lower bounds in the pointer machine model for non-constant dimension [3–5,13], as the previous results could not be extended for d=Ω(log⁡n). The only known lower bounds for rectangle stabbing, when the dimension is non-constant, are based on conditional lower bounds upon the best-known results on CNF-SAT [21]. Therefore, our lower bound is the first non-trivial unconditional lower bound for orthogonal range reporting and rectangle stabbing with non-constant dimension.

AB - We study the orthogonal range reporting and rectangle stabbing problems in moderate dimensions, i.e., when the dimension is clog⁡(n) for some constant c. In orthogonal range reporting, the input is a set of n points in d dimensions, and the goal is to store these n points in a data structure such that given a query rectangle, we can report all the input points contained in the rectangle. The rectangle stabbing problem is the “dual” problem where the input is a set of rectangles, and the query is a point. Our main result is the following: assume using S(n) space, we can solve either problem in d=clog⁡n dimensions, c≥4, using Q(n)+O(t) time in the pointer machine model of computation where t is the output size. Then, we show that if the query time is small, that is, Q(n)=n1−γ, for [Formula presented], then the space must be Ω(n1−γncγ/e−o(cγ)). Interestingly, we obtain this lower bound using a non-constructive method, and we show the existence of some codes that generalize a specific aspect of error correction codes. Our result overcomes the shortcomings of the previous lower bounds in the pointer machine model for non-constant dimension [3–5,13], as the previous results could not be extended for d=Ω(log⁡n). The only known lower bounds for rectangle stabbing, when the dimension is non-constant, are based on conditional lower bounds upon the best-known results on CNF-SAT [21]. Therefore, our lower bound is the first non-trivial unconditional lower bound for orthogonal range reporting and rectangle stabbing with non-constant dimension.

KW - Data structure

KW - High dimension

KW - Lower bound

KW - Orthogonal range reporting

KW - Rectangle stabbing

UR - http://www.scopus.com/inward/record.url?scp=85145592685&partnerID=8YFLogxK

U2 - 10.1016/j.comgeo.2022.101959

DO - 10.1016/j.comgeo.2022.101959

M3 - Journal article

AN - SCOPUS:85145592685

SN - 0925-7721

VL - 111

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

M1 - 101959

ER -