I want to select M points on the N-sphere such that $min_{i\neq j,i,j\in \{1..M\}} ||x_i - x_j||$ is maximized.
Are there good upper bounds for this max-min distance?
3
-
$\begingroup$ What do you consider "good"? $\endgroup$– Igor RivinMay 21, 2014 at 16:57
-
$\begingroup$ Better than the obvious ones (e.g. 2). I basically just said good because the question without it is trivial. $\endgroup$– C. M.May 21, 2014 at 17:07
-
$\begingroup$ See also neilsloane.com/packings/index.html $\endgroup$– Stephane BersierDec 21, 2022 at 19:44
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Call the quantity in question $D(M, N),$ and let the volume of the spherical cap of dimension $N$ and radius $r$ $V(N, r),$normalized so that the volume of the whole sphere is $1.$ Since the caps of radius $2\arcsin D(M, N)/4$ are disjoint, you know that:
$$ M V(N, 2\arcsin D(M, N)/4) < 1. $$ Since The function $V(N, r)$ is well understood, this gives you a bound.
answered May 21, 2014 at 17:02
-
$\begingroup$ I get the gist of your construction. Let me fiddle around with it a bit to see if I get a usable result from it. Very elegant construction though. $\endgroup$– C. M.May 21, 2014 at 17:32
-
1$\begingroup$ This estimate can be improved using Boroczky's classic bound: ams.org/mathscinet-getitem?mr=512399 $\endgroup$– Ian AgolMay 22, 2014 at 5:43