Near-Optimal Randomized Algorithms for Selection in Totally Monotone Matrices
Near-Optimal Randomized Algorithms for Selection in Totally Monotone Matrices
复制标题
DOI：
10.1137/1.9781611976465.89
复制
发表时间：
2021-01
期刊：
影响因子：
--
通讯作者：
Timothy M. Chan
中科院分区：
文献类型：
--
作者：
Timothy M. Chan
我们重新审视有关在完全单调矩阵中搜索的经典问题，这些矩阵在计算几何和其他领域中具有许多应用。在同伴论文中，我们为许多此类问题提供了新的（近）线性时间算法。在本文中，我们描述了更多基本问题的新的次级次级结果，包括以下内容：
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: