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

$$r(1) = 1$$

$$r(2) = 1$$

$$r(3) = {\textstyle{1\over 2}}\sqrt{3}$$

$$r(4) = {\textstyle{1\over 2}}\sqrt{2}$$

$$r(5) = 0.609382864\ldots$$

$$r(6) = 0.555$$

$$r(7) = {\textstyle{1\over 2}}$$

$$r(8) = 0.437$$

$$r(9) = 0.422$$

$$r(10) = 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

$$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$$ (5)

maximized over all $y$, subject to the constraints

$$\sqrt{2}<x<2y+1$$ (6)

$$-1<y<1,$$ (7)

and with

$$a(y) = 80y^2+64y$$ (8)

$$b(y) = 416y^3+384y^2+64y$$ (9)

$$c(y) = 848y^4+928y^3+352y^2+32y$$ (10)

$$d(y) = 768y^5+992y^4+736y^3+288y^2+96y$$

$$e(y) = 256y^6+384y^5+592y^4+480y^3+336y^2+96y+16$$ (11)

$$f(y) = 128y^5+192y^4+256y^3+160y^2+96y+32$$ (12)

$$g(y) = 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

$$\lim_{\epsilon\to 0^+} {1\over\epsilon^2 N(\epsilon)} = {3\sqrt{3}\over 2\pi}$$ (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.