Submatrix Maximum Queries in Monge Matrices and Partial Monge Matrices, and Their Applications
| Autor: | Micha Sharir, Shay Mozes, Haim Kaplan, Yahav Nussbaum |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
Range query (data structures) Inverse Digraph 0102 computer and information sciences 02 engineering and technology Data structure 01 natural sciences Planar graph Combinatorics symbols.namesake Matrix (mathematics) Mathematics (miscellaneous) 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering symbols 020201 artificial intelligence & image processing Rectangle Maxima Mathematics |
| Zdroj: | ACM Transactions on Algorithms. 13:1-42 |
| ISSN: | 1549-6333 1549-6325 |
| DOI: | 10.1145/3039873 |
| Popis: | We describe a data structure for submatrix maximum queries in Monge matrices or partial Monge matrices, where a query seeks the maximum element in a contiguous submatrix of the given matrix. The structure, for an n × n Monge matrix, takes O ( n log n ) space and O ( n log n ) preprocessing time, and answers queries in O (log 2 n ) time. For partial Monge matrices, the space grows by α( n ), the preprocessing grows by α( n )log n (α( n ) is the inverse Ackermann function), and the query remains O (log 2 n ). Our design exploits an interpretation of the column maxima in a Monge (partial Monge, respectively) matrix as an upper envelope of pseudo-lines (pseudo-segments, respectively). We give two applications: (1) For a planar set of n points in an axis-parallel rectangle B , we build a data structure, in O ( n α( n )log 4 n ) time and O ( n α( n )log 3 n ) space, that returns, for a query point p , the largest-area empty axis-parallel rectangle contained in B and containing p , in O (log 4 n ) time. This improves substantially the nearly quadratic storage and preprocessing obtained by Augustine et al. [2010]. (2) Given an n -node arbitrarily weighted planar digraph, with possibly negative edge weights, we build, in O ( n log 2 n /log log n ) time, a linear-size data structure that supports edge-weight updates and graph-distance queries between arbitrary pairs of nodes in O ( n 2/3 log 5/3 n ) time per operation. This improves a previous algorithm of Fakcharoenphol and Rao [2006]. Our data structure has already been applied in a recent maximum flow algorithm for planar graphs in Borradaile et al. [2011]. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|