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