Two Dimensional Range Minimum Queries and Fibonacci Lattices

Gerth Stølting Brodal, Pooya Davoodi, Moshe Lewenstein, Rajeev Raman, and S. Srinivasa Rao

In Proc. 20th Annual European Symposium on Algorithms, volume 7501 of Lecture Notes in Computer Science, pages 217-228. Springer Verlag, Berlin, 2012.

Abstract

Given a matrix of size N, two dimensional range minimum queries (2D-RMQs) ask for the position of the minimum element in a rectangular range within the matrix. We study trade-offs between the query time and the additional space used by indexing data structures that support 2D-RMQs. Using a novel technique-the discrepancy properties of Fibonacci lattices-we give an indexing data structure for 2D-RMQs that uses O(N/c) bits additional space with O(clog c(log log c)2) query time, for any parameter c, 4 ≤ cN. Also, when the entries of the input matrix are from {0,1}, we show that the query time can be improved to O(clog c) with the same space usage.

Copyright notice

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

Online version

esa12.pdf (308 Kb)

DOI

10.1007/978-3-642-33090-2_20

BIBTEX entry

@incollection{esa12,
  author = "Gerth St{\o}lting Brodal and Pooya Davoodi and Moshe Lewenstein and Rajeev Raman and S. Srinivasa Rao",
  booktitle = "Proc. 20th Annual European Symposium on Algorithms",
  doi = "10.1007/978-3-642-33090-2_20",
  isbn = "978-3-642-33089-6",
  pages = "217-228",
  publisher = "Springer {V}erlag, Berlin",
  series = "Lecture Notes in Computer Science",
  title = "Two Dimensional Range Minimum Queries and Fibonacci Lattices",
  volume = "7501",
  year = "2012"
}