Beitr\ EMIS ELibM Electronic Journals Beiträge zur Algebra und Geometrie
Contributions to Algebra and Geometry
Vol. 51, No. 1, pp. 91-109 (2010)

Previous Article

Next Article

Contents of this Issue

Other Issues

ELibM Journals

ELibM Home



Covering a disk by disks

Adrian Dumitrescu and Minghui Jiang

Department of Computer Science, University of Wisconsin, Milwaukee, WI 53201-0784, USA, e-mail:; Department of Computer Science, Utah State University, Logan, UT 84322-4205, USA, e-mail:

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.

© 2010 Heldermann Verlag
© 2010–2013 FIZ Karlsruhe / Zentralblatt MATH for the EMIS Electronic Edition