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.
All Science Journal Classification (ASJC) codes
- Control and Systems Engineering
- Information Systems
- Hardware and Architecture
- Artificial Intelligence