Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility

摘要

In the 2D orthogonal range search problem, we want to pre-process a set of 2D points so that, given any axis-parallel query rectangle, we can report all the data points in the rectangle efficiently. This paper presents a lower bound on the query time that can be achieved by any external memory structure that stores a point at most r times, where r is a constant integer. Previous research has resolved the bound at two extremes: r = 1, and r being arbitrarily large. We, on the other hand, derive the explicit tradeoff at every specific r. A premise that lingers in existing studies is the so-called indivisibility assumption: all the information bits of a point are treated as an atom, i.e., they are always stored together in the same block. We partially remove this assumption by allowing a data structure to freely divide a point into individual bits stored in different blocks. The only assumption is that, those bits must be retrieved for reporting, as opposed to being computed we refer to this requirement as the weak indivisibility assumption. We also describe structures to show that our lower bound is tight up to only a small factor.