DSpace
 

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
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 upon the previously bestknown result.
URI: http://eprint.iitd.ac.in/dspace/handle/2074/298
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