Selection in monotone matrices and computing kth 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.
Full Text
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
Digital Object Identifier (DOI)
- 10.1007/3-540-58218-5_2
Citation Source
- Scopus