Maximum number of points with a fixed minimum distance in a $d$-dimensional ball

332 Views Asked by At

Let $c \leq r$ be real numbers greater than $0$, $d \in \mathbb{N}$ and $B_r(0) = \lbrace x \in \mathbb{R}^d \mid \Vert x \Vert \leq r \rbrace$, the ball with radius $r$ at point $0$ ($\Vert \cdot \Vert$ is here the Euclidean norm). Let $S$ be a set of points such that $S \subseteq B_r(0)$ and for every $x,y \in S$ with $x \neq y$ it is $\Vert x-y \Vert \geq c$.

I want to know what is the maximum number of $\vert S \vert$ as a function of $c$,$r$ and $d$ for a set $S$ that fulfills the conditions above.

EDIT: Because of the hardness of this problem: Are there any lower bounds for this number?

1

There are 1 best solutions below

0
On

Consider the Ball $$B_r'(0) = \lbrace x \in \mathbb{R}^d \mid \Vert x \Vert \leq r' \rbrace, r'=r+\frac{c}{2}$$

It can be easily seen that your problem is now equivalent to packing balls of radius $\frac{c}{2}$ into this modified ball.

Even for $d=2$ this is already a really hard problem, mainly numerical algorithms are used to get an approximations to the best packings. See also this page for numerical results.