Covering a square with n equal discs · n = 14
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 = 14
ObjectiveMinimize the covering radius
Best known, unproven0.18551054726041864107The construction by Kari J. Nurmela and Patric R. J. Östergård is reproduced in Nurmela and Östergård's HUT-TCS-A62 report (2000); the paper's best-known radius is 0.18551054726041864107, with optimality open. The nine-decimal certificate reconstructed from its vector figure and contact topology verifies at 0.185510547628495; it is a reference answer, not a new record.
Proven floor1/√(π·14)no arrangement can go below 0.150786008773026 · the record stands 23.0% 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
