32
$\begingroup$

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.

$\endgroup$
  • 13
    $\begingroup$ I usually think about someone doing it for me... $\endgroup$ – Eleven-Eleven May 7 '14 at 23:03
  • 6
    $\begingroup$ @Eleven Actually, I don't own my own house yet, but questions like these are why I'm getting a condo instead. $\endgroup$ – Mario Carneiro May 7 '14 at 23:05
  • 1
    $\begingroup$ @JackM In this model, the "lawn" is $E_1(S)$, not $S$. In fact the set $S$ is never used directly - it could be reformulated in terms of a set $A$ which is $E_1$ of some set. The reason for this circuity is because my lawnmower is circular, and I want to avoid lawns that are too "pointy" to be mowed without a significant amount of overspill. (For example, there are no paths that mow the unit square without at least $1-1/\sqrt2$ of overspill.) $\endgroup$ – Mario Carneiro May 8 '14 at 0:26
  • 1
    $\begingroup$ I'd conjecture that following the Hilbert space-filling curve would be the most efficient way. $\endgroup$ – rych May 8 '14 at 8:27
  • 2
    $\begingroup$ What a great question... $\endgroup$ – JohnD Oct 25 '14 at 21:29
5
+100
$\begingroup$

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).

$\endgroup$
  • 1
    $\begingroup$ I've made some edits that were easier to apply directly than explain in a comment; please look over them and make sure I haven't misinterpreted anything. $\endgroup$ – Mario Carneiro Dec 12 '14 at 10:50
  • 1
    $\begingroup$ Note that since the length of $\gamma$ is the supremum of $\sum_i||\gamma(t_i)-\gamma(t_{i+1})||$ over any sequence $0=t_0\le t_1\le\dots\le t_n=1$, your inequality at the end is indeed sufficient to deduce $L(\gamma)\le\lambda_\epsilon$. (I believe you, but could you put in a proof for the claimed inequality?) $\endgroup$ – Mario Carneiro Dec 12 '14 at 10:55
  • 1
    $\begingroup$ Also, you cannot make the assumption that the $\gamma_n$ are piecewise linear at the start without more work - it doesn't follow from my proof. That said, it shouldn't matter to the proof, since it is sufficient that they are rectifiable and that follows from the assumption on lengths. $\endgroup$ – Mario Carneiro Dec 12 '14 at 10:59
  • 1
    $\begingroup$ A proof of $\lambda_0=2\pi$: your sequence shows $\lambda_0\le 2\pi$. For the converse, note that in order to cover the points at $r=2-\epsilon$, and some $\theta$, the center must be in a small lemon-shaped region around $r=1$ and the same $\theta$, so by choosing $\theta=2\pi/n$ and $\epsilon$ sufficiently small w.r.t $n$, you can force the lawnmower to visit the points on a regular $n$-gon within some $\epsilon$. And accepting that the edges of an $n$-gon solve the associated TSP problem... $\endgroup$ – Mario Carneiro Dec 13 '14 at 15:03
  • 1
    $\begingroup$ An extension to your attempt at part 2: If $S$ has rectifiable boundary $\gamma$, then let $T=E_1(S)\setminus E_1(\gamma_1)$ and $\{C_n\}$ be the connected components of $E_{1/2}(T)$ (there are finitely many because each has area $\ge\pi/4$). Now $E_2(T)\subseteq E_1(S)$, and each $E_1(C_n)$ has a $\gamma_n$ that covers it with overspill $1/2$, which can be connected to the main path by picking a point in $C_n\setminus T$ (which is nonempty) and drawing a straight line from the point on $\gamma_n$ to the one on $\gamma$ that covers this point. $\endgroup$ – Mario Carneiro Dec 13 '14 at 18:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.