(Near-)Linear-Time Randomized Algorithms for Row Minima in Monge Partial Matrices and Related Problems

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.