The Circles Covering Circles page of Erich Friedman's "Packing Center" shows…
a configuration of 23 unit circles covering a circle of radius ≥ 4.000, which means that the answer is yes! The configuration is in fact attributed to the author of this very question; what a coincidence…
After learning the above information, I set out to try and find a solution myself.
It would be possible to search for a set of sprinkler positions that maximize the amount of the lawn covered, however I chose a slightly different metric. Given a set of sprinkler positions, we can compute the minimum sprinkler radius needed to cover the entire lawn. If we find a position where the minimum radius is less than one, we have a solution to the problem. The approach I used was simulated annealing with a custom local search.
The first step is to calculate the minimum sprinkler radius given an arbitrary set of sprinkler locations. I did this by by constructing the Voronoi diagram of the sprinkler locations. Each cell of the Voronoi diagram consists of the region that is closer to one of the sprinklers than any other, so each sprinkler must cover its entire associated cell. The minimum radius is the largest (maximum) distance from any sprinkler to a vertex of its cell (considering only vertices inside the lawn), or to an intersection of a cell's edge with the boundary of the lawn.
This method works well given an arbitrary set of sprinkler locations, but is not much help in improving a solution since we can't calculate derivatives using this method. Instead, for local search I switch to a different method that assumes the sprinklers move only slightly, so the structure of the solution remains the same.
For a given arrangement there are two types of points that constrain the minimum radius; the points where the edges of three sprinklers' coverage circles nearly intersect ("triple points") and the points where two coverage circles intersect near an edge of the lawn ("edge points"). The diagram below shows a solution with the triple points in red and the edge points in blue:
![Approximate solution; red points are where three small circles overlap, blue points are where two small circles overlap outside of the large circle.](https://cdn.statically.io/img/i.sstatic.net/cCXK0.png)
If the coverage circles shrink too much, then gaps will open starting at these points. I use these points to formulate constraints:
- For the triple points, take the circumcenter of the triangle formed by the three sprinklers; the unique point equidistant from the three sprinklers. To force the coverage circles to overlap at the circumcenter, we constraint the minimum radius to be larger than the circumradius.
- For the edge points, find the intersection of the coverage circles furthest from the center of the lawn, and constrain the distance from the center to be larger than the radius of the lawn.
I used these constraints with a sequential least squares minimizer to find an improved solution. Sometimes the relative positions of the sprinklers changes, so I recompute the minimum radius with the Voronoi method at the end to make sure the discovered solution is still valid.
Putting these together yields the following solution:
![23 unit disks covering a disk of radius 4](https://cdn.statically.io/img/i.sstatic.net/t8k8d.png)
With center coordinates:
0, 1.80750, -2.54225
1, -3.54559, 0.79284
2, 3.21606, -0.47844
3, -3.18095, -0.67348
4, 1.45572, 3.32489
5, 3.49068, 1.00734
6, 3.03556, -1.96799
7, 0.05315, -1.74332
8, 0.71515, 1.68904
9, -0.10081, 3.30695
10, -1.41603, -1.09113
11, -2.60096, 2.01322
12, -1.64927, -2.64764
13, -2.91003, -2.14927
14, -0.81671, 1.64233
15, 2.47350, 2.16792
16, -0.67478, -3.39436
17, 1.73292, 0.53206
18, -1.76213, 0.42552
19, 0.88039, -3.34645
20, -1.65555, 3.23003
21, -0.00075, 0.02442
22, 1.47986, -1.00285
See my code here. Some notes: the algorithms are not 100% robust, so it sometimes crashes, and due to the nature of the search algorithms it will not find the global minimum 100% of the time. However, it will find the optimum solution if you run it a couple times. As for the output, r
is the minimum sprinkler radius; R
is the maximum radius of the lawn, assuming the sprinklers have unit radius (in order to compare the results with the diagrams on Erich Friedman's website).
Using the solution I found we can also answer the bonus:
The minimum sprinkler radius in the above configuration is 0.999815, which is less than 1 so the answer to the bonus is also yes.