A unit square can be covered by a single disk of area $\pi/2$. Let us call the ratio of the square's area to that of the covering disks (i.e. the sum of the areas of the disks) the efficiency of the covering, so that in the base case with one disk the efficiency is $2/\pi\approx63.66\%$. Say that a covering is efficient if its efficiency exceeds this value. If we use a honeycomb (hexagonal) grid of $22$ equal disks in alternating rows of four and five disks, we get a covering efficiency of $24/11\pi\approx69.45\%$; so efficient coverings exist. Allowing disks of different sizes, how few are needed to cover the square efficiently? Can it be done with fewer than $22$ disks?

up vote 26 down vote accepted

With a bit of Googling I found this paper: Covering a Square with up to 30 Equal Circles, by Kari J. Nurmela and Patric R. J. Östergård.

They used a computer search to find coverings of a square by $n$ equal circles, where the radius of those circles is as small as possible. They give a table of radius values, which I reproduce below. I've added columns with the total area of the circles and the efficiency.

  n    radius        Circle Area   Efficiency
  1    0.707106781   1.570796327   0.636619772
  2    0.559016994   1.963495408   0.509295818
  3    0.503891109   2.393010029   0.417883748
  4    0.353553391   1.570796327   0.636619772
  5    0.326160584   1.671024545   0.598435255
  6    0.298727062   1.682093989   0.594497101
  7    0.274291885   1.654526896   0.604402384
  8    0.260300106   1.702897662   0.587234349
  9    0.230636928   1.504007739   0.664890196
  10   0.218233513   1.496210711   0.66835506
  11   0.212516016   1.560723218   0.640728598
  12   0.202275889   1.542479343   0.648306899
  13   0.194312371   1.542034638   0.648493864
  14   0.185510547   1.51361395    0.660670444
  15   0.17966176    1.521081313   0.65742705
  16   0.169427052   1.442897104   0.693050112
  17   0.16568093    1.466033314   0.68211274
  18   0.160639664   1.459244113   0.685286301
  19   0.157841982   1.487128592   0.672436806
  20   0.152246811   1.456385273   0.686631497
  21   0.14895379    1.463768108   0.683168321
  22   0.143693177   1.427068593   0.700737165
  23   0.141244822   1.441527004   0.693708822
  24   0.138302883   1.442193663   0.693388153
  25   0.133548707   1.400777811   0.713889092
  26   0.131764876   1.418151189   0.705143434
  27   0.128633535   1.403531108   0.712488661
  28   0.127317553   1.425884911   0.701318874
  29   0.125553508   1.436169083   0.696296844
  30   0.122036869   1.403631932   0.712437482

As you can see, they become efficient from $n=9$ onwards. Here's a picture from that paper of the first efficient arrangements $n=9 ... 12$.

enter image description here

Of course it may still be possible that with fewer than 9 discs of different sizes you can make an efficient covering.

EDIT:
Inspired by Jack D'Aurizio's solution I found that you can even make an efficient 3-disc covering.

enter image description here

Calculating the optimal solution exactly is horrendous. Just by tweaking the numbers, the best efficiency I found with this configuration is approximately $0.693881$.

I chose the large radius to be $0.6572$, and from that it follows that $|OG|=0.426511$, $|AE|=0.179029$, $|AF|=0.146978$, and the small radius is $|EF|/2 = 0.115816$.

EDIT 2:

To complete the answer, here is a simple proof that 2 discs can never efficiently cover the square.

Consider the 4 vertices of the square. If one of the discs covers two diagonally opposite vertices, then it will be as large as the 1-disc covering, and the non-zero area of the other disc will make any covering with those discs inefficient.

If either disc covers three of the four vertices, then it will cover a diagonal pair, and the covering becomes inefficient as explained above.

The only way therefore to cover the four vertices is if each disc covers two adjacent vertices. This makes their radii greater than $1/2$. This inequality is easily seen to be strict. Their combined area is then strictly greater than $\pi/2$, making any covering by them inefficient.

  • Three looks as though it's going to be hard to beat! I just need to do some checking. – John Bentin Aug 14 at 16:26
  • 2
    I get the optimal value for $|AE|$ as the real root of the cubic $6x^3-9x^2+7x-1=0$, with $|AF|=x-x^2$. – John Bentin Aug 14 at 17:52
  • 1
    The paper uses equal circles. If unequal circles are allowed, the efficiency should never decrease as the number increases, since one could just use fewer circles and "waste" the remainder as circles of zero size. – Gnubie Aug 15 at 12:29

If different circle sizes are allowed, we may reach an efficiency $>76.3\%$ with just five disks:

enter image description here

With $13$ disks the maximum efficiency is already $>80.4\%$. It is enough to replace each "corner disk" above with three disks with approximately half the radius:

enter image description here

If we adjust the configuration in each corner (allowing the most external disks to overlap with the larger disk) the maximum efficiency with $13$ disk is $\geq 82.5\%$:

enter image description here

  • 2
    Very nice. It looks to me like $12/5\pi$. – John Bentin Aug 14 at 13:56
  • 1
    @JohnBentin Yes, I was about to comment the same thing. The distance between the square's vertex and the nearest intersections of the circles is $1/6$. – Jaap Scherphuis Aug 14 at 13:59
  • Even 3 circles are enough to get efficiency $>2/\pi$: let the big circle pass through two lower vertices of the square and leave two small uncovered "triangles" at the upper vertices; cover those "triangles" with two small circles. But I didn't calculate the maximal efficiency one can obtain this way. – Litho Aug 14 at 14:42
  • @Litho I was just doing that too. I added it to my answer, and got an efficiency of $0.693881$. – Jaap Scherphuis Aug 14 at 14:48
  • 1
    What's the inscribed dotted circle in the first diagram? Is it used in a construction of the most efficient covering with that count and symmetry? – aschepler Aug 15 at 1:45

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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