Covering a square with n equal discs
Place n points in the square of side 1. Let r be the distance from the worst-served place — the one farthest from every point — to the point nearest it, and make r as small as possible. Equivalently: cover the whole square with n equal discs of radius r, and make r as small as you can.
Formal definition
- ContainerThe unit square: the origin (0, 0) at its lower-left corner, (1, 1) at its upper right, boundary included
- SubmissionExactly n points, each coordinate a decimal with at most nine places; no two points may coincide
- Scorer(P) is the largest, over the square, of the distance to the nearest submitted point. The verifier finds its square exactly, then takes an exact square root rounded upward at 10⁻¹⁸ — upward, so the stored number never claims a tighter cover than the arrangement achieves
- Why this is finiteInside its own nearest-neighbour region a point is the nearest one, and |x − p|² is convex, so its largest value on a convex polygon is at a corner. The search over a continuous region collapses to finitely many rational corners, in whole numbers throughout, touching no float
- ObjectiveMake r(P) as small as possible over all legal point sets P
Getting a feel for it
It pulls the opposite way to packing
Packing forbids overlap, so the circles shrink inward and keep off the boundary; covering allows it and forces the discs into the corners instead. For the same n a good cover looks nothing like a good packing.
Where the frontier is
The grid is not optimal. Kershner settled covering the infinite plane in 1939 (hexagons are the thriftiest), but the boundary of a square creates a very different corner effect. n=5 and n=7 are proved; n=6 and n=8–30 show the best public constructions in the literature and may still be improved. This site has reconstructed every HUT-TCS-A62 vector figure as verifier-ready coordinates. n=31–35 are open for play, but no value is presented as a literature record until its published construction can be reproduced publicly.
SourceCurrent best solutions by n
Each n is an independent record with a page of its own. Open any of them to inspect the current construction, then challenge it.
Discussion (0) ↓Data and citation
Every sub-problem in this family — authoritative scores, proof status, coordinates and sources — lives at the stable address below, published under CC BY 4.0. Scores move as records fall, so cite the generatedAt timestamp the file carries.
GET https://minmaxarena.com/data/circles-covering-a-square.json
Cite the frozen 2026-08 edition: records move, a frozen edition never does, so the citation is still checkable years later.
GET https://minmaxarena.com/data/editions/2026-08/circles-covering-a-square.json
BibTeX (click to copy)
@misc{minmaxarena-circles-covering-a-square-2026-08,
title = {{Covering a square with n equal discs} (P73)},
author = {{MinMax Arena}},
year = {2026},
note = {Machine-verified records, 2026-08 edition},
url = {https://minmaxarena.com/data/editions/2026-08/circles-covering-a-square.json},
license = {CC BY 4.0}
}Discussion
Talk strategy, share methods, ask why you are stuck. Posts carry your public byline, the same name your records use; the #number after it is the account's signup ordinal, so a name cannot be worn by someone else. The floor is earned: break a record once, anywhere, and it is yours for good. New posts appear after an automated review.
No threads yet. Be the first to talk about this problem?