Afshani, Peyman
A New Lower Bound for Semigroup Orthogonal Range Searching
Abstract
We report the first improvement in the spacetime tradeoff of lower bounds for the orthogonal range searching problem in the semigroup model, since Chazelle's result from 1990. This is one of the very fundamental problems in range searching with a long history. Previously, Andrew Yao's influential result had shown that the problem is already nontrivial in one dimension [Yao, 1982]: using m units of space, the query time Q(n) must be Omega(alpha(m,n) + n/(mn+1)) where alpha(*,*) is the inverse Ackermann's function, a very slowly growing function. In d dimensions, Bernard Chazelle [Chazelle, 1990] proved that the query time must be Q(n) = Omega((log_beta n)^{d1}) where beta = 2m/n. Chazelle's lower bound is known to be tight for when space consumption is "high" i.e., m = Omega(n log^{d+epsilon}n).
We have two main results. The first is a lower bound that shows Chazelle's lower bound was not tight for "low space": we prove that we must have m Q(n) = Omega(n (log n log log n)^{d1}). Our lower bound does not close the gap to the existing data structures, however, our second result is that our analysis is tight. Thus, we believe the gap is in fact natural since lower bounds are proven for idempotent semigroups while the data structures are built for general semigroups and thus they cannot assume (and use) the properties of an idempotent semigroup. As a result, we believe to close the gap one must study lower bounds for nonidempotent semigroups or building data structures for idempotent semigroups. We develope significantly new ideas for both of our results that could be useful in pursuing either of these directions.
BibTeX  Entry
@InProceedings{afshani:LIPIcs:2019:10407,
author = {Peyman Afshani},
title = {{A New Lower Bound for Semigroup Orthogonal Range Searching}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {3:13:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771047},
ISSN = {18688969},
year = {2019},
volume = {129},
editor = {Gill Barequet and Yusu Wang},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10407},
URN = {urn:nbn:de:0030drops104075},
doi = {10.4230/LIPIcs.SoCG.2019.3},
annote = {Keywords: Data Structures, Range Searching, Lower bounds}
}
2019
Keywords: 

Data Structures, Range Searching, Lower bounds 
Seminar: 

35th International Symposium on Computational Geometry (SoCG 2019)

Issue date: 

2019 
Date of publication: 

2019 