More on decomposing coverings by octants
Balázs Keszegh, Dömötör Pálvölgyi · Journal of Computational Geometry (Carleton University) · 2015
$ ewcommand{\R}{\mathbb{R}}$In this note we improve our upper bound given in [Keszegh and Pálvölgyi, 2012] by showing that every $9$-fold covering of a point set in $\R^3$ by finitely many translates of an octant decomposes into two coverings, and our lower bound by a construction for a $4$-fold covering that does not decompose into two coverings. The same bounds also hold for coverings of points in $\R^2$ by finitely many homothets or translates of a triangle. We also prove that certain dynamic interval coloring problems are equivalent to the above question.