Improve or prove optimal the thinnest covering of a unit square by 20 equal circles
Statement
Cover the closed unit square $[0,1]^2$ by $N=20$ equal circles (disks) so as to minimize their common radius $r_{20}$: find center positions such that every point of the square lies within distance $r$ of some center, minimizing $r$. The optimal covering radius $r_{20}$ is not known -- only a best-known (conjectured-optimal) configuration is recorded. Exhibit a valid covering with radius strictly less than the current best-known $r_{20}$, or prove that the best-known configuration is optimal. (This is the covering counterpart of circle packing: minimize radius subject to full coverage, rather than maximize radius subject to disjointness.)
Acceptance. FULLY RESOLVES: a rigorous proof of the optimal covering radius $r_{20}$ (e.g. via verified global optimization). PARTIAL (improve record): 20 center coordinates in the plane and a radius $r < r_{20}^{best}$ such that the whole unit square is covered; verifier -- the covering radius (maximum over $[0,1]^2$ of the distance to the nearest center) is $\le r$, checkable exactly by evaluating that max at the finite set of candidate 'deepest hole' points (pairwise circle-boundary intersections inside the square, intersections of circle boundaries with the square's edges, and the four corners), or via a fine grid with a Lipschitz-1 safety margin. PARTIAL: a certified lower bound on $r_{20}$.
Background
Best-known coverings of the unit square by up to 30 equal circles were computed by K. J. Nurmela & P. R. J. Ostergard, 'Covering a square with up to 30 equal circles', report HUT-TCS-A62, Helsinki University of Technology, 2000 (quasi-Newton / BFGS minimization of uncovered area over random restarts). Rigorous optimality is established only for small $N$ (e.g. $N \le 6$, the latter by deterministic global optimization); for $N=20$ the value is unproven. See also K. Nurmela's covering tables and Melissen's work on optimal coverings.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Nurmela & Ostergard -- Covering a square with up to 30 equal circles (2000) | link |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.