# How to choose $x$ evenly distributed points from within an n-ball

I would like to know how to choose $x$ evenly distributed points from within an n-ball. I think a formal way of defining this is that we want to choose $x$ points from within the n-ball such that we maximize the closest distance between any two points. As a result, it seems, all points should be evenly spaced and many should be located at the surface. What is an algorithm to generate such a set?

• Here is an algorithm for studying the 2D sphere to get a feel for potential theory techniques, and here is a stackoverflow thread discussing the general problem. Commented Jan 26, 2013 at 1:42
• This question is almost an exact duplicate, except it's for points on the sphere instead of the ball. The answers there may still be helpful.
– user856
Commented Jan 26, 2013 at 1:46
• Ok, so far what I'm getting from those questions is that only approximate solutions exist for this type of problem. Commented Jan 26, 2013 at 2:03

Suppose the closest distance between two points is $d$. This implies that $x$ spheres of radius $d/2$ centered at your points can fit inside a sphere of radius $1+d/2$ without overlapping. Equivalently, $x$ spheres of radius $d/(2+d)$ fit in a unit sphere, and maximizing $d$ is equivalent to maximizing $d/(2+d)$.

So your problem amounts to finding the densest packing of $x$ spheres in a sphere. There are some (approximate) precomputed solutions for $x\le51$ in three dimensions, but there is probably no closed-form solution in general. I guess this is not an answer to your question of what is an algorithm to generate such sets, but searching for "sphere packing algorithms" may find you some useful references.

• Cool. But what is the values of $x$ for a given value of $d$? And where did you get $1+d/2$? Commented Jan 26, 2013 at 3:18
• @Matt: Finding the largest $x$ for a given $d$ is just as hard as finding the largest $d$ for a given $x$; as I said there is no known explicit formula. You get $1+d/2$ as follows: If a point lies within distance $1$ of the origin, then a sphere of radius $d/2$ around it may not be contained in the unit sphere around the origin, but it will be contained in a sphere of radius $1+d/2$ around the origin.
– user856
Commented Jan 26, 2013 at 4:45
• Ok, I see. And its 1 because we start from the unit circle, but it could actually be any positive number. Nice. Commented Jan 26, 2013 at 9:15
• @Matt: Right, I somehow assumed you meant the unit $n$-ball in your question. It's just a matter of scaling in the end.
– user856
Commented Jan 26, 2013 at 9:19

I came here looking for an answer to help me implement what you are seeking.

First, the technical term I think you are looking for is a Poisson distribution. In a plane there is a nice algorithm called Bridson's Algorithm that generates a distribution efficiently.

It is possible to use this algorithm in higher dimensions, if you can effectively generate points in a spherical shell.