How hard is halfspace range searching

Herve Bronnimann, Bernard Chazelle

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

We investigate the complexity of halfspace 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 halfspace. 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 (n/log n)1-(d-1)/d(d+1) /m1/d To our knowledge, this is the first nontrivial lower bound for halfspace range searching. Although the bound is unlikely to be optimal, it falls reasonably close to the recent O(n(log m/n)d+1/m1/d upper bound established by Matousek. We also show that it is possible to devise a sequence of n inserts and halfspace range queries that require a total time of n2-Θ(1/d). Our results imply 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 Ω(n1/3) time (modulo a logarithmic factor).

Original languageEnglish (US)
Title of host publicationEighth Annual Symposium On Computational Geometry
PublisherPubl by ACM
Pages271-275
Number of pages5
ISBN (Print)0897915178, 9780897915175
DOIs
StatePublished - 1992
EventEighth Annual Symposium On Computational Geometry - Berlin, Ger
Duration: Jun 10 1992Jun 12 1992

Publication series

NameEighth Annual Symposium On Computational Geometry

Other

OtherEighth Annual Symposium On Computational Geometry
CityBerlin, Ger
Period6/10/926/12/92

All Science Journal Classification (ASJC) codes

  • Engineering(all)

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

Cite this