# On Space Efficient Two Dimensional Range Minimum Data Structures

In * Proc. 18th Annual European Symposium on Algorithms*, volume 6347 of * Lecture Notes in Computer Science*, pages 171-182. Springer Verlag, Berlin, 2010.

## Abstract

The two dimensional range minimum query problem is to preprocess a
static two dimensional *m* by *n* array *A* of size *N*=*m*· *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*. This lower bound holds for any dimension. In particular,
for the one dimensional version of the problem, the lower bound is
tight up to a constant factor. 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. For *c*=*O*(1), this is the first
*O*(1) query time algorithm using optimal *O*(*N*) bits additional
space. 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.

**Copyright notice**
© Springer-Verlag Berlin Heidelberg 2010. All rights reserved.

**Online version**

esa10.pdf (215 Kb)

**DOI**

10.1007/978-3-642-15781-3_15

**Slides**
esa10.pdf (1110 Kb), esa10.pptx (654 Kb)

**BIBT**_{E}X entry

@incollection{esa10,
author = "Gerth St{\o}lting Brodal and Pooya Davoodi and S. Srinivasa Rao",
booktitle = "Proc. 18th Annual European Symposium on Algorithms",
doi = "10.1007/978-3-642-15781-3_15",
isbn = "978-3-642-15780-6",
pages = "171-182",
publisher = "Springer {V}erlag, Berlin",
series = "Lecture Notes in Computer Science",
title = "On Space Efficient Two Dimensional Range Minimum Data Structures",
volume = "6347",
year = "2010"
}

l>