Library · The Fiddler: Solutions · Chapter 69

How Greedily Can You Mow the Lawn?

Revised Report an error

A circular lawn has radius 11. You mow it in straight strips 11 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)

Two parallel strips would suffice if planned, but the greedy rule takes five.
Two parallel strips would suffice if planned, but the greedy rule takes five.

Solution

A clever mower needs only two parallel strips (they tile the band ∣y∣≤1|y|\le1, 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 5 passes.\boxed{5\text{ passes}}.

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-11 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 11 (radius 12\tfrac12) 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 12\tfrac12 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 11 and inner radius 12\tfrac12, whose volume is 43π(1−14)3/2\tfrac43\pi\big(1 - \tfrac14\big)^{3/2}. So the first pass removes a fraction 1−(34)3/2  ≈  0.35051 - \Big(\tfrac34\Big)^{3/2} \;\approx\; 0.3505 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 1111 passes in one run and 1212 in two others, with the final passes removing pieces of order 10−510^{-5} to 10−610^{-6} of the ball. An earlier version of this chapter reported 99 passes from a coarse grid of 40340^3 cells, treating the last specks as grid artefacts; they are not, since after nine passes about 4×10−54 \times 10^{-5} of the ball genuinely remains. So the honest answer is about 11 or 12 passes,\boxed{\text{about } 11 \text{ or } 12 \text{ passes}}, 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.

  1. Scatter 300,000300{,}000 random points in the ball. For each pass, try 60006000 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.

  2. Bore the best cylinder and delete the points it captures.

  3. When fewer than 20,00020{,}000 points remain, draw fresh random points (up to 200200 million) and keep only the ones no borehole has reached, so that even tiny leftovers are measured accurately.

  4. Stop when 200200 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 0.35050.3505 up to sampling noise. With two other random seeds the same program needs 1212 passes; the difference comes from near-ties in the second and later passes, which is why the count above is given as a range.

Report an error on this page

Reports are stored by Netlify. See the privacy note.