14
$\begingroup$

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?

$\endgroup$
9
  • 1
    $\begingroup$ 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. $\endgroup$ Commented May 25, 2012 at 13:26
  • 1
    $\begingroup$ 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) $\endgroup$
    – JRN
    Commented May 25, 2012 at 13:40
  • 2
    $\begingroup$ 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. $\endgroup$ Commented May 25, 2012 at 13:41
  • 11
    $\begingroup$ 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. $\endgroup$ Commented May 25, 2012 at 14:10
  • 3
    $\begingroup$ 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. $\endgroup$ Commented May 25, 2012 at 18:47

4 Answers 4

9
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ Some nice pictures can be found here: www2.stetson.edu/~efriedma/circovcir $\endgroup$
    – JRN
    Commented May 25, 2012 at 13:48
  • 1
    $\begingroup$ Great, thanks for the link, looking forward to going away and reading up on this problem. $\endgroup$ Commented May 25, 2012 at 13:49
  • 4
    $\begingroup$ 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). $\endgroup$ Commented May 25, 2012 at 14:13
23
$\begingroup$

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

$\endgroup$
4
  • 24
    $\begingroup$ 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. $\endgroup$ Commented May 25, 2012 at 18:52
  • $\begingroup$ @Noam: Nice uniqueness proof! $\endgroup$ Commented May 25, 2012 at 23:40
  • 1
    $\begingroup$ @NoamD.Elkies: Pacly Taxel gave a nice analysis for the case $n=6$ disks in this MSE post. $\endgroup$ Commented Feb 17, 2018 at 1:18
  • $\begingroup$ @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 ? $\endgroup$ Commented Sep 2, 2021 at 12:04
8
$\begingroup$

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

$\endgroup$
0
5
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ I think what Bezdek proved is that six disks of radius $r \approx 1.798$ suffice. $\endgroup$ Commented May 25, 2012 at 17:59
  • $\begingroup$ 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. $\endgroup$ Commented May 25, 2012 at 18:28
  • 1
    $\begingroup$ 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. $\endgroup$ Commented May 25, 2012 at 18:30
  • $\begingroup$ @Zsbán: I stand corrected! $\endgroup$ Commented May 25, 2012 at 18:45
  • 2
    $\begingroup$ The packing center is now here: erich-friedman.github.io/packing/index.html $\endgroup$ Commented Dec 6, 2020 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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