Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#235582] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Sen, S, Selection in Monotone Matrices and Computing kth Nearest Neighbors, Journal of Algorithms, vol. 20 no. 3 (1996), pp. 581-601 [doi]
    (last updated on 2017/12/15)

    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.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320