On Space Efficient Two Dimensional Range Minimum Data Structures

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

In Algorithmica, Special issue on ESA 2010, volume 63(4), pages 815-830, 2012.

Abstract

The two dimensional range minimum query problem is to preprocess a static m by n matrix (two dimensional 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 a data structure of size O(N/c) bits requires Ω(c) query time, for any c where 1 ≤ cN. This lower bound holds for arrays of 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 which can be preprocessed in O(N) time to support O(clog2 c) query time. For c=O(1), this is the first O(1) query time algorithm using a data structure of optimal size O(N) bits. 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 space lower bound of Ω(Nlog m) bits for this version of the problem.

Copyright notice

© Springer-Verlag Berlin Heidelberg 2011. All rights reserved.

Online version

algorithmica12min.pdf (181 Kb)

DOI

10.1007/s00453-011-9499-0

BIBTEX entry

@article{algorithmica12min,
  author = "Gerth St{\o}lting Brodal and Pooya Davoodi and S. Srinivasa Rao",
  doi = "10.1007/s00453-011-9499-0",
  issn = "0178-4617",
  journal = "Algorithmica, Special issue on ESA 2010",
  number = "4",
  pages = "815-830",
  title = "On Space Efficient Two Dimensional Range Minimum Data Structures",
  volume = "63",
  year = "2012"
}

Other versions