Pooya Davoodi

The two dimensional range minimum query problem is to preprocess a
static two dimensional array *A* of size *m*×*n*=*N* such that
subsequent queries, asking for the position of the minimum element in a
rectangular range within *A*, can be answered efficiently. We study the
trade-off between the space and query time of the problem. We show that
every algorithm enabled to access *A* during the query and
using *O*(*N*/*c*) bits additional space requires Ω(*c*) query time,
for any *c* where 1 ≤ *c* ≤ *N*. In particular, this lower
bound holds for the one dimensional version of the problem. We
complement this lower bound with an indexing data structure of
size *O*(*N*/*c*)$ bits additional space which can be preprocessed in *O*(*N*)
time and achieves *O*(*c* log^{2} *c*) query time. For *c*=*O*(1), this is the
first optimal algorithm using *O*(*N*) bits additional space achieving
*O*(1) query time. For the case where queries can not probe *A*, we give
a data structure of size *O*(*N*·min{*m*,log *n*}) bits with *O*(1)
query time, assuming *m*≤*n*. This leaves a gap to the lower bound of
Ω(*N* log *m*) bits for this version of the problem.