Tight lower bounds for halfspace range searching
Sunil Arya, David M. Mount, Jian Xia · 2010
We establish two new lower bounds for the halfspace range searching problem: Given a set of n points in ℜd, where each point is associated with a weight from a commutative semigroup, compute the semigroup sum of the weights of the points lying within any query halfspace. Letting $m$ denote the space requirements, we prove a lower bound for general semigroups of Ω(n1-1/(d+1)/m1/(d+1)) and for integral semigroups of Ω(n/m1/d).