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

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

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.

Instancen = 17

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.138877106203405	今天	Record details ↓

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⁻¹⁸ $E (P) = \underset{L}{\int \int} \min_{i} {‖ x - p_{i} ‖}^{2} d x$
ObjectiveMake E(P) as small as possible over all legal point sets P $\min_{P} E (P)$

Open the full editor ↗

Layout shown: site record

2y0

1234567891011121314151617

0x2

VERIFIED CONSTRUCTION17 regions; the most expensive one accounts for 14.2% of the total cost

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.

LAYOUT & HISTORY

Record details

Inspect the layout, solver notes and record history.

Record holder今天

Solution methodHuman

Challenge this record ↗Submit a proof / idea ↓Share a proof or idea in the discussion. Accepted contributions can earn proof points.

Record holder's solver noteNo solver note yet (expand)＋

The record holder has not shared a solver note yet.

Record history (1 changes)

今天Human
0.320434112530895→0.138877106203405
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, with each coordinate written as a decimal string such as "0.25", to at most nine decimal places. Every point must lie in the L; the score is the integral of squared distance to the nearest point over the region, and smaller is better.

The current leader's answer

{
  "points": [
    [
      "0.500000000",
      "0.388888889"
    ],
    [
      "1.505128206",
      "0.484273457"
    ],
    [
      "0.500000000",
      "1.055555556"
    ],
    [
      "0.333333333",
      "0.611111111"
    ],
    [
      "1.144615290",
      "0.712649667"
    ],
    [
      "0.219487039",
      "1.763931718"
    ],
    [
      "0.666666667",
      "0.240740741"
    ],
    [
      "1.708717855",
      "0.274586848"
    ],
    [
      "0.666666667",
      "0.907407407"
    ],
    [
      "0.250000000",
      "0.462962963"
    ],
    [
      "0.916666667",
      "0.462962963"
    ],
    [
      "0.250000000",
      "1.129629630"
    ],
    [
      "0.583333333",
      "0.685185185"
    ],
    [
      "1.659230863",
      "0.946723647"
    ],
    [
      "0.777179111",
      "1.813390314"
    ],
    [
      "0.416666667",
      "0.314814815"
    ],
    [
      "1.271025829",
      "0.139430058"
    ]
  ]
}

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

Instance parameters

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

The current leader's answer

{
  "points": [
    [
      "0.500000000",
      "0.388888889"
    ],
    [
      "1.505128206",
      "0.484273457"
    ],
    [
      "0.500000000",
      "1.055555556"
    ],
    [
      "0.333333333",
      "0.611111111"
    ],
    [
      "1.144615290",
      "0.712649667"
    ],
    [
      "0.219487039",
      "1.763931718"
    ],
    [
      "0.666666667",
      "0.240740741"
    ],
    [
      "1.708717855",
      "0.274586848"
    ],
    [
      "0.666666667",
      "0.907407407"
    ],
    [
      "0.250000000",
      "0.462962963"
    ],
    [
      "0.916666667",
      "0.462962963"
    ],
    [
      "0.250000000",
      "1.129629630"
    ],
    [
      "0.583333333",
      "0.685185185"
    ],
    [
      "1.659230863",
      "0.946723647"
    ],
    [
      "0.777179111",
      "1.813390314"
    ],
    [
      "0.416666667",
      "0.314814815"
    ],
    [
      "1.271025829",
      "0.139430058"
    ]
  ]
}

DISCUSSION

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?