A data structure for orthogonal range queries
- 1 October 1978
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 28-34
- https://doi.org/10.1109/sfcs.1978.1
Abstract
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.Keywords
This publication has 9 references indexed in Scilit:
- Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad treesActa Informatica, 1977
- Multidimensional Searching ProblemsSIAM Journal on Computing, 1976
- Partial-Match Retrieval AlgorithmsSIAM Journal on Computing, 1976
- Divide-and-conquer in multidimensional spacePublished by Association for Computing Machinery (ACM) ,1976
- On Finding the Maxima of a Set of VectorsJournal of the ACM, 1975
- Multidimensional binary search trees used for associative searchingCommunications of the ACM, 1975
- Analysis of range searches in quad treesInformation Processing Letters, 1975
- Quad trees a data structure for retrieval on composite keysActa Informatica, 1974
- Binary Search Trees of Bounded BalanceSIAM Journal on Computing, 1973