Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 2 down vote favorite

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?

share|improve this question
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. – Eugene Shvarts Jan 26 at 1:42
1  
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. – Rahul Narain Jan 26 at 1:46
Ok, so far what I'm getting from those questions is that only approximate solutions exist for this type of problem. – Matt Munson Jan 26 at 2:03

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
Cool. But what is the values of $x$ for a given value of $d$? And where did you get $1+d/2$? – Matt Munson Jan 26 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. – Rahul Narain Jan 26 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. – Matt Munson Jan 26 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. – Rahul Narain Jan 26 at 9:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.