P74 · Extremal configurations · Classic · Applied frontier

Covering an equilateral triangle with n equal discs · n = 9

Place n centres in a unit equilateral triangle. Every centre has the same covering radius; every point of the triangle must lie in at least one disc, and that radius is minimised.

Instancen = 9

ObjectiveMinimize the covering radius

Proven optimum0.166666667608464The construction by Hans Melissen appears in Figure 2 of Nurmela (2000); the paper's continuous value is 0.1666666666666666667. The paper also reports this n as proved optimal; the site's nine-decimal reconstruction of the published contact graph verifies at 0.166666667608464.

Proven floor√(A(K)/(π·9))no arrangement can go below 0.123752541563016 · the record stands 34.7% above itHere K is the verifier's fixed-grid equilateral triangle and A(K) is its area. The area bound nπr² ≥ A(K) gives r ≥ √(A(K)/(πn)); the displayed value is rounded down from the exact rational value of A(K)

FinishedAn answer reaching the ceiling is already published, so there is nothing left to take

Formal definition

ContainerThe closed convex polygon with vertices (0,0), (1,0), and (0.5,0.866025404), the site's unambiguous nine-decimal representative of an equilateral triangle
SubmissionExactly n distinct points inside the container
ScoreTake the distance to the nearest centre at every place in the container, then the largest of those distances; rational Voronoi polygons make the verifier exact $r (P) = \max_{x \in K} \min_{i} ‖ x - p_{i} ‖$
ObjectiveMake the covering radius as small as possible $\min_{P} r (P)$

Open the editor and look ↗

VERIFIED CONSTRUCTION9 equal discs of shared radius 0.166667; the marked place is the hardest to reach, and it is what sets the radius

Getting a feel for it

Corners and interior compete for centres

The three sharp corners demand attention, but pushing every centre outward leaves a hole in the middle. The best configurations are usually not a simple equally spaced triangular grid.

Published records and verifiable constructions are included

Nurmela (2000) collected and extended high-precision constructions for n=2–36. The site reconstructs n=7–36 from the contact graphs in Figures 2–4, showing both the paper's continuous value and the verifier-exact nine-decimal certificate. The n=9 and n=10 rows are proved optimal; the other n≤36 rows remain challengeable known bests. The paper explicitly reports no searches beyond n=36, so n=37–40 ship only transparent site starts obtained by filling successive farthest holes of n=36, without invented external records.

Source

Current leader

0.166666667608464

the covering radius

OptimalThe optimum is proven; there is nothing left to gain

Answer sourceHans Melissen

Solution methodPublished reference construction

The optimum is proven; there is nothing left to gain

ANSWER FORMAT

How to write your answer

The base runs from (0,0) to (1,0), with apex (0.5, 0.866025404). This explicitly defined nine-decimal representative of the equilateral triangle is the boundary the verifier actually uses.

Submit points: exactly n centres, with each coordinate a decimal string of at most nine places. The verifier computes the shared radius; smaller is better.

The current leader's answer

{
  "points": [
    [
      "0.833333333",
      "0"
    ],
    [
      "0.583333328",
      "0.144337564"
    ],
    [
      "0.333333333",
      "0"
    ],
    [
      "0.833333328",
      "0.288675132"
    ],
    [
      "0.083333334",
      "0.144337568"
    ],
    [
      "0.333333333",
      "0.288675131"
    ],
    [
      "0.583333333",
      "0.433012702"
    ],
    [
      "0.333333331",
      "0.577350263"
    ],
    [
      "0.583333328",
      "0.721687834"
    ]
  ]
}

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

Instance parameters

{
  "n": 9
}

The current leader's answer

{
  "points": [
    [
      "0.833333333",
      "0"
    ],
    [
      "0.583333328",
      "0.144337564"
    ],
    [
      "0.333333333",
      "0"
    ],
    [
      "0.833333328",
      "0.288675132"
    ],
    [
      "0.083333334",
      "0.144337568"
    ],
    [
      "0.333333333",
      "0.288675131"
    ],
    [
      "0.583333333",
      "0.433012702"
    ],
    [
      "0.333333331",
      "0.577350263"
    ],
    [
      "0.583333328",
      "0.721687834"
    ]
  ]
}

Submit points: exactly n centres, with each coordinate a decimal string of at most nine places. The verifier computes the shared radius; smaller is better. · Verifier v1.0.0

DISCUSSION

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?