# On Space Efficient Two Dimensional Range Minimum Data Structures

## Darren Strash

The two dimensional range minimum query problem is to preprocess a
static two-dimensional matrix *A* with *N* elements so that reporting
the minimum element in a rectangular range can be done efficiently. 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*. This lower bound
holds for any dimension. In two dimensions, we complement the 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. Taking *c* to be O(1), this is the first O(1) query time
algorithm using optimal O(*N*) bits additional space.

(Based on a paper by Brodal, Davoodi, and Rao at ESA 2010.)