22
$\begingroup$

You have a perfectly circular lawn with radius exactly 4 metres. Lately the grass has been turning yellow and quite rough, so you go to Stiv's Diabolical Instruments and describe your problem.

"All we've got for you is 23 sprinklers, each one irrigating a perfectly circular area exactly 1 metre in radius," the shopkeeper replied.

Clearly one or two sprinklers won't do, since you have an eagle's eye for detail and hate any dry patch of grass down to the last little spot on a single blade; there is also no horizontal movement of water once it hits the ground. So you buy all 23 sprinklers available, but will you be able to keep your entire lawn irrigated with them?

Bonus: Would uniformly less powerful sprinklers (irrigating a circle of smaller radius) suffice, and if so how much less?

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ Just to make a hash of this: you can buy sprinklers that are programmable (mechanical stops) to sweep out a noncircular region by limiting the spray distance over specified angle ranges. In theory, then, you could take one of the solutions and adjust the sprays so that the entire lawn gets uniform amounts of water :-) $\endgroup$
    – Carl Witthoft
    Jun 25, 2021 at 12:37

7 Answers 7

Reset to default
24
$\begingroup$

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.

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

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ In the configuration displayed on Erich's page, the next digits are 739, so there is about $\frac34$ mm tolerance. This, all the other results and the code I used to find them may be viewed in the folder starting from here. $\endgroup$
    – Parcly Taxel
    Jun 23, 2021 at 2:14
  • $\begingroup$ Also note that Erich's page indicates that this is apparently optimal, since the ratio for 22 circles is less than 4, though just barely. (Not sure if that's proven or just nobody's found a 22-circle solution yet?) $\endgroup$
    – Darrel Hoffman
    Jun 23, 2021 at 13:28
  • $\begingroup$ Maybe you can apply this method to math.stackexchange.com/questions/556882/… $\endgroup$
    – RobPratt
    Nov 10, 2021 at 23:16
8
$\begingroup$

Here's an approximate solution, obtained by randomly generating 10,000 points and solving the corresponding set cover problem. There are still some gaps, but maybe it can be tweaked to cover them. It is different than the others posted so far because it has a circle that is concentric with the outer circle.

enter image description here

Improve this answer
$\endgroup$
1
  • $\begingroup$ Excellent work... your solution is very, very close to the actual solution. It seems as though some study of the algorithm behind the given solution would be interesting for you! $\endgroup$
    – ErikE
    Jun 24, 2021 at 19:29
7
$\begingroup$

For any circle touching the perimeter, the longest possible chord between the two contact points is the diameter of the circle - 2 meters. This is shorter than the side length of an inscribed dodecagon but not that of an inscribed tredecagon, so any valid sprinkler setup must have at least 13 sprinklers on the perimeter.

Unfortunately, I can't cover the interior in fewer than twelve (but you're free to try here!), much like Kabir's answer which unfortunately has gaps at time of writing.
enter image description here

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ when you say "longer", you probably mean "shorter" :-) $\endgroup$
    – Bass
    Jun 22, 2021 at 15:44
  • $\begingroup$ You are assuming that the outer ring must be circularly symmetrical, but there's no rule that says their centers all need to be the same distance from the center of the big circle. Once you relax that constraint, things may work better for you? $\endgroup$
    – Floris
    Jun 23, 2021 at 16:54
  • 1
    $\begingroup$ @Floris Circular symmetry was the starting point I used to do some initial guesswork and cut down on the number of free variables. The argument for at least 13 in the perimeter doesn't depend on it at all. $\endgroup$
    – AxiomaticSystem
    Jun 24, 2021 at 1:33
  • $\begingroup$ I understand that - but if twelve of the thirteen are a bit closer to the center and the thirteenth is “making up the gap” (or perhaps there are two gap fillers) the fact that the others are closer to the center may help fill the remaining space with one fewer sprinkler… $\endgroup$
    – Floris
    Jun 24, 2021 at 11:08
  • $\begingroup$ Comparing your answer to the accepted answer, it seems that your intuition about using symmetry to simplify the problem was good, the only difference being that the accepted answer's symmetry began in the center. While it's surprising that the solution uses 7 circles around the center one instead of 6 (which perfectly tiles a plane), it makes sense when you realize that increasing the number of 2nd-ring circles makes the second ring take up more space, so the outer ring's circles (being placed sequentially in a jagged formation) finally touch without leaving any gaps. $\endgroup$
    – ErikE
    Jun 24, 2021 at 19:28
4
$\begingroup$

Partial Answer

Let me start with a baseline - 27 sprinklers, and try to build from there:

enter image description here

Desmos Link

With some manual tweaks, I am able to bring it down to 25 sprinklers.

enter image description here

Desmos Link

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ odd question here, I hope is not outside the spirit of the puzzle, but won't the overlapped areas be over-watered? I know the puzzle doesn't mention a criteria for how much water one part should receive over another, nor the terrain or evidence that the circles at a lower elevation will automatically receive run-off, etc. etc. but I thought I'd point it out anyway that you probably need far-fewer sprinklers :) $\endgroup$
    – Dan Chase
    Jun 23, 2021 at 15:33
  • 1
    $\begingroup$ The question clearly states that once water hits the ground it does not move horizontally. In other words the water stays put or vanishes. It's not meant to be realistic, so no need to worry about overwatering. $\endgroup$
    – Squirtle
    Jun 25, 2021 at 15:19
3
$\begingroup$

I believe you cannot go further down then

22

sprinklers.

I can't show a solution that it's possible to do it with this number yet. But here is my reasoning why I believe it's not possible to go any lower.

Approach:

Instead of using circles, I was looking at the puzzle in terms of hexagons. The reasoning behind this is that you will always have overlap between circles, and you want to minimize the overlap. The tightest packing is achieved for circles where the center points form regular hexagons.

Necessary formulas:

Area of a hexagon with a side length s: $A=3/2 \; \sqrt{3} s^2$
Area of a hexagon with apothem a: $A = 3/2 \; \sqrt{3} 4/3 a^2 = 2 \sqrt{3} a^2 $

The area will be tiled by small hexagons which are circumscribed by a circle of radius 1m. The area of those hexagons is $A_s = 1/2 \; \sqrt{3}\; (1m)^2 = \sqrt{3}/2 \; m^2$.

Then:

The tiling formed by the hexagons will again be a hexagon. To fill the circle, we need this to be the hexagon of which the inscribed circle equals our circular lawn. This is the hexagon with the area $A_l = 2 \sqrt{3} (4m)^2 = 32 \sqrt{3} m^2$

Therefore, the fewest number of sprinklers is:

$\frac{32 \sqrt{3}}{3/2 \sqrt{3}} = \frac{64}{3} \approx 21.33$ The smallest whole number larger than this is 22.

Improve this answer
$\endgroup$
5
  • 10
    $\begingroup$ It seems a bit weird how you make a very decent case for a lower bound, but start with "it's possible to reach this particular lower bound" without any reasoning as to why this might be the case. $\endgroup$
    – Bass
    Jun 22, 2021 at 15:08
  • $\begingroup$ I agree. I edited the text. $\endgroup$
    – nishuba
    Jun 23, 2021 at 9:46
  • $\begingroup$ I like how you prevented the overlapped areas from being over-watered. If we went just a little further, we could solve for the typical water flow, and the dispersion within the soil (assuming a level terrain) to reduce it even more and still ensure all of the grass is watered. Granted I know the puzzle mentioned no horizontal movement. $\endgroup$
    – Dan Chase
    Jun 23, 2021 at 15:37
  • $\begingroup$ I think this is the cleanest answer; it uses simpler geometry than the accepted answer. It is interesting how you used hexagons to approximate the area +1 for the idea. $\endgroup$
    – dan
    Jun 24, 2021 at 1:50
  • $\begingroup$ "To fill the circle, we need this to be the hexagon of which the inscribed circle equals our circular lawn. " is false, apply the same reasoning with r=1 instead of 4. $\endgroup$
    – Pete Kirkham
    Jun 24, 2021 at 10:23
3
$\begingroup$

I'm going to say

no

because you said:

hate any dry patch of grass down to the last little spot on a single blade; there is also no horizontal movement of water once it hits the ground

and coupled with

what I consider a sprinkler, being a device larger than a blade of grass fed by a hose larger than a blade of grass, means that somewhere in your sprinkler setup is at least one blade of grass that is in the rain shadow of either a sprinkler or a hose, and given that your water doesn't run sideways, that blade won't be watered.

Of course, you could take the unconventional approach of

using your considerable engineering prowess to suspend your entire sprinkler network upside down over the lawn, in which case see other answers, or read on if you want to save money..

Which would mean, if you have an appetite for such wizardry, I can comfortably assert

yes you can water the entire lawn, with one sprinkler: mount the sprinkler on a cart attached by a Nmm wide hose at least 4500mm* long, to a central cylinder of radius 159-N/2 mm. Ensure the cart has a system to drive the wheels based on the flow of the water. Turning the water on will see the cart drive round the central cylinder in a spiral that becomes 1m closer to the center each circuit. At the point the cart reaches the center the wheels are halted and the flow stops, saving precious water, and given that the central pole radius is less than the sprinkle radius the center of the lawn is already well watered in advance of the cart reaching the stop point.

Bonus: considerably less powerful I dare say - the limit rather depends on relatively intangible physical properties of the entire affair, if you're prepared to engineer a spiral with a LOT of turns and wait a long time for your tiny cart to execute them, a puny stream of water carried over a hairlike hose

*it can be marginally smaller but all values are approximate given the spirit of the answer

Improve this answer
$\endgroup$
2
  • $\begingroup$ Underground pipes? Allowing there to be no grass where the sprinkler pipe protrudes from the ground wouldn't change the problem as by problem definition the sprinkler evenly waters all grass in a radius around it. As long as the sprinkler pipe is a tiny fraction of the sprinkler coverage. $\endgroup$
    – ErikE
    Jun 24, 2021 at 19:32
  • $\begingroup$ Thought about that, and realized I'm so precious about the lawn that I wouldn't dig it up to put them in ;) $\endgroup$
    – Caius Jard
    Jun 24, 2021 at 21:07
1
$\begingroup$

I was pointed to this very interesting post by RobPratt, who helped me with a related problem.

After implementing a similar solution to his, using a random scatter of points and looking for a solution by set cover binary linear programming (which works quite well indeed), I thought I'd give a try to a more 'geometry-based' solution.

[BTW, I am using hidden sections because I take it this is the idea in this particular SE site, but please feel free to advise me otherwise.]

In essence we want to find the location of the sprinklers such that the union of the areas spanned by their circles of radius 1, intersected with the big lawn circle of radius 4, is as close as possible to the full circle of radius 4.

However, calculating that exactly from the positions of the sprinklers is prohibitively complex (at least for me). There might be a way, as I hinted to in the linked post, but probably very hard to code.

Here's the intuition:

As the search for a solution is numerical and not exact anyway, just as well to calculate the area of the union numerically, too. And this can be done, in R, by function quad2d from package pracma, which does double integrals. Integrating the logical 'OR' of all the conditions $(x-x_i)^2+(y-y_i)^2 \le r^2$ intersected with the domain of the big lawn circle of radius R is equivalent to measuring the area of lawn 'covered' by the sprinklers. At that point it is sufficient to find the positions such that this area is as close as possible to $\pi \cdot R^2$.

To do this, I started from 23 circularly placed sprinklers, with some added small error:

enter image description here

After 1947 iterations of the solver, this is what came up:

enter image description here

Although it says 100%, the coverage is not exactly 100%, as also shown by the picture; this is due to the small error from quad2d.

Overall I think this is an interesting approach.
Perhaps if one could introduce some constraints, it would perform even better.

Here are the coordinates:

structure(c(-0.0192124302696741, 1.69210228374458, 1.12207220007407, -0.458898282169877, -1.68459206671881, -1.70572906611192, -0.318261987390775, 1.21913074028621, 3.47057522438769, 2.88566291913126, 2.35704067670984, 0.876234839830577, -0.347322720559182, -1.7670113219972, -2.72089899862811, -3.27982525875973, -3.37521750345377, -2.78059651594498, -1.73354422501726, -0.649925560795611, 0.881358800028353, 2.4205497798494, 3.05182438644101, 0.0849395846722759, 0.0381557538473754, 1.57068493479492, 1.79759347364571, 0.936034350433627, -0.572036690983195, -1.64730572005061, -1.37720408225443, 0.291592074635348, 1.50768382825572, 3.03140145000842, 3.18999836840338, 3.65852384689267, 2.82264267884141, 2.01624557285127, 0.659227568775992, -0.590041349219451, -2.07085783149175, -2.5464904659875, -3.45043043487102, -3.10716258638463, -2.7191961236181, -1.23602359917925), .Dim = c(23L, 2L), .Dimnames = list(NULL, c("x", "y")))

Improve this answer
$\endgroup$
3
  • $\begingroup$ I calculate the missing area to be about 0.081423 (0.16%), so pretty good! Doing a 2D integral means that you have to sample very finely in order to find the gaps. Adaptive sampling won't help if you are using a boolean function, since the gradient will be zero everywhere. You might get better results by using polygonal approximations of the circles and doing set operations on the polygons. $\endgroup$
    – 2012rcampion
    Jul 10, 2021 at 21:52
  • $\begingroup$ A followup thought: since the minimum sprinkler radius (call it r) is < 1, you could pick a polygon that fits entirely within a circle of radius 1 but completely encloses a circle of radius r; using the upper bound on r I found, a regular polygon with at least 164 sides would work. Then any solution you find is guaranteed to be a solution for circles of radius 1, and you are guaranteed to be able to find a solution since one exists for circles of radius r. $\endgroup$
    – 2012rcampion
    Jul 10, 2021 at 23:38
  • $\begingroup$ Thanks @2012rcampion , interesting suggestions. When I found that integral2 was not very precise, I tested other quadrature tools, and chose quad2d as a compromise between speed and precision. adaptIntegrate from the cubature package was by far the most precise, even with these logical functions. Not sure how it does it, but it does. But yes, slow. Concerning your suggestions to use polygons, yes, that would simplify a bit the calculation, but then maybe just as well to do the maths with the actual circles. E.g. math.stackexchange.com/questions/96839/… $\endgroup$
    – user6376297
    Jul 11, 2021 at 19:06

Your Answer

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

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