Covering a square with n equal discs · n = 31
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.
Instancen = 31
ObjectiveMinimize the covering radius
Proven floor1/√(π·31)no arrangement can go below 0.101331440553455 · the record stands 20.4% above itThe area bound: n discs of radius r cover at most nπr² of area and the square has area 1, so r ≥ 1/√(πn) — for every n, resting on nothing unproven
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
