Improve or prove optimal the packing of 50 equal circles in a unit square
Statement
Place 50 points in the closed unit square $[0,1]^2$ so as to maximize the minimum pairwise Euclidean distance $s_{50}$. Equivalently (scaling), pack 50 non-overlapping equal circles of maximum radius into a unit square; the two problems are related by $r = s/(2(1+s))$ given points, or directly $s_{50}$ is the max achievable minimum separation. The optimal value $s_{50}$ is not known: only a best-known (conjectured-optimal) configuration is recorded. Exhibit a configuration whose minimum pairwise distance exceeds the current best-known value, or prove that the best-known configuration is optimal.
Acceptance. FULLY RESOLVES: a rigorous (e.g. interval-arithmetic branch-and-bound) proof that the best-known 50-circle packing is optimal, determining $s_{50}$. PARTIAL (improve record): a list of 50 points in $[0,1]^2$ (coordinates) whose minimum pairwise distance strictly exceeds the current Packomania best-known $s_{50}$; verifier -- compute all $\binom{50}{2}$ pairwise distances, confirm the minimum, and confirm all points lie in $[0,1]^2$. PARTIAL: a certified upper bound on $s_{50}$ narrowing the gap to the best-known lower bound.
Background
Rigorous optimality proofs for packing $N$ equal circles in a square are known only for small $N$: all $N \le 30$, and $N = 31, 32, 33$ by computer-assisted interval-arithmetic global optimization (Markot & Csendes and others; see P. G. Szabo et al., 'Global Optimization in Geometry -- Circle Packing into the Square', survey). For $N = 50$ the value is unproven. Best-known configurations and separations for $N$ up to ~1000 are maintained by E. Specht on Packomania (packomania.com, 'circles in the unit square'). SIAM J. Optim. and J. Global Optim. host the verified-optimization methodology.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Szabo et al. -- Global Optimization in Geometry: Circle Packing into the Square (survey) | link |
| REF-02 | E. Specht -- Packomania (best-known equal-circle packings) | link |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.