Problema de calcular los caminos más cortos alrededor de obstáculos geométricos.
Ejemplo de camino más corto en un espacio euclidiano tridimensional
El problema del camino más corto euclidiano es un problema de geometría computacional : dado un conjunto de obstáculos poliédricos en un espacio euclidiano , y dos puntos, encontrar el camino más corto entre los puntos que no interseque a ninguno de los obstáculos.
Dos dimensiones
En dos dimensiones, el problema puede resolverse en tiempo polinomial en un modelo de cálculo que permita la suma y comparación de números reales, a pesar de las dificultades teóricas que implican la precisión numérica necesaria para realizar dichos cálculos. Estos algoritmos se basan en dos principios diferentes, ya sea realizando un algoritmo de ruta más corta, como el algoritmo de Dijkstra, en un gráfico de visibilidad derivado de los obstáculos o (en un enfoque llamado método continuo de Dijkstra ) propagando un frente de onda desde uno de los puntos hasta que se encuentra con el otro.
Dimensiones superiores
En tres (y superiores) dimensiones el problema es NP-difícil en el caso general, [1] pero existen algoritmos de aproximación eficientes que se ejecutan en tiempo polinómico basados en la idea de encontrar una muestra adecuada de puntos en los bordes del obstáculo y realizar una Cálculo del gráfico de visibilidad utilizando estos puntos de muestra.
Hay muchos resultados sobre el cálculo de caminos más cortos que permanecen en una superficie poliédrica. Dados dos puntos s y t, digamos en la superficie de un poliedro convexo , el problema es calcular el camino más corto que nunca abandone la superficie y conecte s con t. Esta es una generalización del problema bidimensional, pero es mucho más fácil que el problema tridimensional.
Variantes
Hay variaciones de este problema, donde los obstáculos están ponderados , es decir, uno puede atravesar un obstáculo, pero atravesar un obstáculo incurre en un costo adicional. El problema estándar es el caso especial en el que los obstáculos tienen un peso infinito. Esto se denomina en la literatura como el problema de la región ponderada .
^
J. Canny y JH Reif, "Nuevas técnicas de límite inferior para problemas de planificación del movimiento de robots", Proc. 28º año. Simposios IEEE. Encontró. Computadora. Sci., 1987, págs. 49-60.
Referencias
Alexandrov, Lyudmil; Maheshwari, Anil; Sack, Joerg (2005), "Determinación de los caminos más cortos aproximados en superficies poliédricas ponderadas", Journal of the ACM , 52 : 25–53, doi :10.1145/1044731.1044733, S2CID 697658.
Chiang, Yi-Jen; Mitchell, Joseph SB (1999), "Consultas de ruta más corta euclidiana de dos puntos en el plano", Proc. Décimo simposio ACM-SIAM sobre algoritmos discretos (SODA 1999), Association for Computing Machinery, págs. 215–224, ISBN 9780898714340.
Hershberger, John; Suri, Subhash (1999), "Un algoritmo óptimo para los caminos más cortos euclidianos en el plano", SIAM Journal on Computing , 28 (6): 2215–2256, CiteSeerX 10.1.1.47.2037 , doi :10.1137/S0097539795289604.
Kapoor, S.; Maheshwari, SN; Mitchell, Joseph SB (1997), "Un algoritmo eficiente para los caminos más cortos euclidianos entre obstáculos poligonales en el plano", Geometría discreta y computacional , 18 (4): 377–383, doi : 10.1007/PL00009323.
Lanthier, Marcos; Maheshwari, Anil; Sack, Jörg-Rüdiger (2001), "Aproximación de caminos más cortos en superficies poliédricas ponderadas", Algorithmica , págs..
Lee, DT ; Preparata, FP (1984), "Los caminos más cortos euclidianos en presencia de barreras rectilíneas", Networks , 14 (3): 393–410, doi :10.1002/net.3230140304.
Li, Fajie; Klette, Reinhard (2011), Caminos euclidianos más cortos: algoritmos exactos o aproximados , Springer-Verlag , doi :10.1007/978-1-4471-2256-2, ISBN 978-1-4471-2255-5.
Samuel, David; Toussaint, Godfried T. (1990), "Cálculo del diámetro geodésico externo de un polígono simple", Computación , 44 (1): 1–19, doi :10.1007/BF02247961, S2CID 31450333.
Toussaint, Godfried T. (1989), "Cálculo de propiedades geodésicas dentro de un polígono simple" (PDF) , Revue d'Intelligence Artificielle , 3 (2): 9–42.
