Hostname: page-component-78c5997874-t5tsf Total loading time: 0 Render date: 2024-11-06T02:09:09.925Z Has data issue: false hasContentIssue false
  • English
  • Français

Boundary domination and the distribution of the largest nearest-neighbor link in higher dimensions

Published online by Cambridge University Press:  14 July 2016

J. Michael Steele  and
Luke Tierney
J. Michael Steele*
Affiliation:
Princeton University
Luke Tierney*
Affiliation:
University of Minnesota
*
∗Postal address: Department of Statistics, Princeton University, Fine Hall, Washington Road, Princeton, NJ 08544, USA.
∗∗Postal address: School of Statistics, 270 Vincent Hall, 206 Church St SE, University of Minnesota, Minneapolis, MN 55455, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

For a sample of points drawn uniformly from either the d-dimensional torus or the d-cube, d ≧ 2, we give limiting distributions for the largest of the nearest-neighbor links. For d ≧ 3 the behavior in the torus is proved to be different from the behavior in the cube. The results given also settle a conjecture of Henze (1982) and throw light on the choice of the cube or torus in some probabilistic models of computational complexity of geometrical algorithms.

Keywords

COMPUTATIONAL GEOMETRYSPIRAL SEARCHEXTREME-VALUE DISTRIBUTIONGUMBEL DISTRIBUTION
Type
Short Communications
Information
Journal of Applied Probability , Volume 23 , Issue 2 , June 1986 , pp. 524 - 528
Copyright
Copyright © Applied Probability Trust 1986 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

Research supported in part by NSF Contract DMS-8414069.

References

Bentley, J. L. (1976) Divide and Conquer Algorithms for Closest Point Problems in Multidimensional Space. , University of North Carolina.Google Scholar
Bentley, J. L., Weide, B. W. and Yao, A. G. (1980) Optimal expected-time algorithms for closest point problems. ACM Trans. Math. Software 6, 563–580.CrossRefGoogle Scholar
Bickel, P. J. and Breiman, L. (1983) Sums of functions of nearest neighbor distances, moment bounds, limit theorems and a goodness of fit test. Ann. Prob. 11, 185–214.Google Scholar
Friedman, J. H., Baskett, F. and Shustek, L. J. (1975) An algorithm for finding nearest neighbors. IEEE Trans. Computers 24, 1000–1006.CrossRefGoogle Scholar
Friedman, J. H., Bentley, J. L. and Finkel, R. A. (1977) An algorithm for finding best matches in logarithmic expected time. ACM Trans. Math. Software 3, 209–226.Google Scholar
Henze, N. (1981) Ein asymptotischer Satz uber den maximalen Minimalabstand von unabhängigen Zufallsvektoren mit Anwendung auf einen Anpassungstest im RP und auf der Kugel. Unpublished Doctoral Dissertation, University of Hannover.Google Scholar
Henze, N. (1982) The limit distribution for maxima of ‘weighted’ r-th nearest-neighbor distances. J. Appl. Prob. 19, 344–354.Google Scholar
Henze, N. (1983) Ein asymptotisher Satz uber den maximalen Minimlabstand von unabhängigen Zufallsvektoren mit Anwendung auf einen Anpassungstest im Rp und auf der Kugel. Metrika 30, 245–259.CrossRefGoogle Scholar
Lee, R. C. T., Chin, I. I. and Chang, S. C. (1976) Application of principal component analysis to multikey searching. IEEE Trans. Software Engineering 2, 185–193.CrossRefGoogle Scholar
Lipton, R. and Tarjan, R. E. (1977) Applications of a planar separator theorem. 18 Symp. Foundations of Computer Science, IEEE, 162–170.Google Scholar
Papadimitriou, C. H. and Bentley, J. L. (1980) Worst-case analysis of nearest neighbor searching by projection. Technical Report CMU–CS–80–109, Department of Computer Science, Carnegie-Mellon University.Google Scholar
Schilling, M. F. (1983a) Goodness of fit testing in Rm based on the weighted empirical distribution of nearest neighbor statistics. Ann. Statist. 11, 1–12.Google Scholar
Schilling, M. F. (1983b) An infinite-dimensional approximation for nearest neighbor goodness of fit tests. Ann. Statist. 11, 13–24.CrossRefGoogle Scholar
Shamos, M. I. (1978) Computational Geometry. , Yale University.Google Scholar
Weide, B. W. (1978) Statistical Methods in Algorithm Design and Analysis. , Carnegie-Mellon University.Google Scholar
Weiss, L. (1965) On asymptotic sampling theory for distributions approaching the uniform distribution. Z. Wahrscheinlichkeitsth. 4, 217–221.Google Scholar
Weiss, L. (1969) The asymptotic joint distribution of an increasing number of sample quantiles. Ann. Inst. Statist. Math. 21, 257–263.Google Scholar
Yuval, G. (1976) Finding nearest neighbors. Inf. Process. Lett. 5, 63–65.CrossRefGoogle Scholar
Zolnowsky, J. E. (1978) Topics in Computational Geometry. , Stanford University.Google Scholar