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 '16 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$ – Martin Thoma Oct 19 '16 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$ – Martin Thoma Oct 19 '16 at 20:49
  • $\begingroup$ Am I the only one not grasping how the (maximum) distance between $k>2$ points is defined here? $\endgroup$ – Jack D'Aurizio Oct 19 '16 at 20:51
  • $\begingroup$ @JackD'Aurizio I've added a definition of the distance. I hope that helps. $\endgroup$ – Martin Thoma Oct 19 '16 at 21:01

(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 $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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