Lower Bounds in Geometric Searching (Thesis)
Report ID: TR-343-91Author: Rosenburg, Burton
Date: 1991-10-00
Pages: 74
Download Formats: |PDF|
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.