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 x n Monge staircase matrix in O(n) expected time; this improves a longstanding O(n alpha(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 x 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 x n totally monotone (complete) matrix in O(n + K log^* n) expected time.
- A randomized algorithm that reports the k_i smallest elements in the i-th row, for every i, in an n x n totally monotone (complete) matrix in O((n + K) log^* n) expected time, where K = sum_i k_i.
- A randomized algorithm that finds the row minima in an n x n totally monotone "v-matrix" in O(n alpha(n) log^* n loglog n) expected time; this answers an open question by Klawe [SODA'90]. The log^* n factor can be removed in the Monge case.

- To appear in Proc. 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021

We revisit classical problems about searching in totally monotone matrices, which have many applications in computational geometry and other areas. In a companion paper, we gave new (near-)linear-time algorithms for a number of such problems. In the present paper, we describe new subquadratic results for more basic problems, including the following:

- A randomized algorithm to select the K-th smallest element in an n x n totally monotone matrix in O(n^{4/3} polylog n) expected time; this improves previous O(n^{3/2} polylog n) algorithms by Alon and Azar [SODA'92], Mansour, Park, Schieber, and Sen (1993), and Agarwal and Sen (1996).
- A near-matching lower bound of Omega(n^{4/3}) for the problem (which holds even for Monge matrices).
- A similar result for selecting the k_i-th smallest in the i-th row for all i.
- In the case when all k_i's are the same, an improvement of the running time to O(n^{6/5} polylog n).
- Variants of all these bounds that are sensitive to K (or sum_i k_i).

These matrix searching problems are intimately related to problems about arrangements of pseudo-lines. In particular, our selection algorithm implies an O(n^{4/3} polylog n) algorithm for computing incidences between n points and n pseudo-lines in the plane. This improves, extends, and simplifies a previous method by Agarwal and Sharir [SODA'02].

- To appear in Proc. 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021

The documents contained in this directory are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Timothy Chan (Last updated Nov 2020)