Kolloquiumsvortrag: Dr. Pawel Gawrychowski, MPI Informatik

22.11.2013 von 14:15 bis 16:00


Improved Submatrix Maximum Queries in Monge Matrices


We present efficient data structures for submatrix maximum queries in Monge matrices and Monge partial matrices. For n x n Monge matrices, we give a datastructure that requires O(n) space and answers submatrix maximum queries in O(log n) time. The best previous data structure [Kaplan et al., SODA`12] required O(n log n) space and O(log^2 n) query time. We also give an alternative data structure with constant query-time and O(n^{1+e}) construction time and space for any fixed e<1. For n x n partial Monge matrices we obtain a data structure with O(n) space and O(log n * alpha(n)) query time. The data structure of Kaplan et al. required O(n log n * alpha(n)) space and O(log^2 n) query time. Our improvements are enabled by a technique for exploiting the structure of the upper envelope of Monge matrices to efficiently report column maxima in skewed rectangular Monge matrices. We hope this technique can be useful in obtaining faster search algorithms in Monge partial matrices. In addition, we give a linear upper bound on the number of breakpoints in the upper envelope of a Monge partial matrix. This shows that the inverse Ackermann alpha(n) term in the analysis of the data structure of Kaplan et. al is superfluous.

Prof. Dr. Dirk Nowotka

Diesen Termin meinem iCal-Kalender hinzufügen