How hard is half-space range searching?

Hervé Brönnimann, Bernard Chazelle, János Pach

Research output: Contribution to journalArticle

36 Scopus citations

Abstract

We investigate the complexity of half-space range searching: given n points in d-space, build a data structure that allows us to determine efficiently how many points lie in a query half-space. We establish a tradeoff between the storage m and the worst-case query time t in the Fredman/Yao arithmetic model of computation. We show that t must be at least on the order of {Mathematical expression} Although the bound is unlikely to be optimal, it falls reasonably close to the recent upper bound of O(n/m 1/d ) established by Matoušek. We also show that it is possible to devise a sequence of n inserts and half-space range queries that require a total time of n 2-O(1/d) . Our results imply the first nontrivial lower bounds for spherical range searching in any fixed dimension. For example, they show that, with linear storage, circular range queries in the plane require Ω(n 1/3) time (modulo a logarithmic factor).

Original languageEnglish (US)
Pages (from-to)143-155
Number of pages13
JournalDiscrete & Computational Geometry
Volume10
Issue number1
DOIs
StatePublished - Dec 1 1993

All Science Journal Classification (ASJC) codes

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

Fingerprint Dive into the research topics of 'How hard is half-space range searching?'. Together they form a unique fingerprint.

  • Cite this