Optimal quantization in an L-shaped region
Place n representative points in the L-shaped region formed by removing the top-right 1 × 1 square from a 2 × 2 square so as to minimize the integral over L of the squared Euclidean distance to the nearest point.
Formal definition
- ContainerL = ([0,2] × [0,1]) ∪ ([0,1] × [1,2]), boundary included, with total area 3
- SubmissionExactly n distinct points in L, with coordinates of at most nine decimal places
- AssignmentEvery location is assigned to its nearest point in Euclidean distance; equidistant boundaries have measure zero and do not affect the integral
- ScoreE(P) is the integral of squared distance to the nearest submitted point over the L-shaped region; the verifier integrates in exact rationals and rounds upward at 10⁻¹⁸
- ObjectiveMinimize E(P) over all valid point sets P
Getting a feel for it
Quantizing a continuous domain
Approximating a continuous domain by n discrete representatives assigns each location to its nearest point. Integrating the squared distance measures total quantization distortion across the domain.
Non-convex geometry and coupled arms
Although the L-shaped domain is the union of three unit squares, Voronoi cells cut freely across the seams between them. Near the re-entrant corner at (1,1), Voronoi edges couple the two arms directly to the corner square.
Local minima in Lloyd iteration
Lloyd's algorithm, which repeatedly moves each point to the centroid of its Voronoi cell, converges to a centroidal Voronoi tessellation (CVT). On a non-convex domain multiple inequivalent stable configurations exist, and from n = 5 onward different initializations settle into distinct local minima.
Open instances
While continuous quadratic quantization is classical, no systematic per-n table has been published for this L-shaped domain. Omitting the elementary cases n = 1–4, all instances from n = 5 to n = 24 are open.
Current best solutions by n
Each parameter n is an independently scored sub-problem. Select any card to inspect the current record construction or submit a stronger solution.
Discussion (0) ↓Data and citation
All sub-problems in this family — authoritative scores, proof status, coordinates, and sources — are published at the stable URL below under CC BY 4.0. Because scores update as records fall, please cite the file's generatedAt timestamp.
GET https://minmaxarena.com/data/l-shaped-optimal-quantization.json
Cite the frozen 2026-10 edition: live records change, whereas a frozen edition stays fixed and reproducible.
GET https://minmaxarena.com/data/editions/2026-10/l-shaped-optimal-quantization.json
BibTeX (click to copy)
@misc{minmaxarena-l-shaped-optimal-quantization-2026-10,
title = {{Optimal quantization in an L-shaped region} (P71)},
author = {{MinMax Arena}},
year = {2026},
note = {Machine-verified records, 2026-10 edition},
url = {https://minmaxarena.com/data/editions/2026-10/l-shaped-optimal-quantization.json},
license = {CC BY 4.0}
}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.
Grouped by player and sub-problem, showing the latest note first. Earlier versions and replies are preserved; click any note to read or reply. Notes can be published alongside record-breaking submissions.