Beiträge zur Algebra und Geometrie
Contributions to Algebra and Geometry
Vol. 51, No. 1, pp. 91-109 (2010)
Covering a disk by disks
Adrian Dumitrescu and Minghui JiangDepartment of Computer Science, University of Wisconsin, Milwaukee, WI 53201-0784, USA, e-mail: firstname.lastname@example.org; Department of Computer Science, Utah State University, Logan, UT 84322-4205, USA, e-mail: email@example.com
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:
Electronic version published on: 27 Jan 2010. This page was last modified: 28 Jan 2013.