Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

How many disks with radius 1/2 are needed to cover a disk with radius 1? It certainly cannot be done with less than 5 small disks, and some non-rigorous drawings of mine suggest it can be done with 7 small disks. Can it be done with less?

Slightly more generally, can anybody point me in the direction of any work on covering bounded bodies with disks? Am i right in thinking that covering disks with smaller disks is the most inefficient kind of covering?

share|improve this question
1  
I think you are asking for covering a circle with disks, the distinction being that a circle is a 1D curve, whereas a disk is the 2D region bounded by a circle. –  Joseph O'Rourke May 25 '12 at 13:26
1  
You cannot cover a disk with $r=1$ with five disks with radius $r=0.5$. It seems that to use five disks requires that their radius be around 0.609383. (See mathworld.wolfram.com/FiveDisksProblem.html) –  Joel Reyes Noche May 25 '12 at 13:40
2  
Even if it's not literally a packing problem, it's a natural enough variation that the tag is reasonable. Even Conway and Sloane's Sphere Packings, Lattices, and Groups [a.k.a. SPLAG, including by the authors] has a few sections on sphere covering. –  Noam D. Elkies May 25 '12 at 13:41
9  
After a bit of further thought: in this case it's easy to show that six discs do not suffice. Consider the following seven points: the vertices of a hexagon inscribed in the circle, together with its center [for either referent of "its"]. One of the small disks would have to cover two of them, and thus be on the midpoint of one of the $12$ unit segments formed by our seven points. Now rotate the hexagon to get a contradiction. –  Noam D. Elkies May 25 '12 at 14:10
2  
Sorry, what I meant was that one of the seven centers must be included among those 12 points, none of which is the center of the original disk. Rotations yield uncountably many disjoint sets of 12 points with the same property, which gives the desired contradiction. –  Noam D. Elkies May 25 '12 at 18:47

4 Answers 4

up vote 8 down vote accepted

You'll need seven disks with $r=0.5$ to cover a disk with $r=1$. See http://mathworld.wolfram.com/DiskCoveringProblem.html.

share|improve this answer
1  
Some nice pictures can be found here: www2.stetson.edu/~efriedma/circovcir –  Joel Reyes Noche May 25 '12 at 13:48
    
Great, thanks for the link, looking forward to going away and reading up on this problem. –  Oliver Roche-Newton May 25 '12 at 13:49
4  
For an elementary proof, see my comment above (for the question itself, showing six do not suffice), together with the picture Joseph O'Rourke posted (showing a seven-disc covering). –  Noam D. Elkies May 25 '12 at 14:13

Just to help think about the problem, here is the natural cover by seven $\frac{1}{2}$ disks:
          Disk cover

share|improve this answer
12  
Indeed this "natural cover" is also unique up to rotations. One disk must cover the center, and thus have at most one point of intersection with the perimeter. Each of the other six discs can cover at most $1/6$ of the perimeter, so together the only way the entire perimeter can be covered is as shown. Now the remaining disc must be centered to cover the unaccounted-for area (colored light green in Joseph O'Rourke's graphic), QED. –  Noam D. Elkies May 25 '12 at 18:52
    
@Noam: Nice uniqueness proof! –  Joseph O'Rourke May 25 '12 at 23:40

A more general version of this question is discussed (and answered) in this paper by Dumitrescu and Jiang

share|improve this answer
    
+1, very nice ! –  Joel Reyes Noche May 25 '12 at 13:49

Erich Friedman's packing center claims that you can't cover with 6 disks, and that this was proved by Károly Bezdek in 1979. If you want a more exact reference, ask Erich Friedman in email.

share|improve this answer
    
I think what Bezdek proved is that six disks of radius $r \approx 1.798$ suffice. –  Joseph O'Rourke May 25 '12 at 17:59
    
No, what he proved is that a disk of radius $ \approx 1.798 $ can be covered by six unit disks, but no larger disk can be covered. –  Zsbán Ambrus May 25 '12 at 18:28
    
In the context of the packing pages, "proved" refers to proving optimality, whereas just proving that a packing or covering works is listed as "found". For context, see www2.stetson.edu/~efriedma/cirinsqu where finding the smallest square with 9 disks is trivial, but proving it optimal is difficult, so whoever has first proved it is listed. –  Zsbán Ambrus May 25 '12 at 18:30
    
@Zsbán: I stand corrected! –  Joseph O'Rourke May 25 '12 at 18:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.