P66 · Packing and covering · Classic · Hard

Unit circles in a minimum-area triangle · n = 32

Also known ascircles in arbitrary trianglesunit circles in a minimum-area trianglecircle packing in a triangle of variable shape

Place n radius-1 circles with disjoint interiors inside an arbitrary triangle. The triangle's three vertices are part of the answer. Minimize its area.

Instancen = 32

ObjectiveMinimize the triangle area

Best known, unproven127.07490417923377167Tej Stead configuration listed by Erich Friedman's table; coordinates reconstructed here from the published figure and verified exactly on the nine-decimal grid

Formal definition

ContainerThe container is a non-degenerate triangle whose shape is not fixed in advance; its vertices and all centres lie in the 0-to-200 coordinate frame
SubmissionThree triangle vertices in counter-clockwise order and exactly n circle centres
CirclesEvery circle has fixed radius 1; circle interiors are pairwise disjoint and tangency is allowed
ContainmentEvery circle lies wholly inside the triangle and may be tangent to an edge
ObjectiveMake the triangle area as small as possible

Challenge this record ↗

VERIFIED CONSTRUCTION32 circles with radius 1

Getting a feel for it

The container is a variable

Ordinary packing moves the circles; here all three edge directions move too. A tiny edge rotation can release several contacts at once—or destabilize the whole packing.

The hard part is the contact structure

A candidate optimum is usually jammed by circle-circle and circle-edge tangencies. The real search is not uniform spacing but finding the right contact graph among many possibilities.

Starting beyond the trivial cases

Friedman's public table gives the current best-known constructions through n=50. The n=1 and n=2 rows are proved and n=3 is still the elementary equilateral arrangement, so the arena starts at n=4; matching a published construction reaches the frontier, while beating it sets a new record.

Source

Current leader

127.07490417923377167

the triangle area

Matches the best known

Answer sourceTej Stead

Solution methodPublished reference construction

Challenge this record ↗

ANSWER FORMAT

How to write your answer

The coordinate unit is the circle radius: every circle has radius 1. Put all vertices and centres in the box 0≤x,y≤200 and list the vertices counter-clockwise.

Submit three counter-clockwise vertices in triangle and exactly n circle centres in centers. Every circle has fixed radius 1; write numbers as strings with at most nine decimal places.

The current leader's answer

{
  "centers": [
    [
      "6.815936727",
      "12.743782415"
    ],
    [
      "7.986641417",
      "11.122224357"
    ],
    [
      "5.996978600",
      "10.919143384"
    ],
    [
      "9.157346107",
      "9.500666298"
    ],
    [
      "7.167683290",
      "9.297585326"
    ],
    [
      "5.178020473",
      "9.094504353"
    ],
    [
      "10.328050797",
      "7.879108240"
    ],
    [
      "8.338387980",
      "7.676027267"
    ],
    [
      "6.348725163",
      "7.472946295"
    ],
    [
      "4.359062345",
      "7.269865322"
    ],
    [
      "11.498755487",
      "6.257550182"
    ],
    [
      "9.509092670",
      "6.054469209"
    ],
    [
      "7.519429853",
      "5.851388236"
    ],
    [
      "5.529767035",
      "5.648307264"
    ],
    [
      "3.540104218",
      "5.445226291"
    ],
    [
      "12.669460177",
      "4.635992123"
    ],
    [
      "10.679797360",
      "4.432911150"
    ],
    [
      "8.690134543",
      "4.229830178"
    ],
    [
      "6.700471725",
      "4.026749205"
    ],
    [
      "2.721146091",
      "3.620587260"
    ],
    [
      "4.710329755",
      "3.412521954"
    ],
    [
      "12.040009645",
      "2.737626501"
    ],
    [
      "14.040009647",
      "2.737626501"
    ],
    [
      "9.860839233",
      "2.608272119"
    ],
    [
      "6.966365549",
      "2.044502883"
    ],
    [
      "3.402861305",
      "1.740357387"
    ],
    [
      "15.104494893",
      "1.044404221"
    ],
    [
      "1.544940169",
      "1.000000001"
    ],
    [
      "5.260782441",
      "1.000000001"
    ],
    [
      "8.671948657",
      "1.000000001"
    ],
    [
      "11.049729808",
      "1.000000001"
    ],
    [
      "13.049729810",
      "1.000000001"
    ]
  ],
  "triangle": [
    [
      "0.000000000",
      "0.000000000"
    ],
    [
      "17.249855980",
      "0.000000000"
    ],
    [
      "6.612855755",
      "14.733445233"
    ]
  ]
}

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

Instance parameters

{
  "n": 32
}

The current leader's answer

{
  "centers": [
    [
      "6.815936727",
      "12.743782415"
    ],
    [
      "7.986641417",
      "11.122224357"
    ],
    [
      "5.996978600",
      "10.919143384"
    ],
    [
      "9.157346107",
      "9.500666298"
    ],
    [
      "7.167683290",
      "9.297585326"
    ],
    [
      "5.178020473",
      "9.094504353"
    ],
    [
      "10.328050797",
      "7.879108240"
    ],
    [
      "8.338387980",
      "7.676027267"
    ],
    [
      "6.348725163",
      "7.472946295"
    ],
    [
      "4.359062345",
      "7.269865322"
    ],
    [
      "11.498755487",
      "6.257550182"
    ],
    [
      "9.509092670",
      "6.054469209"
    ],
    [
      "7.519429853",
      "5.851388236"
    ],
    [
      "5.529767035",
      "5.648307264"
    ],
    [
      "3.540104218",
      "5.445226291"
    ],
    [
      "12.669460177",
      "4.635992123"
    ],
    [
      "10.679797360",
      "4.432911150"
    ],
    [
      "8.690134543",
      "4.229830178"
    ],
    [
      "6.700471725",
      "4.026749205"
    ],
    [
      "2.721146091",
      "3.620587260"
    ],
    [
      "4.710329755",
      "3.412521954"
    ],
    [
      "12.040009645",
      "2.737626501"
    ],
    [
      "14.040009647",
      "2.737626501"
    ],
    [
      "9.860839233",
      "2.608272119"
    ],
    [
      "6.966365549",
      "2.044502883"
    ],
    [
      "3.402861305",
      "1.740357387"
    ],
    [
      "15.104494893",
      "1.044404221"
    ],
    [
      "1.544940169",
      "1.000000001"
    ],
    [
      "5.260782441",
      "1.000000001"
    ],
    [
      "8.671948657",
      "1.000000001"
    ],
    [
      "11.049729808",
      "1.000000001"
    ],
    [
      "13.049729810",
      "1.000000001"
    ]
  ],
  "triangle": [
    [
      "0.000000000",
      "0.000000000"
    ],
    [
      "17.249855980",
      "0.000000000"
    ],
    [
      "6.612855755",
      "14.733445233"
    ]
  ]
}

Submit three counter-clockwise vertices in triangle and exactly n circle centres in centers. Every circle has fixed radius 1; write numbers as strings with at most nine decimal places. · 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?