# The Encoding Complexity of Two Dimensional Range Minimum Data Structures

In * Proc. 21st Annual European Symposium on Algorithms*, volume 8125 of * Lecture Notes in Computer Science*, pages 229-240. Springer Verlag, Berlin, 2013.

## Abstract

In the two-dimensional range minimum query problem an input matrix *A*
of dimension *m* x *n*, *m*≤ *n*, has to be preprocessed into a
data structure such that given a query rectangle within the matrix,
the position of a minimum element within the query range can be
reported. We consider the space complexity of the encoding variant of
the problem where queries have access to the constructed data
structure but can not access the input matrix *A*, i.e. all
information must be encoded in the data structure. Previously it was
known how to solve the problem with space *O*(*m**n*min{*m*,log *n*}) bits
(and with constant query time), but the best lower bound was
Ω(*m**n*log *m*) bits, i.e. leaving a gap between the upper and
lower bounds for non-quadratic matrices. We show that this space lower
bound is optimal by presenting an encoding scheme using *O*(*m**n*log *m*)
bits. We do not consider query time.

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

**Online version**

esa13rmq.pdf (323 Kb)

**DOI**

10.1007/978-3-642-40450-4_20

**Slides**
esa13rmq.pdf (569 Kb), esa13rmq.pptx (359 Kb)

**BIBT**_{E}X entry

@incollection{esa13rmq,
author = "Gerth St{\o}lting Brodal and Andrej Brodnik and Pooya Davoodi",
booktitle = "Proc. 21st Annual European Symposium on Algorithms",
doi = "10.1007/978-3-642-40450-4_20",
isbn = "0302-9743",
pages = "229-240",
publisher = "Springer {V}erlag, Berlin",
series = "Lecture Notes in Computer Science",
title = "The Encoding Complexity of Two Dimensional Range Minimum Data Structures",
volume = "8125",
year = "2013"
}

l>