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

Journal of the ACM - Tập 37 Số 2 - Trang 200-212 - 1990
Bernard Chazelle1
1Princeton Univ., Princeton, NJ

Tóm tắt

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 [ a 1 , b 1 ] X … X [ a d , b d ], report every point whose i th coordinate lies in [ a i , b i ], 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 Ω( 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.

Từ khóa


Tài liệu tham khảo

BENTLEY , J.L. Decomposable searching problems. Inf. Proc. Lett. 8 ( 1979 ), 244 - 251 . BENTLEY, J.L. Decomposable searching problems. Inf. Proc. Lett. 8 (1979), 244-251.

10.1145/358841.358850

10.1137/0215051

10.1137/0217026

CHAZELLE , B. , AND EDELSBRUNNER , H. Linear space data structures for two types of range search. Discrete Comput. Geom. 2 ( 1987 ), 113 - 126 . CHAZELLE, B., AND EDELSBRUNNER, H. Linear space data structures for two types of range search. Discrete Comput. Geom. 2 (1987), 113-126.

CHAZELLE , B. , AND GUIBAS , L.J. Fractional cascading : If. Applications. Algorithmica I ( 1986 ), 163 - 191 . CHAZELLE, B., AND GUIBAS, L.J. Fractional cascading: If. Applications. Algorithmica I (1986), 163-191.

FELLER , W. All Introduction to Probability Theory and Its Applications, vol. l, 3rd ed . Wiley , New York , 1968 . FELLER, W. All Introduction to Probability Theory and Its Applications, vol. l, 3rd ed. Wiley, New York, 1968.

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 . 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.

MCCREIGHT , E.M. Priority search trees. SIAMJ. Comput. 14 , 2 ( 1985 ), 257-276. MCCREIGHT, E.M. Priority search trees. SIAMJ. Comput. 14, 2 (1985), 257-276.

MEHLHORN , K. Data Structures and Algorithms. 3: Multidimensional Searching and Computational Geometry . Springer-Verlag , Berlin , 1984 . MEHLHORN, K. Data Structures and Algorithms. 3: Multidimensional Searching and Computational Geometry. Springer-Verlag, Berlin, 1984.

TARJAN , R. E. A class of algorithms which require nonlinear time to maintain disjoint sets. J. Comput. System Sci. 18 ( 1979 ), 110 - 127 . TARJAN, R. E. A class of algorithms which require nonlinear time to maintain disjoint sets. J. Comput. System Sci. 18 (1979), 110-127.

10.1137/0214019

10.1145/3828.3839

Thông tin
Thông tin xuất bản

Journal of the ACM

Tập 37 Số 2

200-212

Thông tin tác giả