Please use this identifier to cite or link to this item:
Title: Two Dimensional Range Minimum Queries and Fibonacci Lattices
Authors: Brodal, Gerth Stølting
Davoodi, Pooya
Lewenstein, Moshe
Raman, Rajeev
Srinivasa Rao, Satti
First Published: 17-Feb-2016
Publisher: Elsevier
Citation: Theoretical Computer Science, 2016, DOI: 10.1016/j.tcs.2016.02.016
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) ²) 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.
DOI Link: 10.1016/j.tcs.2016.02.016
ISSN: 0304-3975
Version: Post-print
Status: Peer-reviewed
Type: Journal Article
Rights: Copyright © the authors, 2016. After an embargo period this version will be an open-access article distributed under the terms of the Creative Commons Attribution-Non Commercial-No Derivatives License ( ), which permits use and distribution in any medium, provided the original work is properly cited, the use is non-commercial and no modifications or adaptations are made.
Description: The file associated with this record is under a 24-month embargo from publication in accordance with the publisher's self-archiving policy. The full text may be available through the publisher links provided above.
Appears in Collections:Published Articles, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
paper.pdfPost-review (final submitted)386.86 kBAdobe PDFView/Open

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.