firstname.lastname@example.org (Alexander G. Belyaev) writes: > Consider a set of 3D points whose coordinates > are random and uniformly distributed in [0,1]. > Let us connect every point with its K nearest neighbors. > What is the minimal K such that (in average) all points > are connected together?
There is always some (possibly tiny) fraction of unconnected points, and boundary effects make points in the unit cube messy to analyze. Probably what you want is the probability of having an infinite component for Poisson-distributed points in the whole space (if there is an infinite component, there is almost surely only one).
Shang-Hua Teng and Frances Yao had a paper they were working on a few years ago that covered this topic, but apparently nothing ever came of it.
Haggstrvm and Meester, "Nearest neighbor and hard sphere models in continuum percolation", [Random Structures & Algorithms 9(3):295-315, 1996] also seems to be on exactly this topic. According to the abstract they show that for any dimension there exists a minimal K for which percolation occurs, and that for large enough dimension K=2. They also present computational evidence that "large enough" means d>=3. For d=2 it appears that the minimal percolating K is K=3. -- David Eppstein UC Irvine Dept. of Information & Computer Science email@example.com http://www.ics.uci.edu/~eppstein/