P73 · Extremal configurations · Classic

Covering a square with n equal discs · n = 7

Place n points in the unit square to minimize the maximum distance r from any point of the square to its nearest placed point; equivalently, cover the unit square with n equal discs of shared radius r and minimize r.

Instancen = 7

ObjectiveMinimize the covering radius

Proven floor1/√(π·7)no valid arrangement can go below 0.213243618622923 · the record stands 28.6% 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

Record comparison

the covering radius · Lower is better

Record	Value / interval	Author / holder	Source
Proven optimum	0.274291885508214	Tibor Tarnai and Zsolt Gáspár2000	HUT-TCS-A62 ↗
Site record	No player record yet	—	—

FinishedA construction reaching the theoretical ceiling is already published, leaving nothing further to improve

Formal definition

ContainerThe closed unit square [0, 1] × [0, 1], with lower-left corner (0, 0) and upper-right corner (1, 1)
SubmissionExactly n distinct points, each coordinate a decimal string with at most nine places
Scorer(P) is the maximum over the square of the distance to the nearest submitted point. The verifier computes its exact rational square and rounds the square root upward at 10⁻¹⁸, guaranteeing a valid covering radius $r (P) = \max_{x \in K} \min_{i} ‖ x - p_{i} ‖$
Why this is finiteWithin each point's Voronoi cell, the convex function |x − p|² attains its maximum on a convex polygon at a vertex. The continuous maximum therefore reduces to checking finitely many rational Voronoi vertices in exact arithmetic
ObjectiveMinimize r(P) over all valid point sets P $\min_{P} r (P)$

Inspect in editor ↗

Layout shown: starter layout

1y0

1234567

0x1

VERIFIED CONSTRUCTION7 equal discs of shared radius 0.274292; the marked bottleneck point is the furthest from its nearest center and determines the radius

Getting a feel for it

Contrast with circle packing

Circle packing forbids overlap and keeps centres at least one radius away from the boundary; covering allows discs to overlap and protrude beyond the edges, making the four corners the primary bottlenecks. For the same n, optimal coverings and optimal packings have very different structures.

Literature results and open cases

Kershner proved in 1939 that the regular hexagonal lattice gives the thinnest covering of the infinite plane, but the boundary and corners of a square break lattice symmetry. Optimal coverings are proved for n = 5 and n = 7; n = 6 and n = 8–30 feature the best constructions from the literature (reconstructed as verifiable coordinates from the vector figures in report HUT-TCS-A62), while n = 31–35 remain open without publicly reproducible coordinates.

Source

LAYOUT & HISTORY

Starter layout

Inspect the layout, solver notes and record history.

The optimum is proven; no further improvement is possibleSubmit a proof / idea ↓Share a proof or bound argument in the discussion board. Accepted contributions earn proof points.

ANSWER FORMAT

How to write your answer

The container is the unit square [0, 1]² with lower-left corner (0, 0) and upper-right corner (1, 1). Submit n circle centres as decimal strings of at most nine places; the verifier computes the required covering radius directly.

Submit points: n circle centres, each coordinate written as a decimal string of at most nine places (such as "0.25"). The score is the shared radius needed to cover the whole square; smaller is better.

Starter answer

{
  "points": [
    [
      "0.749999999",
      "0.887145944"
    ],
    [
      "0.750000001",
      "0.112854059"
    ],
    [
      "0.249999999",
      "0.887145941"
    ],
    [
      "0.250000001",
      "0.112854056"
    ],
    [
      "1.000000000",
      "0.500000004"
    ],
    [
      "0.500000000",
      "0.500000000"
    ],
    [
      "0.000000000",
      "0.499999996"
    ]
  ]
}

Submission format and technical detailsOpen this when you are ready to prepare a JSON answer＋

Instance parameters

{
  "n": 7
}

Starter answer

{
  "points": [
    [
      "0.749999999",
      "0.887145944"
    ],
    [
      "0.750000001",
      "0.112854059"
    ],
    [
      "0.249999999",
      "0.887145941"
    ],
    [
      "0.250000001",
      "0.112854056"
    ],
    [
      "1.000000000",
      "0.500000004"
    ],
    [
      "0.500000000",
      "0.500000000"
    ],
    [
      "0.000000000",
      "0.499999996"
    ]
  ]
}

DISCUSSION

Discussion

Discuss strategies, share construction methods, or ask questions. Any signed-in user can post under their public byline and unique #UID. New posts appear after moderation.

网站提交成绩机制需要改善pikachu345#3154 replies28d ago