Lower bounds for orthogonal range searching: part II. The arithmetic model

ABSTRACT

Lower bounds on the complexity of orthogonal range searching in the static case are established. Specifically, we consider the following dominance search problem: Given a collection of n weighted points in d-space and a query point q, compute the cumulative weight of the points dominated (in all coordinates) by q. It is assumed that the weights are chosen in a commutative semigroup and that the query time measures only the number of arithmetic operations needed to compute the answer. It is proved that if m units of storage are available, then the query time is at least proportional to (log n/log(2m/n))d–1 in both the worst and average cases. This lower bound is provably tight for m = &OHgr;(n(log n) d–1+&egr;) and any fixed &egr; > 0. A lower bound of &OHgr;(n/log log n)d) on the time required for executing n inserts and queries is also established. —Author's Abstract

REFERENCES

• 1: J. L. Bentley , H. T. Kung , M. Schkolnick , C. D. Thompson, On the Average Number of Maxima in a Set of Vectors and Applications, Journal of the ACM (JACM), v.25 n.4, p.536-543, Oct. 1978 [doi>10.1145/322092.322095]
• 2: BENTLEY, J. L., AND MAURER, H.A. Efficient worst-case data structures for range searching. Acta Inf. 13 (1980), 155-168.
• 3: Bernard Chazelle, Lower bounds for orthogonal range searching: I. The reporting case, Journal of the ACM (JACM), v.37 n.2, p.200-212, April 1990 [doi>10.1145/77600.77614]
• 4: ERDOS, P., AND SPENCER, J. Probabilistic Methods in Combinatorics. Academic Press, Orlando, Fla., 1974.
• 5: Michael L. Fredman, A Lower Bound on the Complexity of Orthogonal Range Queries, Journal of the ACM (JACM), v.28 n.4, p.696-705, Oct. 1981 [doi>10.1145/322276.322281]
• 6: FREDMAN, M.L. Lower bounds on the complexity of some optimal data structures. SIAM J. Comput. 10 ( 1981 ), 1- l 0.
• 7: Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
• 8: Mark H. Overmars, Design of Dynamic Data Structures, Springer-Verlag New York, Inc., Secaucus, NJ, 1987
• 9: P M Vaidya, Space-time tradeoffs for orthogonal range queries, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.169-174, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22164]
• 10: WILLARD, D.E. Log-logarithmic worst-case range queries are possible in space O(n). Inf. Process. Lett. 17 (1983), 81-84.
• 11: D E Willard, Lower bounds for dynamic range query problems that permit subtraction, International Colloquium on Automata, Languages and Programming on Automata, languages and programming, p.444-453, September 1986, Rennes, France
• 12: Andrew C. Yao, Space-time tradeoff for answering range queries (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.128-136, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802185]
• 13: YAO, A.C. Lower bounds by probabilistic arguments. In Proceedings of the 24th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 420-428.
• 14: YAO, A. C. On the complexity of maintaining partial sums. SIAM J. Comput. 14, 2 (1985), 277-288.

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

Additional Classification:
  E. Data

General Terms:
Algorithms, Measurement, Theory