Library · The Fiddler: Solutions · Chapter 69
How Greedily Can You Mow the Lawn?
A circular lawn has radius . You mow it in straight strips unit wide. Rather than plan ahead, you mow greedily: each pass is oriented and positioned to cut as much still-unmown grass as possible. How many passes does it take to mow the entire lawn?
The Fiddler, Zach Wissner-Gross, June 20, 2025(original post)
Solution
A clever mower needs only two parallel strips (they tile the band , which contains the disk). Greed does worse: the first pass takes the widest cut, the central strip, leaving two caps; no single later strip can clear both caps at once, so the cuts fan out at different angles and leftovers linger near the rim. Simulating the greedy rule on a fine grid, full coverage takes
The computation
Grid the disk, and at each pass try every strip orientation: for a given angle, project the uncovered points onto the perpendicular axis and slide a width- window to the position covering the most. Take the best strip over all angles, mark it mown, repeat.
import numpy as np
h = 0.005; xs = np.arange(-1, 1 + h, h); X, Y = np.meshgrid(xs, xs)
m = X*X + Y*Y <= 1; px, py = X[m], Y[m]; cov = np.zeros(len(px), bool)
ang = np.linspace(0, np.pi, 120, endpoint=False); passes = 0
while not cov.all():
best = (-1, None)
for th in ang:
pv = np.sort((px*np.cos(th) + py*np.sin(th))[~cov])
cnt = np.searchsorted(pv, pv + 1, 'right') - np.arange(len(pv))
i = cnt.argmax()
if cnt[i] > best[0]: best = (cnt[i], (np.cos(th), np.sin(th), pv[i]))
nx, ny, c = best[1]; p = px*nx + py*ny
cov |= (p >= c - 1e-9) & (p <= c + 1 + 1e-9); passes += 1
print(passes) # 5
Extra Credit
Instead of mowing a lawn, you bore cylinders of diameter (radius ) through a solid unit ball. Again you greedily orient each borehole to carve out as much of the remaining ball as possible. With this greedy approach, how many passes does it take to pulverise the entire ball?
Solution
The first pass is exact. A borehole through the centre removes everything within of a diameter, and no other position removes more, by the same argument as on the lawn. Slicing the ball into thin discs perpendicular to the axis, the part left over is a “napkin ring” with outer radius and inner radius , whose volume is . So the first pass removes a fraction of the ball.
After that the problem stops being tidy. Each later pass must find, among all directions and offsets, the cylinder that meets the most of an irregular leftover shape, and there is no clean description of those shapes. The number of passes can only be found numerically, and the numbers are delicate in a way the lawn was not. Late in the process the leftovers are tiny slivers wedged between earlier boreholes; the second pass already has several near-equal choices, and a slightly different early choice changes which slivers remain later.
Careful simulations (described below) clear the ball in passes in one run and in two others, with the final passes removing pieces of order to of the ball. An earlier version of this chapter reported passes from a coarse grid of cells, treating the last specks as grid artefacts; they are not, since after nine passes about of the ball genuinely remains. So the honest answer is with the exact count not certified here, because it depends on resolving near-ties in the greedy choice more finely than any simulation can. (The source’s value is paywalled; this is my own.)
The computation
The ball is represented by random points rather than a grid, so no cell size limits what can be seen.
Scatter random points in the ball. For each pass, try random directions and offsets, keep the eight that capture the most remaining points, and polish each by a local search on a smoothed count of captured points.
Bore the best cylinder and delete the points it captures.
When fewer than points remain, draw fresh random points (up to million) and keep only the ones no borehole has reached, so that even tiny leftovers are measured accurately.
Stop when million fresh points include no uncovered one.
import math
import numpy as np
from scipy.optimize import minimize
rng3 = np.random.default_rng(3)
R = 0.5 # radius of each borehole
def ball(n):
"""n points uniform in the unit ball."""
p = rng3.normal(size=(n, 3)); p /= np.linalg.norm(p, axis=1, keepdims=True)
return p*rng3.random(n)[:, None]**(1/3)
def frame(th, ph):
u = np.array([math.sin(th)*math.cos(ph), math.sin(th)*math.sin(ph), math.cos(th)])
a = np.array([1., 0, 0]) if abs(u[0]) < 0.9 else np.array([0, 1., 0])
e1 = np.cross(u, a); e1 /= np.linalg.norm(e1)
return u, e1, np.cross(u, e1)
def dist2(P, x):
"""Squared distance of points P from the axis of borehole x."""
th, ph, s, t = x; u, e1, e2 = frame(th, ph)
q = P - np.outer(P @ u, u) - (s*e1 + t*e2)
return (q*q).sum(axis=1)
def best_bore(P):
"""Greedy step: the borehole removing the most remaining points."""
sub = P if len(P) <= 15000 else P[rng3.choice(len(P), 15000, replace=False)]
cands = []
for _ in range(6000): # random directions and offsets
u = rng3.normal(size=3); u /= np.linalg.norm(u)
th, ph = math.acos(u[2]), math.atan2(u[1], u[0])
c = sub[rng3.integers(len(sub))]; _, e1, e2 = frame(th, ph)
x = (th, ph, c @ e1 + rng3.normal()*0.25, c @ e2 + rng3.normal()*0.25)
cands.append(((dist2(sub, x) <= R*R).sum(), x))
cands.sort(key=lambda z: -z[0])
out = []
for _, x in cands[:8]: # polish the best few
for w in (0.03, 0.01, 0.003): # on a smoothed count
soft = lambda y: -np.sum(1/(1 + np.exp(np.clip(
(np.sqrt(dist2(P, y)) - R)/w, -50, 50))))
x = minimize(soft, x, method="Nelder-Mead",
options={"xatol": 1e-6, "fatol": 1e-4, "maxiter": 3000}).x
out.append(((dist2(P, x) <= R*R).sum(), x))
return max(out, key=lambda z: z[0])[1]
N0 = 300_000; P = ball(N0); weight = 1/N0 # each point stands for this much ball
bores = []
def uncovered(Q):
c = np.zeros(len(Q), bool)
for x in bores: c |= dist2(Q, x) <= R*R
return ~c
while True:
if len(P) < 20000: # top up with fresh points
fresh, drawn = [], 0
while sum(map(len, fresh)) < 20000 and drawn < 200_000_000:
Q = ball(2_000_000); drawn += len(Q); fresh.append(Q[uncovered(Q)])
P = np.concatenate(fresh); weight = 1/drawn
if len(P) == 0:
print("no uncovered point among", drawn, "fresh samples"); break
x = best_bore(P); hit = dist2(P, x) <= R*R; bores.append(x)
print("pass %2d removes %.2e of the ball, leaving %.2e"
% (len(bores), hit.sum()*weight, (len(P) - hit.sum())*weight))
P = P[~hit]
It prints (in about four minutes)
pass 1 removes 3.53e-01 of the ball, leaving 6.47e-01
pass 2 removes 2.25e-01 of the ball, leaving 4.22e-01
pass 3 removes 2.11e-01 of the ball, leaving 2.11e-01
pass 4 removes 6.95e-02 of the ball, leaving 1.42e-01
pass 5 removes 6.12e-02 of the ball, leaving 8.06e-02
pass 6 removes 5.29e-02 of the ball, leaving 2.77e-02
pass 7 removes 1.75e-02 of the ball, leaving 1.04e-02
pass 8 removes 6.57e-03 of the ball, leaving 3.82e-03
pass 9 removes 3.80e-03 of the ball, leaving 3.60e-05
pass 10 removes 2.99e-05 of the ball, leaving 4.87e-06
pass 11 removes 5.04e-06 of the ball, leaving 0.00e+00
no uncovered point among 200000000 fresh samples
The first pass matches up to sampling noise. With two other random seeds the same program needs passes; the difference comes from near-ties in the second and later passes, which is why the count above is given as a range.