Selection in monotone matrices and computing kth nearest neighbors

Abstract

An m×n matrix A=(a_{i, j}), 1≤i≤m and 1≤j≤n, is called a totally monotone matrix if for all i₁, i₂, j₁, j₂, satisfying 1≤i₁<i₂≤m, 1≤j₁<j₂≤n. a_i1,j1<a_i1,j2⇒a_i2,j1<a_i2,j2. We present an O((m+n)√nlog n) time algorithm to select the kth smallest item from an m×n totally monotone matrix for any k≤mn. This is the first subquadratic algorithm for selecting an item from a totally monotone matrix. Our method also yields an algorithm of the same time complexity for ageneralized row-selection problemin monotone matrices. Given a set S={p₁,..., p_n} of n points in convex position and a vectork={k₁,..., k_n}, we also present an O(n^4/3log^c n) algorithm to compute the k_ith nearest neighbor of p_i for every i≤n; herecis an appropriate constant. This algorithm is considerably faster than the one based on a row-selection algorithm for monotone matrices. If the points of S are arbitrary, then the k_ith nearest neighbor of p_i, for all i≤n, can be computed in time O(n^7/5log^c n), which also improves upon the previously best-known result.