mwang@watmath.UUCP (mwang) (05/23/85)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
DATA STRUCTURING SEMINAR
- Thursday, May 30, 1985.
Dr. M.H. Overmars of the University of Utrecht will
speak on ``Range Searching on a Grid.''
TIME: 3:30 PM
ROOM: MC 6091A
ABSTRACT
The range searching problem asks for storing a set of
points in the plane (or higher dimensional space) such
that those points lying in a given axis-parallel rec-
tangle can be determined efficiently. The problem has
been studied in great detail and many efficient solu-
tions have been (k+logn) using (nlogn) storage, where
-- - - -
n is the number of points in the set and k the number
- -
of reported answers.
We consider the range searching problem restricted to a
U*U grid. In other words, the point in the set have
---
integer coordinates between 1 and U. In this situation
-
other techniques (e.g. perfect hashing) can be used for
storing and retrieving points. In the paper two dif-
ferent techniques will be given to solve the range
searching problem on a grid.
The first solution exploits perfect hashing techniques
to obtain a structure with a query time of (k+loglogU)
-- -
using (nlogU) storage. Unfortunately, the preprocess-
- -
ing time of this structure is very high.
The second solution uses table lookup rather than
searching and obtains a query time of (k+\/logU) using
--------
(nlogU) storage. This structure can be built in
- -
(nlogU) time. Both solutions are static.
Some related problems can be solved efficiently as
well. For example the ECDF searching problem and the
range searching problem with half infinite ranges can
both be solved in the same query time bounds as stated
above, using only (n) storage.
-