In this paper we investigate data structures obtained by a recursive partit
ioning 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 multidim
ensional versions of the stratified tree by van Emde Boas [VEB]. We show th
at under the assumption that the input points have limited precision (i.e.,
are drawn from the integer grid of size u) these data structures yield eff
icient solutions to many important problems. In particular, they allow us t
o achieve O (log log u) time per operation for dynamic approximate nearest
neighbor (under insertions and deletions) and exact on-line closest pair (u
nder insertions only) in any constant number of dimensions. They allow O (l
og log u) point location in a given planar shape or in its expansion (dilat
ion by a ball of a given radius). Finally, we provide a linear time (optima
l) algorithm for computing the expansion of a shape represented by a region
quadtree, This result shows that the spatial order imposed by this regular
data structure is sufficient to optimize the operation of dilation by a ba
ll.