Sparse Hitting Set for Rectangles

Definitions and mathematical statement

Let $n$ be a nonnegative integer and let $A\subset{\mathbb{R}}^2$ be a finite set of $n$ distinct points. An axis-parallel rectangle is a set $R=[a,b]\times[c,d]$, with real endpoints $a\le b$ and $c\le d$. Call $R$ $1000$-rich for $A$ if $|A\cap R|\ge1000$. A subset $A'\subseteq A$ hits the rich rectangles if \[ \forall a\le b\ \forall c\le d,\qquad |A\cap([a,b]\times[c,d])|\ge1000 \ \Longrightarrow\ A'\cap([a,b]\times[c,d])\ne\varnothing. \] For every even $n$ and every such $A$, does there exist a hitting subset $A'$ with $|A'|=n/2$? This is the literal half-size formulation in the supplied statement whenever its cardinality is integral. Replacing equality by $|A'|\le n/2$ gives the same question for even $n$, since a smaller hitting subset can be enlarged inside $A$. The record does not specify a rounding convention for odd $n$; an all-$n$ version with $|A'|\le\lfloor n/2\rfloor$ is a possible interpretation, not an established correction of the source wording. Here "containing $1000$ points" is understood as containing at least $1000$, in accordance with the supplied background's rich-rectangle formulation. Closed rectangles fix a boundary convention; on a finite point set, the traces of other usual bounded axis-parallel rectangle boundary conventions can be realized by shifting endpoints slightly.

The registry labels the problem open. Its literature triage dated 17 August 2026 reports that no theorem giving a half-size hitting subset for all $1000$-rich rectangles was located in the checked sources, and that no distinct partial result was verified. The requested alternative is a proof of this claim or a counterexample; the dated search assessment is not a proof of present-day openness.

Short English statement

Can half of any finite planar point set be selected so that every axis-parallel rectangle containing at least $1000$ original points contains a selected point? The exact half-size wording is integral for even cardinality; the source leaves odd-cardinality rounding unspecified.

Sources

• Local UnsolvedMath registry, permanent ID $137$, source code catalogue entry, "Sparse Hitting Set for Rectangles"; supplied statement and background, attributed to Ben Green's 100 Open Problems.
• B. Green, 100 Open Problems, updated January 2026, as identified in the supplied literature triage: https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf.
• Supplied literature triage checked 17 August 2026: classified open; no half-size theorem or distinct verified partial progress located in its checked source. This draft has not independently consulted the linked source.