# zbMATH — the first resource for mathematics

Two dimensional range minimum queries and Fibonacci lattices. (English) Zbl 1365.68172
Epstein, Leah (ed.) et al., Algorithms – ESA 2012. 20th annual European symposium, Ljubljana, Slovenia, September 10–12, 2012. Proceeding. Berlin: Springer (ISBN 978-3-642-33089-6/pbk). Lecture Notes in Computer Science 7501, 217-228 (2012).
Summary: 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(\log \log c)^{2})$$ query time, for any parameter $$c$$, $$4 \leq c \leq 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.
For the entire collection see [Zbl 1246.68031].

##### MSC:
 68P05 Data structures
Full Text: