Making Octants Colorful and Related Covering Decomposition Problems
Jean Cardinal, Kolja Knauer, Piotr Micek, Torsten Ueckerdt · SIAM Journal on Discrete Mathematics · 2014
We give new positive results on the long-standing open problem of geometric covering decomposition for homothetic polygons. In particular, we prove that for any positive integer $k$, every finite set of points in $\mathbb{R}^3$ can be colored with $k$ colors so that every translate of the negative octant containing at least $k^6$ points contains at least one of each color. The best previously known bound was doubly exponential in $k$. This yields, among other corollaries, the first polynomial bound for the decomposability of multiple coverings by homothetic triangles. We also investigate related decomposition problems involving intervals appearing on a line. We prove that no algorithm can dynamically maintain a decomposition of a multiple covering by intervals under insertion of new intervals, even in a semionline model, in which some coloring decisions can be delayed. This implies that a wide range of sweeping plane algorithms cannot guarantee any bound even for special cases of the octant problem.