Consider $m$ points $v_1, \ldots, v_m \in R^{n}$, which are uniformly distributed on the $n$-dimensional unit sphere $S^{n-1} = \{v:\|v\|_2 = 1\}$. Let the minimum separation be $$ \rho = \min_{i,j\in{\{1,\ldots,m\}}} \|v_i - v_j\|_2. $$ Question: What is the expectation of $\rho$? How fast does $\rho$ converge to its expectation as $m,n\to\infty$?

Here are some closely related questions:

Mean minimum distance for N random points on a one-dimensional line

Mean minimum distance for N random points on a unit square (plane)

Mean minimum distance for K random points on a N-dimensional (hyper-)cube

However, the case for n-dimensional sphere seems less clear.

  • $\begingroup$ When you say "How fast does ρ converge to its expectation", what do you mean? I suppose you are sending $m\to\infty$, do you? Please specify! $\endgroup$ – Wolfgang Jul 25 '16 at 7:52
  • $\begingroup$ @Wolfgang Yes I mean $m\to\infty$. Thanks for pointing it out! $\endgroup$ – Minkov Jul 25 '16 at 8:23
  • $\begingroup$ It might also be interesting to think about limits where $m$ and $n$ diverge simultaneously. $\endgroup$ – user25199 Aug 4 '16 at 10:08
  • $\begingroup$ @Carl Thanks for the suggestion. I have modified accordingly. $\endgroup$ – Minkov Aug 6 '16 at 2:18

The preprint "Random Point Sets on the Sphere --- Hole Radii, Covering, and Separation" by Johann S. Brauchart, Edward B. Saff, Ian H. Sloan, Yu Guang Wang, and Robert S. Womersley gives the following result in Corollary 3.4:

$\mathbb{E}[N^{2/d}\Theta_\text{min}]\to C_d = (\kappa_d/2)^{-1/d}\Gamma(1+\tfrac{1}{d})$ as $N\to\infty$

It also gives a bound on the variance.

| cite | improve this answer | |

If the angle between the vectors $v_i$ and $v_j$ is denoted by $\theta_{ij}$, then using cosine rule we have $$\rho = 2 \min_{i,j \in\{1,2,\dots,m\}}\sin({\theta_{ij}}/{2})$$ Assuming that $m$ is a large number, then minimum will occur for a very small value of $\theta_{ij}$. Hence, $$\rho \approx \min_{i,j \in\{1,2,\dots,m\}} \theta_{ij}$$ Since the points are distributed uniformly, It is not difficult to find the distribution of $\theta_{ij}$ and then find the expectation and variance of $\rho$. This I guess will give a pretty good estimate of the actual value of expectation and variance of $\rho$.

| cite | improve this answer | |
  • 1
    $\begingroup$ Thanks for the answer. If possible, could you provide more details on the estimate? $\endgroup$ – Minkov Jul 26 '16 at 4:42

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.