A note on piercing discrete rectangles

Abstract

In 2008, Halman proved a discrete Helly-type theorem for axis-parallel boxes in ${\mathbb{R}}^d$. Very recently, this result was extended to the $(p,q)$ setting with $p\ge q\ge d+1$ by Edwards and Soberón, and subsequently to the case $p\ge q\ge 2$ by Gangopadhyay, Polyanskii, and the author of this paper. In this paper, we obtain improved bounds for the $(p,q)$ problem in the case $q=2$ and $d=2$. More precisely, our main result asserts that for any integer $p\ge 2$, any set $P\subseteq {\mathbb{R}}^2$, and any finite family $\mathcal{B}$ of axis-parallel rectangles in ${\mathbb{R}}^2$ such that every rectangle contains a point of $P$, if among every $p$ rectangles there exist two whose intersection contains a point of $P$, then there exists a subset $S\subseteq P$ of size at most $O((p\log \log p{)}^2)$ such that every rectangle contains a point of $S$. Moreover, when $p=2$, the size of $S$ can be bounded by $4$.

We improve the bounds obtained in the original manuscript