Two dimensional range minimum queries and Fibonacci lattices

Gerth Stølting Brodal; Pooya Davoodi; Moshe Lewenstein; Rajeev Raman; Srinivasa Rao Satti

doi:10.1016/j.tcs.2016.02.016

Two dimensional range minimum queries and Fibonacci lattices

Gerth Stølting Brodal, Pooya Davoodi, Moshe Lewenstein^*, Rajeev Raman, Srinivasa Rao Satti

^*Corresponding author for this work

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review

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.

Original language	English
Journal	Theoretical Computer Science
Volume	638
Pages (from-to)	33-43
Number of pages	11
ISSN	0304-3975
DOIs	https://doi.org/10.1016/j.tcs.2016.02.016
Publication status	Published - 25 Jul 2016

Keywords

Fibonacci lattices
Pattern matching
Range minimum queries

Access to Document

10.1016/j.tcs.2016.02.016

Cite this

@article{06252697861f4a1989fcb3551a96c72a,

title = "Two dimensional range minimum queries and Fibonacci lattices",

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)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.",

keywords = "Fibonacci lattices, Pattern matching, Range minimum queries",

author = "{St{\o}lting Brodal}, Gerth and Pooya Davoodi and Moshe Lewenstein and Rajeev Raman and Satti, {Srinivasa Rao}",

year = "2016",

month = jul,

day = "25",

doi = "10.1016/j.tcs.2016.02.016",

language = "English",

volume = "638",

pages = "33--43",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier BV",

}

TY - JOUR

T1 - Two dimensional range minimum queries and Fibonacci lattices

AU - Stølting Brodal, Gerth

AU - Davoodi, Pooya

AU - Lewenstein, Moshe

AU - Raman, Rajeev

AU - Satti, Srinivasa Rao

PY - 2016/7/25

Y1 - 2016/7/25

N2 - 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.

AB - 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.

KW - Fibonacci lattices

KW - Pattern matching

KW - Range minimum queries

UR - http://www.scopus.com/inward/record.url?scp=84979465407&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2016.02.016

DO - 10.1016/j.tcs.2016.02.016

M3 - Journal article

AN - SCOPUS:84979465407

SN - 0304-3975

VL - 638

SP - 33

EP - 43

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Two dimensional range minimum queries and Fibonacci lattices

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this