Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: when K nearest neighbors graph connects all points
Replies: 1   Last Post: May 16, 2000 12:09 PM

 Messages: [ Previous | Next ]
 eppstein@euclid.ics.uci.edu Posts: 128 Registered: 12/8/04
Re: when K nearest neighbors graph connects all points
Posted: May 16, 2000 12:09 PM

belyaev@u-aizu.ac.jp (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
eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/

Date Subject Author
5/16/00 Alexander G. Belyaev
5/16/00 eppstein@euclid.ics.uci.edu