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.

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.

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.