Range searching and point location among fat objects

We present a data structure that can store a set of disjoint fat objects in d-space such that point location and bounded-size range searching with arbitrarily shaped ranges can be performed efficiently. The structure can deal with either arbitrary (fat) convex objects or nonconvex (fat) polytopes. The multipurpose data structure supports point location 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 Academic Press, Inc.