In Algorithmica, Special issue on ESA 2010, volume 63(4), pages 815-830, 2012.
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 ≤ c ≤ N. 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(clog^{2} 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 m≤ n. 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
BIBT_{E}X 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