Selection in monotone matrices and computing kth nearest neighbors


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