¿Existe una solución general para el "problema de la araña y la mosca"?

Question

(Agradecería que alguien diera una formulación más formal de este problema).

El El problema de la araña y la mosca es un problema en el que el objetivo es minimizar la distancia que debe recorrer la araña para llegar a la mosca que está al otro lado de la habitación.

La araña sólo puede moverse en la superficie de la habitación. Sea S el punto donde está la araña y F el punto donde está la mosca. Se da la longitud de YG, GF, PH y HS, así como la longitud, anchura y altura del prisma rectangular. Supongamos que la mosca y la araña permanecen en sus respectivos lados, pero aparte de eso, sus puntos no están necesariamente donde se colocan en el diagrama. ¿Existe una fórmula general para calcular la distancia más corta entre la araña y la mosca? (¿Existe una fórmula general para la geodésica del cubo?)

He resuelto el problema original de la araña y la mosca (simplemente creando mallas del cubo y teniendo suerte), pero no veo cómo podría generalizar el resultado, sobre todo porque la araña y la mosca no tienen que estar en la misma posición que en el problema original. En el problema original, la araña está centrada y a una unidad de la parte superior, y la mosca está centrada y a una unidad de la parte inferior. He intentado considerar el caso más sencillo en el que la mosca y la araña permanecen en el mismo lugar, pero aún no he podido generalizarlo, especialmente para casos más extremos (si hacemos que la altura muy grande en comparación con los demás, nuestra línea se saldrá de la malla, no estoy seguro de cómo lidiar con esto).

He buscado en Internet alguna pista sobre el problema, y el la página de Mathworld utilizó la palabra "geodésica" para describir la solución. Investigué un poco más, pero sólo pude encontrar soluciones para la esfera y algunas otras formas tridimensionales. Tampoco pude encontrar ninguna página que describiera una solución general al problema, sólo páginas que utilizaban las mallas del prisma rectangular como solución.

Answer 1

He aquí un esbozo de solución integral. Dudo que pueda existir una fórmula simple de forma cerrada, si es lo que buscas.

Consideremos la secuencia de caras que recorre el camino óptimo. Cada par de caras consecutivas tiene una arista común, por lo que toda la secuencia se puede "desplegar" en el plano. Para que el camino sea óptimo, debe ser una única línea recta que se encuentre completamente dentro de las caras desplegadas.

Sólo hay un número finito de desdoblamientos diferentes de la sala, que corresponden a diferentes árboles de extensión del grafo de adyacencia de las caras de la sala (en este caso, el grafo octaédrico). Para cada uno de ellos, comprueba si el segmento de línea que une las posiciones desplegadas de la araña y la mosca se encuentra completamente dentro del despliegue; si es así, registra su longitud. Prueba todos los desdoblamientos posibles y quédate con el camino de menor longitud.

Este algoritmo funciona para salas poliédricas arbitrarias. Editar: Bueno, quizás no ingenuamente ( ver el contraejemplo de Namiki ), pero si interpretas que "se encuentra completamente dentro del desdoblamiento" como "no deja ninguna cara al cruzar un borde que ha sido cortado", entonces debería seguir funcionando.

Answer 2

Puede que sea una estupidez, y aún no tengo pruebas de ello, pero creo que esto daría la solución correcta y sería relativamente sencillo de expresar.

Considera las caras del cubo. Para cada punto dentro del cuboide, asigna la etiqueta de la(s) cara(s) más cercana(s). Los puntos con exactamente dos etiquetas se encuentran en una interfaz plana, y los puntos con más de dos etiquetas se encuentran en una interfaz lineal.

Bueno, esto es sólo una forma de verlo, pero a lo que voy es que se obtiene un cuboide formado por cuatro toblerones iguales cuya base son las "caras de longitud" (rectángulos), y dos pirámides cuya base son las caras "delantera y trasera" (cuadrados). Si la longitud del cubo es menor que el lado del cuadrado, entonces se obtienen cuatro toblerones y dos trapecios con base cuadrada.

Cada pirámide/trapecio y toblerón corresponde a una única cara, y podemos asociar cada interfaz con al menos una arista.

A continuación, dibuje el segmento SF, y marque sus intersecciones con las interfaces entre pirámide/toblero dentro del cubo. Si hay tales intersecciones en las interfaces lineales (más de dos etiquetas), entonces los límites de la etiqueta "después" y "antes" de la intersección en el segmento debe permitir identificar exactamente un borde.

Para cada uno de estos puntos de la interfaz, proyecte el punto a la arista correspondiente, y hágalo en el plano o línea definida por la propia interfaz.

Creo que los puntos que se obtienen en los bordes permiten dibujar la trayectoria óptima. Sin embargo, todavía no estoy seguro de lo que hay que hacer si la intersección se encuentra en la base pequeña de los trapecios. Todavía estoy pensando en cómo probarlo.

NOTA: descripción aclarada tras los comentarios de Rahul Narain, gracias

Answer 3

EDITAR : Esta solución es defectuosa como se explica en el comentario de abajo. Sin embargo, me parece lo suficientemente interesante como para dejarla como está aquí.

Como se indica en el comentario de Pavel M, el caso general de una sala con forma arbitraria puede ser bastante complicado. Sin embargo, en el marco limitado sugerido en el PO: una habitación con forma de "malla cúbica", existe una solución puramente geométrica y sin cálculos, que se explica a continuación. Demostraré que siempre hay una única geodésica, y mi argumento también implica inmediatamente una fórmula para la distancia mínima, que será una suma de dos o tres raíces cuadradas.

Si la habitación fuera convexa, las geodésicas serían obviamente segmentos de línea. Aquí nuestra habitación no es convexa, pero podemos descomponerla como una unión de tres subconjuntos convexos (los rectángulos verde, rojo y amarillo de la figura 1). Para que la araña no pierda tiempo, debe necesariamente caminar primero por el rectángulo verde, luego cruzar el rojo y finalmente ir a $F$ en el amarillo, sin volver nunca dentro del rectángulo rojo. Queda entonces claro que cualquier geodésica desde $S$ a $F$ debe ser de hecho una unión de tres segmentos, $[SA],[AB]$ y $[BF]$ como en la figura 1.

Así que todo lo que queda por hacer es determinar la posición de $A$ y $B$ . Lo que resuelve todo es aplicar dos veces el siguiente lema (o más bien su corolario) :

Lema. Dejemos que $P,Q$ sean dos puntos distintos en el plano, y sea $D$ sea una línea que separa $P$ y $Q$ . Considere la función $f: D \to {\mathbb R}^{+}$ definido por $f(M)=PM+QM$ . Sea $I$ denotan el punto de intersección de $D$ y $[PQ]$ . Entonces $f$ alcanza un mínimo global en $I$ y en cada media línea a partir de $I$ , $f(M)$ disminuye estrictamente como $M$ se acerca a $I$ .

Prueba del lema $f$ es una suma de dos funciones estrictamente convexas y, por tanto, es estrictamente convexa, qed.

Corolario Dejemos que $P,Q,D,I,f$ sea como el anterior. Sea $D’$ sea cualquier segmento de $D$ . Entonces $f$ tiene un mínimo único en $D’$ , alcanzada en el punto más cercano a $I$ dentro de $D’$ .

Volviendo a nuestro problema inicial, hay tres casos :

Caso 1. El segmento $[SF]$ está completamente incluido en la habitación. En ese caso, el segmento recto de $S$ a $F$ es la solución única obvia.

Caso 2. El segmento $[SF]$ sale sólo una vez de la habitación. En ese caso, obviamos la parte prohibida utilizando la esquina más cercana (véanse las figuras 2.1 y 2.2). Aplicando el corolario dos veces, ésta es la única geodésica desde $S$ a $F$ en este caso.

Caso 3. El segmento $[SF]$ sale dos veces de la habitación. En ese caso utilizamos las dos esquinas $A$ y $B$ (como en la figura 3). Aplicando el corolario dos veces, ésta es la única geodésica desde $S$ a $F$ en este caso.