Two dimensional range minimum queries and Fibonacci lattices

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Gerth Stølting Brodal
  • Pooya Davoodi, New York University
  • ,
  • Moshe Lewenstein, Bar-Ilan University
  • ,
  • Rajeev Raman, University of Leicester
  • ,
  • Srinivasa Rao Satti, Seoul National University

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≤c≤N. 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.

Original languageEnglish
JournalTheoretical Computer Science
Volume638
Pages (from-to)33-43
Number of pages11
ISSN0304-3975
DOIs
Publication statusPublished - 25 Jul 2016

    Research areas

  • Fibonacci lattices, Pattern matching, Range minimum queries

See relations at Aarhus University Citationformats

ID: 109021539