For this question, I'm thinking only about the euclidean distance:

Let $p_1 = (x_1^{(1)}, \dots, x_n^{(1)})$ and $p_2 = (x_1^{(2)}, \dots, x_n^{(2)})$ be $n$-dimensional points. The euclidean distance of $p_1$ and $p_2$ is $$d(p_1, p_2) = \sqrt{\sum_{i=1}^n {\left (x_i^{(1)} - x_i^{(2)} \right )}^2}$$

Lets say $\alpha(n, k)$ is the maximum distance for $k$ points in the unit-hypercube of $\mathbb{R}^n$:

$$\alpha(n, k) = \max( \left \{\min(d(p_i, p_j))| (p_1, \dots, p_k) \in [0, 1]^n, i, j \in \{1, \dots, k\} \right \})$$

$n = 1$

  • $\alpha(1, k = 2 = 2^n) = 1$
  • $\alpha(1, k = 3)= 0.5$
  • $\alpha(1, k) = \frac{1}{k-1}$

$n = 2$

  • $\alpha(2, k = 2) = \sqrt{2}$: The maximum distance is the diagonal and hence $\sqrt{1+1}$
  • $\alpha(2, k = 3)=?$
  • $\alpha(2, k = 4 = 2^n) = 1$: Putting each point at the corners of the square.
  • $\alpha(2, k = 5)$: I guess like 4 but with one point in the center? (hence $\frac{\sqrt 2}{2}$?)

n = 3

  • $\alpha(3, k = 2) = \sqrt{3}$: The diagonal again and hence $\sqrt{1+1+1}$
  • $\alpha(3, k = 2^n)$: The corners again and hence 1

Arbitrary $n$

  • $\alpha(n, k=2) = \sqrt{n}$
  • $\alpha(n, 2^n) = 1$

What is $\alpha(n, k)$?

  • $\begingroup$ if $k\leq n$ isn't it sufficent to consider the graph made up by the corners of the hypercube? $\endgroup$
    – tired
    Oct 19, 2016 at 20:33
  • 1
    $\begingroup$ @tired: I'm not sure. This would mean $\alpha(2, 3) = 1$, but I'm relatively certain that you could place the points on the edges (not the corners) and get a bigger distance. $\endgroup$ Oct 19, 2016 at 20:40
  • 1
    $\begingroup$ @tired: No. This would mean $\alpha(2, 3) = 1$. But $p_1 = (0, 0.5)$, $p_2 = (0, 0.75)$, $p_3 = (1, 1)$ has a bigger distance than 1. $\endgroup$ Oct 19, 2016 at 20:49
  • $\begingroup$ Am I the only one not grasping how the (maximum) distance between $k>2$ points is defined here? $\endgroup$ Oct 19, 2016 at 20:51
  • $\begingroup$ @JackD'Aurizio I've added a definition of the distance. I hope that helps. $\endgroup$ Oct 19, 2016 at 21:01

2 Answers 2


(This should be a comment but I'll post it as an answer since I don't have enough reputation to comment.)

I'd like to answer the case with $n = 2$ and $k = 3$. The proof is really simple and can be found geometrically, if you assume two facts:

  • the first point is on a vertex of the 2D hypercube, and the two others are on the opposite edges. It makes sense all 3 points should be on the edges to maximize distance.
  • the resulting triangle is equilateral. This also makes sense, as in a non-equilateral triangle, one of the sides would have a smaller length and thus penalize the minimal distance between the points.

The triangle will look like this:

Equilateral triangle inside unit square

Solving for $x$ (using the fact than the triangle is equilateral), we find $x = 2-\sqrt{3} \approx 0.2679$, and finally:

$$ a = \alpha(2, k=3) = \sqrt{6} - \sqrt{2} \approx 1.035276\dots $$

But solving for $\alpha(n, k)$ in the general case seems challenging and I did not find a solution on the internet, interesting problem!


Let's start with the $2$D case.

Consider to have $m$ circles of radius $r$.

Packing them inside a square $C_r$ of size $(1+2r) \times (1+2r)$, will be equvalent to ask that their centers be inside the unit square and at mutual distance $r \le d$.

Then your question is equivalent to:
what is the maximum $r$ such that it is still possible to pack $m$ circles in the square $C_r$ ?

Clearly the same holds for any dimension $n$ and of course, you can size down the square to become unitary and correspondingly the radius of the balls by $\frac{1}{1+2r}$, and ask
in $n$ dimension, what is the maximum $\rho = r/(1+2r)$ such that it is still possible to pack $m$ balls of radius $\rho$ in the unit cube ?
and that is a typical Packing problem, whose difficulty is well known.

Some results have been reached and published in specialized literature and sites, and some of them are proved.

For example, for $n = 2$ in this site it is stated that the minimum side of the square containing $3$ unitary circles is $$ s = 2 + {{\sqrt 2 + \sqrt 6 } \over 2} $$ then the corresponding radius for your problem will be $$ {s \over 1} = {{1 + 2r} \over r}\quad \Rightarrow \quad r = {1 \over {s - 2}} = {2 \over {\sqrt 2 + \sqrt 6 }} = 0.5176 \ldots $$


You must log in to answer this question.

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