Minimum star discrepancy in the unit square
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.
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.