Two dimensional range minimum queries and Fibonacci lattices

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)O(N/c) bits additional space with O(clog⁡c(log⁡log⁡c)2)O(clog⁡c(log⁡log⁡c)2) query time, for any parameter c  , 4≤c≤N4≤c≤N. Also, when the entries of the input matrix are from {0,1}{0,1}, we show that the query time can be improved to O(clog⁡c)O(clog⁡c) with the same space usage.