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.

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)

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