Aarhus University Seal

Two Dimensional Range Minimum Queries and Fibonacci Lattices

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

  • Gerth Stølting Brodal
  • Pooya Davoodi, Polytechnic Institute of New York University, United States
  • Moshe Lewenstein, Bar-Ilan University, Israel
  • Rajeev Raman, University of Leicester, United Kingdom
  • Satti Srinivasa Rao, Seoul National University, Korea, Republic of
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(clogc(loglogc)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(clogc) with the same space usage
Original languageEnglish
Book seriesLecture Notes in Computer Science
Pages (from-to)217-228
Number of pages12
Publication statusPublished - 2012
EventAnnual European Symposium on Algorithms - Ljubljana, Slovenia
Duration: 10 Sept 201212 Sept 2012
Conference number: 20


ConferenceAnnual European Symposium on Algorithms

Bibliographical note

Title of the vol.: Algorithms – ESA 2012 : 20th Annual European Symposium, Ljubljana, Slovenia, September 10-12, 2012. Proceedings / eds.: Leah Epstein, Paolo Ferragina.
ISBN: 978-3-642-33089-6, 978-3-642-33090-2

See relations at Aarhus University Citationformats

ID: 52195169