[ont.events] UW Data Struct. Seminar, Dr. Overmars on "Range Searching on a Grid"

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.
                    -