The Encoding Complexity of Two Dimensional Range Minimum Data Structures

Gerth Stølting Brodal, Andrej Brodnik, and Pooya Davoodi

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, mn, 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(mnmin{m,log n}) bits (and with constant query time), but the best lower bound was Ω(mnlog 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(mnlog 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)

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