{"ID":5937804,"CreatedAt":"2026-07-07T03:14:33.014478982Z","UpdatedAt":"2026-07-08T21:19:27.062958272Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.04509","arxiv_id":"2607.04509","title":"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 $κ\\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.","short_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\\})$...","url_abs":"https://arxiv.org/abs/2607.04509","url_pdf":"https://arxiv.org/pdf/2607.04509v1","authors":"[\"Paweł Gawrychowski\",\"Adam Górkiewicz\",\"Srinivasa Rao Satti\"]","published":"2026-07-05T21:19:21Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}