In Proc. 18th Annual European Symposium on Algorithms, volume 6347 of Lecture Notes in Computer Science, pages 171-182. Springer Verlag, Berlin, 2010.
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 ≤ c ≤ N. 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 m≤ n. 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
Slidesesa10.pptx (654 Kb)
BIBTEX entry
@incollection{esa10,
author = "Gerth Stø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"
}