Submatrix Maximum Queries in Monge and Partial Monge Matrices Are Equivalent to Predecessor Search
| Autor: | Oren Weimann, Paweł Gawrychowski, Shay Mozes |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
0209 industrial biotechnology
Polynomial Reduction (recursion theory) Matching (graph theory) 0102 computer and information sciences 02 engineering and technology Binary logarithm Space (mathematics) Data structure 01 natural sciences Upper and lower bounds Combinatorics 020901 industrial engineering & automation Mathematics (miscellaneous) 010201 computation theory & mathematics Log-log plot Mathematics |
| Zdroj: | ACM Transactions on Algorithms. 16:1-24 |
| ISSN: | 1549-6333 1549-6325 |
| DOI: | 10.1145/3381416 |
| Popis: | We present an optimal data structure for submatrix maximum queries in n × 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 (log log n ) time, as well as a matching lower bound, showing that O (log log n ) query-time is optimal for any data structure of size O ( n polylog( n )). Our result settles the problem, improving on the O (log 2 n ) query time in SODA’12, and on the O (log n ) query-time in ICALP’14. In addition, 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-Ackermann factors. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|