Range Searching and Point Location among Fat Objects

✍ Scribed by Mark H. Overmars; Frank A. van der Stappen

• Book ID: 102578216
• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 314 KB
• Volume: 21
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1996.0063

✦ Synopsis

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 Ž dy 1 . supports point location and range searching queries in time O log n and Ž dy 1 . Ž d y 1 . requires O n log n storage, after O n log n log log n preprocessing. The data structure and query algorithm are rather simple.