14

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?

Oliver Roche-Newton
  • 1,478
  • 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
  • Yes sorry about that. I am asking about covering disks by smaller disks. – Oliver Roche-Newton May 25 '12 at 13:30
  • 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 http://mathworld.wolfram.com/FiveDisksProblem.html) – JRN 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
  • @Noam, yes, you are correct. I'm deleting my comment above. Thanks. – JRN May 25 '12 at 13:43
  • 1
    This page suggests that the minimum is 7 - http://mathworld.wolfram.com/DiskCoveringProblem.html – François G. Dorais May 25 '12 at 13:46
  • 11
    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
  • 1
    For the less adept among us, rotate Noam's hexagon by a small angle epsilon, and note the difficulty of covering all points within delta of the large circumference, using just 6 circles. Gerhard "Turned Over In My Mind" Paseman, 2012.05.25 – Gerhard Paseman May 25 '12 at 17:19
  • 3
    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 Answers4

23

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

Joseph O'Rourke
  • 149,182
  • 34
  • 342
  • 933
  • 24
    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
  • 1
    @NoamD.Elkies: Pacly Taxel gave a nice analysis for the case $n=6$ disks in this MSE post. – Tito Piezas III Feb 17 '18 at 01:18
  • @JosephO'Rourke- A small query: I believe centres of all red six disks lie on the perimeter of the hexagon and due to symmetry two opposite centres (red disks) will pass through the centre of the yellow disk. Is it true that these three points are collinear ? – maths123456 Sep 02 '21 at 12:04
9

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

JRN
  • 1,329
  • 1
    Some nice pictures can be found here: http://www2.stetson.edu/~efriedma/circovcir/ – JRN May 25 '12 at 13:48
  • 1
    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
8

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

Igor Rivin
  • 95,560
5

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.

Zsbán Ambrus
  • 1,924
  • 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
  • 1
    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 http://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
  • 2
    The packing center is now here: https://erich-friedman.github.io/packing/index.html – Erich Friedman Dec 06 '20 at 19:02