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

Paweł Gawrychowski, Adam Górkiewicz, Srinivasa Rao Satti

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 e…