Submatrix Maximum Queries in Monge Matrices are Equivalent to Predecessor Search

Abstract

We present an optimal data structure for submatrix maximum queries in n x n Monge matrices. Our result is a two-way reduction showing that the problem is equivalent to the classical predecessor problem in a universe of polynomial size. This gives a data structure of O(n) space that answers submatrix maximum queries in O(loglogn) time. It also gives a matching lower bound, showing that O(loglogn) query-time is optimal for any data structure of size O(n polylog(n)). Our result concludes a line of improvements that started in SODA'12 with O(log^2 n) query-time and continued in ICALP'14 with O(log n) query-time. Finally, we show that partial Monge matrices can be handled in the same bounds as full Monge matrices. In both previous results, partial Monge matrices incurred additional inverse-Ackerman factors.