LOWER BOUNDS FOR ORTHOGONAL RANGE SEARCHING .2. THE ARITHMETIC MODEL

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. © 1990, ACM. All rights reserved.