University of Leicester
Browse
paper.pdf (386.86 kB)

Two Dimensional Range Minimum Queries and Fibonacci Lattices

Download (386.86 kB)
journal contribution
posted on 2016-05-06, 09:25 authored by Gerth Stølting Brodal, Pooya Davoodi, Moshe Lewenstein, Rajeev Raman, Satti Srinivasa Rao
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.

History

Citation

Theoretical Computer Science, 2016, DOI: 10.1016/j.tcs.2016.02.016

Author affiliation

/Organisation/COLLEGE OF SCIENCE AND ENGINEERING/Department of Computer Science

Version

  • AM (Accepted Manuscript)

Published in

Theoretical Computer Science

Publisher

Elsevier

issn

0304-3975

Acceptance date

2016-02-12

Copyright date

2016

Available date

2018-02-17

Publisher version

http://www.sciencedirect.com/science/article/pii/S0304397516001389

Notes

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.

Language

en

Usage metrics

    University of Leicester Publications

    Categories

    Exports