Near-Optimal Randomized Algorithms for Selection in Totally Monotone Matrices

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 × 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 et al. (1993), and Agarwal and Sen (1996).

• A near-matching lower bound of Ω(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 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].