Colorful two-piercing theorem for boxes
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909963416240128 |
|---|---|
| author | Chakraborty, Sourav Ghosh, Arijit Nandi, Soumi |
| author_facet | Chakraborty, Sourav Ghosh, Arijit Nandi, Soumi |
| contents | We prove a colorful extension of a Helly-type theorem by Danzer and Grünbaum (Combinatorica, 1982) concerning two-piercing families of axis-parallel boxes in $\mathbb{R}^d$. We also show that our result is tight by constructing extremal families that achieve the bound. Related work includes a graph-theoretic proof of the original theorem by Pendavingh, Puite, and Woeginger (Discrete Applied Mathematics, 2008), and a two-piercing result for lower-dimensional boxes by Baños and Oliveros (Acta Mathematica Hungarica, 2018). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2207_14368 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Colorful two-piercing theorem for boxes Chakraborty, Sourav Ghosh, Arijit Nandi, Soumi Computational Geometry Combinatorics 52A35 We prove a colorful extension of a Helly-type theorem by Danzer and Grünbaum (Combinatorica, 1982) concerning two-piercing families of axis-parallel boxes in $\mathbb{R}^d$. We also show that our result is tight by constructing extremal families that achieve the bound. Related work includes a graph-theoretic proof of the original theorem by Pendavingh, Puite, and Woeginger (Discrete Applied Mathematics, 2008), and a two-piercing result for lower-dimensional boxes by Baños and Oliveros (Acta Mathematica Hungarica, 2018). |
| title | Colorful two-piercing theorem for boxes |
| topic | Computational Geometry Combinatorics 52A35 |
| url | https://arxiv.org/abs/2207.14368 |