TOPICS
Search

Disk Covering Problem

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

Given a unit disk, find the smallest radius r(n) required for n equal disks to completely cover the unit disk. The first few such values are

r(1)=1
(1)
r(2)=1
(2)
r(3)=1/2sqrt(3)
(3)
r(4)=1/2sqrt(2)
(4)
r(5)=0.609382864...
(5)
r(6) approx 0.555
(6)
r(7)=1/2
(7)
r(8) approx 0.437
(8)
r(9) approx 0.422
(9)
r(10) approx 0.398.
(10)

Here, values for n=6, 8, 9, 10 are approximate values obtained using computer experimentation by Zahn (1962).

DiskCoveringProblem5

For a symmetrical arrangement with n=5 (known as the five disks problem), r(5)=phi-1=1/phi=0.6180340..., where phi is the golden ratio. However, rather surprisingly, the radius can be slightly reduced in the general disk covering problem where symmetry is not required; this configuration is illustrated above (Friedman). Neville (1915) showed that the value r(5) is equal to cos(theta+phi/2), where theta and phi are solutions to

2sintheta-sin(theta+1/2phi+psi)-sin(psi-theta-1/2phi)=0
(11)
2sinphi-sin(theta+1/2phi+chi)-sin(chi-theta-1/2phi)=0
(12)
2sintheta+sin(chi+theta)-sin(chi-theta)-sin(psi+phi)-sin(psi-phi)-2sin(psi-2theta)=0
(13)
cos(2psi-chi+phi)-cos(2psi+chi-phi)-2coschi+cos(2psi+chi-2theta)+cos(2psi-chi-2theta)=0.
(14)

These solutions can be found exactly as

theta=sin^(-1)r_1
(15)
phi=2sin^(-1)r_2
(16)

where

r_1=(576x^(16)+3136x^(14)-16720x^(12)+31744x^(10)-32756x^8+22580x^6-12267x^4+4482x^2-675)_4
(17)
r_2=(746496x^(16)-3032064x^(14)+4995456x^(12)-4241024x^(10)+1931140x^8-435956x^6+36149x^4-22x^2-75)_4
(18)

are the smallest positive roots of the given polynomials, with (P(x))_n denoting the nth root of the polynomial P(x) in the ordering of the Wolfram Language. This gives r(5)=0.609382864... (OEIS A133077) exactly as

r(5)=(1296x^8+2112x^7-3480x^6+1360x^5+1665x^4-1776x^3+22x^2-800x+625)_3,
(19)

where the root is the smallest positive one of the above polynomial.

r(5) 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
(20)

maximized over all y, subject to the constraints

sqrt(2)<x<2y+1
(21)
-1<y<1,
(22)

and with

a(y)=80y^2+64y
(23)
b(y)=416y^3+384y^2+64y
(24)
c(y)=848y^4+928y^3+352y^2+32y
(25)
d(y)=768y^5+992y^4+736y^3+288y^2+96y
(26)
e(y)=256y^6+384y^5+592y^4+480y^3+336y^2+96y+16
(27)
f(y)=128y^5+192y^4+256y^3+160y^2+96y+32
(28)
g(y)=64y^2+64y+16
(29)

(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->0^+)1/(epsilon^2N(epsilon))=(3sqrt(3))/(2pi)
(30)

(OEIS A086089; Kershner 1939, Verblunsky 1949).

See also

Circle Covering, Five Disks Problem

Explore with Wolfram|Alpha

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. R. "Circular Coverage Constants." §2.2 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 484-489, 2003.Friedman, E. "Circles Covering Circles." http://www.stetson.edu/~efriedma/circovcir/.Gardner, M. The Second Scientific American Book of Puzzles & Diversions: A New Selection. New York: Simon and Schuster, pp. 142-144, 1961.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.Sloane, N. J. A. Sequences A086089 and A133077 in "The On-Line Encyclopedia of Integer Sequences."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.

Referenced on Wolfram|Alpha

Disk Covering Problem

Cite this as:

Weisstein, Eric W. "Disk Covering Problem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/DiskCoveringProblem.html

Subject classifications