A data structure for orthogonal range queries
George S. Lueker · Annual Symposium on Foundations of Computer Science · 1978
Given a set of points in a d-dimensional space, an orthogonal range query is a request for the number of points in a specified d-dimensional box. We present a data structure and algorithm which enable one to insert and delete points and to perform orthogonal range queries. The worstcase time complexity for n operations is O(n logd n); the space usea is O(n logd-1 n). (O-notation here is with respect to n; the constant is allowed to depend on d.) Next we briefly discuss decision tree bounds on the complexity of orthogonal range queries. We show that a decision tree of height O(dn log n) (Where the implied constant does not depend on d or n) can be constructed to process n operations in d dimensions. This suggests that the standard decision tree model will not provide a useful method for investigating the complexity of such problems.
Cited by 206 works. doi:10.1109/sfcs.1978.1
Authors
References
- The Design and Analysis of Computer Algorithms
- Multidimensional binary search trees used for associative searching
- Quad trees a data structure for retrieval on composite keys
- AN ALGORITHM FOR THE ORGANIZATION OF INFORMATION
- On Finding the Maxima of a Set of Vectors
- Multidimensional Searching Problems
- Partial-Match Retrieval Algorithms
- Binary Search Trees of Bounded Balance
- Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees
- Divide-and-conquer in multidimensional space