| Research Support Tool |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Context
Selection in monotone matrices and computing kth nearest neighbors
Title:
Selection in monotone matrices and computing kth nearest neighbors
Archive:
Eprints@IIT Delhi
Author(s):
Agarwal, Pankaj K.
Sen, Sandeep
Sen, Sandeep
Date:
2005-06-08
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.
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.
Index terms:
Discipline(s):
monotone
Subject(s):
subquadratic; algorithm; row-selection
Method/Approach:
Coverage:
Publisher:
Contributors:
Source:
Language:
en
Relation:
Type:
Article
Format:
451853 bytes
application/pdf
Copyright Information:
Browse Archive