Piercing axis-parallel boxes (Q1753044)

Summary: 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)\).