Foundations of Computer Science Seminar Haim Kaplan Tel Aviv University will speak on Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications Abstract: We describe a data structure for submatrix maximum queries in Monge matrices or Monge partial matrices, where a query specifies a contiguous submatrix of the given matrix, and its output is the maximum element of that submatrix. Our data structure for an $n \times n$ Monge matrix takes $O(n \log n)$ space, $O(n \log^2 n)$ preprocessing time, and can answer queries in $O(\log^2 n)$ time. For a Monge partial matrix the space bound and the preprocessing time both grow by the small factor $\alpha(n)$, where $\alpha(n)$ is the inverse Ackermann function. We apply our data structure to get more efficient algorithms for the following problems: (1) Given a set of $n$ points in a rectangle $B$ in the plane, build a data structure that, given a query point $p$, returns the largest-area empty axis-parallel rectangle contained in $B$ and containing $p$. (2) Given an $n$-node arbitrarily weighted planar digraph, with possibly negative edge weights, build a data structure that supports efficient edge-weight updates and distance queries between arbitrary pairs of nodes Our data structure has already been applied in a recent maximum flow algorithm for planar graphs of Borradaile et al.\ [FOCS 2011]. Joint with Shay Mozes, Yahav Nussbaum and Micha Sharir. The lecture will take place in the Seminar Room, Room 261, Ziskind Building on Monday, Feb 13, 2012 14:30 - 15:30

Faculty of Mathematics and Computer Science The Weizmann Institute of Science POB 26, Rehovot 76100, ISRAEL Tel: 972-8-934-3540     Fax: 972-8-934-4122 This file was last modified on Monday, 13-Feb-2012 03:00:06 IST.