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 -