Piercing axis-parallel boxes

MaRDI QIDQ1753044zbMATH OpenFDO

Authors Maria Chudnovsky, Sophie Spirkl, Shira Zerbib

Publication date 25 May 2018

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.00089, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i1p70

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

axis-parallel boxeshitting setmatching and coveringpacking and coveringpiercing

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17)

Abstract: Let $F$ be a finite family of axis-parallel boxes in $R^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 $FinF$ and $MinM$ with $FcapMeqemptyset$, either $F$ contains a corner of $M$ or $M$ contains $2^{d-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(kloglog(k))$ points, and in the special case where $F$ contains only cubes this bound improves to $O(k)$.

Review text

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

Recommendations

• Piercing random boxes
• 3-PIERCING OF d-DIMENSIONAL BOXES AND HOMOTHETIC TRIANGLES
• Covering boxes by points
• From a \((p, 2)\)-theorem to a tight \((p, q)\)-theorem
• A fractional Helly theorem for boxes

Cites work

• A note about weak -nets for axis-parallel boxes in d-space
• Approximation algorithms for maximum independent set of pseudo-disks
• Covering and coloring problems for relatives of intervals
• Covering boxes by points
• scientific article; zbMATH DE number 3152801 (Why is no real title available?)
• scientific article; zbMATH DE number 1234104 (Why is no real title available?)
• Intersection Graphs of Rectangles and Segments
• New existence proofs ε-nets
• On point covers of parallel rectangles
• Small-size -nets for axis-parallel rectangles and boxes
• Tight lower bounds for the size of epsilon-nets
• Über eine kombinatorisch-geometrische Frage von Hadwiger und Debrunner

Cited in

(17)

• 2-piercings via graph theory
• On Wegner's inequality for axis-parallel rectangles
• Piercing all translates of a set of axis-parallel rectangles
• From a \((p, 2)\)-theorem to a tight \((p, q)\)-theorem
• Brick partition problems in three dimensions
• Piercing random boxes
• scientific article; zbMATH DE number 1254001 (Why is no real title available?)
• Helly-type theorems for hollow axis-aligned boxes
• 3-PIERCING OF d-DIMENSIONAL BOXES AND HOMOTHETIC TRIANGLES
• From a \((p,2)\)-theorem to a tight \((p,q)\)-theorem
• Bounds on piercing and line-piercing numbers in families of convex sets in the plane
• Fractional Helly theorem for Cartesian products of convex sets
• Lower bounds for piercing and coloring boxes
• Piercing all translates of a set of axis-parallel rectangles
• Stabbing boxes with finitely many axis-parallel lines and flats
• Covering boxes by points
• Intersection of parallelepipeds in \(\mathbb R^d\)

This page was built for publication: Piercing axis-parallel boxes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1753044)