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

Full metadata record

DC FieldValueLanguage
dc.contributor.authorAgarwal, Pankaj K.-
dc.contributor.authorSen, Sandeep-
dc.identifier.citationJournal of Algorithms, 20(3), 581-601en
dc.description.abstractAn 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 upon the previously bestknown result.en
dc.format.extent451853 bytes-
dc.titleSelection in monotone matrices and computing kth nearest neighborsen
Appears in Collections:Computer Science and Engineering

Files in This Item:

File Description SizeFormat
agarwalsel96.pdf441.26 kBAdobe PDFView/Open
View Statistics

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


Valid XHTML 1.0! DSpace Software Copyright © 2002-2010  Duraspace - Feedback