Lower Bounds for Orthogonal Range Searching: Part II. The Arithmetic Model

Research output: Contribution to journalArticlepeer-review

81 Scopus citations


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 languageEnglish (US)
Pages (from-to)439-463
Number of pages25
JournalJournal of the ACM (JACM)
Issue number3
StatePublished - Jan 7 1990

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Cite this