¿Lo que ' s la forma más eficiente para cortar el césped?

Question

Para $S\subseteq\Bbb R^2$ y $x\in\Bbb R$, definir $E_x(S)=\{y\in\Bbb R^2:d(y,S)<x\}$. ($E_x(S)$ representa la expansión de la $S$ $x$.) Dada una ruta $\gamma:[0,1]\a\Bbb R^2$, denotan su longitud como $L(\gamma)=\int_\gamma|dx|\[0,\infty]$ (para no subsanables caminos, $L(\gamma)=\infty$).

Supongamos ahora que la $S$ es conectado y acotado, y dejar que $$\lambda_\epsilon=\inf\Big\{L(\gamma):E_1(S)\subseteq \overline{E_1(\gamma)}\subseteq \overline{E_{1+\epsilon}(S)}\Big\}.$$ Esta es nuestra mejor ruta para una cortadora de césped con el corte de radio $1$ a cortar el césped de $E_1(S)$, con una recepción de más de $\epsilon$. Las preguntas son:

• Hace $\lambda_\epsilon$ existir por cada $\epsilon>0$? (Creo que me puede demostrar esto.)
• Hace $\lambda_0$ existir? (No estoy seguro acerca de esto.)
• Es $\lambda_\epsilon$ un mínimo en cualquiera de los casos, es decir, hay una aceptable camino cuya longitud es de $\lambda_\epsilon$?
• Existen algoritmos para la búsqueda de caminos cuya longitud es de menos de $\delta$ de $\lambda_\epsilon$? (No estoy seguro de cómo hacer esto precisa.)

Esto es lo que pienso cada vez que me segar el césped, y apuesto a que no estoy solo.

Edit: Una prueba para la primera pregunta: Dejar que $\epsilon>0$. Desde $S$ es limitada, por lo que es de $E_{\epsilon/2}(S) de dólares, y también es totalmente acotado. Por lo tanto, hay un número finito de tapa $B(\epsilon/2,x_k))_{k=1}^n$ de $E_{\epsilon/2}(S)$ por bolas de radio $\epsilon/2$. Desde $E_{\epsilon/2}(S)$ es una unión de abrir conjuntos conectados, que están conectados juntos en $S$, también está conectada. Ahora cualquier conjunto conectado es el camino conectados por poligonal caminos, así que hay una poligonal ruta de acceso de $x_i$ $x_{i+1}$ por cada $1\le i<$ n. La concatenación de estos es una poligonal ruta $\gamma$ que pasa a través de cada $x_i$ y queda en $\bigcup_{k=1}^nB(\epsilon/2,x_k)\subseteq E_{\epsilon}(S) de dólares. Entonces $E_1(\gamma)\subseteq E_{1+\epsilon}(S) de dólares, y cualquier punto de $E_1(S)$ es de menos de $1-\epsilon/2$ de un punto en $E_{\epsilon/2}(S) de dólares, que es menos de $\epsilon/2$ de $x_k\en\gamma$, entonces $E_1(S)\subseteq E_1(\gamma)$. Por último, dado que $\gamma$ es poligonal, es subsanables, por lo que $\lambda_\epsilon\le L(\gamma)$ y $\lambda_\epsilon$ existe.

Si se considera el lineal de las rutas desde $x_i$ $x_j$ cuando las bolas de $B(\epsilon/2,x_i)$ y $B(\epsilon/2,x_j)$ no son disjuntos, se obtiene una gráfica en $$ n vértices, y el problema de encontrar la ruta más corta en este gráfico que visita todos los vértices es exactamente el Problema del Viajante de comercio. Por lo tanto esto no augura nada bueno para los algoritmos eficientes para resolver este problema.

Answer 1

El problema es más bonito con el cierre de la disco cortadoras de césped, así que permítanme definir $D_x(S) = \{y \in \mathbb{R}^2 | d(y,S) \leq x\}$, y definir $\mu_{\epsilon}$ como: $$ \mu_{\epsilon} = \inf\left\{L(\gamma) | D_{1}(S) \subseteq D_1(\gamma) \subseteq \overline{D_{1+\epsilon}(S)}\right\} $$ Si $\epsilon>0$, creo que su existencia prueba funciona de la misma por $\mu_{\epsilon}$. A continuación puedo demostrar el infimum que se puede lograr cuando el uso de estos cerrada-cortadoras de disco. Yo también le doy un posible contra-ejemplo para abrir-cortadoras de disco.

---

Revisión $\epsilon\geq 0$ y se asume que $\mu_{\epsilon}$ existe y es positiva. Deje que $\gamma_n(t)$ ser una secuencia infinita de subsanables en caminos con la propiedad $D_1(S) \subseteq D_1(\gamma_n) \subseteq \overline{D_{1+\epsilon}(S)}$, y tal que $\lim_{n\rightarrow\infty} L(\gamma_n) = \mu_{\epsilon}$. Podemos asumir que cada ruta $\gamma_n$ se define a recorrer su curso a velocidad constante de $L(\gamma_n)$ distancia/tiempo (ver más abajo el comentario de Mario para más justificación de esta hipótesis). Así, por $0 \leq t \leq 1$, $\gamma_n(t)$ es el punto en la ruta, que es una fracción $t$ de la distancia total de la ruta. Para todo $n$ y todos los $t, v \in [0,1]$ tenemos:

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

(véase la Nota 1 para más detalle sobre esto). Además, las rutas de $\gamma_n(t)$ son todos los que figuran en una región acotada de $\mathbb{R}^2$. Deje que $\{q_1, q_2, \ldots\}$ ser un listado de racionales en $[0,1]$. Por el lema de diagonalización en el Apéndice de la Probabilidad y Medida por Billingsley, hay una larga $n_k$ tal que $\gamma_{n_k}(q_i)$ converge para todo $i$ as $k\rightarrow\infty$ (esto es, esencialmente, un countably-extensión infinita de la de Bolzano-Wierstrass teorema). Deje que $\gamma(q_i)$ ser el valor de limitación, definidos para cada racional $q_i$.

La función $\gamma(q_i)$ es continua sobre los racionales, porque para cualquiera de los dos racionales $q_i, q_j$ en el intervalo $[0,1]$ tenemos:

\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}

Teniendo un límite de $k\rightarrow \infty$ implica $||\gamma(q_i)-\gamma(q_j)|| \leq |q_i-q_j|\mu_{\epsilon}$.

Por lo tanto, podemos extender $\gamma(q_i)$ a una función continua $\gamma(t)$ más de los reales $t \in [0,1]$. Con un poco más de trabajo, podemos mostrar la misma larga de funciones $\gamma_{n_k}(t)$ de hecho convergen (pointwise para todos $t \in [0,1]$) $\gamma(t)$ y $\gamma(t)$ sí debe satisfacer para todos $t, v \in [0,1]$:

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

Queda por mostrar dos propiedades: (i) $D_1(S) \subseteq D_1(\gamma)\subseteq \overline{D_{1+\epsilon}(S)}$, y (ii) $\gamma(t)$ es subsanables con una longitud que alcanza el infimum $\mu_{\epsilon}$. La primera propiedad es por las Notas 2 y 3 a continuación. La segunda propiedad tiene porque: Para cualquier partición finita de veces $0 \leq t_0 < t_1 < \cdots < t_N \leq 1$ tenemos $\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}$ así $\gamma$ es subsanables con $L(\gamma) \leq \mu_{\epsilon}$. Pero, por supuesto, la primera propiedad, a continuación, se asegura de $L(\gamma)\geq \mu_{\epsilon}$. Y por lo que $\gamma$ alcanza el infimum $\mu_{\epsilon}$.

---

Nota 1: Prueba $||\gamma_n(t)-\gamma_n(v)|| \leq t |v|L(\gamma_n)$. Suponga que $v>t$ y $\gamma_n(t)$ path tiene velocidad constante. Entonces $\gamma_n(t)$ es el punto en la ruta, que es una fracción $t$ de la distancia total, y $\gamma_n(v)$ es el punto más a lo largo de la ruta que es una fracción $v$ de la distancia total. Así que hay un camino de longitud $(v-t)L(\gamma_n)$ entre los puntos $\gamma_n(t)$ y $\gamma_n(v)$, y esta longitud debe ser mayor que o igual a la longitud de la línea recta entre estos puntos.

---

Nota 2: la Prueba de que $D_1(\gamma) \subseteq \overline{D_{1+\epsilon}(S)}$. Deje que $x \in D_1(\gamma)$. Entonces hay un punto de $\gamma(t)$ ($t \in[0,1]$) $||\gamma(t)-x|| \leq 1$. La secuencia de puntos de $\gamma_{n_k}(t)$ converge a $\gamma(t)$ $k\rightarrow\infty$. Sin embargo, $D_1(\gamma_{n_k})\subseteq\overline{D_{1+\epsilon}(S)}$ para todo $k$, y así cualquier cosa dentro del radio de 1 de $\gamma_{n_k}(t)$ es $\overline{D_{1+\epsilon}(S)}$. De ello se sigue que $x$ es arbitrariamente cerca de puntos en el conjunto cerrado $\overline{D_{1+\epsilon}(S)}$, por lo que debe estar también en este conjunto.

---

Nota 3: la Prueba de que $D_1(S) \subseteq D_1(\gamma)$. Deje que $x \in D_1(S) de dólares. Entonces $x \in D_1(\gamma_{n_k})$ de cada índice $k$. Así que hay veces $t_k \in [0,1]$ tal que para todo $k$ tenemos $||x - \gamma_{n_k}(t_k)|| \leq 1$. Elegir un determinado larga de los índices de $k(m)$ más de los cuales $t_{k(m)}$ converge (por Bolzano-Wierstrass) a un punto $t \in[0,1]$. Así que para cualquier $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}

Teniendo un límite de $m\rightarrow\infty$ da $||x - \gamma(t)|| \leq 1$, y por lo que $x \in D_1(\gamma)$.

---

Respuesta parcial a la pregunta 2: El valor de $\lambda_0$ existirá siempre que el conjunto $S$ es convexo con un subsanables límite, desde versiones a escala de conjuntos convexos "encajar dentro de" unos a otros como tazas de medir. Así que podemos tomar un camino que consiste en la frontera junto con una adecuada reducción de escala de las versiones de los (conectados por segmentos cortos).

---

Posible contra-ejemplo que muestra infimum no es alcanzable cuando usamos abierto de disco, cortadoras de césped, es decir, usando $E_1(\cdot)$: Deja de $S$ ser cerrada disco de radio 1 con respecto al origen. Entonces $E_1(S)$ es la de abrir el disco de radio 2 sobre el origen. Creo que $\lambda_0=2\pi$ (intuitivo, pero difícil de demostrar rigurosamente), y esto se puede lograr de manera arbitraria de cerca por la ruta de acceso que consta de la unidad de círculo sobre el origen, además de un pequeño segmento de la línea de tamaño $\epsilon$ a partir de cualquier punto en el círculo y se mueve en el interior del origen (este segmento de línea que permite la cobertura de el origen de la misma). El límite de $\gamma$ de esos caminos (y creo que el único candidato posible ruta que podría alcanzar el infimum) es el círculo unidad en sí. Pero el origen está en $E_1(S)$ pero no en $E_1(\gamma)$. Por lo que $E_1(S)$ es no un subconjunto de $E_1(\gamma)$, y el infimum no se logra. Sin embargo, esto podría lograrse con un cerrado disco de cortadora de césped.

Una simplificación de la contra-ejemplo en el mismo espíritu puede ser cuando $S$ es una plaza cerrada de lado 2.

---

Bien Mario de la finalización de la "limón" ejemplo hace obvio que $2\pi$ es el min. En realidad es fácil mostrar que cualquier convexidad $S$ debe incluir el límite de $S$ en cualquier ruta que cubre $E_1(S)$ y $\epsilon=0$ caso. Pero me pregunto si $\lambda_{\epsilon}=\lambda_{0}$ en todos los casos? (parece intuitivamente cierto si $S$ es la unidad de disco, pero de alguna manera no está claro cómo rigurosamente probar).