P75 · Extremal configurations · Formed here · Applied frontier · Hard

Covering a regular pentagon with n equal discs · n = 31

Place the centres of n equal-radius discs in a regular pentagon so their union covers it completely, and minimise the shared radius.

Instancen = 31

ObjectiveMinimize the covering radius

Proven floor√(A(K)/(π·31))no arrangement can go below 0.078124524675343 · the record stands 22.4% above itHere K is the verifier's fixed-grid regular pentagon 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)

Formal definition

ContainerThe closed convex polygon with successive vertices (0.5,1), (0.024471742,0.654508497), (0.206107374,0.095491503), (0.793892626,0.095491503), and (0.975528258,0.654508497)
SubmissionExactly n distinct points inside the container
ScoreThe distance from the hardest-to-cover place to its nearest centre, determined exactly by finitely many rational Voronoi vertices $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 full editor ↗

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

Getting a feel for it

Fivefold symmetry need not survive

The boundary has five corners, but n is usually not a multiple of five. Extra centres reshape the interior Voronoi cells; as n changes, the farthest holes and adjacency topology change as well, so there is no obvious periodic motif that can simply be repeated.

Published work settles only one small case

Liu (2022) studies the continuous p-center problem in a regular pentagon and publicly illustrates n=3–10. Only n=5 closes the upper/lower-bound gap; after two hours of computation, n=7, 8, 9, and 10 still leave gaps of 5.87%, 5.75%, 6.35%, and 10.24%. The site reconstructs n=7–10 point by point from the vector objects in Figure 9 and uses their verifier-exact radii as known bests. No publicly reproducible external configurations were found for n=11–35, so those rows carry only transparent site multi-start baselines, not invented SOTA claims.

Source

Current leader

0.095587149715447

the covering radius

Answer sourceMinMax Arena

Solution methodMinMax Arena offline search

Challenge this record ↗

ANSWER FORMAT

How to write your answer

The container is the explicit nine-decimal representative of an upward-pointing regular pentagon whose circumcircle has diameter 1. The strict definition lists the five vertices used by the verifier.

Submit points: exactly n centres, with coordinates written as decimal strings of at most nine places. The verifier computes the radius exactly; smaller is better.

The current leader's answer

{
  "points": [
    [
      "0.412313787",
      "0.855036842"
    ],
    [
      "0.274402281",
      "0.528348235"
    ],
    [
      "0.296540927",
      "0.774224153"
    ],
    [
      "0.873873439",
      "0.497711041"
    ],
    [
      "0.19247563",
      "0.687938463"
    ],
    [
      "0.896066163",
      "0.643264741"
    ],
    [
      "0.371957348",
      "0.293961481"
    ],
    [
      "0.628291628",
      "0.157145031"
    ],
    [
      "0.852619598",
      "0.318274303"
    ],
    [
      "0.746134634",
      "0.428748749"
    ],
    [
      "0.425728654",
      "0.431581124"
    ],
    [
      "0.480167645",
      "0.726676485"
    ],
    [
      "0.730405788",
      "0.564025517"
    ],
    [
      "0.343926938",
      "0.667692399"
    ],
    [
      "0.753442416",
      "0.175574682"
    ],
    [
      "0.197617764",
      "0.322046432"
    ],
    [
      "0.368433321",
      "0.127544045"
    ],
    [
      "0.506792047",
      "0.177795681"
    ],
    [
      "0.296286218",
      "0.413241421"
    ],
    [
      "0.777767703",
      "0.697484159"
    ],
    [
      "0.134973987",
      "0.465704569"
    ],
    [
      "0.599528908",
      "0.635345466"
    ],
    [
      "0.450504266",
      "0.554910147"
    ],
    [
      "0.582849397",
      "0.467935231"
    ],
    [
      "0.545359331",
      "0.308958119"
    ],
    [
      "0.111001653",
      "0.614055527"
    ],
    [
      "0.691308107",
      "0.775440107"
    ],
    [
      "0.596776476",
      "0.821156745"
    ],
    [
      "0.689505551",
      "0.320611562"
    ],
    [
      "0.523811391",
      "0.931698608"
    ],
    [
      "0.242547173",
      "0.18376793"
    ]
  ]
}

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

Instance parameters

{
  "n": 31
}

The current leader's answer

{
  "points": [
    [
      "0.412313787",
      "0.855036842"
    ],
    [
      "0.274402281",
      "0.528348235"
    ],
    [
      "0.296540927",
      "0.774224153"
    ],
    [
      "0.873873439",
      "0.497711041"
    ],
    [
      "0.19247563",
      "0.687938463"
    ],
    [
      "0.896066163",
      "0.643264741"
    ],
    [
      "0.371957348",
      "0.293961481"
    ],
    [
      "0.628291628",
      "0.157145031"
    ],
    [
      "0.852619598",
      "0.318274303"
    ],
    [
      "0.746134634",
      "0.428748749"
    ],
    [
      "0.425728654",
      "0.431581124"
    ],
    [
      "0.480167645",
      "0.726676485"
    ],
    [
      "0.730405788",
      "0.564025517"
    ],
    [
      "0.343926938",
      "0.667692399"
    ],
    [
      "0.753442416",
      "0.175574682"
    ],
    [
      "0.197617764",
      "0.322046432"
    ],
    [
      "0.368433321",
      "0.127544045"
    ],
    [
      "0.506792047",
      "0.177795681"
    ],
    [
      "0.296286218",
      "0.413241421"
    ],
    [
      "0.777767703",
      "0.697484159"
    ],
    [
      "0.134973987",
      "0.465704569"
    ],
    [
      "0.599528908",
      "0.635345466"
    ],
    [
      "0.450504266",
      "0.554910147"
    ],
    [
      "0.582849397",
      "0.467935231"
    ],
    [
      "0.545359331",
      "0.308958119"
    ],
    [
      "0.111001653",
      "0.614055527"
    ],
    [
      "0.691308107",
      "0.775440107"
    ],
    [
      "0.596776476",
      "0.821156745"
    ],
    [
      "0.689505551",
      "0.320611562"
    ],
    [
      "0.523811391",
      "0.931698608"
    ],
    [
      "0.242547173",
      "0.18376793"
    ]
  ]
}

Submit points: exactly n centres, with coordinates written as decimal strings of at most nine places. The verifier computes the radius exactly; 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?