info prev up next book cdrom email home

Disk Covering Problem

N.B. A detailed on-line essay by S. Finch was the starting point for this entry.


Given a Unit Disk, find the smallest Radius $r(n)$ required for $n$ equal disks to completely cover the Unit Disk. For a symmetrical arrangement with $n=5$ (the Five Disks Problem), $r(5)=\phi-1=1/\phi=0.6180340\ldots$, where $\phi$ is the Golden Ratio. However, the radius can be reduced in the general disk covering problem where symmetry is not required. The first few such values are

$\displaystyle r(1)$ $\textstyle =$ $\displaystyle 1$  
$\displaystyle r(2)$ $\textstyle =$ $\displaystyle 1$  
$\displaystyle r(3)$ $\textstyle =$ $\displaystyle {\textstyle{1\over 2}}\sqrt{3}$  
$\displaystyle r(4)$ $\textstyle =$ $\displaystyle {\textstyle{1\over 2}}\sqrt{2}$  
$\displaystyle r(5)$ $\textstyle =$ $\displaystyle 0.609382864\ldots$  
$\displaystyle r(6)$ $\textstyle =$ $\displaystyle 0.555$  
$\displaystyle r(7)$ $\textstyle =$ $\displaystyle {\textstyle{1\over 2}}$  
$\displaystyle r(8)$ $\textstyle =$ $\displaystyle 0.437$  
$\displaystyle r(9)$ $\textstyle =$ $\displaystyle 0.422$  
$\displaystyle r(10)$ $\textstyle =$ $\displaystyle 0.398.$  

Here, values for $n=6$, 8, 9, 10 were obtained using computer experimentation by Zahn (1962). The value $r(5)$ is equal to $\cos(\theta+\phi/2)$, where $\theta$ and $\phi$ are solutions to
$2\sin\theta-\sin(\theta+{\textstyle{1\over 2}}\phi+\psi)-\sin(\psi-\theta-{\textstyle{1\over 2}}\phi)=0$ (1)
$2\sin\phi-\sin(\theta+{\textstyle{1\over 2}}\phi+\chi)-\sin(\chi-\theta-{\textstyle{1\over 2}}\phi)=0$ (2)
$2\sin\theta+\sin(\chi+\theta)-\sin(\chi-\theta)-\sin(\psi+\phi)$
$ -\sin(\psi-\phi)-2\sin(\psi-2\theta)=0\quad$ (3)
$\cos(2\psi-\chi+\phi)-\cos(2\psi+\chi-\phi)-2\cos\chi$
$ +\cos(2\psi+\chi-2\theta)+\cos(2\psi-\chi-2\theta)=0\quad$ (4)
(Neville 1915). It is also given by $1/x$, where $x$ is the largest real root of


\begin{displaymath}
a(y)x^6-b(y)x^5+c(y)x^4-d(y)x^3+e(y)x^2-f(y)x+g(y)=0
\end{displaymath} (5)

maximized over all $y$, subject to the constraints
\begin{displaymath}
\sqrt{2}<x<2y+1
\end{displaymath} (6)


\begin{displaymath}
-1<y<1,
\end{displaymath} (7)

and with


$\displaystyle a(y)$ $\textstyle =$ $\displaystyle 80y^2+64y$ (8)
$\displaystyle b(y)$ $\textstyle =$ $\displaystyle 416y^3+384y^2+64y$ (9)
$\displaystyle c(y)$ $\textstyle =$ $\displaystyle 848y^4+928y^3+352y^2+32y$ (10)
$\displaystyle d(y)$ $\textstyle =$ $\displaystyle 768y^5+992y^4+736y^3+288y^2+96y$  
$\displaystyle e(y)$ $\textstyle =$ $\displaystyle 256y^6+384y^5+592y^4+480y^3+336y^2+96y+16$ (11)
$\displaystyle f(y)$ $\textstyle =$ $\displaystyle 128y^5+192y^4+256y^3+160y^2+96y+32$  
      (12)
$\displaystyle g(y)$ $\textstyle =$ $\displaystyle 64y^2+64y+16$ (13)

(Bezdek 1983, 1984).


Letting $N(\epsilon)$ be the smallest number of Disks of Radius $\epsilon$ needed to cover a disk $D$, the limit of the ratio of the Area of $D$ to the Area of the disks is given by

\begin{displaymath}
\lim_{\epsilon\to 0^+} {1\over\epsilon^2 N(\epsilon)} = {3\sqrt{3}\over 2\pi}
\end{displaymath} (14)

(Kershner 1939, Verblunsky 1949).

See also Five Disks Problem


References

Ball, W. W. R. and Coxeter, H. S. M. ``The Five-Disc Problem.'' In Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 97-99, 1987.

Bezdek, K. ``Über einige Kreisüberdeckungen.'' Beiträge Algebra Geom. 14, 7-13, 1983.

Bezdek, K. ``Über einige optimale Konfigurationen von Kreisen.'' Ann. Univ. Sci. Budapest Eötvös Sect. Math. 27, 141-151, 1984.

Finch, S. ``Favorite Mathematical Constants.'' http://www.mathsoft.com/asolve/constant/circle/circle.html

Kershner, R. ``The Number of Circles Covering a Set.'' Amer. J. Math. 61, 665-671, 1939.

Neville, E. H. ``On the Solution of Numerical Functional Equations, Illustrated by an Account of a Popular Puzzle and of its Solution.'' Proc. London Math. Soc. 14, 308-326, 1915.

Verblunsky, S. ``On the Least Number of Unit Circles which Can Cover a Square.'' J. London Math. Soc. 24, 164-170, 1949.

Zahn, C. T. ``Black Box Maximization of Circular Coverage.'' J. Res. Nat. Bur. Stand. B 66, 181-216, 1962.



info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein
1999-05-24