Two Dimensional Range Minimum Queries and Fibonacci Lattices

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

In Theoretical Computer Science, volume 638, pages 33-43, 2016.

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(loglog 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

Copyright © 2016 by Elsevier Inc.. All rights reserved.

Online version

tcs16.pdf (387 Kb)

DOI

10.1016/j.tcs.2016.02.016

BIBTEX entry

@article{tcs16,
  author = "Gerth St{\o}lting Brodal and Pooya Davoodi and Moshe Lewenstein and Rajeev Raman and S. Srinivasa Rao",
  doi = "10.1016/j.tcs.2016.02.016",
  issn = "0304-3975",
  journal = "Theoretical Computer Science",
  pages = "33-43",
  title = "Two Dimensional Range Minimum Queries and Fibonacci Lattices",
  volume = "638",
  year = "2016"
}