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!


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.