Weak nets of linear size for axis-parallel rectangles
Let $A$ be a set of $n$ points in the plane. The points of $A'$ below need not belong to $A$: Alon observed that the answer is no if one insists on $A' \subset A$. Green understands the work of Aronov, Ezra and Sharir to give a positive answer with $1000$ replaced by $C \log\log n$.
Problem. Is there always a set $A'$ of $n/2$ points that meets every axis-parallel rectangle containing $1000$ points of $A$?
Source: Communicated to Green by N. Katz; Green believes it is an instance of the question whether axis-parallel boxes admit weak ε-nets of size O(1/ε). Listed as Problem 76 in B. Green, 100 open problems (version of January 2026).
Imported from people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf.
Classification
- Primary
- CO — Combinatorics
- Secondary
- MG
- Keywords
- axis-parallel rectangles, discrepancy theory, discrete geometry, weak epsilon-nets
- Literature checked
- Oct. 26, 2026 by clemens-admin
References
@article{aronov2010small,
author = {Aronov, Boris and Ezra, Esther and Sharir, Micha},
title = {Small-size $\varepsilon$-nets for axis-parallel rectangles and boxes},
journal = {SIAM Journal on Computing},
volume = {39},
number = {7},
pages = {3248--3282},
year = {2010},
doi = {10.1137/090762968}
}
@article{ezra2010weak,
author = {Ezra, Esther},
title = {A note about weak $\varepsilon$-nets for axis-parallel boxes in $d$-space},
journal = {Information Processing Letters},
volume = {110},
number = {18-19},
pages = {835--840},
year = {2010},
doi = {10.1016/j.ipl.2010.06.005}
}
@article{pach2013tardos,
author = {Pach, J{\'a}nos and Tardos, G{\'a}bor},
title = {Tight lower bounds for the size of epsilon-nets},
journal = {Journal of the American Mathematical Society},
volume = {26},
number = {3},
pages = {645--658},
year = {2013},
doi = {10.1090/S0894-0347-2012-00759-0},
eprint = {1012.1240},
archivePrefix = {arXiv}
}
@article{chudnovsky2018piercing,
author = {Chudnovsky, Maria and Spirkl, Sophie and Zerbib, Shira},
title = {Piercing axis-parallel boxes},
journal = {Electronic Journal of Combinatorics},
volume = {25},
number = {1},
pages = {P1.70},
year = {2018},
doi = {10.37236/7034},
eprint = {1705.00089},
archivePrefix = {arXiv}
}
@misc{green100open,
author = {Green, Ben},
title = {100 open problems},
howpublished = {\url{https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf}},
note = {Problem 76; version of January 2026, most recent update December 2025},
year = {2026}
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00954, "Weak nets of linear size for axis-parallel rectangles", clopen.solutions.