Optimal quantization in the unit square · n = 23
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 = 23
ObjectiveMinimize the average squared distance
Proven floor5/(18√3·23)no valid arrangement can go below 0.006972829338038 · the record stands 3.5% 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.007218156525266 | 游侠 | 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⁻¹⁸
- ObjectiveMinimize E(P) over all valid point sets P
