Near-Optimal and Efficient Encoding for Two-Dimensional Range Minimum Queries

Abstract

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 $\hat{I}º\in [1,\log \log n]$, our encoding uses $O(\hat{I}ºmn(\log m+\log \log n))$ bits and answers 2D RMQ queries in $O({\log }^{1/\hat{I}º}n)$ time.

to appear in ESA 2026