Piercing axis-parallel boxes

Maria Chudnovsky¹ ; Sophie Spirkl¹ ; Shira Zerbib²

¹Princeton University
²University of Michigan

The electronic journal of combinatorics, Tome 25 (2018) no. 1

Résumé

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)$.

Détail

DOI : 10.37236/7034

Classification : 05B40, 52C17, 52C15
Mots-clés : axis-parallel boxes, hitting set, piercing, packing and covering, matching and covering