Lower Bounds in Geometric Searching (Thesis)

Abstract:

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
semi-group, and $m$ intervals of the form $I sub k^=^[i,j],$ where
$0^<^i^<^j^<=^n,$ then the computation of $A[i]^+ cdot cdot cdot +^[j]$
for all $I sub k$ will require $OMEGA (n^+^m alpha (m,n))$ semigroup
additions. Here $ alpha $ is the functional inverse of Ackermann's
function. Related to the problem of simplex range reporting we prove
that given a collection $P$ of $n$ points in $d$-space, any data
structure which can be modeled on a pointer machine and which can
report the $r$ points inside of an arbitrary $d$-simplex in time $O(n
sup delta ^ +^r)$ will require storage $OMEGA size 7 (n sup {d(1 -
delta ) - epsilon})$, for any fixed $epsilon > ^0$. Both of these
lower bounds are tight within small functional factors.