Abstract
Lower bounds on the complexity of orthogonal range searching in thestatic case are established. Specifically, we consider the followingdominance search problem: Given a collection of n weighted points in d -space and a query point q, compute the cumulative weight ofthe points dominated 1990 by q. It is assumed that the weights arechosen in a commutative semigroup and that the query time measures onlythe number of arithmetic operations needed to compute the answer. It isproved that if m units of storage areavailable, then the query time is at least proportional to on the time required for executing n inserts and queries is also established.
Original language | English (US) |
---|---|
Pages (from-to) | 439-463 |
Number of pages | 25 |
Journal | Journal of the ACM (JACM) |
Volume | 37 |
Issue number | 3 |
DOIs | |
State | Published - Jan 7 1990 |
All Science Journal Classification (ASJC) codes
- Software
- Control and Systems Engineering
- Information Systems
- Hardware and Architecture
- Artificial Intelligence