TY - GEN

T1 - How hard is halfspace range searching

AU - Bronnimann, Herve

AU - Chazelle, Bernard

PY - 1992

Y1 - 1992

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=0026995267&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0026995267&partnerID=8YFLogxK

U2 - 10.1145/142675.142730

DO - 10.1145/142675.142730

M3 - Conference contribution

AN - SCOPUS:0026995267

SN - 0897915178

SN - 9780897915175

T3 - Eighth Annual Symposium On Computational Geometry

SP - 271

EP - 275

BT - Eighth Annual Symposium On Computational Geometry

PB - Publ by ACM

T2 - Eighth Annual Symposium On Computational Geometry

Y2 - 10 June 1992 through 12 June 1992

ER -