Agarwal, Pankaj K. ; Sen, Sandeep
(1996)
*Selection in monotone matrices and computing kth nearest neighbors*
Journal of Algorithms, 20
(3).
pp. 581-601.
ISSN 0196-6774

Full text not available from this repository.

Official URL: http://www.sciencedirect.com/science/article/pii/S...

Related URL: http://dx.doi.org/10.1006/jagm.1996.0028

## Abstract

An m×n matrix A=(a_{i, j}), 1≤i≤m and 1≤j≤n, is called a totally monotone matrix if for all i_{1}, i_{2}, j_{1}, j_{2}, satisfying 1≤i_{1}<i_{2}≤m, 1≤j_{1}<j_{2}≤n. a_{i1,j1}<a_{i1,j2}⇒a_{i2,j1}<a_{i2,j2}. We present an O((m+n)√nlog n) time algorithm to select the kth smallest item from an m×n totally monotone matrix for any k≤mn. This is the first subquadratic algorithm for selecting an item from a totally monotone matrix. Our method also yields an algorithm of the same time complexity for ageneralized row-selection problemin monotone matrices. Given a set S={p_{1},..., p_{n}} of n points in convex position and a vectork={k_{1},..., k_{n}}, we also present an O(n^{4/3}log^{c} n) algorithm to compute the k_{i}th nearest neighbor of p_{i} for every i≤n; herecis 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_{i}th nearest neighbor of p_{i}, for all i≤n, can be computed in time O(n^{7/5}log^{c} n), which also improves upon the previously best-known result.

Item Type: | Article |
---|---|

Source: | Copyright of this article belongs to Elsevier Science. |

ID Code: | 53428 |

Deposited On: | 08 Aug 2011 12:08 |

Last Modified: | 08 Aug 2011 12:08 |

Repository Staff Only: item control page