# On Space Efficient Two Dimensional Range Minimum Data Structures

## Gerth Stølting Brodal, Pooya Davoodi, and S. Srinivasa Rao

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 ≤ cN. 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(clog2 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 mn. This leaves a gap to the lower bound of Ω(Nlog m) bits for this version of the problem.

Online version

esa10.pdf (215 Kb)

DOI

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

Slides

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

BIBTEX 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"
}
```