Optimal quantization in an L-shaped region
Place n points in the L obtained by removing the top-right 1 × 1 square from a 2 × 2 square. Every location is assigned to its nearest point; minimize the integral of squared distance from each location to the point serving it over the whole L.
Formal definition
- ContainerL = ([0,2] × [0,1]) ∪ ([0,1] × [1,2]), including its boundary, with area 3
- SubmissionExactly n distinct points, with coordinates of at most nine decimals, all lying in the L
- AssignmentEvery location is assigned to its nearest point in Euclidean distance; exactly equidistant boundaries have zero area and do not affect the score
- ScoreE(P) is the integral of squared distance to the nearest submitted point over the whole L-shaped region; the verifier integrates in exact rationals and rounds upward at 10⁻¹⁸
- ObjectiveMake E(P) as small as possible over all legal point sets P
Getting a feel for it
Think of compressing a map
You may retain only n representative locations, and every place on the map is replaced by its nearest representative. Squared distance is the information lost in that replacement; make the integrated loss over the map as small as possible.
Why the three squares do not separate
The three unit squares are only how the verifier partitions the integral, not service boundaries. A point may serve locations across those seams; near the re-entrant corner, Voronoi edges couple both arms to the central region.
Where the room for improvement is
Repeatedly moving each point to the centroid of the region it serves is Lloyd's algorithm. It stops at a centroidal Voronoi configuration, not necessarily the global optimum; from n = 5 onward, different starts already settle into different stable structures.
Where the frontier is
Quadratic quantization is classical, but no published per-n table was found for this fixed L-shaped family. The closed-form or single-symmetry cases n = 1–4 are omitted; no proved global optimum has been entered here for any row n = 5–24, so every listed row remains open.
Current best solutions by n
Each n is an independent record with a page of its own. Open any of them to inspect the current construction, then challenge it.
Discussion (0) ↓Data and citation
Every sub-problem in this family — authoritative scores, proof status, coordinates and sources — lives at the stable address below, published under CC BY 4.0. Scores move as records fall, so cite the generatedAt timestamp the file carries.
GET https://minmaxarena.com/data/l-shaped-optimal-quantization.json
Cite the frozen 2026-08 edition: records move, a frozen edition never does, so the citation is still checkable years later.
GET https://minmaxarena.com/data/editions/2026-08/l-shaped-optimal-quantization.json
BibTeX (click to copy)
@misc{minmaxarena-l-shaped-optimal-quantization-2026-08,
title = {{Optimal quantization in an L-shaped region} (P71)},
author = {{MinMax Arena}},
year = {2026},
note = {Machine-verified records, 2026-08 edition},
url = {https://minmaxarena.com/data/editions/2026-08/l-shaped-optimal-quantization.json},
license = {CC BY 4.0}
}Discussion
Talk strategy, share methods, ask why you are stuck. Every signed-in user can post. 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. New posts appear after an automated review.
No threads yet. Be the first to talk about this problem?
Grouped by player and sub-problem, with the newest note shown first. Historical notes and replies are preserved; open any note to read or reply. Notes are published from record submissions.
No solver notes yet.