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

68P05 Data structures
Full Text: DOI