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




Re: when K nearest neighbors graph connects all points
Posted:
May 16, 2000 12:09 PM


belyaev@uaizu.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 Poissondistributed points in the whole space (if there is an infinite component, there is almost surely only one).
ShangHua 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):295315, 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/



