TY - GEN

T1 - Near-optimal randomized algorithms for selection in totally monotone matrices

AU - Chan, Timothy M.

N1 - Funding Information:
This research has been supported in part by NSF Grant CCF-1814026.
Publisher Copyright:
Copyright © 2021 by SIAM

PY - 2021

Y1 - 2021

N2 - 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(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 Pi 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].

AB - 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(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 Pi 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].

UR - http://www.scopus.com/inward/record.url?scp=85105268714&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85105268714&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85105268714

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1483

EP - 1495

BT - ACM-SIAM Symposium on Discrete Algorithms, SODA 2021

A2 - Marx, Daniel

PB - Association for Computing Machinery

T2 - 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021

Y2 - 10 January 2021 through 13 January 2021

ER -