# well separated points on sphere

Is there a way to generate k points on a n-sphere, say, $x_1,\dots,x_k$ such that $\min_{ i \neq j } \| x_i - x_j \|$ is as large as possible? Approximate solutions are also OK, I just need well separated points on a sphere.

-
Possible duplicate: math.stackexchange.com/questions/9846/… See my answer there for links. –  lhf Apr 7 '11 at 20:55
Thanks, I have marked this question as a duplicate. [Update] Actually this question appears a little bit different, anyway... –  ACARCHAU Apr 7 '11 at 21:00
One of lhf's links leads to a page of results on spherical packings, which is precisely to maximize the minimum distance between a specified number of points on a 2-sphere. Little is known about the problem beyond dimension 5 or so. I looked into that about half a year ago for someone in a newsgroup. –  hardmath Apr 7 '11 at 21:27
@hardmath: I disagree with "little is known about the problem beyond dimension 5 or so". Conway & Sloane's "Sphere Packings, Lattices and Groups" is quite a voluminous compendium, and quite a bit of it is about sphere packings in higher dimensions. You can see the table of contents here: gbv.de/dms/goettingen/245890696.pdf –  joriki Apr 8 '11 at 5:25
@joriki: I should have framed it as a comparative. That's Sloane's page linked above. It may be outdated; the link to his book "Sphere Packings, Lattices, and Groups" with Conway (3ed., 1998, same as your PDF) seems to be broken. Coverage of dimensions > 5 there is sparse and unsystematic, amounting to only a couple of dozen packings, and while the he writes the packings for dimensions 3,4,5 listed in part 1 are "putatively optimal", the higher dimensional packings are only said to be "nice", "good", or "interesting". –  hardmath Apr 8 '11 at 11:57
show 1 more comment

I suspect you might get reasonable results by starting with k randomly chosen points and optimizing locally (find the closest pair, and move one of them to a point that's a local max of the minimum distance from all other points, then repeat...).

-

Here's a sci.math thread, "putting points on a unit sphere?", from July 2010, that provides some additional links to the literature.

Around the middle of the thread I point out the three regular polytopes that exist in each dimension $N \geq 5$, namely the N-simplex (with N+1 vertices), the N-cube (with $2^N$ vertices), and the dual of the latter, the N-orthoplex (with 2N vertices). If the number of points k happens to match up with one of these, then you are in luck!

For more general numbers of points on a hyper-sphere, I suggested an approximate solution that inducts on the dimension. That is, the N-1 sphere (sitting in N dimensions) has longitudinal sections that are N-2 spheres, e.g. the equator. A crude lower bound on the maximum number of points with a given distance (equiv., central angular) separation can be obtained by longitudinally stratifying the N-1 sphere into these N-2 spheres appropriately far apart, then doing the packing in the reduced dimensions (using when sufficiently low dimensions are reached Sloane's library of known configurations).

One can also get an equally crude upper bound on number of points with given separation R by dividing the "surface" measure of the N-1 sphere (sitting in N dimensions) by the measure of "spherical caps" having the given distance or angular "radius" R/2.

I applied these ideas to a separation of 30 degrees on the 2-sphere, and got a lower bound (constructive) of 44 points and an upper bound of 59 points. Sloane's library gives the optimum count for this separation as 48. It seems inevitable that as the dimension increases, such approximations will become less and less accurate. Still, if one needs a design for an arbitrary number of points, that's how I'd tackle it. If the number of points were happily close to one of those special regular polytopes, then I'd try perturbing the coordinates to add (or lose) a few points.

Edit: Corrected my example to say separation of 30 degrees, where originally I posted 60 degrees.

-