MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this 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
up vote 4 down vote accepted

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.
      Spheres in Sphere
      (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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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