ABSTRACT
Range searching is among the most fundamental problems in computational geometry. An n-element point set in Rd is given along with an assignment of weights to these points from some commutative semigroup. Subject to a fixed space of possible range shapes, the problem is to preprocess the points so that the total semigroup sum of the points lying within a given query range η can be determined quickly. In the approximate version of the problem we assume that η is bounded, and we are given an approximation parameter ε > 0. We are to determine the semigroup sum of all the points contained within η and may additionally include any of the points lying within distance ε • diam(η) of η's boundar.In this paper we contrast the complexity of range searching based on semigroup properties. A semigroup (S,+) is idempotent if x + x = x for all x ∈ S, and it is integral if for all k ≥ 2, the k-fold sum x + ... + x is not equal to x. For example, (R, min) and (0,1, ∨) are both idempotent, and (N, +) is integral. To date, all upper and lower bounds hold irrespective of the semigroup. We show that semigroup properties do indeed make a difference for both exact and approximate range searching, and in the case of approximate range searching the differences are dramatic.First, we consider exact halfspace range searching. The assumption that the semigroup is integral allows us to improve the best lower bounds in the semigroup arithmetic model. For example, assuming O(n) storage in the plane and ignoring polylog factors, we provide an Ω*(n2/5) lower bound for integral semigroups, improving upon the best lower bound of Ω*(n1/3), thus closing the gap with the O(n1/2) upper bound.We also consider approximate range searching for Euclidean ball ranges. We present lower bounds and nearly matching upper bounds for idempotent semigroups. We also present lower bounds for range searching for integral semigroups, which nearly match existing upper bounds. These bounds show that the advantages afforded by idempotency can result in major improvements. In particular, assuming roughly linear space, the exponent in the ε-dependencies is smaller by a factor of nearly 1/2. All our results are presented in terms of space-time tradeoffs, and our lower and upper bounds match closely throughout the entire spectrum.To our knowledge, our results provide the first proof that semigroup properties affect the computational complexity of range searching in the semigroup arithmetic model. These are the first lower bound results for any approximate geometric retrieval problems. The existence of nearly matching upper bounds, throughout the range of space-time tradeoffs, suggests that we are close to resolving the computational complexity of both idempotent and integral approximate spherical range searching in the semigroup arithmetic model.
- P. K. Agarwal and J. Erickson. Geometric range searching and its relatives. In B. Chazelle, J. E. Goodman, and R. Pollack, editors, Advances in Discrete and Computational Geometry, volume 223 of Contemporary Mathematics, pages 1--56. American Mathematical Society, Providence, RI, 1999.Google Scholar
- S. Arya and T. Malamatos. Linear-size approximate Voronoi diagrams. In Proc. 13th ACM-SIAM Sympos. Discrete Algorithms, pages 147--155, 2002. Google ScholarDigital Library
- S. Arya, T. Malamatos, and D. M. Mount. Space-efficient approximate Voronoi diagrams. In Proc. 34th Annual ACM Sympos. Theory Comput., pages 721--730, 2002. Google ScholarDigital Library
- S. Arya, T. Malamatos, and D. M. Mount. Space-time tradeoffs for approximate spherical range counting. In Proc. 16th ACM-SIAM Sympos. Discrete Algorithms, pages 535--544, 2005. Google ScholarDigital Library
- S. Arya and D. M. Mount. Approximate range searching. Computational Geometry: Theory and Applications, 17:135--152, 2000. Google ScholarDigital Library
- J.-D. Boissonnat and M. Yvinec. Algorithmic Geometry. Cambridge University Press, UK, 1998. Translated by H. Brönnimann. Google ScholarDigital Library
- H. Brönnimann, B. Chazelle, and J. Pach. How hard is halfspace range searching. Discrete Comput. Geom., 10:143--155, 1993.Google ScholarDigital Library
- B. Chazelle. Lower bounds on the complexity of polytope range searching. J. Amer. Math. Soc., 2:637--666, 1989.Google ScholarCross Ref
- B. Chazelle, D. Liu, and A. Magen. Approximate range searching in higher dimension. In Proc. 16th Canad. Conf. Comput. Geom., 2004.Google Scholar
- B. Chazelle, M. Sharir, and E. Welzl. Quasi-optimal upper bounds for simplex range searching and new zone theorems. Algorithmica, 8:407--429, 1992.Google ScholarDigital Library
- J. Erickson. Space-time tradeoffs for emptiness queries. SIAM J. Comput., 29:1968--1996, 2000. Google ScholarDigital Library
- M. L. Fredman. Lower bounds on the complexity of some optimal data structures. SIAM J. Comput., 10:1--10, 1981.Google ScholarDigital Library
- S. Har-Peled. A replacement for Voronoi diagrams of near linear size. In Proc. 42nd Annu. IEEE Sympos. Found. Comput. Sci., pages 94--103, 2001. Google ScholarDigital Library
- J. Matoušek. Range searching with efficient hierarchical cuttings. Discrete Comput. Geom., 10(2):157--182, 1993.Google ScholarDigital Library
- J. Matoušek. Geometric range searching. ACM Comput. Surv., 26:421--461, 1994. Google ScholarDigital Library
- A. C. Yao. On the complexity of maintaining partial sums. SIAM J. Comput., 14:277--288, 1985.Google ScholarDigital Library
Index Terms
- On the importance of idempotence
Recommendations
The Effect of Corners on the Complexity of Approximate Range Searching
Given an n-element point set in źd, the range searching problem involves preprocessing these points so that the total weight, or for our purposes the semigroup sum, of the points lying within a given query range ź can be determined quickly. In ź-...
The Effect of Corners on the Complexity of Approximate Range Searching
Given an n-element point set in ℝd , the range searching problem involves preprocessing these points so that the total weight, or for our purposes the semigroup sum, of the points lying within a given query range η can be determined quickly. In ε-...
The effect of corners on the complexity of approximate range searching
SCG '06: Proceedings of the twenty-second annual symposium on Computational geometryRange searching is among the most fundamental problems in computational geometry. Given an n-element point set in Rd, the problem is to preprocess the points so that the total weight (or generally semigroup sum) of the points lying within a given query ...
Comments