Piercing Axis-Parallel Boxes

Source abstract

Let $\mathcal{F}$ be a finite family of axis-parallel boxes in $\mathbb{R}^d$ such that $\mathcal{F}$ contains no $k+1$ pairwise disjoint boxes. We prove that if $\mathcal{F}$ contains a subfamily $\mathcal{M}$ of $k$ pairwise disjoint boxes with the property that for every $F\in \mathcal{F}$ and $M\in \mathcal{M}$ with $F \cap M \neq \emptyset$, either $F$ contains a corner of $M$ or $M$ contains $2^{d-1}$ corners of $F$, then $\mathcal{F}$ can be pierced by $O(k)$ points. One consequence of this result is that if $d=2$ and the ratio between any of the side lengths of any box is bounded by a constant, then $\mathcal{F}$ can be pierced by $O(k)$ points. We further show that if for each two intersecting boxes in $\mathcal{F}$ a corner of one is contained in the other, then $\mathcal{F}$ can be pierced by at most $O(k\log\log(k))$ points, and in the special case where $\mathcal{F}$ contains only cubes this bound improves to $O(k)$.