×

An O(n log n) algorithm for the all-nearest-neighbors problem. (English) Zbl 0663.68058

Given a set V of n points in k-dimensional space, and an \(L_ q\)-metric (Minkowski metric), the all-nearest-neighbors problem is defined as follows: for each point p in V, find all those points in V-\(\{\) \(p\}\) that are closest to p under the distance metric \(L_ q\). We give an O(n log n) algorithm for the all-nearest-neighbors problem, for fixed dimension k and fixed metric \(L_ q\). Since there is an \(\Omega\) (n log n) lower bound, in the algebraic decision-tree model of computation, on the time complexity of any algorithm that solves the all-nearest- neighbors problem (for \(k=1)\), the running time of our algorithm is optimal up to a constant factor.

MSC:

68Q25 Analysis of algorithms and problem complexity
51K05 General theory of distance geometry
68U99 Computing methodologies and applications
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] M. Ben-Or, Lower bounds for algebraic computation trees,Proc. 15th Annual ACM Symp. Theory Comput., 1983, pp. 80-86.
[2] J. L. Bentley, Multidimensional divide-and-conquer,Comm. ACM23 (1980), 214-229. · Zbl 0434.68049 · doi:10.1145/358841.358850
[3] 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. · Zbl 0373.68041 · doi:10.1016/0020-0190(77)90070-9
[4] J. L. Bentley, B. Weide, and A. Y. Yao, Optimal expected-time algorithms for closest-point problems,ACM Tran. Math. Software6 (1982), 563-579. · Zbl 0441.68077 · doi:10.1145/355921.355927
[5] K. Clarkson, Fast algorithms for the all-nearest-neighbors problem,Proc. 24th Annual Symp. Found. Comput. Sci., 1983, pp. 226-232.
[6] 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.
[7] F. P. Preparata and M. I. Shamos,Computational Geometry: An Introduction, Springer-Verlag, New York, 1985. · Zbl 0759.68037 · doi:10.1007/978-1-4612-1098-6
[8] E. M. Reingold, J. Nievergelt, and N. Deo,Combinatorial Algorithms: Theory and Practice, Prentice Hall, Englewood Cliffs, NJ, 1977. · Zbl 0367.68032
[9] M. I. Shamos, Computational Geometry, Ph.D. dissertation, Yale University, New Haven, CT, 1978.
[10] Rabin, M. O.; Traub, J. F. (ed.), Probabilistic algorithms, 21-30 (1976), New York · Zbl 0384.60001
[11] F. Yuval, Finding nearest neighbors,Inform. Process. Lett.3 (1975), 113-114. · doi:10.1016/0020-0190(75)90044-7
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.