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

Optimal quantization in an L-shaped region · n = 18

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.

Instancen = 18

ObjectiveMinimize squared-distance integral

Record comparison

squared-distance integral · Lower is better

Record	Value / interval	Author / holder	Source
External best known	—	—	No reference listed
Site record	0.085209326327712	今天	Record details ↓

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) = \underset{L}{\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

2y0

123456789101112131415161718

0x2

VERIFIED CONSTRUCTION18 Voronoi cells; the costliest cell accounts for 8.2% of total cost

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.

LAYOUT & HISTORY

Record details

Inspect the layout, solver notes and record history.

Record holder今天

Solution methodAI · DeepSeek: DeepSeek V4.1 Flash

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 (3 changes)

今天AI · DeepSeek: DeepSeek V4.1 Flash
0.092063831208822→0.085209326327712
2026-09-20
NUE_13Human
0.119971350904174→0.092063831208822
2026-09-20
今天Human
0.319305487482874→0.119971350904174
2026-09-20

ANSWER FORMAT

How to write your answer

The container is a square of side 2 with its top-right 1 × 1 square removed: the lower-left corner is (0, 0), and the missing region is where x > 1 and y > 1. Its area is 3.

Submit points: a list of n points inside the L-shaped region, with each coordinate written as a decimal string of at most nine places (for example, "0.25"). The score is the integral of squared distance to the nearest submitted point over the region; smaller is better.

The current leader's answer

{
  "points": [
    [
      "0.163753369",
      "1.046429715"
    ],
    [
      "0.178786935",
      "0.211935670"
    ],
    [
      "0.220748526",
      "0.629232043"
    ],
    [
      "0.244628783",
      "1.814768499"
    ],
    [
      "0.265532289",
      "1.442738755"
    ],
    [
      "0.529024992",
      "1.037143346"
    ],
    [
      "0.547011160",
      "0.205891770"
    ],
    [
      "0.650732426",
      "0.599760283"
    ],
    [
      "0.745248160",
      "1.798226630"
    ],
    [
      "0.773641071",
      "1.395079728"
    ],
    [
      "0.912177210",
      "0.934698000"
    ],
    [
      "0.938915016",
      "0.192974454"
    ],
    [
      "1.094083697",
      "0.548774243"
    ],
    [
      "1.366122815",
      "0.173416493"
    ],
    [
      "1.378771174",
      "0.837546857"
    ],
    [
      "1.541412219",
      "0.500492589"
    ],
    [
      "1.815935901",
      "0.227112030"
    ],
    [
      "1.819800078",
      "0.769785728"
    ]
  ]
}

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

Instance parameters

{
  "n": 18,
  "domain": "L-2x2-minus-1x1",
  "metric": "squared-euclidean",
  "measure": "uniform"
}

The current leader's answer

{
  "points": [
    [
      "0.163753369",
      "1.046429715"
    ],
    [
      "0.178786935",
      "0.211935670"
    ],
    [
      "0.220748526",
      "0.629232043"
    ],
    [
      "0.244628783",
      "1.814768499"
    ],
    [
      "0.265532289",
      "1.442738755"
    ],
    [
      "0.529024992",
      "1.037143346"
    ],
    [
      "0.547011160",
      "0.205891770"
    ],
    [
      "0.650732426",
      "0.599760283"
    ],
    [
      "0.745248160",
      "1.798226630"
    ],
    [
      "0.773641071",
      "1.395079728"
    ],
    [
      "0.912177210",
      "0.934698000"
    ],
    [
      "0.938915016",
      "0.192974454"
    ],
    [
      "1.094083697",
      "0.548774243"
    ],
    [
      "1.366122815",
      "0.173416493"
    ],
    [
      "1.378771174",
      "0.837546857"
    ],
    [
      "1.541412219",
      "0.500492589"
    ],
    [
      "1.815935901",
      "0.227112030"
    ],
    [
      "1.819800078",
      "0.769785728"
    ]
  ]
}

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.