Math @ Duke

Publications [#235582] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Sen, S, Selection in Monotone Matrices and Computing kth Nearest Neighbors,
Journal of Algorithms, vol. 20 no. 3
(1996),
pp. 581601 [doi]
(last updated on 2017/12/15)
Abstract: 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 subquadratic algorithm for selecting an item from a totally monotone matrix. Our method also yields an algorithm of the same time complexity for a generalized rowselection 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 rowselection 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 bestknown result. © 1996 Academic Press, Inc.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

