Slicing axis-parallel rectangles with few lines
Call two axis-parallel rectangles in the plane independent if their projections to the $x$-axis are disjoint and their projections to the $y$-axis are also disjoint, and call a set of rectangles independent if its members are pairwise independent.
Vatter met the question in work on permutation classes and showed that the number $f(m)$ below is finite, with an exponential upper bound. Werner and Lenz proved $f(m) = O(m^2)$, a bound they report Tardos and Károlyi had found earlier, and Soberón pointed out that a theorem of Kaiser already gives $f(m) \le 2m$.
Problem. Let $f(m)$ be the least number such that every collection of axis-parallel rectangles containing no independent set of $m$ or more rectangles can be sliced by $f(m)$ horizontal and vertical lines, that is, every rectangle of the collection meets at least one of the lines. Determine $f(m)$.
Source: Vatter (2009); Problem 74 of The Open Problems Project (Demaine, Mitchell and O'Rourke).
Imported from topp.openproblem.net.
Classification
- Primary
- CO — Combinatorics
- Secondary
- MG
- Keywords
- axis-parallel rectangles, independent set, piercing number, The Open Problems Project
References
@misc{vatter2008,
author = {Vatter, Vincent},
title = {Small permutation classes},
year = {2008},
eprint = {0712.4006},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/0712.4006v2},
}
@article{kaiser1997,
author = {Kaiser, T.},
title = {Transversals of $d$-intervals},
journal = {Discrete Comput. Geom.},
volume = {18},
number = {2},
year = {1997},
pages = {195--203},
}
@misc{werner2010,
author = {Werner, Daniel and Lenz, Matthias},
title = {Polynomial bounds on the rectangle slicing number},
year = {2010},
eprint = {1004.3381},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/1004.3381},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01106, "Slicing axis-parallel rectangles with few lines", clopen.solutions.