The effect of corners on the complexity of approximate range searching

ABSTRACT

Range searching is among the most fundamental problems in computational geometry. Given an n-element point set in R^d, the problem is to preprocess the points so that the total weight (or generally semigroup sum) of the points lying within a given query range η can be determined quickly. In the ε-approximate version we assume that η is bounded and 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 boundary.In this paper we contrast the complexity of approximate range searching based on properties of the semigroup and range space. 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. Idempotence is important because points may be multiply counted, and this implies that generator subsets may overlap one another. Our recent results [Arya, Malamatos, Mount, "On the Importance of Idempotence," STOC 2006, to appear] imply that for approximate Euclidean-ball range searching, idempotence offers significant advantages. In particular, nearly matching upper and lower bounds show that the exponents in the ε-dependencies are roughly halved for idempotent semigroups.These prior results made critical use of two properties of Euclidean balls: smoothness and rotational symmetry. In this paper we consider two alternative formulations that arise from relaxing these properties. The first involves ranges with sharp corners and the second involves arbitrary smooth convex ranges. We show that, as with integrality, sharp corners have an adverse effect on the problem's complexity. We consider d-dimensional unit hypercube ranges under rigid motions. Assuming linear space, we show here that in the semigroup arithmetic model the worst-case query time assuming an arbitrary (possibly idempotent) faithful semigroup is Ω(1/ε^d−2√d). We further prove a tighter lower bound of Ω(1/ε^d−2 for the special case of integral semigroups. This nearly matches the best known upper bound of O(log n + (1/ε)^d−1), which holds for arbitrary semigroups.In contrast, we show that the improvements offered by idempotence do apply to smooth convex ranges. We define a class of smooth convex ranges to have the property that at any boundary point of the range, it is possible to place a large Euclidean ball within the range that touches this point. We show that for smooth ranges and idempotent semigroups, ε-approximate range queries can be answered in O(log n + (1/ε)^(d−1)/2 log (1/ε)) time using O(n/ε) space. We show that this is nearly tight by presenting a lower bound of Ω(log n + (1/ε)^(d−1)/2). This bound is in the algebraic decision-tree model and holds irrespective of space.Our results show that, in contrast to exact range searching, the interplay of semigroup properties and the range space can result in dramatic differences in query times. This is born out through both upper and lower bounds.

REFERENCES

• 1: 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.
• 2: Sunil Arya , Theocharis Malamatos, Linear-size approximate voronoi diagrams, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.147-155, January 06-08, 2002, San Francisco, California
• 3: Sunil Arya , Theocharis Malamatos , David M. Mount, Space-efficient approximate Voronoi diagrams, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510011]
• 4: Sunil Arya , Theocharis Malamatos , David M. Mount, Space-time tradeoffs for approximate spherical range counting, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 5: Sunil Arya , Theocharis Malamatos , David M. Mount, On the importance of idempotence, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132598]
• 6: Sunil Arya , David M. Mount, Approximate range searching, Computational Geometry: Theory and Applications, v.17 n.3-4, p.135-152, Dec. 2000 [doi>10.1016/S0925-7721(00)00022-5 ]
• 7: I. Bárány. Intrinsic volumes and f-vectors of random polytopes. Math. Annalen, 285:671--699, 1989.
• 8: I. Bárány. The technique of M-regions and cap-coverings: A survey. In Proc. III International Conference in Stochastic Geometry, Convex Bodies and Empirical Measures, Part II, volume 65 of Rendi. del Circ. Matemat. di Palermo, pages 21--38, 2000.
• 9: I. Bárány and D. Larman. Convex bodies, economic cap coverings, random polytopes. Mathematika, 35:274--291, 1988.
• 10: H. Brönnimann, B. Chazelle, and J. Pach. How hard is halfspace range searching. Discrete Comput. Geom., 10:143--155, 1993.
• 11: B. Chazelle. Lower bounds on the complexity of polytope range searching. J. Amer. Math. Soc., 2:637--666, 1989.
• 12: B. Chazelle, D. Liu, and A. Magen. Approximate range searching in higher dimension. In Proc. 16th Canad. Conf. Comput. Geom., pages 154--157, 2004.
• 13: Jeff Erickson, Space-Time Tradeoffs for Emptiness Queries, SIAM Journal on Computing, v.29 n.6, p.1968-1996, April 2000 [doi>10.1137/S0097539798337212]
• 14: G. Ewald, D. G. Larman, and C. A. Rogers. The directions of the line segments and of the r-dimensional balls on the boundary of a convex body in Euclidean space. Mathematika, 17:1--20, 1970.
• 15: M. L. Fredman. Lower bounds on the complexity of some optimal data structures. SIAM J. Comput., 10:1--10, 1981.
• 16: J. Matoušek. Range searching with efficient hierarchical cuttings. Discrete Comput. Geom., 10(2):157--182, 1993.
• 17: Jiří Matoušek, Geometric range searching, ACM Computing Surveys (CSUR), v.26 n.4, p.422-461, Dec. 1994 [doi>10.1145/197405.197408]
• 18: A. C. Yao. On the complexity of maintaining partial sums. SIAM J. Comput., 14:277--288, 1985.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms

Keywords:
approximation algorithms, idempotence, range searching