Lower Bounds for Orthogonal Range Searching: I. The Reporting Case

Research output: Contribution to journalArticle

107 Scopus citations

Abstract

We establish lower bounds on the complexity of orthogonal range reporting in the static case. Given a collection of n points in d-space and a box [a1, b1] X … X [ad, bd], report every point whose ith coordinate lies in [ai, bi], for each i = l, …, d. The collection of points is fixed once and for all and can be preprocessed. The box, on the other hand, constitutes a query that must be answered online. It is shown that on a pointer machine a query time of O1990), where k is the number of points to be reported, can only be achieved at the expense of Ω(n(log n/log log n)d-1) storage. Interestingly, these bounds are optimal in the pointer machine model, but they can be improved (ever so slightly) on a random access machine. In a companion paper, we address the related problem of adding up weights assigned to the points in the query box.

Original languageEnglish (US)
Pages (from-to)200-212
Number of pages13
JournalJournal of the ACM (JACM)
Volume37
Issue number2
DOIs
StatePublished - Jan 4 1990

All Science Journal Classification (ASJC) codes

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

Cite this