Higher-dimensional Orthogonal Range Reporting and Rectangle Stabbing in the Pointer Machine Model

摘要

In this paper, we consider two fundamental problems in the pointer machine model of computation, namely orthogonal range reporting and rectangle stabbing. Orthogonal range reporting is the problem of storing a set of n points in d-dimensional space in a data structure, such that the t points in an axis-aligned query rectangle can be reported efficiently. Rectangle stabbing is the "dual" problem where a set of n axis-aligned rectangles should be stored in a data structure, such that the t rectangles that contain a query point can be reported efficiently. Very recently an optimal O(log n + t) query time pointer machine data structure was developed for the three-dimensional version of the orthogonal range reporting problem. However, in four dimensions the best known query bound of O(log~2 n/log log n + t) has not been improved for decades. We describe an orthogonal range reporting data structure that is the first structure to achieve significantly less than O(log~2 n +1) query time in four dimensions. More precisely, we develop a structure that uses O(n(log n/ log log n)~d) space and can answer d-dimensional orthogonal range reporting queries (ford > 4) in O(logn(logn/loglogn)~(d-4+1/(d-2))+t) time. Ignoring log log n factors, this speeds up the best previous query time by a log~(1-1/(d-2)) n factor. For the rectangle stabbing problem, we show that any data structure that uses nh space must use Ω(logn(log n/log h)d~2 + t) time to answer a query. This improves the previous results by a log h factor, and is the first lower bound that is optimal for a large range of h, namely for h > log~(d-2+ε) n where e > 0 is an arbitrarily small constant. By a simple geometric transformation, our result also implies an improved query lower bound for orthogonal range reporting.