TY - JOUR
T1 - Piercing axis-parallel boxes
AU - Chudnovsky, Maria
AU - Spirkl, Sophie
AU - Zerbib, Shira
N1 - Funding Information:
∗Supported by NSF grant DMS-1550991 and US Army Research Office Grant W911NF-16-1-0404.
Funding Information:
∗ Supported by NSF grant DMS-1550991 and US Army Research Office Grant W911NF-16-1-0404.
Publisher Copyright:
© 2018, Australian National University. All rights reserved.
PY - 2018/3/29
Y1 - 2018/3/29
N2 - Let F be a finite family of axis-parallel boxes in ℝd such that F contains no k + 1 pairwise disjoint boxes. We prove that if F contains a subfamily M of k pairwise disjoint boxes with the property that for every F ∈ F and M ∈ M with F ∩ M ≠ ∅, either F contains a corner of M or M contains 2d −1 corners of F, then 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 F can be pierced by O(k) points. We further show that if for each two intersecting boxes in F a corner of one is contained in the other, then F can be pierced by at most O(k log log(k)) points, and in the special case where F contains only cubes this bound improves to O(k).
AB - Let F be a finite family of axis-parallel boxes in ℝd such that F contains no k + 1 pairwise disjoint boxes. We prove that if F contains a subfamily M of k pairwise disjoint boxes with the property that for every F ∈ F and M ∈ M with F ∩ M ≠ ∅, either F contains a corner of M or M contains 2d −1 corners of F, then 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 F can be pierced by O(k) points. We further show that if for each two intersecting boxes in F a corner of one is contained in the other, then F can be pierced by at most O(k log log(k)) points, and in the special case where F contains only cubes this bound improves to O(k).
UR - http://www.scopus.com/inward/record.url?scp=85044715354&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85044715354&partnerID=8YFLogxK
U2 - 10.37236/7034
DO - 10.37236/7034
M3 - Article
AN - SCOPUS:85044715354
SN - 1077-8926
VL - 25
JO - Electronic Journal of Combinatorics
JF - Electronic Journal of Combinatorics
IS - 1
M1 - #P1.70
ER -