SELECTION IN MONOTONE MATRICES AND COMPUTING KTH NEAREST NEIGHBORS

An m x n matrix A = (a(i,j)), 1 less than or equal to i less than or e qual to m and 1 less than or equal to j less than or equal to n, is ca lled a totally monotone matrix if for all i(1), i(2),j(1),j(2), satisf ying 1 less than or equal to i(1) < i(2) less than or equal to m, 1 le ss than or equal to j(1) < j(2) less than or equal to n. a(i1,J1) < a( i1,j2) double right arrow a(i2,j1) < a(i2,j2). We present an O((m + n) root n log n) time algorithm to select the kth smallest item from an m x n totally monotone matrix for any k less than or equal to mn. This is the first sub-quadratic algorithm for selecting an item from a tota lly monotone matrix Our method also yields an algorithm of the same ti me complexity for a generalized row-selection problem in monotone matr ices. Given a set S = {p(1),..., p(n)} of n points in convex position and a vector k = {k(1),...,k(n)}, we also present an O(n(4/3)log(c) n) algorithm to compute the k(i)th nearest neighbor of p(i) for every i less than or equal to n; here c is an appropriate constant. This algor ithm is considerably faster than the one based on a row-selection algo rithm for monotone matrices. If the points of S are arbitrary, then th e k(i)th nearest neighbor of p(i), for all i less than or equal to n, can be computed in time O(n(7/5) log(c) n), which also improves upon t he previously best known result. (C) 1996 Academic Press, Inc.