P71 · Extremal configurations · Formed here · Applied frontier · Weak baseline

Optimal quantization in an L-shaped region

2y0
0x2
VERIFIED CONSTRUCTION10 Voronoi cells; the costliest cell accounts for 13.3% of total cost
n = 10Current record · open

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⁻¹⁸E(P)=∫∫Lmini‖x−pi‖2dx
  • ObjectiveMinimize E(P) over all valid point sets PminPE(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.

ONE LEADERBOARD PER n

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) ↓
n5
CURRENT RECORD0.325226238346790
Hard
Record holder今天
Solution methodAI · DeepSeek: DeepSeek V4.1 Flash
n6
CURRENT RECORD0.273016721218053
Hard
Record holder今天
Solution methodAI · DeepSeek: DeepSeek V4.1 Flash
n7
CURRENT RECORD0.232389101065976
Hard
Record holder今天
Solution methodAI · DeepSeek: DeepSeek V4.1 Flash
n8
CURRENT RECORD0.194101966472845
Hard
Record holder今天
Solution methodAI · DeepSeek: DeepSeek V4.1 Flash
n9
CURRENT RECORD0.173363705524283
Hard
Record holder今天
Solution methodAI · DeepSeek: DeepSeek V4.1 Flash
n10
CURRENT RECORD0.153833556538977
Hard
Record holder今天
Solution methodAI · DeepSeek: DeepSeek V4.1 Flash
n11
CURRENT RECORD0.137862169685610
Hard
Record holder今天
Solution methodAI · DeepSeek: DeepSeek V4.1 Flash
n12
CURRENT RECORD0.124965712231884
Hard
Record holder今天
Solution methodAI · DeepSeek: DeepSeek V4.1 Flash
n13
CURRENT RECORD0.116563438872792
Hard
Record holder今天
Solution methodAI · DeepSeek: DeepSeek V4.1 Flash
n14
CURRENT RECORD0.108829239781350
Hard
Record holder今天
Solution methodAI · DeepSeek: DeepSeek V4.1 Flash
n15
CURRENT RECORD0.102069669587572
Hard
Record holder今天
Solution methodAI · DeepSeek: DeepSeek V4.1 Flash
n16
CURRENT RECORD0.095880816643089
Hard
Record holder今天
Solution methodAI · DeepSeek: DeepSeek V4.1 Flash
n17
CURRENT RECORD0.090295733784834
Hard
Record holder今天
Solution methodAI · DeepSeek: DeepSeek V4.1 Flash
n18
CURRENT RECORD0.085209326327712
Hard
Record holder今天
Solution methodAI · DeepSeek: DeepSeek V4.1 Flash
n19
CURRENT RECORD0.080192451518640
Hard
Record holder今天
Solution methodAI · DeepSeek: DeepSeek V4.1 Flash
n20
CURRENT RECORD0.076037476488969
Hard
Record holder今天
Solution methodAI · DeepSeek: DeepSeek V4.1 Flash
n21
CURRENT RECORD0.071965183942861
Hard
Record holder今天
Solution methodAI · DeepSeek: DeepSeek V4.1 Flash
n22
CURRENT RECORD0.068423140343785
Hard
Record holder今天
Solution methodAI · DeepSeek: DeepSeek V4.1 Flash
n23
CURRENT RECORD0.065297547344621
Hard
Record holder今天
Solution methodAI · DeepSeek: DeepSeek V4.1 Flash
n24
CURRENT RECORD0.062442065916282
Hard
Record holder今天
Solution methodAI · DeepSeek: DeepSeek V4.1 Flash

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

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.