Skip to main content
2 of 3
Updated information obtained in comment.
Dorian
  • 2.6k
  • 23
  • 32

How to minimize the length of a graph connecting n points in $\mathbb{R}^3$

More precisely I would like to consider the following problem:

Let $\{a_i\}_{i=1}^n$ be n points in $\mathbb{R}^3$ and assume I have the constraint $\min_{i \neq j} |a_i-a_j| = r_{min}>0$. How can I place $n$ points in $\mathbb{R}^3$ as to minimize $\sum_{i \neq j} |a_i-a_j|.$

When $n=2$ this is trivial. When $n=3$ the minimizer will clearly be an equilateral triangle with a point at each vertex. When $n=4$ as pointed out by the commenter below, the solution would be a tetrahedron. For higher $n$ the answer is not clear to me. I would also be interested in the patterns in the asymptotic limit as $n \to +\infty$.

I presume that if this is known, it is a well established result in graph theory, and I would appreciate any references.

Dorian
  • 2.6k
  • 23
  • 32