#
Selection in monotone matrices and computing k^{th}
nearest neighbors

Published

Conference Paper

© 1994, Springer Verlag. All rights reserved. We present an O((m + n)√n log n) time algorithm to select the k th smallest item from an m × n totally monotone matrix for any k ≤ ran. This is the first subquadratic algorithm for selecting an item from a totally monotone matrix. Our method also yields an algorithm for generalized row selection in monotone matrices of the same time complexity. 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 logO(1) n) algorithm to compute the kith nearest neighbor of pi for every i ≤ n; 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 kith h nearest neighbor of pi, for all i ≤ n, can be computed in time O(n7/5 logc n), which also improves upon the previously best-known result.

### Duke Authors

### Cited Authors

- Agarwal, PK; Sen, S

### Published Date

- January 1, 1994

### Published In

### Volume / Issue

- 824 LNCS /

### Start / End Page

- 13 - 24

### Electronic International Standard Serial Number (EISSN)

- 1611-3349

### International Standard Serial Number (ISSN)

- 0302-9743

### International Standard Book Number 13 (ISBN-13)

- 9783540582182

### Citation Source

- Scopus