Near-Optimal Randomized Algorithms for Selection in Totally Monotone Matrices
Timothy M. Chan · Society for Industrial and Applied Mathematics eBooks · 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 sub-quadratic 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(n4/3 polylog n) expected time; this improves previous O(n3/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 Ω(n4/3) for the problem (which holds even for Monge matrices). A similar result for selecting the ki-th smallest in the i-th row for all i. In the case when all ki's are the same, an improvement of the running time to O(n6/5 polylog n). Variants of all these bounds that are sensitive to K (or Σi ki). These matrix searching problems are intimately related to problems about arrangements of pseudo-lines. In particular, our selection algorithm implies an O(n4/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].