Lower bounds in geometric searching

We study algorithms for geometric range searching, particularly for the problems of reporting and counting points inside of axis-parallel rectangles and simplices in Euclidean d-space. Lower bounds are discussed as well as the models of computation in which the lower bounds hold. The relevance of these models to practical computing is considered. We then present two new lower bounds for geometric range searching. Related to the problem of computing partial sums off-line, we show that given an array A with n entries in an additive semigroup, and m intervals of the form $I\sb k$ = (i, j), where 0 $ $ 0. Both of these lower bounds are tight within small functional factors.