2007 | OriginalPaper | Buchkapitel
Two-Dimensional Range Minimum Queries
verfasst von : Amihood Amir, Johannes Fischer, Moshe Lewenstein
Erschienen in: Combinatorial Pattern Matching
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
We consider the two-dimensional Range Minimum Query problem: for a static (
m
×
n
)-matrix of size
N
=
mn
which may be preprocessed, answer on-line queries of the form “where is the position of a minimum element in an axis-parallel rectangle?”. Unlike the one-dimensional version of this problem which can be solved in provably optimal time and space, the higher-dimensional case has received much less attention. The only result we are aware of is due to Gabow, Bentley and Tarjan [1], who solve the problem in
O
(
N
log
N
) preprocessing time and space and
O
(log
N
) query time. We present a class of algorithms which can solve the 2-dimensional RMQ-problem with
O
(
kN
) additional space,
preprocessing time and
O
(1) query time for any
k
> 1, where
denotes the iterated application of
k
+ 1 logarithms. The solution converges towards an algorithm with
preprocessing time and space and
O
(1) query time. All these algorithms are significant improvements over the previous results: query time is optimal, preprocessing time is quasi-linear in the input size, and space is linear. While this paper is of theoretical nature, we believe that our algorithms will turn out to have applications in different fields of computer science, e.g., in computational biology.