k-nearest-neighbor clustering and percolation theory
Let P be a realization of a homogeneous Poisson point process in R-d with density 1. We prove that there exists a constant k(d), 1  = k(d). In particular, we prove that k(2) <= 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(2) = 3. We also obtain similar results for finite random point sets.
clustering percolation random point set nearest neighbor graph