About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Algorithmica (New York)
Paper
Efficient regular data structures and algorithms for dilation, location, and proximity problems
Abstract
In this paper we investigate data structures obtained by a recursive partitioning of the multi-dimensional 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 [vEB]. We show that 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 efficient solutions to many important problems. In particular, they allow us to achieve O (log log u) time per operation for dynamic approximate nearest neighbor (under insertions and deletions) and exact on-line closest pair (under insertions only) in any constant number of dimensions. They allow O (log log u) point location in a given planar shape or in its expansion (dilation by a ball of a given radius). Finally, we provide a linear time (optimal) 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 ball.