Covering a disk by disks

Adrian Dumitrescu and Minghui Jiang

Abstract: For a convex body $C$ in $\RR^d$, what is the smallest number $f = f_d(C)$ such that any sequence of smaller homothetic copies of $C$ whose total volume is at least $f$ times the volume of $C$ permits a translative covering of $C$? László Fejes Tóth conjectured in 1984 that $f_2(C) \leq 3$ for any convex body $C$ in the plane. This conjecture has been only confirmed for parallelograms and triangles: Moon and Moser had shown in 1967 that $f_2(C) = 3$ for a square $C$. Since $f_d(C)$ is invariant under affine transformation of $C$, it follows from Moon and Moser's result that $f_2(C) = 3$ for any parallelogram $C$. In 2003, Füredi settled the case of triangles with a sharper bound, by showing that $f_2(C) = 2$ for a triangle $C$, and thus confirming a stronger conjecture of A. Bezdek and K. Bezdek for this case. For an arbitrary planar convex body $C$, the current best bound is $f_2(C) \leq 6.5$, due to Januszewski. In this paper, we prove that $f_2(D) < 3$ for a disk $D$, and thereby confirm the conjecture of László Fejes Tóth for disks. We also present the first non-trivial bound for covering a disk by disks in the online model. Our methods lead to very efficient algorithms for both offline and online disk covering.

Full text of the article:

• Compressed PostScript file (661 kilobytes)
• PDF file (232 kilobytes)