4
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ For $n=4$ the vertices of a tetrahedron would be optimal. Also note that you can rephrase your problem to a sphere packing problem. $\endgroup$
    – Koen S
    Commented Jan 30, 2012 at 11:36

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 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? $\endgroup$
    – JSE
    Commented Feb 1, 2012 at 14:39
  • $\begingroup$ @JSE: I certainly have no proof. Therefore, I have changed "will be" to "should be"! $\endgroup$
    – Joseph O'Rourke
    Commented Feb 1, 2012 at 15:40
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Feb 1, 2012 at 17:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .