Create N points that are spaced as far as possible within a D dimensional sphere

Question

I'm not a big geometry buff, but I was wondering if you're give a dimension $D$ and a number of points $N$ and a radius $R$ of a sphere in that dimension. How would you generate $N$ points on the edge or in the sphere such that their magnitude and cosine similarity between each point is as far as possible? The dimensional space could be something as large as 512.

The ultimate goal is to achieve something like: Assume we're placing planets in a galaxy that is spherical, but we have no idea how big each planet is, so we want to place all the origins of each planet as far as possible from each other in order to avoid overlapping even if the planets are very large.

Answer 1

One way to pick a random point on a $d$-dimensional hypersphere ${\cal S}$ is to generate $n$ Gaussian random variables $x_1, x_2, ..., x_n$ and then the distribution of the vectors

$$ \frac{1}{\sqrt{x_1^2 + x_2^2 + \cdots + x_n^2}} \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix}$$

is uniform over the surface ${\cal S}^{d-1}$, as desribed in

Muller, M. E. "A Note on a Method for Generating Points Uniformly on N-Dimensional Spheres." Comm. Assoc. Computing Machinery 2, 19-20 (Apr. 1959)

Answer 2

In one dimension, you can place two points at $x = 1$ and $x = -1$. If you need more points, the best you can do is to evenly space them between the endpoints because the entire boundary is occupied.

In two dimensions, you can use the corners of a regular n-gon inscribed in the unit circle, to get an arbitrarily large number of equally spaced points. (I'm not completely clear what your criterion is, but if you wanted interior points as well, I'm not sure yet how you would optimize for closest to equal distance between all pairs of points; it may be that the n-gon is still optimal even in that case.

In three dimensions, I have always found it interesting from VSPER molecular geometry in chemistry, that you can equally space two, or three, or four, or six atoms around a central atom, but for five the closest you can get is the trigonal bipyramidal form, with two on the "North Pole" and "South Pole" and three equally spaced around the "equator". Likewise the compound $IF_7$ demonstrates that the lowest energy state for seven has the poles and five equally spaced around the equator. In the chemistry case, what is being optimized is the lowest energy state of the mutual repulsion of the electron domains around the central atom, which sounds similar to the condition you want. Using point groups based on the Platonic solids (tetrahedron, cube, octahedron, dodecahedron, icosahedron) you can get a few more with total symmetry. Buckminsterfullerene $(C_{60})$ has a higher symmetry, probably the maximum that can be achieved in 3 dimensions.

In higher dimensions, with $N \leq D$, you can use the lower dimensional arrangements, which remain optimal in the higher dimensional setting. For $N = D + 1$ the generalization of a tetrahedron has total symmetry. I've never worked out that formula myself but I am sure it has been done. It reminds me of the formula for the content (generalization of length, area, volume) of a hypersphere in n dimensions.

If you can state the exact condition you are trying to optimize, it might help others to home in more precisely on what you need.