𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

No coin nor oath required. For personal study only.

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


πŸ“œ SIMILAR VOLUMES