Selection in monotone matrices and computing kth nearest neighbors

Agarwal, Pankaj K. ; Sen, Sandeep (1996) Selection in monotone matrices and computing kth nearest neighbors Journal of Algorithms, 20 (3). pp. 581-601. ISSN 0196-6774

Full text not available from this repository.

Official URL:

Related URL:


An m×n matrix A=(ai, j), 1≤i≤m and 1≤j≤n, is called a totally monotone matrix if for all i1, i2, j1, j2, satisfying 1≤i1<i2≤m, 1≤j1<j2≤n. ai1,j1<ai1,j2⇒ai2,j1<ai2,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={p1,..., pn} of n points in convex position and a vectork={k1,..., kn}, we also present an O(n4/3logc n) algorithm to compute the kith nearest neighbor of pi 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 kith nearest neighbor of pi, for all i≤n, can be computed in time O(n7/5logc n), which also improves upon the previously best-known result.

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
ID Code:53428
Deposited On:08 Aug 2011 12:08
Last Modified:08 Aug 2011 12:08

Repository Staff Only: item control page