More on decomposing coverings by octants

Balázs Keszegh, Dömötör Pálvölgyi

Abstract


$\newcommand{\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.

Full Text:

PDF


DOI: http://dx.doi.org/10.20382/jocg.v6i1a13

ISSN: 1920-180X