We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Tight Lower Bounds for Halfspace Range Searching.
- Authors
Arya, Sunil; Mount, David; Xia, Jian
- Abstract
We establish two new lower bounds for the halfspace range searching problem: Given a set of n points in ℝ, where each point is associated with a weight from a commutative semigroup, compute the semigroup sum of the weights of the points lying within any query halfspace. Letting m denote the space requirements, we prove a lower bound for general semigroups of $\widetilde{\varOmega}(n^{1-1/(d+1)}/m^{1/(d+1)})$ and for integral semigroups of $\widetilde{\varOmega}(n/m^{1/d})$. Our lower bounds are proved in the semigroup arithmetic model. Neglecting logarithmic factors, our result for integral semigroups matches the best known upper bound due to Matoušek. Our result for general semigroups improves upon the best known lower bound due to Brönnimann, Chazelle, and Pach. Moreover, Fonseca and Mount have shown that, given uniformly distributed points, halfspace range queries over idempotent semigroups can be answered in O( n/ m) time in the semigroup arithmetic model. As our lower bounds are established for uniformly distributed point sets, it follows that they also resolve the computational complexity of halfspace range searching over idempotent semigroups in this important special case.
- Subjects
IDEMPOTENTS; GENERATORS (Computer programs); VECTOR spaces; ORTHOGONALIZATION; RANGE imaging; COMPUTATIONAL complexity
- Publication
Discrete & Computational Geometry, 2012, Vol 47, Issue 4, p711
- ISSN
0179-5376
- Publication type
Article
- DOI
10.1007/s00454-012-9412-x