How Greedily Can You Mow the Lawn?

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

Now you bore cylinders of diameter $1$ (radius $\tfrac12$) greedily through a unit sphere, each cylinder removing the most remaining material. How many passes to pulverise the whole sphere?

Solution

The same greedy rule in three dimensions clears the ball in about $$\boxed{9\text{ passes}}.$$ (The exact count is paywalled and mildly grid-sensitive; this is my own simulation: the unmown fraction falls $0.65,0.43,0.23,0.15,0.08,0.03,0.013,0.003,0.001$ over nine passes, the last specks being voxel-grid artifacts.)

The computation

Voxelise the ball. Each pass samples many cylinder axes (random directions); for each, project the remaining voxels onto the plane perpendicular to the axis and find the radius-$\tfrac12$ disk covering the most. Bore the best cylinder and repeat, tracking the unmown fraction.

rng = np.random.default_rng(0); n = 40
xs = (np.arange(n) + 0.5) / n * 2 - 1
X, Y, Z = np.meshgrid(xs, xs, xs, indexing='ij')
m = (X*X + Y*Y + Z*Z) <= 1
V = np.column_stack([X[m], Y[m], Z[m]]); cov = np.zeros(len(V), bool)
def basis(nrm):                          # two axes spanning the plane perp to nrm
    a = np.array([1.0, 0, 0]) if abs(nrm[0]) < 0.9 else np.array([0, 1.0, 0])
    e1 = np.cross(nrm, a); e1 /= np.linalg.norm(e1)
    return e1, np.cross(nrm, e1)
frac = []
while not cov.all():
    idx = np.where(~cov)[0]; rem = V[idx]; best = -1; sel_best = None
    for _ in range(60):
        nrm = rng.normal(size=3); nrm /= np.linalg.norm(nrm)
        e1, e2 = basis(nrm); P = np.column_stack([rem @ e1, rem @ e2])
        for c in P[rng.integers(0, len(P), 50)]:    # candidate disk centres
            sel = (P[:, 0] - c[0])**2 + (P[:, 1] - c[1])**2 <= 0.25
            if sel.sum() > best: best = int(sel.sum()); sel_best = idx[sel]
    cov[sel_best] = True; frac.append(round((~cov).mean(), 3))
print(frac)            # [0.649, 0.427, 0.227, 0.15, 0.078, 0.031, 0.013, 0.003, 0.001, ...]