Boundary domination and the distribution of the largest nearest-neighbor link in higher dimensions
作者： J. Michael Steele , Luke Tierney
DOI: 10.2307/3214195
关键词:
摘要: For a sample of points drawn uniformly from either the d-dimensional torus or d-cube, d 2, we give limiting distributions for largest nearest-neighbor links. - 3 behavior in is proved to be different cube. The results given also settle conjecture Henze (1982) and throw light on choice cube some probabilistic models computational complexity geometrical algorithms.
jstor.org
sci-hub.se 参考文章(17)
Bruce Warren Weide, Statistical methods in algorithm design and analysis. Carnegie Mellon University. ,(1978)
Jon Louis Bentley, Divide and conquer algorithms for closest point problems in multidimensional space. The University of North Carolina at Chapel Hill. ,(1976)
Christos H. Papadimitriou, Jon Louis Bentley, A Worst-Case Analysis of Nearest Neighbor Searching by Projection international colloquium on automata, languages and programming. pp. 470- 482 ,(1980) , 10.1007/3-540-10003-2_92
Mark F. Schilling, Goodness of Fit Testing in $\mathbb{R}^m$ Based on the Weighted Empirical Distribution of Certain Nearest Neighbor Statistics Annals of Statistics. ,vol. 11, pp. 1- 12 ,(1983) , 10.1214/AOS/1176346051
G. Yuval, Finding nearest neighbours Information Processing Letters. ,vol. 5, pp. 63- 65 ,(1976) , 10.1016/0020-0190(76)90064-8
Mark F. Schilling, An Infinite-Dimensional Approximation for Nearest Neighbor Goodness of Fit Tests Annals of Statistics. ,vol. 11, pp. 13- 24 ,(1983) , 10.1214/AOS/1176346052
J.H. Friedman, F. Baskett, L.J. Shustek, An Algorithm for Finding Nearest Neighbors IEEE Transactions on Computers. ,vol. 24, pp. 1000- 1006 ,(1975) , 10.1109/T-C.1975.224110
Richard J. Lipton, Robert Endre Tarjan, Applications of a planar separator theorem 18th Annual Symposium on Foundations of Computer Science (sfcs 1977). pp. 162- 170 ,(1977) , 10.1109/SFCS.1977.6
Jerome H. Friedman, Jon Louis Bentley, Raphael Ari Finkel, An Algorithm for Finding Best Matches in Logarithmic Expected Time ACM Transactions on Mathematical Software. ,vol. 3, pp. 209- 226 ,(1977) , 10.1145/355744.355745
Jon Louis Bentley, Bruce W Weide, Andrew C Yao, None, Optimal Expected-Time Algorithms for Closest Point Problems ACM Transactions on Mathematical Software. ,vol. 6, pp. 563- 580 ,(1980) , 10.1145/355921.355927