2007 | OriginalPaper | Chapter
Two-Dimensional Range Minimum Queries
Authors : Amihood Amir, Johannes Fischer, Moshe Lewenstein
Published in: Combinatorial Pattern Matching
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.