|
EPrints@IIT Delhi >
Faculty Research Publicatons >
Computer Science and Engineering >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/2074/298
|
| Title: | Selection in monotone matrices and computing kth nearest neighbors |
| Authors: | Agarwal, Pankaj K.
Sen, Sandeep |
| Keywords: | monotone
subquadratic
algorithm
row-selection |
| Issue Date: | 1996 |
| Citation: | Journal of Algorithms, 20(3), 581-601 |
| 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 row-selection 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 row-selection 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 up... |
| URI: | http://eprint.iitd.ac.in/dspace/handle/2074/298 |
| Appears in Collections: | Computer Science and Engineering
|
Files in This Item:
| File |
Description |
Size | Format |
|---|
| agarwalsel96.pdf | | 441Kb | Adobe PDF | View/Open |
|
Show full item record
All items in DSpace are protected by copyright, with all rights reserved.
|
