# 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$, 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.

Update: Thanks for the helpful comment and the answer. This answers my question.

-
For $n=4$ the vertices of a tetrahedron would be optimal. Also note that you can rephrase your problem to a sphere packing problem. –  Koen S Jan 30 '12 at 11:36
add comment

## 1 Answer

As Koen S says, your problem is related to sphere packing. The optimal packings of equal spheres in a larger sphere will should be close to optimal under your measure.

(Image from this link.)

As $n \rightarrow \infty$, the packing should approach the optimal density $\frac{\pi}{\sqrt{18}}$, cubic close-packing clipped to a bounding sphere.

-
The sphere packing problem essentially asks you for a lower bound on max |a_i - a_j| (i.e L_infinty norm) given a lower bound on min |a_i - a_j|. Poster is asking for a lower bound on L_1. It wouldn't be surprising if these were close, but is it obvious? –  JSE Feb 1 '12 at 14:39
@JSE: I certainly have no proof. Therefore, I have changed "will be" to "should be"! –  Joseph O'Rourke Feb 1 '12 at 15:40
For large n, it should be clear that configurations that are contained in an ellipsoid of some eccentricity are nonoptimal, as you can move an extremal point to one closer to the center of mass. If nothing else, you should be able to show e.g. for n > 20 a containing ellipsoid with eccentricity greater than delta_n is nonoptimal. Gerhard "Proof Through Elimination Of Cases" Paseman, 2012.02.01 –  Gerhard Paseman Feb 1 '12 at 17:23
add comment