4
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Jan 26, 2013 at 1:42
  • 1
    $\begingroup$ 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. $\endgroup$
    – user856
    Jan 26, 2013 at 1:46
  • $\begingroup$ Ok, so far what I'm getting from those questions is that only approximate solutions exist for this type of problem. $\endgroup$ Jan 26, 2013 at 2:03

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Cool. But what is the values of $x$ for a given value of $d$? And where did you get $1+d/2$? $\endgroup$ Jan 26, 2013 at 3:18
  • $\begingroup$ @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. $\endgroup$
    – user856
    Jan 26, 2013 at 4:45
  • $\begingroup$ Ok, I see. And its 1 because we start from the unit circle, but it could actually be any positive number. Nice. $\endgroup$ Jan 26, 2013 at 9:15
  • $\begingroup$ @Matt: Right, I somehow assumed you meant the unit $n$-ball in your question. It's just a matter of scaling in the end. $\endgroup$
    – user856
    Jan 26, 2013 at 9:19
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .