11
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Possible duplicate: math.stackexchange.com/questions/9846/… See my answer there for links. $\endgroup$ – lhf Apr 7 '11 at 20:55
  • $\begingroup$ Thanks, I have marked this question as a duplicate. [Update] Actually this question appears a little bit different, anyway... $\endgroup$ – Arin Chaudhuri Apr 7 '11 at 21:00
  • 2
    $\begingroup$ 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. $\endgroup$ – hardmath Apr 7 '11 at 21:27
  • $\begingroup$ @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 $\endgroup$ – joriki Apr 8 '11 at 5:25
  • $\begingroup$ @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". $\endgroup$ – hardmath Apr 8 '11 at 11:57
6
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

For the classic $2$-sphere, Dave Rusin's excellent collection of links and notes in Mathematical Atlas has disappeared from the Web, but see:

The most regular placements of points on a sphere correspond to the vertices of Platonic solids (Wikipedia)

However only five such configurations exist, for n = 4,6,8,12,20 vertices.

There is an updated collection of links at Anton Sherwood's page on sphere distribution problems.

Around the middle of the sci.math 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.

$\endgroup$

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.