Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Two Dimensional Range Minimum Queries and Fibonacci Lattices
verfasst von : Gerth Stølting Brodal, Pooya Davoodi, Moshe Lewenstein, Rajeev Raman, Satti Srinivasa Rao
Erschienen in: Algorithms – ESA 2012
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
(
c
log
c
(loglog
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
(
c
log
c
) with the same space usage.