Range Searching and Point Location among Fat Objects |
| |
Authors: | Mark H Overmars Frank A van der Stappen |
| |
Institution: | Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508 TB, Utrecht, The Netherlands |
| |
Abstract: | We present a data structure that can store a set of disjoint fat objects ind-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 timeO(logd−1 n) and requiresO(n logd−1 n) storage, afterO(n logd−1 n log log n) preprocessing. The data structure and query algorithm are rather simple. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|