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
    $\begingroup$ That “shell of a ball” would be a sphere. Computing the distribution for the distance between a pair of points should be relatively easy, but several such distances would no longer be independent, thus complicating matters. It might be worthwhile to randomly pick some points in a Monte-Carlo fashion, so that you have some numbers against which you can compare proposed formulas. $\endgroup$
    – MvG
    Nov 17 '16 at 14:21
  • $\begingroup$ @MvG Yes, the shell of the ball is a sphere. You are correct in saying that the distances are no longer independent. However, since we are after a lower ground we can do the following $P[ \cap S_i ]=1- P[ \cup S_i^c ]\ge 1- \sum P[S_i^c]$. My concern, if there are any issues with going from geodesic distance to euclidean? $\endgroup$
    – Boby
    Nov 17 '16 at 14:25
  • $\begingroup$ Your main question (first paragraph) doesn't mention that you're looking for a bound on the expected value; it sounds like you'd want an exact formula. Some readers might loose interest there even though they would be able to help find a bound. $\endgroup$
    – MvG
    Nov 17 '16 at 14:29
  • $\begingroup$ @MvG thanks. I added a correction. $\endgroup$
    – Boby
    Nov 17 '16 at 14:36
  • $\begingroup$ It's not clear whether you are interested in a bound or an asymptotic for large $N$ $\endgroup$
    – leonbloy
    Nov 17 '16 at 15:10

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} $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.