Abstract
Given a setV ofn points ink-dimensional space, and anL q -metric (Minkowski metric), the all-nearest-neighbors problem is defined as follows: for each pointp inV, find all those points inV−{p} that are closest top under the distance metricL q . We give anO(n logn) algorithm for the all-nearest-neighbors problem, for fixed dimensionk and fixed metricL q . Since there is an Θ(n logn) lower bound, in the algebraic decision-tree model of computation, on the time complexity of any algorithm that solves the all-nearest-neighbors problem (fork=1), the running time of our algorithm is optimal up to a constant factor.
Article PDF
Similar content being viewed by others
References
M. Ben-Or, Lower bounds for algebraic computation trees,Proc. 15th Annual ACM Symp. Theory Comput., 1983, pp. 80–86.
J. L. Bentley, Multidimensional divide-and-conquer,Comm. ACM23 (1980), 214–229.
J. L. Bentley, D. F. Stanat, and E. H. Williams, Jr., The complexity of finding fixed radius nearest neighbors,Inform. Process. Lett. 6 (1977), 209–212.
J. L. Bentley, B. Weide, and A. Y. Yao, Optimal expected-time algorithms for closest-point problems,ACM Tran. Math. Software 6 (1982), 563–579.
K. Clarkson, Fast algorithms for the all-nearest-neighbors problem,Proc. 24th Annual Symp. Found. Comput. Sci., 1983, pp. 226–232.
H. N. Gabow, J. L. Bentley, and R. E. Tarjan, Scaling and related techniques for geometry problems,Proc. 16th Annual ACM Symp. Theory Comput., 1984, pp. 135–143.
F. P. Preparata and M. I. Shamos,Computational Geometry: An Introduction, Springer-Verlag, New York, 1985.
E. M. Reingold, J. Nievergelt, and N. Deo,Combinatorial Algorithms: Theory and Practice, Prentice Hall, Englewood Cliffs, NJ, 1977.
M. I. Shamos, Computational Geometry, Ph.D. dissertation, Yale University, New Haven, CT, 1978.
M. O. Rabin, Probabilistic algorithms, inAlgorithms and Complexity (J. F. Traub, ed.), Academic Press, New York, 1976, pp. 21–30.
F. Yuval, Finding nearest neighbors,Inform. Process. Lett. 3 (1975), 113–114.
Author information
Authors and Affiliations
Additional information
Communicated by Herbert Edelsbrunner
This research was supported by a fellowship from the Shell Foundation. The author is currently at AT&T Bell Laboratories, Murray Hill, New Jersey, USA.
Rights and permissions
About this article
Cite this article
Vaidya, P.M. AnO(n logn) algorithm for the all-nearest-neighbors Problem. Discrete Comput Geom 4, 101–115 (1989). https://doi.org/10.1007/BF02187718
Received:
Revised:
Published:
Issue date:
DOI: https://doi.org/10.1007/BF02187718