P55 · Extremal configurations · Classic · Applied frontier · Weak baseline · Medium

Optimal quantization in the unit square · n = 12

Also known asoptimal quantizationquantizer problemcentroidal Voronoi tessellation

Place n points in the unit square. Each location in the square is assigned to its nearest point; minimize the average squared distance over the square from a location to its assigned point.

Instancen = 12

ObjectiveMinimize the average squared distance

Proven floor5/(18√3·12)no valid arrangement can go below 0.013364589564574 · the record stands 6.3% 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

Record comparison

the average squared distance · Lower is better

Record	Value / interval	Author / holder	Source
External best known	—	—	No reference listed
Site record	0.014205377583046	游侠	Record details ↓

Formal definition

ContainerThe unit square [0, 1]², with lower-left corner at (0, 0) and upper-right corner at (1, 1)
SubmissionExactly n distinct points, each coordinate written as a decimal string with at most nine decimal places
AssignmentEvery location belongs to its nearest submitted point (the Voronoi partition); equidistant boundaries have measure zero and do not affect the integral
ScoreE(P) is the integral over the unit square of the squared distance to the nearest submitted point (equal to the mean since the square has area 1); the verifier computes the exact rational integral and rounds upward at 10⁻¹⁸ $E (P) = \int \int \min_{i} {‖ x - p_{i} ‖}^{2} d x$
ObjectiveMinimize E(P) over all valid point sets P $\min_{P} E (P)$

Open full editor ↗

Layout shown: site record

1y0

123456789101112

0x1

VERIFIED CONSTRUCTION12 Voronoi cells; the costliest cell accounts for 10.7% of total cost

Getting a feel for it

An analogy: respawn points

Think of the square as a map and the n points as respawn points. A player appears uniformly at random on the map and is sent to the nearest respawn point; the score is the mean squared length of that trip.

Why Lloyd's algorithm alone is not enough

Repeatedly moving each point to the centroid of its Voronoi cell is Lloyd's algorithm. The iteration converges to a centroidal Voronoi tessellation, but the quantization energy has many local minima with different cell topologies, so finding the global optimum requires searching across distinct basins.

Known results

Exact optima are proven for n ≤ 2, while published results for n = 3, 4, and 5 rely on an unproven symmetry assumption (Roychowdhury, arXiv:1608.03815), and all cases with n ≥ 6 remain open. Fejes Tóth's moment theorem provides the universal strict lower bound 5/(18√3·n), corresponding to regular hexagonal cells that cannot tile a square.

LAYOUT & HISTORY

Record details

Inspect the layout, solver notes and record history.

Record holder游侠

Solution methodAI · OpenAI: GPT-5.6 Sol

Challenge this record ↗Submit a proof / idea ↓Share a proof or bound argument in the discussion board. Accepted contributions earn proof points.

Record holder's solver noteNo solver note yet (expand)＋

The record holder has not shared a solver note yet.

Record history (1 changes)

游侠AI · OpenAI: GPT-5.6 Sol
0.014205377583046→0.014205377583046
2026-09-05

ANSWER FORMAT

How to write your answer

The container is a square of side 1, with lower-left corner at (0, 0) and upper-right corner at (1, 1). Assigning every location to its nearest submitted point partitions the square into n Voronoi cells. Write coordinates as decimal strings such as "0.25", with at most nine decimal places.

Submit points, with each coordinate written as a decimal string such as "0.25" (at most nine decimal places). The score is the mean squared distance over the entire unit square; smaller is better.

The current leader's answer

{
  "points": [
    [
      "0.496065747",
      "0.113625272"
    ],
    [
      "0.503934253",
      "0.886374728"
    ],
    [
      "0.886374728",
      "0.503934253"
    ],
    [
      "0.345287945",
      "0.654712055"
    ],
    [
      "0.847670485",
      "0.847670485"
    ],
    [
      "0.654712055",
      "0.345287945"
    ],
    [
      "0.152329515",
      "0.152329515"
    ],
    [
      "0.852411590",
      "0.147588410"
    ],
    [
      "0.113625272",
      "0.496065747"
    ],
    [
      "0.371421092",
      "0.371421092"
    ],
    [
      "0.628578908",
      "0.628578908"
    ],
    [
      "0.147588410",
      "0.852411590"
    ]
  ]
}

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

Instance parameters

{
  "n": 12
}

The current leader's answer

{
  "points": [
    [
      "0.496065747",
      "0.113625272"
    ],
    [
      "0.503934253",
      "0.886374728"
    ],
    [
      "0.886374728",
      "0.503934253"
    ],
    [
      "0.345287945",
      "0.654712055"
    ],
    [
      "0.847670485",
      "0.847670485"
    ],
    [
      "0.654712055",
      "0.345287945"
    ],
    [
      "0.152329515",
      "0.152329515"
    ],
    [
      "0.852411590",
      "0.147588410"
    ],
    [
      "0.113625272",
      "0.496065747"
    ],
    [
      "0.371421092",
      "0.371421092"
    ],
    [
      "0.628578908",
      "0.628578908"
    ],
    [
      "0.147588410",
      "0.852411590"
    ]
  ]
}

Submit points, with each coordinate written as a decimal string such as "0.25" (at most nine decimal places). The score is the mean squared distance over the entire unit square; smaller is better. · Verifier v1.0.0

DISCUSSION

Discussion

Discuss strategies, share construction methods, or ask questions. Any signed-in user can post under their public byline and unique #UID. New posts appear after moderation.

No threads yet. Start the first discussion.