(Near-)Linear-Time Randomized Algorithms for Row Minima in Monge Partial Matrices and Related Problems
Timothy M. Chan · Society for Industrial and Applied Mathematics eBooks · 2021
We revisit classical problems about searching in totally monotone and Monge matrices, which have many applications in computational geometry and other areas. We present a number of new results, including the following: A randomized algorithm that finds the row minima in an n × n Monge staircase matrix in O(n) expected time; this improves a longstanding O(nα(n)) bound by Klawe and Kleitman (1990) for totally monotone staircase matrices. A randomized algorithm that reports the K smallest elements (in an arbitrary order) in an n × n Monge (complete or staircase) matrix in O(n + K) expected time; this improves and extends a previous O(n + K log n) algorithm by Kravets and Park [SODA'90]. A randomized algorithm that reports the K smallest elements (in an arbitrary order) in an n × n totally monotone (complete) matrix in O(n + K log∗ n) expected time. A randomized algorithm that reports the ki smallest elements in the i-th row, for every i, in an n × n totally monotone (complete) matrix in O((n + K) log∗ n) expected time, where K = Σi ki. A randomized algorithm that finds the row minima in an n × n totally monotone “v-matrix” in O(nα(n) log∗ n log log n) expected time; this answers an open question by Klawe [SODA'90]. The log∗ n factor can be removed in the Monge case.