The R-tree is a well-known bounding-volume hierarchy that is suitable for storing geometric data on secondary memory. Unfortunately, no good analysis of its query time exists. We describe a new algorithm to construct an R-tree for a set of planar objects that has provably good query complexity for point location queries and range queries with ranges of small width. For certain important special cases, our bounds are optimal. We also show how to update the structure dynamically, and we generalize our results to higher-dimensional spaces.
|Title of host publication||Algorithms - ESA 2000 : 8th annual european symposium, Saarbrücken, Germany, September 5-8, 2000 : proceedings|
|Place of Publication||Berlin|
|Publication status||Published - 2000|
|Name||Lecture Notes in Computer Science|