Lower bounds for off-line range searching

Research output: Contribution to journalArticlepeer-review

22 Scopus citations


This paper proves three lower bounds for variants of the following range-searching problem: Given n weighted points in Rd and n axis-parallel boxes, compute the sum of the weights within each box: (1) if both additions and subtractions are allowed, we prove that Ω(n log log n) is a lower bound on the number of arithmetic operations; (2) if subtractions are disallowed the lower bound becomes Ω(n(log n/log log n)d-1), which is nearly optimal; (3) finally, for the case where boxes are replaced by simplices, we establish a quasi-optimal lower bound of Ω(n2-2/(d+1))/polylog(n).

Original languageEnglish (US)
Pages (from-to)53-65
Number of pages13
JournalDiscrete and Computational Geometry
Issue number1
StatePublished - Jan 1997

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Lower bounds for off-line range searching'. Together they form a unique fingerprint.

Cite this