Succinct Indices for Range Queries with applications to Orthogonal Range Maxima

Abstract

We consider the problem of preprocessing $N$ points in 2D, each endowed with a priority, to answer the following queries: given a axis-parallel rectangle, determine the point with the largest priority in the rectangle. Using the ideas of the \emph{effective entropy} of range maxima queries and \emph{succinct indices} for range maxima queries, we obtain a structure that uses O(N) words and answers the above query in $O(\log N\log \log N)$ time. This is a direct improvement of Chazelle's result from FOCS 1985 for this problem -- Chazelle required $O(N/\epsilon )$ words to answer queries in $O((\log N{)}^{1+\epsilon })$ time for any constant $\epsilon >0$.

To appear in ICALP 2012