10
$\begingroup$

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.

$\endgroup$
4
  • $\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
    Commented Jul 25, 2016 at 7:52
  • $\begingroup$ @Wolfgang Yes I mean $m\to\infty$. Thanks for pointing it out! $\endgroup$
    – Minkov
    Commented Jul 25, 2016 at 8:23
  • $\begingroup$ It might also be interesting to think about limits where $m$ and $n$ diverge simultaneously. $\endgroup$
    – user25199
    Commented Aug 4, 2016 at 10:08
  • $\begingroup$ @Carl Thanks for the suggestion. I have modified accordingly. $\endgroup$
    – Minkov
    Commented Aug 6, 2016 at 2:18

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Thanks for the answer. If possible, could you provide more details on the estimate? $\endgroup$
    – Minkov
    Commented Jul 26, 2016 at 4:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .