How hard is halfspace range searching?
Hervé Brönnimann, Bernard Chazelle · 1992
We investigate the complexity of halfspace range searching: Given n points in d-space, build a data structure that allows us to determine efficiently how many points lie in a query halfspace. We establish a tradeoff between the storage m and the worst-case query time t in the Fredman/Yao arithmetic model of computation. We show that t must be at least on the order of (n/log n)1-((d-1)/(d(d+1))m1/d.