What's the most efficient way to mow a lawn?

Solution 1:

The problem is nicer with closed-disc lawnmowers, so let me define $D_x(S) = \{y \in \mathbb{R}^2 | d(y,S) \leq x\}$, and define $\mu_{\epsilon}$ as: $$ \mu_{\epsilon} = \inf\left\{L(\gamma) | D_{1}(S) \subseteq D_1(\gamma) \subseteq \overline{D_{1+\epsilon}(S)}\right\} $$ If $\epsilon>0$, I think your existence proof works the same for $\mu_{\epsilon}$. Below I prove the infimum can be achieved when using these closed-disc mowers. I also give a possible counter-example for open-disc mowers.

Fix $\epsilon\geq 0$ and assume $\mu_{\epsilon}$ exists and is positive. Let $\gamma_n(t)$ be an infinite sequence of rectifiable paths with the property $D_1(S) \subseteq D_1(\gamma_n) \subseteq \overline{D_{1+\epsilon}(S)}$, and such that $\lim_{n\rightarrow\infty} L(\gamma_n) = \mu_{\epsilon}$. We can assume each path $\gamma_n$ is defined to traverse its course at constant speed of $L(\gamma_n)$ distance/time (see below comment of Mario for further justification of this assumption). So for $0 \leq t \leq 1$, $\gamma_n(t)$ is the point on the path that is a fraction $t$ of the total distance of the path. For all $n$ and all $t, v \in [0,1]$ we have:

$$ ||\gamma_n(t)-\gamma_n(v)|| \leq |t-v|L(\gamma_n) $$

(see Note 1 for more detail on this). Furthermore, the paths $\gamma_n(t)$ are all contained in a bounded region of $\mathbb{R}^2$. Let $\{q_1, q_2, \ldots\}$ be a listing of rationals in $[0,1]$. By the diagonalization lemma in the Appendix of Probability and Measure by Billingsley, there is a subsequence $n_k$ such that $\gamma_{n_k}(q_i)$ converges for all $i$ as $k\rightarrow\infty$ (this is essentially a countably-infinite extension of the Bolzano-Wierstrass theorem). Let $\gamma(q_i)$ be the limiting value, defined for each rational $q_i$.

The function $\gamma(q_i)$ is continuous over the rationals because for any two rationals $q_i, q_j$ in the interval $[0,1]$ we have:

\begin{align}||\gamma(q_i)-\gamma(q_j)||&\leq ||\gamma(q_i)-\gamma_{n_k}(q_i)||+ ||\gamma_{n_k}(q_i)-\gamma_{n_k}(q_j)||+ ||\gamma_{n_k}(q_j)-\gamma(q_j)||\\ &\leq ||\gamma(q_i)-\gamma_{n_k}(q_i)|| + |q_i-q_j|L(\gamma_{n_k}) +||\gamma_{n_k}(q_j)-\gamma(q_j)|| \end{align}

Taking a limit as $k\rightarrow \infty$ implies that $||\gamma(q_i)-\gamma(q_j)|| \leq |q_i-q_j|\mu_{\epsilon}$.

Thus, we can extend $\gamma(q_i)$ to a continuous function $\gamma(t)$ over the reals $t \in [0,1]$. With a little more work, we can show the same subsequence of functions $\gamma_{n_k}(t)$ indeed converge (pointwise for all $t \in [0,1]$) to $\gamma(t)$, and $\gamma(t)$ itself must satisfy for all $t, v \in [0,1]$:

$$ ||\gamma(t)-\gamma(v)|| \leq |t-v|\mu_{\epsilon} $$

It remains to show two properties: (i) $D_1(S) \subseteq D_1(\gamma)\subseteq \overline{D_{1+\epsilon}(S)}$, and (ii) $\gamma(t)$ is rectifiable with length that achieves the infimum $\mu_{\epsilon}$. The first property holds by Notes 2 and 3 below. The second property holds because: For any finite partition of times $0 \leq t_0 < t_1 < \cdots < t_N \leq 1$ we have $\sum_{i=1}^N||\gamma(t_i)-\gamma(t_{i-1})|| \leq \mu_{\epsilon}\sum_{i=1}^N|t_i-t_{i-1}| \leq \mu_{\epsilon}$ and so $\gamma$ is rectifiable with $L(\gamma) \leq \mu_{\epsilon}$. But of course the first property then ensures $L(\gamma)\geq \mu_{\epsilon}$. And so $\gamma$ achieves the infimum $\mu_{\epsilon}$.

Note 1: Proving $||\gamma_n(t)-\gamma_n(v)|| \leq |t-v|L(\gamma_n)$. Suppose that $v>t$, and the $\gamma_n(t)$ path has constant speed. Then $\gamma_n(t)$ is the point on the path that is a fraction $t$ of the total distance, and $\gamma_n(v)$ is the point further along the path that is a fraction $v$ of the total distance. So there is a path of length $(v-t)L(\gamma_n)$ between points $\gamma_n(t)$ and $\gamma_n(v)$, and this length must be greater than or equal to the length of the straight line between these points.

Note 2: Proof that $D_1(\gamma) \subseteq \overline{D_{1+\epsilon}(S)}$. Let $x \in D_1(\gamma)$. Then there is a point $\gamma(t)$ (for some $t \in[0,1]$) such that $||\gamma(t)-x|| \leq 1$. The sequence of points $\gamma_{n_k}(t)$ converges to $\gamma(t)$ as $k\rightarrow\infty$. However, $D_1(\gamma_{n_k})\subseteq\overline{D_{1+\epsilon}(S)}$ for all $k$, and so anything within radius 1 of $\gamma_{n_k}(t)$ is in $\overline{D_{1+\epsilon}(S)}$. It follows that $x$ is arbitrarily close to points in the closed set $\overline{D_{1+\epsilon}(S)}$, so it must also be in this set.

Note 3: Proof that $D_1(S) \subseteq D_1(\gamma)$. Let $x \in D_1(S)$. Then $x \in D_1(\gamma_{n_k})$ for every index $k$. So there are times $t_k \in [0,1]$ such that for all $k$ we have $||x - \gamma_{n_k}(t_k)|| \leq 1$. Choose a particular subsequence of indices $k(m)$ over which $t_{k(m)}$ converges (by Bolzano-Wierstrass) to a point $t \in[0,1]$. So for any $m$:

\begin{align} ||x - \gamma(t)|| &\leq ||x - \gamma_{n_{k(m)}}(t_{k(m)}) ||+ ||\gamma_{n_{k(m)}}(t_{k(m)}) - \gamma_{n_{k(m)}}(t)|| + ||\gamma_{n_{k(m)}}(t) - \gamma(t)|| \\ &\leq 1 + |t_{k(m)}-t|L(\gamma_{n_{k(m)}}) + ||\gamma_{n_{k(m)}}(t) - \gamma(t)|| \end{align}

Taking a limit as $m\rightarrow\infty$ gives $||x - \gamma(t)|| \leq 1$, and so $x \in D_1(\gamma)$.

Partial answer to question 2: The value $\lambda_0$ will exist whenever the set $S$ is convex with a rectifiable boundary, since scaled versions of convex sets “fit inside” each other like measuring cups. So we can take a path consisting of the boundary together with suitable reduced-scale versions of those (connected by short segments).

Possible counter-example showing infimum is not achievable when we use open-disc lawnmowers, i.e., using $E_1(\cdot)$: Let $S$ be the closed disc of radius 1 about the origin. Then $E_1(S)$ is the open disc of radius 2 about the origin. I believe $\lambda_0=2\pi$ (intuitive, but hard to prove rigorously), and this can be achieved arbitrarily closely by the path that consists of the unit circle about the origin, plus a small line segment of size $\epsilon$ starting from any point on the circle and moving inward to the origin (this line segment allows coverage of the origin itself). The limit $\gamma$ of such paths (and I think the only possible candidate path that could achieve the infimum) is the unit circle itself. But the origin is in $E_1(S)$ but not in $E_1(\gamma)$. So $E_1(S)$ is not a subset of $E_1(\gamma)$, and the infimum is not achieved. However, it would be achieved with a closed-disc lawnmower.

A simpler counter-example in the same spirit might be when $S$ is a closed square of side length 2.

Okay Mario's completion of the "lemon" example makes it obvious that $2\pi$ is the min. Actually it is easy to show that any convex shape $S$ must include the boundary of $S$ in any path that covers $E_1(S)$ and for the $\epsilon=0$ case. But I wonder if $\lambda_{\epsilon}=\lambda_{0}$ in all those cases? (seems intuitively true if $S$ is the unit disc, but somehow not clear how to rigorously prove).