Lower bounds for orthogonal range searching: part II. The arithmetic model
Author:
Open Access
- 1 July 1990
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 37 (3) , 439-463
Abstract
Lower bounds on the complexity of orthogonal range searching in the static case are established. Specifically, we consider the following dominance search problem: Given a collection of n weighted points in d -space and a query point q , compute the cumulative weight of the points dominated (in all coordinates) by q . It is assumed that the weights are chosen in a commutative semigroup and that the query time measures only the number of arithmetic operations needed to compute the answer. It is proved that if m units of storage are available, then the query time is at least proportional to (log n /log(2 m / n )) d –*1 in both the worst and average cases. This lower bound is provably tight for m = Ω( n (log n ) d –1+ϵ) and any fixed ϵ > 0. A lower bound of Ω( n /log log n ) d ) on the time required for executing n inserts and queries is also established. —Author's AbstractKeywords
This publication has 7 references indexed in Scilit:
- Lower bounds for orthogonal range searching: I. The reporting caseJournal of the ACM, 1990
- Data Structures and Algorithms 31984
- Log-logarithmic worst-case range queries are possible in space Θ(N)Information Processing Letters, 1983
- A Lower Bound on the Complexity of Orthogonal Range QueriesJournal of the ACM, 1981
- Lower Bounds on the Complexity of Some Optimal Data StructuresSIAM Journal on Computing, 1981
- Efficient worst-case data structures for range searchingActa Informatica, 1980
- On the Average Number of Maxima in a Set of Vectors and ApplicationsJournal of the ACM, 1978