Selection in monotone matrices and computing kth nearest neighbors

An m×n matrix A=(a<SUB>i, j</SUB>), 1≤i≤m and 1≤j≤n, is called a totally monotone matrix if for all i<SUB>1</SUB>, i<SUB>2</SUB>, j<SUB>1</SUB>, j<SUB>2</SUB>, satisfying 1≤i<SUB>1</SUB>&lt;i<SUB>2</SUB>≤m, 1≤j<SUB>1</SUB>&lt;j<SUB>2</SUB>≤n. a<SUB>i<SUB>1</SUB>,j<SUB>1</SUB></SUB>&lt;a<SUB>i<SUB>1</SUB>,j<SUB>2</SUB></SUB>⇒a<SUB>i<SUB>2</SUB>,j<SUB>1</SUB></SUB>&lt;a<SUB>i<SUB>2</SUB>,j<SUB>2</SUB></SUB>. 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<SUB>1</SUB>,..., p<SUB>n</SUB>} of n points in convex position and a vectork={k<SUB>1</SUB>,..., k<SUB>n</SUB>}, we also present an O(n<SUP>4/3</SUP>log<SUP>c</SUP> n) algorithm to compute the k<SUB>i</SUB>th nearest neighbor of p<SUB>i</SUB> 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<SUB>i</SUB>th nearest neighbor of p<SUB>i</SUB>, for all i≤n, can be computed in time O(n<SUP>7/5</SUP>log<SUP>c</SUP> n), which also improves upon the previously best-known result