Lower bounds for orthogonal range searching: I. The reporting case

ABSTRACT

We establish lower bounds on the complexity of orthogonal range reporting in the static case. Given a collection of n points in d-space and a box [a1, b1] X … X [ad, bd], report every point whose ith coordinate lies in [ai, bi], for each i = l, … , d. The collection of points is fixed once and for all and can be preprocessed. The box, on the other hand, constitutes a query that must be answered online. It is shown that on a pointer machine a query time of O(k + polylog(n)), where k is the number of points to be reported, can only be achieved at the expense of &OHgr;(n(log n/log log n)d-1) storage. Interestingly, these bounds are optimal in the pointer machine model, but they can be improved (ever so slightly) on a random access machine. In a companion paper, we address the related problem of adding up weights assigned to the points in the query box.

REFERENCES

• 1: BENTLEY, J.L. Decomposable searching problems. Inf. Proc. Lett. 8 (1979), 244-251.
• 2: Jon Louis Bentley, Multidimensional divide-and-conquer, Communications of the ACM, v.23 n.4, p.214-229, April 1980 [doi>10.1145/358841.358850]
• 3: Bernard Chazelle, Filtering search: a new approach to query answering, SIAM Journal on Computing, v.15 n.3, p.703-724, August 1986 [doi>10.1137/0215051]
• 4: Bernard Chazelle, Functional approach to data structures and its use in multidimensional searching, SIAM Journal on Computing, v.17 n.3, p.427-462, June 1988 [doi>10.1137/0217026]
• 5: CHAZELLE, B., AND EDELSBRUNNER, H. Linear space data structures for two types of range search. Discrete Comput. Geom. 2 (1987), 113-126.
• 6: CHAZELLE, B., AND GUIBAS, L.J. Fractional cascading: If. Applications. Algorithmica I (1986), 163-191.
• 7: FELLER, W. All Introduction to Probability Theory and Its Applications, vol. l, 3rd ed. Wiley, New York, 1968.
• 8: LUEKER, G.S. A data structure for orthogonal range queries. In Proceedings of the 19th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1978, pp. 28-34.
• 9: MCCREIGHT, E.M. Priority search trees. SIAMJ. Comput. 14, 2 (1985), 257-276.
• 10: Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
• 11: TARJAN, R. E. A class of algorithms which require nonlinear time to maintain disjoint sets. J. Comput. System Sci. 18 (1979), 110-127.
• 12: WILLgao, D.E. Predicate-oriented database search algorithms. Rep. TR-20-78. PhD dissertation, Aiken Computational Lab., Harvard Univ., Cambridge, Mass., 1978.
• 13: Dan E. Willard, New data structures for orthogonal range queries, SIAM Journal on Computing, v.14 n.1, p.232-253, Feb. 1985 [doi>10.1137/0214019]
• 14: Dan E. Willard , George S. Lueker, Adding range restriction capability to dynamic data structures, Journal of the ACM (JACM), v.32 n.3, p.597-617, July 1985 [doi>10.1145/3828.3839]

INDEX TERMS

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

Additional Classification:
  E. Data

General Terms:
Algorithms, Theory