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⁴/³ polylog n) expected time; this improves previous O(n³/² 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⁴/³) 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⁶/⁵ polylog n). • Variants of all these bounds that are sensitive to K (or ^P_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⁴/³ 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].