We consider the  two-dimensional range maximum query (2D-RMQ)  problem: given an array  A  of ordered values, to pre-process it so that we can find the position of the largest element in a (user-specified) range of rows and range of columns. We focus on determining the  effective  entropy of 2D-RMQ, i.e., how many bits are needed to encode  A  so that 2D-RMQ queries can be answered  without  access to  A . We give tight upper and lower bounds on the expected effective entropy for the case when  A  contains independent identically-distributed random values, and new upper and lower bounds for arbitrary  A , for the case when  A  contains few rows. The latter results improve upon upper and lower bounds by Brodal et al. (ESA 2010). We also give some efficient data structures for 2D-RMQ whose space usage is close to the effective entropy.
['Mordecai J. Golin', 'John Iacono', 'Danny Krizanc', 'Rajeev Raman', 'S. Srinivasa Rao']
Encoding 2d range maximum queries