AnO(n logn) algorithm for the all-nearest-neighbors Problem
Tóm tắt
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.
Tài liệu tham khảo
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.