3
$\begingroup$

Place $N$ points in a 3d cube in a way that maximizes the minimum of their pairwise distances.

The problem can easily be solved for $N\lt5$, but how to proceed for larger $N$?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Why the downvotes and the close vote? $\endgroup$
    – Stefan Kohl ♦
    Dec 12, 2013 at 22:00
  • 6
    $\begingroup$ Perhaps the downvotes are for asking a well-known hard question without any sign of research effort. $\endgroup$
    – Gerry Myerson
    Dec 12, 2013 at 22:36

2 Answers 2

Reset to default
7
$\begingroup$

This is equivalent to sphere packing in a cube. This type of problem is messy. Even if you look at circle packings in a square, only a few configurations have been proved optimal. The best configurations known for many other values are complicated, and it's not easy to specify a short list of possible combinatorial types of configurations to test.

Hugo Pfoertner has tabulated numerical calculations for up to $72$ spheres in a cube. These are not guaranteed to be the best possible.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for your insightful answer. I suppose the packing problem is: given N, find maximal R such that N spheres of radii no less than R can be packed into a unit cube. In addition, find the corresponding packing configuration(s). The equivalent maximized minimal pairwise distance of my original question is then R(1+2R) $\endgroup$
    – Minnie
    Dec 13, 2013 at 0:05
  • $\begingroup$ 1. The packing problem as formulated above is different from the standard formulation, in which the quantity to be maximized is the volume of the spheres. Is it obvious that the two are equivalent? 2. Correction to the above: 2R(1+2R) $\endgroup$
    – Minnie
    Dec 16, 2013 at 15:42
3
$\begingroup$

A very simple, cute "math-folklore" solution for $N=9$ goes as folows: the eight vertices and the center of the unit cube form a configuration of nine points, in which the minimum distance between them is $\sqrt3/2$. This is the maximum of the minimum over all configurations. Proof: partition the cube into eight cubes of edge length $1/2$. No matter how you place nine points in the unit cube, two of them must be contained in one of the small cubes; the distance between them is at most $\sqrt3/2$. With a bit more elaboration one can prove that the extreme configuration is unique. Analogous proofs work for five points in a square and seventeen points in the $4$-dim. cube, but fails in dimensions higher than $4$.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Thank you, this is very elegant. As a practical matter, I will rarely need to go beyond N=9. $\endgroup$
    – Minnie
    Dec 16, 2013 at 15:49
  • 1
    $\begingroup$ The proofs for $N\le 4$ and $N=8$ are not very hard either. The proofs and configurations for $N=7, 9, 10,$ and $11$ (very non-trivial) were found by Jonathan Shaer, and for $N=14$ by Antal Joos, this last one one quite recently, despite an long-known and highly believable conjecture. As far as I know, no proof exists for any $N>14$. $\endgroup$
    – Wlodek Kuperberg
    Dec 16, 2013 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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