Average minimum distance between $N$ points generate i.i.d. uniformly on the shell (sphere) of ball

1k Views Asked by At

What is the expected minimum euclidean distance between $N$ points uniformly and independently chosen on the shell(sphere) of 3-D ball of radius $R$? Note that the expected minimum distance might be difficult to compute, so a good lower bound is also fine.

My approach I take the approach similar to this question.

Suppose we put $N$ circles of radius $r$ uniformly on the surface of the ball.
Therefore we could compute the expected minimum distance by the following expression \begin{align} E[D]=\int_0^\infty P(D>t) dt. \end{align}

So, it remains to compute $P(D>t)$. Actually, since we are after a lower bound on $E[D]$ it is enought to give a lower bound on $P(D>t)$.

Let $S_i$ be the event that the pair of circles does not intersect which should be given by \begin{align} P(S_i) = \frac{ Surf(R)-Surf(r)}{Surf(R)}= 1-\frac{ \pi r^2}{ 4\pi R^2}=1-\frac{ r^2}{ 4 R^2} \end{align}

Now the probability that euclidean minimum distance $D$ between $N$ balls is bigger than $t$ should be similar to \begin{align} P[ D \ge t] \stackrel{?}{=} P[ \cap S_i] \end{align} However, I think we somehow need to converte from the geodesic distance to euclidean distance but I am not very sure how to do that?

1

There are 1 best solutions below

0
On BEST ANSWER

The asymptotics is a straightforward (or boring) generalization of my previous answer.

Sketch: Take a point over the unit sphere ($R=1$). Then the "excluded area" $a(D)$ (points that lie at a -euclidean- distance less than $D$ from the point) is $$a(D)=\pi D^2$$

The probability that a "link is free" (distance between points pair $i$ isgreater than $D$ is

$$p(S_i) =1-\frac{1}{4}D^2 \hspace{1cm} 0\le D \le 2 \tag{1}$$

Assuming independence as asympotical approximation:

$$p(\cap S_i) \approx (1-\frac{1}{4}D^2 )^M, \hspace{1cm} M=\frac{N(N-1)}{2} \tag{2}$$

Then, letting $t=$ minimum distance between points

$$E(t) = \int P(t >D) \, dD = \int p(\cap S_i)\, dD \approx \int_{0}^2 (1-\frac{1}{4}D^2 )^M \, dD \tag{3}$$

For large $M$ this tends to

$$E(t) \approx \frac{\sqrt{\pi}}{\sqrt{M}}\approx \frac{\sqrt{2 \pi}}{N} \tag{4}$$

For general ball radius $R$:

$$E(t) \approx R \frac{\sqrt{\pi}}{\sqrt{M}}\approx R \frac{\sqrt{2 \pi}}{N} $$