Article ID: | iaor20023564 |
Country: | United States |
Volume: | 30 |
Issue: | 2 |
Start Page Number: | 164 |
End Page Number: | 187 |
Publication Date: | Jun 2001 |
Journal: | Algorithmica |
Authors: | Amir A., Efrat A., Indyk P., Samet H. |
In this paper we investigate data structures obtained by a recursive partitioning of the multidimensional input domain into regions of equal size. One of the best known examples of such a structure is the quadtree. It is used here as a basis for more complex data structures. We also provide multidimensional versions of the stratified tree by van Emde Boas. We show that under the assumption that the input points have limited precision (i.e., are drawn from the integer grid of size