<Emphasis Type="Italic">k</Emphasis>-Nearest-Neighbor Clustering and Percolation Theory

Let P be a realization of a homogeneous Poisson point process in ℝ ^d with density 1. We prove that there exists a constant k _d , 1<k _d <∞, such that the k-nearest neighborhood graph of P has an infinite connected component with probability 1 when k≥k _d . In particular, we prove that k ₂≤213. Our analysis establishes and exploits a close connection between the k-nearest neighborhood graphs of a Poisson point set and classical percolation theory. We give simulation results which suggest k ₂=3. We also obtain similar results for finite random point sets. Part of the work was done while S.-H. Teng was at Xerox Palo Alto Research Center and MIT. The work of F.F. Yao was supported in part by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China Project No. CityU 1165/04E].