On Nearest-Neighbor Graphs
作者： D. Eppstein , M. S. Paterson , F. F. Yao
DOI: 10.1007/PL00009293
关键词: Ball tree 、 Random graph 、 Null graph 、 Combinatorics 、 Mathematics 、 Random geometric graph 、 Random regular graph 、 Fixed-radius near neighbors 、 Nearest neighbor graph 、 Line graph 、 Discrete mathematics
摘要: The "nearest-neighbor" relation, or more generally the "k-nearest-neighbors" defined for a set of points in metric space, has found many uses computational geometry and clustering analysis, yet surprisingly little is known about some its basic properties. In this paper we consider natural questions that are motivated by geometric embedding problems. We derive bounds on relationship between size depth components nearest-neighbor graph prove probabilistic properties k-nearest-neighbors random points.
springer.com
sci-hub.se 参考文章(17)
Michael S. Paterson, F. Frances Yao, On Nearest-Neighbor Graphs international colloquium on automata languages and programming. pp. 416- 426 ,(1992) , 10.1007/3-540-55719-9_93
Jay Boris, A vectorized near neighbors algorithm of order N using a monotonic logical grid Journal of Computational Physics. ,vol. 66, pp. 1- 20 ,(1986) , 10.1016/0021-9991(86)90050-1
Pravin M. Vaidya, AnO(n logn) algorithm for the all-nearest-neighbors Problem Discrete & Computational Geometry. ,vol. 4, pp. 101- 115 ,(1989) , 10.1007/BF02187718
E. Bannai, N. J. A. Sloane, J. H. Conway, Sphere packings, lattices, and groups ,(1987)
Paul B. Callahan, S. Rao Kosaraju, A decomposition of multi-dimensional point-sets with applications to k-nearest-neighbors and n-body potential fields (preliminary version) symposium on the theory of computing. pp. 546- 556 ,(1992) , 10.1145/129712.129766
Herbert Edelsbrunner, Algorithms in Combinatorial Geometry ,(1987)
Matthew T. Dickerson, David Eppstein, Algorithms for proximity problems in higher dimensions Computational Geometry: Theory and Applications. ,vol. 5, pp. 277- 291 ,(1996) , 10.1016/0925-7721(95)00009-7
L. Devroye, The expected size of some graphs in computational geometry Computers & Mathematics with Applications. ,vol. 15, pp. 53- 64 ,(1988) , 10.1016/0898-1221(88)90071-5
Clyde Monma, Subhash Suri, Transitions in geometric minimum spanning trees (extended abstract) symposium on computational geometry. pp. 239- 249 ,(1991) , 10.1145/109648.109675
Joel Spencer, The Probabilistic Method ,(1991)