Near-Optimal and Efficient Encoding for Two-Dimensional Range Minimum Queries
For data structures researchers, this provides a new trade-off between space and query time for 2D RMQ, though the improvement is incremental over existing results.
The paper tackles the problem of encoding a 2D array to support range maximum queries efficiently. It achieves near-optimal space (O(κ mn (log m + log log n)) bits) with query time O(log^{1/κ} n), improving over prior work that either had suboptimal space or no query time guarantee.
We consider the 2D RMQ encoding problem: given an $m\times n$ array of $mn$ elements over a total order, encode it such that, for any query rectangle, the position of its maximum element can be reported without accessing the original array. For $m \le n$, it is known how to encode the array in $O(mn \min\{m, \log n\})$ bits with $O(1)$-time queries [Brodal et al., Algorithmica 2012], and also how to obtain an asymptotically optimal encoding consisting of $O(mn \log m)$ bits [Brodal et al., ESA 2013]. However, the latter approach does not prove any guarantee on the query time, and it appears to be inherently sequential: it requires scanning the whole encoding to answer a query. We design a different encoding that uses near-optimal space while allowing for efficient queries. More concretely, for every parameter $κ\in[1, \log\log n]$, our encoding uses $O(κmn(\log m+\log\log n))$ bits and answers 2D RMQ queries in $O(\log^{1/κ}n)$ time.