Selection in Monotone Matrices and Computing kth Nearest Neighbors


Journal Article

An m × n matrix script A sign = (ai, j), 1 ≤ i ≤ m and 1 < j < n, is called a totally monotone matrix if for all i1, i2, j1, j2, satisfying 1 < i1 < i2 < m, 1 < j1 < j2 < n. ai1, j1 < ai1, j2 ⇒ ai2, j1 < ai2, j2. We present an O((m + n)√n log n) time algorithm to select the kth smallest item from an m × n totally monotone matrix for any k ≤ mn. This is the first sub-quadratic algorithm for selecting an item from a totally monotone matrix. Our method also yields an algorithm of the same time complexity for a generalized 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 logc n) algorithm to compute the kith 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 kith 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. © 1996 Academic Press, Inc.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Sen, S

Published Date

  • January 1, 1996

Published In

Volume / Issue

  • 20 / 3

Start / End Page

  • 581 - 601

International Standard Serial Number (ISSN)

  • 0196-6774

Digital Object Identifier (DOI)

  • 10.1006/jagm.1996.0028

Citation Source

  • Scopus