We study the graph constructed on a Poisson point process in @math dimensions by connecting each point to the @math points nearest to it. This graph a.s. has an infinite cluster if @math where @math , known as the critical value, depends only on the dimension @math . This paper presents an improved upper bound of 188 on the value of @math . We also show that if @math the infinite cluster of @math has an infinite subset of points with the property that the distance along the edges of the graphs between these points is at most a constant multiplicative factor larger than their Euclidean distance. Finally we discuss in detail the relevance of our results to the study of multi-hop wireless sensor networks.
Let P be a realization of a homogeneous Poisson point process in ℝd with density 1. We prove that there exists a constant kd, 1<kd<∞, such that the k-nearest neighborhood graph of P has an infinite connected component with probability 1 when k≥kd. In particular, we prove that k2≤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 k2=3. We also obtain similar results for finite random point sets. Consider a Poisson process X in Rd with density 1. We connect each point of X to its k nearest neighbors by undirected edges. The number k is the parameter in this model. We show that, for k = 1, no percolation occurs in any dimension, while, for k = 2, percolation occurs when the dimension is sufficiently large. We also show that if percolation occurs, then there is exactly one infinite cluster. Another percolation model is obtained by putting balls of radius zero around each point of X and let the radii grow linearly in time until they hit another ball. We show that this model exists and that there is no percolation in the limiting configuration. Finally we discuss some general properties of percolation models where balls placed at Poisson points are not allowed to overlap (but are allowed to be tangent). 0 1996 John Wiley & Sons, Inc. 