@inbook {IOPORT.06086324,
    author       = {Brodal, Gerth St{\o}lting and Davoodi, Pooya and Lewenstein, Moshe and Raman, Rajeev and Srinivasa Rao, Satti},
    title        = {Two dimensional range minimum queries and Fibonacci lattices.},
    year         = {2012},
    booktitle    = {Algorithms -- ESA 2012. 20th annual European symposium, Ljubljana, Slovenia, September 10--12, 2012. Proceeding},
    isbn         = {978-3-642-33089-6},
    pages        = {217-228},
    publisher    = {Berlin: Springer},
    doi          = {10.1007/978-3-642-33090-2_20},
    abstract     = {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.},
    identifier   = {06086324},
}