# A disc contains $n$ random points. Each point is connected to its nearest neighbor. What does the average cluster size approach as $n\to\infty$?

A disc contains $$n$$ independent uniformly random points. Each point is connected by a line segment to its nearest neighbor, forming clusters of connected points.

For example, here are $$20$$ random points and $$7$$ clusters, with an average cluster size of $$\frac{20}{7}$$.

What does the average cluster size approach as $$n\to\infty$$ ?

My attempt:

I made a random point generator that generates $$20$$ random points. The average cluster size is usually approximately $$3$$.

I considered what happens when we add a new random point to a large set of random points. Adding the point either causes no change in the number of clusters, or it causes the number of clusters to increase by $$1$$ (Edit: this is not true, as noted by @TonyK in the comments). The probability that adding a new point increases the number of clusters by $$1$$, is the reciprocal of the answer to my question. (Analogy: Imagine guests arriving to a party; if 25% of guests bring a bottle of wine, then the expectation of the average number of guests per bottle of wine is $$4$$.) But I haven't worked out this probability.

Context:

This question was inspired by the question Stars in the universe - probability of mutual nearest neighbors.

Edit: Postd on MO.

• Adding a new point can actually decrease the number of clusters. For instance, consider points on the $x$-axis at $0,4,9,$ and $13$: they form two clusters, $\{0,4\}$ and $\{9,13\}$. Now add a point at $x=6$: these five points form a single cluster. Jan 15 at 16:16

This is Stars in the universe - probability of mutual nearest neighbors in disguise. If there are $$k$$ pairs of mutual nearest neighbours, then there are $$n-k$$ edges (since $$n$$ edges are drawn and $$k$$ of them occur twice). There can’t be any cycles (unless it’s an Escher disk) because the distances would have to decrease all along the cycle. So the graph is a forest of $$n-(n-k)=k$$ trees. For $$n\to\infty$$, the fraction of points that are their nearest neighbour’s nearest neighbour goes to the probability for that to happen; $$\frac kn$$ is half that fraction, and the expected average cluster size is the reciprocal of that. In two dimensions, that yields

$$2\left(\frac43+\frac{\sqrt3}{2\pi}\right)\approx3.218\;.$$

• @Dan: Most likely, yes. I just saw that the same answer was already given at MO. Perhaps that was a slightly premature crosspost for a question like this after only half a day. Jan 16 at 3:57
• (+1) Amazing! I didn't expect that OP's question can be answered without knowing cluster-size distribution. Jan 16 at 4:39
• The numerical coincidence amounts to $13/6+\sqrt{3}/\pi\approx e$, with the latter only larger by about one part in 10000. Jan 16 at 21:05
• I suppose there is a possibility that there are 3 points forming a regular triangle, in which case they can form a 3-cycle. But the probability of that is infinitesimal. Jan 17 at 15:51
• @Dan: Thanks. I think this is related to some ideas I had about learning more about the degree distribution of the nearest-neighbour graph, but they involve some complicated integration and it'll probably take a while before I work them out properly. Jan 24 at 16:03

Your question is scratching the surface of the area in probability called percolation theory.

Indeed, noting that the connectivity of a random graph in OP's model is independent of the scale, we may consider $$n$$ independent points sampled uniformly at random from a disk of radius $$\sqrt{n}$$. Then, as $$n \to \infty$$, the thermodynamic limit of this model converges to what is termed as the nearest-neighbor continuum percolation model [1], which can be described as follows:

Limit Model. Let $$X$$ be a Poisson point process on $$\mathbb{R}^2$$ with constant intensity. For any two distinct points $$x$$ and $$y$$ in $$X$$, connect $$x$$ and $$y$$ if $$y$$ is a nearest neighbor of $$x$$.

Q. Can we say anything about the cluster-size distribution in this model?

To my knowledge, it seems that most of the questions regarding this distribution, including OP's one, has never been explored in the literature, and I have a hunch that it is almost impossible to answer this exactly. At least, it is known that all the clusters are finite with probability one, as proved in [1].

Edit. @joriki demonstrated that OP's question can be answered without explicitly knowing the size distribution of the connected clusters, via associating each cluster to the unique "mutual nearest-neighbor pair" contained in it.

[1] Häggström, O. and Meester, R. (1996), Nearest neighbor and hard sphere models in continuum percolation. Random Struct. Alg., 9: 295-315. https://doi.org/10.1002/(SICI)1098-2418(199610)9:3<295::AID-RSA3>3.0.CO;2-S

This is a community wiki answer to provide a graphical demonstration of @joriki's idea. (Feel free to expand this!)

In the image below, we generated $$40$$ random points. Then, from each point $$x$$, an arrow is drawn to its nearest neighbor $$y$$ along with the translucent disk of radius $$\overline{xy}$$ centered at $$x$$:

It is clear from the picture that each graph contains exactly one "mutual arrow", visually confirming joriki's observation.

Below is the Mathematica code that is used to generate the above image:

n = 40;

(* Generate n points uniformly at random from the unit disk *)
pts = Table[Sqrt[RandomReal[]]*ReIm[Exp[2Pi*I*RandomReal[]]], {n}];

(* Construct the percolation graph *)
edges = Table[i -> Ordering[Table[If[j==i, Infinity, Norm[pts[[j]]-pts[[i]]]], {j,n}]][[1]], {i, n}]

(* Visualize! *)
Graphics[{
{Directive[Dotted], Circle[{0, 0}, 1]},
{FaceForm[Directive[Opacity[.1], Orange]], EdgeForm[Directive[Opacity[.5], Orange, Thickness[Thin]]], Table[Disk[pts[[edge[[1]]]], Norm[pts[[edge[[2]]]]-pts[[edge[[1]]]]]], {edge, edges}]},
{PointSize[Large], Red, Point/@pts},

Here is a simple JavaScript simulation intended for large $$n$$. (Note that it will not work on Safari.) For example, for $$n=1359356$$ it returns an average cluster size of $$3.2174$$.