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. – 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

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$? – 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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 25, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9408568739891052, "perplexity_flag": "head"}