# How few disks are needed to cover a square efficiently?

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?

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.

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$.

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.

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 '18 at 16:26
• 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 '18 at 17:52
• 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 '18 at 12:29
• @jaapscherphuis hi. can the efficiency be arbitrarily close to 1 with arbitrarily many circles allowed? – mathworker21 Sep 30 '19 at 18:02
• @mathworker21 No, there will always be overlap. I suspect the best covering is a hexagonal arrangement of equal radius circles, which has an efficiency of $\frac{3\sqrt{3}}{2\pi} \approx 82.699\%$. – Jaap Scherphuis Sep 30 '19 at 19:51

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

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:

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\%$:

• Very nice. It looks to me like $12/5\pi$. – John Bentin Aug 14 '18 at 13:56
• @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 '18 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 '18 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 '18 at 14:48
• 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 '18 at 1:45
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9040635824203491, "perplexity": 406.90739868789234}, "config": {"markdown_headings": true, "markdown_code": false, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2020-45/segments/1603107874340.10/warc/CC-MAIN-20201020221156-20201021011156-00343.warc.gz"}