MinMax Arena
中/EN
P55 · Extremal configurations · Classic · Applied frontier · Weak baseline

Optimal quantization in the unit square · n = 19

Place n points in the square of side 1. Every location in the square is served by whichever point is nearest; your score is the average, over the whole square, of the squared distance from a location to the point serving it. Make that average as small as you can.

Instancen = 19
ObjectiveMinimize the average squared distance
Best known, unproven0.008851717018979our own offline search: Lloyd to convergence from 33 deterministic starts, won by seed 30, reproducible digit-for-digit via tools/p55-lloyd.ts; optimality unknown
Proven floor5/(18√3·19)no arrangement can go below 0.008440793409205 · the record stands 4.9% above itFejes Tóth's moment theorem: the mean squared distance cannot go below what n equal-area regular hexagons would achieve — and hexagons do not tile a square, so the line can be approached but never reached

Formal definition

  • ContainerThe unit square: the origin (0, 0) at its lower-left corner, (1, 1) at its upper right
  • SubmissionExactly n points, each coordinate a decimal with at most nine places; no two points may coincide
  • AssignmentEvery location belongs to the nearest point; the exactly-equidistant locations form a set of zero area, so their assignment cannot change the score
  • ObjectiveMake E(P) = ∫∫ min‖x − pᵢ‖² dx as small as possible. Scored in exact rationals, rounded up at 10⁻¹⁸
Open the full editor ↗
1y0
0x1
VERIFIED CONSTRUCTION19 regions; the most expensive one accounts for 7.0% of the total cost

Getting a feel for it

An analogy: respawn points

Read the square as a map and the n points as respawn points. A player appears uniformly at random anywhere on it and is sent to the nearest one — your score is the average squared length of that trip.

Where the room for improvement is

Moving every point to the centre of mass of its region, over and over, is Lloyd's algorithm: it always stops, but where it stops is a stationary point, not the best one. This energy has many local minima, and which one you fall into depends entirely on where you started — that gap is the contest.

Where the frontier is

n ≤ 2 is proven; n = 3, 4 and 5 rest on an unproven symmetry conjecture (Roychowdhury, arXiv:1608.03815); of anything larger the literature says it "is extremely difficult and the answer is not known yet". One floor holds for every n: 5/(18√3·n), the level of regular hexagons — which never tile a square.

Current leader

0.008851717018979

the average squared distance

Matches the best known
Record holderFounding benchmark
Solution methodHuman
Challenge this record ↗
ANSWER FORMAT

How to write your answer

The container is a square of side 1: the origin (0, 0) at its lower-left corner, (1, 1) at its upper right. Every place belongs to whichever point is nearest, so the square is divided into n regions that neither overlap nor leave a gap. 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 score is the average squared distance over the whole map, and smaller is better.

The current leader's answer

{
  "points": [
    [
      "0.663792763",
      "0.885093524"
    ],
    [
      "0.904247977",
      "0.410320065"
    ],
    [
      "0.863932555",
      "0.657748483"
    ],
    [
      "0.367068408",
      "0.511160070"
    ],
    [
      "0.115535730",
      "0.120522798"
    ],
    [
      "0.103096607",
      "0.390544463"
    ],
    [
      "0.405126754",
      "0.905238530"
    ],
    [
      "0.558333167",
      "0.693545469"
    ],
    [
      "0.889391663",
      "0.122641353"
    ],
    [
      "0.508938491",
      "0.316492329"
    ],
    [
      "0.660503322",
      "0.508082430"
    ],
    [
      "0.283521229",
      "0.293759742"
    ],
    [
      "0.108652314",
      "0.628647302"
    ],
    [
      "0.124480672",
      "0.885276845"
    ],
    [
      "0.376572030",
      "0.098720540"
    ],
    [
      "0.628958715",
      "0.098007315"
    ],
    [
      "0.734033768",
      "0.288480846"
    ],
    [
      "0.890766937",
      "0.884833856"
    ],
    [
      "0.308580472",
      "0.722139930"
    ]
  ]
}
Submission format and technical detailsOpen this when you are ready to prepare a JSON answer＋

Instance parameters

{
  "n": 19
}

The current leader's answer

{
  "points": [
    [
      "0.663792763",
      "0.885093524"
    ],
    [
      "0.904247977",
      "0.410320065"
    ],
    [
      "0.863932555",
      "0.657748483"
    ],
    [
      "0.367068408",
      "0.511160070"
    ],
    [
      "0.115535730",
      "0.120522798"
    ],
    [
      "0.103096607",
      "0.390544463"
    ],
    [
      "0.405126754",
      "0.905238530"
    ],
    [
      "0.558333167",
      "0.693545469"
    ],
    [
      "0.889391663",
      "0.122641353"
    ],
    [
      "0.508938491",
      "0.316492329"
    ],
    [
      "0.660503322",
      "0.508082430"
    ],
    [
      "0.283521229",
      "0.293759742"
    ],
    [
      "0.108652314",
      "0.628647302"
    ],
    [
      "0.124480672",
      "0.885276845"
    ],
    [
      "0.376572030",
      "0.098720540"
    ],
    [
      "0.628958715",
      "0.098007315"
    ],
    [
      "0.734033768",
      "0.288480846"
    ],
    [
      "0.890766937",
      "0.884833856"
    ],
    [
      "0.308580472",
      "0.722139930"
    ]
  ]
}

Submit points, each coordinate written as a decimal string such as "0.25", to at most nine decimal places. The score is the average squared distance over the whole map, and smaller is better. · Verifier v1.0.0