Piercing axis-parallel boxes (Q1753044)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Piercing axis-parallel boxes |
scientific article |
Statements
Piercing axis-parallel boxes (English)
0 references
25 May 2018
0 references
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)\).
0 references
axis-parallel boxes
0 references
hitting set
0 references
piercing
0 references
packing and covering
0 references
matching and covering
0 references