P53 · Extremal configurations · Classic · Applied frontier · Weak baseline

The biggest little polygon · n = 26

Take n points, no two further apart than 1, and make the convex polygon they span as large as possible; every point must be a vertex of the hull.

Instancen = 26

ObjectiveMaximize the area

Formal definition

ContainerNo container: the one global constraint is that no two points are further than 1 apart; coordinates are written inside [0, 1.5] × [0, 1.5]
SubmissionExactly n points
ConstraintsAll pairwise distances at most 1; every point a genuine hull vertex — on another pair's segment or inside does not count
ObjectiveMake the polygon area as large as possible; compared internally by twice the area, exactly

Open the full editor ↗

1.5y0

1234567891011121314151617181920212223242526

0x1.5

VERIFIED CONSTRUCTIONthe polygon they enclose, and its longest pair

Getting a feel for it

Why the even cases are the hard ones

For odd n the regular polygon is provably optimal — nothing to contest. For even n it is NOT: Graham hexagon beats the regular one by about 4% of area. That is why only even n are offered here.

Where the frontier is

Regular polygons are optimal for odd n (Reinhardt 1922), so only even n are offered. On the even side n = 6, 8, 10 and 12 are proven (from Graham 1975 to Audet et al.); n ≥ 14 has only numerical best values and is open.

Current leader

0.497776581631905516

the area

Record holderFounding benchmark

Solution methodHuman

Challenge this record ↗

ANSWER FORMAT

How to write your answer

This problem has no container; the only constraint is that no two points are more than 1 apart. Coordinates are written inside a [0, 1.5] × [0, 1.5] frame, which is a coordinate system rather than an extra restriction: a set of diameter at most 1 always fits in a 1 × 1 box, and this leaves a further quarter unit on every side so that where you centre it can never matter. Coordinates are plain decimals such as "0.25", to at most nine decimal places.

Submit points, each coordinate written as a decimal string such as "0.25", to at most nine decimal places.

The current leader's answer

{
  "points": [
    [
      "1.15",
      "0.75"
    ],
    [
      "1.138376727",
      "0.845726266"
    ],
    [
      "1.10418241",
      "0.935889269"
    ],
    [
      "1.049404299",
      "1.015249063"
    ],
    [
      "0.977225899",
      "1.079193546"
    ],
    [
      "0.891841955",
      "1.124006497"
    ],
    [
      "0.798214672",
      "1.14708355"
    ],
    [
      "0.701785328",
      "1.14708355"
    ],
    [
      "0.608158045",
      "1.124006497"
    ],
    [
      "0.522774101",
      "1.079193546"
    ],
    [
      "0.450595701",
      "1.015249063"
    ],
    [
      "0.39581759",
      "0.935889269"
    ],
    [
      "0.361623273",
      "0.845726266"
    ],
    [
      "0.35",
      "0.75"
    ],
    [
      "0.361623273",
      "0.654273734"
    ],
    [
      "0.39581759",
      "0.564110731"
    ],
    [
      "0.450595701",
      "0.484750937"
    ],
    [
      "0.522774101",
      "0.420806454"
    ],
    [
      "0.608158045",
      "0.375993503"
    ],
    [
      "0.701785328",
      "0.35291645"
    ],
    [
      "0.798214672",
      "0.35291645"
    ],
    [
      "0.891841955",
      "0.375993503"
    ],
    [
      "0.977225899",
      "0.420806454"
    ],
    [
      "1.049404299",
      "0.484750937"
    ],
    [
      "1.10418241",
      "0.564110731"
    ],
    [
      "1.138376727",
      "0.654273734"
    ]
  ]
}

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

Instance parameters

{
  "n": 26
}

The current leader's answer

{
  "points": [
    [
      "1.15",
      "0.75"
    ],
    [
      "1.138376727",
      "0.845726266"
    ],
    [
      "1.10418241",
      "0.935889269"
    ],
    [
      "1.049404299",
      "1.015249063"
    ],
    [
      "0.977225899",
      "1.079193546"
    ],
    [
      "0.891841955",
      "1.124006497"
    ],
    [
      "0.798214672",
      "1.14708355"
    ],
    [
      "0.701785328",
      "1.14708355"
    ],
    [
      "0.608158045",
      "1.124006497"
    ],
    [
      "0.522774101",
      "1.079193546"
    ],
    [
      "0.450595701",
      "1.015249063"
    ],
    [
      "0.39581759",
      "0.935889269"
    ],
    [
      "0.361623273",
      "0.845726266"
    ],
    [
      "0.35",
      "0.75"
    ],
    [
      "0.361623273",
      "0.654273734"
    ],
    [
      "0.39581759",
      "0.564110731"
    ],
    [
      "0.450595701",
      "0.484750937"
    ],
    [
      "0.522774101",
      "0.420806454"
    ],
    [
      "0.608158045",
      "0.375993503"
    ],
    [
      "0.701785328",
      "0.35291645"
    ],
    [
      "0.798214672",
      "0.35291645"
    ],
    [
      "0.891841955",
      "0.375993503"
    ],
    [
      "0.977225899",
      "0.420806454"
    ],
    [
      "1.049404299",
      "0.484750937"
    ],
    [
      "1.10418241",
      "0.564110731"
    ],
    [
      "1.138376727",
      "0.654273734"
    ]
  ]
}

Submit points, each coordinate written as a decimal string such as "0.25", to at most nine decimal places. · Verifier v1.0.0