RANGE SEARCHING AND POINT LOCATION AMONG FAT OBJECTS

We present a data structure that can store a set of disjoint fat objec ts in d-space such that point location and bounded-size range searchin g with arbitrarily shaped ranges can be performed efficiently. The str ucture can deal with either arbitrary (fat) convex objects or nonconve x (fat) polytopes. The multipurpose data structure supports point loca tion and range searching queries in time O(log(d-1) n) and requires O( n log(d-1) n) storage, after O(n log(d-1) n log log n) preprocessing. The data structure and query algorithm are rather simple. (C) 1996 Aca demic Press, Inc.