An Optimal Lower Bound for Simplex Range Reporting

TY - GEN

T1 - An Optimal Lower Bound for Simplex Range Reporting

AU - Cheng, Pingan

AU - Afshani, Peyman

PY - 2023

Y1 - 2023

N2 - We give a simplified and improved lower bound for the simplex range reporting problem. We show that given a set P of n points in R d, any data structure that uses S(n) space to answer such queries must have Q(n) = Ω((n 2/S(n)) (d−1) /d + k) query time, where k is the output size. For near-linear space data structures, i.e., S(n) = O(nlog O(1) n), this improves the previous lower bounds by Chazelle and Rosenberg [13] and Afshani [1] but perhaps more importantly, it is the first ever tight lower bound for any variant of simplex range searching for d ≥ 3 dimensions. We obtain our lower bound by making a simple connection to well-studied problems in incident geometry which allows us to use known constructions in the area. We observe that a small modification of a simple already existing construction can lead to our lower bound. We believe that our proof is accessible to a much wider audience, at least compared to the previous intricate probabilistic proofs based on measure arguments by Chazelle and Rosenberg [13] and Afshani [1]. The lack of tight or almost-tight (up to polylogarithmic factor) lower bounds for near-linear space data structures is a major bottleneck in making progress on problems such as proving lower bounds for multilevel data structures. It is our hope that this new line of attack based on incidence geometry can lead to further progress in this area.

AB - We give a simplified and improved lower bound for the simplex range reporting problem. We show that given a set P of n points in R d, any data structure that uses S(n) space to answer such queries must have Q(n) = Ω((n 2/S(n)) (d−1) /d + k) query time, where k is the output size. For near-linear space data structures, i.e., S(n) = O(nlog O(1) n), this improves the previous lower bounds by Chazelle and Rosenberg [13] and Afshani [1] but perhaps more importantly, it is the first ever tight lower bound for any variant of simplex range searching for d ≥ 3 dimensions. We obtain our lower bound by making a simple connection to well-studied problems in incident geometry which allows us to use known constructions in the area. We observe that a small modification of a simple already existing construction can lead to our lower bound. We believe that our proof is accessible to a much wider audience, at least compared to the previous intricate probabilistic proofs based on measure arguments by Chazelle and Rosenberg [13] and Afshani [1]. The lack of tight or almost-tight (up to polylogarithmic factor) lower bounds for near-linear space data structures is a major bottleneck in making progress on problems such as proving lower bounds for multilevel data structures. It is our hope that this new line of attack based on incidence geometry can lead to further progress in this area.

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

U2 - 10.1137/1.9781611977585.ch25

DO - 10.1137/1.9781611977585.ch25

M3 - Article in proceedings

SP - 272

EP - 277

BT - 6th Symposium on Simplicity in Algorithms (SOSA 2023)

A2 - Kavitha, Telikepalli

A2 - Mehlhorn, Kurt

PB - Society for Industrial and Applied Mathematics

ER -