Abstract
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≤mn. 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=p 1, ..., pn of n points in convex position and a vector k=k 1, ..., kn, we also present an O(n 4/3 logO(1) n) algorithm to compute the k thi nearest neighbor of p i 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 k thi nearest neighbor of p i, for all i≤n, can be computed in time O(n 7/5 logc n), which also improves upon the previously best-known result.
Pankaj Agarwal has been supported by an NYI award and National Science Foundation Grant CCR-93-01259.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
P.K. Agarwal, B. Aronov, M. Sharir and S. Suri, Selecting distances in the plane, Algorithmica 9 (1993), 495–514.
P.K. Agarwal and J. Matoušek, Ray shooting and parametric search, SIAM J. Computing 22 (1993), 794–806.
P.K. Agarwal and J. Matoušek, Range searching with semi-algebraic sets, Proc. 17th Symp. Mathematical Foundations of Computer Science, (Lecture Notes in Computer Science 629), Springer-Verlag 1992, pp. 1–13. (Also to appear in Discrete and Computational Geometry.)
A. Aggarwal, M. Klawe, S. Moran, P. Shor, and R. Wilber, Geometric applications of a matrix-searching algorithm, Algorithmica 2 (1987), 195–208.
A. Aggarwal and J. Park, Parallel searching in multidimensional monotone arrays, to appear in J. Algorithms.
A. Aggarwal and J. Park, Sequential searching in multidimensional monotone arrays, to appear in J. Algorithms.
A. Aggarwal and J. Park, Improved algorithm for economic lot size problems, Operations Research 41 (1993), 549–571.
A. Aggarwal, D. Kravets, J. Park, and S. Sen, Parallel searching in generalized Monge arrays with applications, Proc. 2nd ACM Symp. Parallel Algorithms and Architectures, 1990, pp. 259–268.
A. Aggarwal and S. Suri, Computing the longest diagonal of a simple polygon, Information Processing Letters 35 (1990), 13–18.
N. Alon and Y. Azar, Comparison-sorting and selecting in totally monotone matrices, Proceedings 3rd Annual ACM-SIAM Symposium on Discrete Algorithms, 1992, pp. 403–408.
R. Bar Yehuda and S. Fogel, Variations on ray shooting, Algorithmica 11 (1994), 133–145.
M. Blum, R. Floyd, V. Pratt, R. Rivest, and R. Tarjan, Time bounds for selection, J. Computer and Systems Sciences 7 (1973), 448–461.
P. Callahan and S. Kosaraju, Faster algorithms for some geometric graph problems in higher dimensions, Proceedings 4th Annual ACM-SIAM Symposium on Discrete Algorithms, 1993, pp. 291–300.
B. Chazelle, R. Cole, F. Preparata and C. Yap, New upper bounds for neighbor searching, Information and Control 68 (1986), 105–124.
E. Dijkstra, A Discipline of Programming, Prentice-Hall, Englewood Cliff, NJ, 1976.
H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, Berlin, 1987.
P. Erdős and G. Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1935), 463–470.
G. Frederickson and D. Johnson, Generalized selection and ranking: sorted matrices, SIAM J. Computing 13 (1984), 14–30.
D. Johnson and T. Mitzoguchi, Selecting the kth element in X+Y and X 1+X2+...+Xm, SIAM J. Computing 7 (1978), 147–153.
D. Kravets and J. Park, Selection and sorting in totally monotone arrays, Mathematical Systems Theory 24 (1991), 201–220.
Y. Mansour, J. Park, B. Schieber and S. Sen, Improved selection in totally monotone arrays, International J. of Computational Geometry and Applications 3 (1993), 115–132.
J. Matoušek and E. Welzl, Good splitters for counting points in triangles, J. Algorithms 13 (1992), 307–319.
N. Megiddo, Applying parallel computation algorithms in the design of serial algorithms, J. ACM 30 (1983), 852–865.
N. Sarnak, and R. E. Tarjan, Planar point location using persistent search trees, Comm. ACM 29 (1986), 609–679.
P. Vaidya, An O(n log n) algorithm for the all-nearest-neighbors problem, Discrete and Computational Geometry 4 (1989), 101–115.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Agarwal, P.K., Sen, S. (1994). Selection in monotone matrices and computing k th nearest neighbors. In: Schmidt, E.M., Skyum, S. (eds) Algorithm Theory — SWAT '94. SWAT 1994. Lecture Notes in Computer Science, vol 824. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-58218-5_2
Download citation
DOI: https://doi.org/10.1007/3-540-58218-5_2
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58218-2
Online ISBN: 978-3-540-48577-3
eBook Packages: Springer Book Archive