The Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   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
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply



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/







Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.