What's the most efficient way to mow a lawn? For $S\subseteq\Bbb R^2$ and $x\in\Bbb R$, define $E_x(S)=\{y\in\Bbb R^2:d(y,S)<x\}$. ($E_x(S)$ represents the expansion of $S$ by $x$.) Given a path $\gamma:[0,1]\to\Bbb R^2$, denote its length as $L(\gamma)=\int_\gamma|dx|\in[0,\infty]$ (for non-rectifiable paths, $L(\gamma)=\infty$).
Assume now that $S$ is connected and bounded, and let $$\lambda_\epsilon=\inf\Big\{L(\gamma):E_1(S)\subseteq \overline{E_1(\gamma)}\subseteq \overline{E_{1+\epsilon}(S)}\Big\}.$$ This is our best path for a lawnmower with cutting radius $1$ to mow the lawn $E_1(S)$ with an overspill of at most $\epsilon$. The questions are:


*

*Does $\lambda_\epsilon$ exist for every $\epsilon>0$? (I think I can prove this.)

*Does $\lambda_0$ exist? (Not sure about this.)

*Is $\lambda_\epsilon$ a minimum in either case, i.e. is there an acceptable path whose length is $\lambda_\epsilon$?

*Are there any algorithms for finding paths whose lengths are within $\delta$ of $\lambda_\epsilon$? (I'm not sure how to make this precise.)


This is what I'm thinking about every time I mow my lawn, and I bet I'm not alone.
Edit: A proof for the first question: Let $\epsilon>0$. Since $S$ is bounded, so is $E_{\epsilon/2}(S)$, and it is also totally bounded. Therefore, there is a finite cover $(B(\epsilon/2,x_k))_{k=1}^n$ of $E_{\epsilon/2}(S)$ by balls of radius $\epsilon/2$. Since $E_{\epsilon/2}(S)$ is a union of open connected sets, which are connected together by $S$, it is also connected. Now any open connected set is path-connected by polygonal paths, so there is a polygonal path from $x_i$ to $x_{i+1}$ for every $1\le i<n$. The concatenation of these is a polygonal path $\gamma$ which passes through each $x_i$ and remains in $\bigcup_{k=1}^nB(\epsilon/2,x_k)\subseteq E_{\epsilon}(S)$. Then $E_1(\gamma)\subseteq E_{1+\epsilon}(S)$, and any point in $E_1(S)$ is within $1-\epsilon/2$ of a point in $E_{\epsilon/2}(S)$, which is within $\epsilon/2$ of some $x_k\in\gamma$, so $E_1(S)\subseteq E_1(\gamma)$. Finally, since $\gamma$ is polygonal, it is rectifiable, so $\lambda_\epsilon\le L(\gamma)$ and $\lambda_\epsilon$ exists.
If you consider the linear paths from $x_i$ to $x_j$ when the balls $B(\epsilon/2,x_i)$ and $B(\epsilon/2,x_j)$ are not disjoint, you get a graph on $n$ vertices, and the problem of finding the shortest path on this graph that visits all the vertices is exactly the Traveling Salesman Problem. Thus this does not bode well for efficient algorithms to solve this problem.
 A: 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).
