P54 · Extremal configurations · Classic · Applied frontier · Weak baseline

Minimum star discrepancy in the unit square

1y0
0x1
VERIFIED CONSTRUCTIONthe dashed box covers 84.6% of the square, so it should hold 20.3 points; it holds 24 — off by 0.1536, which is the score
n = 24Current record · open

Place n sample points in the unit square. Every axis-aligned rectangle anchored at the origin should hold the same share of the points as it holds of the area; your score is the largest mismatch over all such rectangles. Make it as small as you can.

Formal definition

  • ContainerThe unit square: the origin (0, 0) at its lower-left corner, (1, 1) at its upper right
  • SubmissionExactly n points, each coordinate a decimal with at most nine places; no two points may coincide
  • RectanglesThe rectangles compared are half-open, [0, u) × [0, v), their upper-right corner anywhere in the square; a point exactly on the top or right edge counts as outside
  • ObjectiveMake D*, the largest mismatch over all rectangles, as small as possible. The supremum is attained on the grid of submitted coordinates and scored exactly in integers

Getting a feel for it

An analogy: a sampling budget

Read the square as a frame you are about to render and the n points as your entire sampling budget. A rectangle holding more than its share of the points is budget spent twice in one place; fewer, and that region's detail is lost.

Where the room for improvement is

Grids and random scatters are both systematically biased on some rectangle; low-discrepancy constructions (Hammersley, van der Corput) do far better — but for each particular n, nobody knows how low it goes.

Where the frontier is

Optima for n ≤ 21 were proven by Clément, Doerr, Klamroth and Paquete in 2025 (Proc. Amer. Math. Soc. Ser. B 12: 78–90), which is why this problem starts at n = 22; beyond that, every n is open.

ONE LEADERBOARD PER n

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.

n22
CURRENT RECORD0.163190939155409
Record holderNUE_13
Solution methodHuman
View problem
n23
CURRENT RECORD0.128336388848979
Record holderNUE_13
Solution methodHuman
View problem
n24
CURRENT RECORD0.153606248045778
Record holderNUE_13
Solution methodHuman
View problem
n25
CURRENT RECORD0.399456000000000
Record holderFounding benchmark
Solution methodHuman
View problem
n26
CURRENT RECORD0.399467455628699
Record holderFounding benchmark
Solution methodHuman
View problem
n27
CURRENT RECORD0.399478737993485
Record holderFounding benchmark
Solution methodHuman
View problem
n28
CURRENT RECORD0.399489795924490
Record holderFounding benchmark
Solution methodHuman
View problem
n29
CURRENT RECORD0.399500594540369
Record holderFounding benchmark
Solution methodHuman
View problem
n30
CURRENT RECORD0.399511111118889
Record holderFounding benchmark
Solution methodHuman
View problem
n31
CURRENT RECORD0.399521331941208
Record holderFounding benchmark
Solution methodHuman
View problem
n32
CURRENT RECORD0.387343750000000
Record holderFounding benchmark
Solution methodHuman
View problem
n33
CURRENT RECORD0.379843893480349
Record holderFounding benchmark
Solution methodHuman
View problem
n34
CURRENT RECORD0.379844290657267
Record holderFounding benchmark
Solution methodHuman
View problem
n35
CURRENT RECORD0.379844897960103
Record holderFounding benchmark
Solution methodHuman
View problem
n36
CURRENT RECORD0.379845679012655
Record holderFounding benchmark
Solution methodHuman
View problem
n37
CURRENT RECORD0.379846603359478
Record holderFounding benchmark
Solution methodHuman
View problem
n38
CURRENT RECORD0.379847645428532
Record holderFounding benchmark
Solution methodHuman
View problem
n39
CURRENT RECORD0.379848783696089
Record holderFounding benchmark
Solution methodHuman
View problem
n40
CURRENT RECORD0.379850000000000
Record holderFounding benchmark
Solution methodHuman
View problem
n41
CURRENT RECORD0.379851278998186
Record holderFounding benchmark
Solution methodHuman
View problem
n42
CURRENT RECORD0.379852607706917
Record holderFounding benchmark
Solution methodHuman
View problem
n43
CURRENT RECORD0.379853975119011
Record holderFounding benchmark
Solution methodHuman
View problem
n44
CURRENT RECORD0.379855371901447
Record holderFounding benchmark
Solution methodHuman
View problem
n45
CURRENT RECORD0.379856790122655
Record holderFounding benchmark
Solution methodHuman
View problem
n46
CURRENT RECORD0.379858223063706
Record holderFounding benchmark
Solution methodHuman
View problem
n47
CURRENT RECORD0.379859665009168
Record holderFounding benchmark
Solution methodHuman
View problem
n48
CURRENT RECORD0.379861111113889
Record holderFounding benchmark
Solution methodHuman
View problem
n49
CURRENT RECORD0.379862557270461
Record holderFounding benchmark
Solution methodHuman
View problem
n50
CURRENT RECORD0.379864000000000
Record holderFounding benchmark
Solution methodHuman
View problem