Submatrix Maximum Queries in Monge Matrices and Partial Monge Matrices, and Their Applications

DOI10.1145/3039873zbMath1446.68041OpenAlexW2592415985MaRDI QIDQ4962663

Haim Kaplan, Yahav Nussbaum, Shay Mozes, Micha Sharir

Publication date: 5 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3039873

zbMATH Keywords

planar graphsMonge matrixpseudo-linerange querydynamic distance oracleempty rectanglespseudo-segment

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Special matrices (15B99)

Related Items (7)

Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time ⋮ Unnamed Item ⋮ Faster shortest paths in dense distance graphs, with applications ⋮ Empty squares in arbitrary orientation among points ⋮ Fault-tolerant distance labeling for planar graphs ⋮ Single-source shortest paths and strong connectivity in dynamic planar graphs ⋮ Fault-tolerant distance labeling for planar graphs

This page was built for publication: Submatrix Maximum Queries in Monge Matrices and Partial Monge Matrices, and Their Applications