EPrints@IIT Delhi >
Faculty Research Publicatons >
Computer Science and Engineering >
Please use this identifier to cite or link to this item:
http://eprint.iitd.ac.in/handle/2074/298

Title:  Selection in monotone matrices and computing kth nearest neighbors 
Authors:  Agarwal, Pankaj K. Sen, Sandeep 
Keywords:  monotone subquadratic algorithm rowselection 
Issue Date:  1996 
Citation:  Journal of Algorithms, 20(3), 581601 
Abstract:  An m x n matrix A=(ai j),1,i,m and 1,j<n is called a totally motone matrix if for i1.i2.j1.j2satisfying1=i1.i2.m1=j1.j2.n ai1.ji1<ai1.j2=ai2j1<ai2.j2.We present an O ((m+n)nlogn time algorithm to select the kth smallest item from an m=n totally monotone matrix for any kFmn. This is the first subquadraticm algorithm for selecting an item from a totally monotone matrix. Our method also yields an algorithm of the same time complexity for a generalized 4 rowselection problem in monotone matrices. Given a set S= (p1 . . . .pn)
of n points in convex position and a vector k= (k1 . . . . . kn) we also present an O(n4/3 logn) algorithm to compute the k th nearest neighbor of pi for every i <n: here c is an appropriate constant. This algorithm is considerably faster than the one based on a rowselection algorithm for monotone matrices. If the points of S are arbitrary, then the k th nearest neighbor of pi for all iFn, can be i<n
can be computed in time O(n7/5 log n) which also improves upon the previously bestknown result. 
URI:  http://eprint.iitd.ac.in/dspace/handle/2074/298 
Appears in Collections:  Computer Science and Engineering

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
