paper.pdf (386.86 kB)
Two Dimensional Range Minimum Queries and Fibonacci Lattices
journal contribution
posted on 2016-05-06, 09:25 authored by Gerth Stølting Brodal, Pooya Davoodi, Moshe Lewenstein, Rajeev Raman, Satti Srinivasa RaoGiven 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.
History
Citation
Theoretical Computer Science, 2016, DOI: 10.1016/j.tcs.2016.02.016Author affiliation
/Organisation/COLLEGE OF SCIENCE AND ENGINEERING/Department of Computer ScienceVersion
- AM (Accepted Manuscript)