Problema de cálculo de rutas más cortas 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 ninguno de los obstáculos.
Dos dimensiones
En dos dimensiones, el problema puede resolverse en tiempo polinómico en un modelo de cálculo que permite la suma y comparación de números reales, a pesar de las dificultades teóricas que implica la precisión numérica necesaria para realizar tales 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 sobre 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 dimensiones (y más) el problema es NP-difícil en el caso general, [1] pero existen algoritmos de aproximación eficientes que se ejecutan en tiempo polinomial basados en la idea de encontrar una muestra adecuada de puntos en los bordes de los obstáculos y realizar un cálculo de gráfico de visibilidad utilizando estos puntos de muestra.
Existen muchos resultados sobre el cálculo de caminos más cortos que permanecen en una superficie poliédrica. Dados dos puntos s y t, por ejemplo, en la superficie de un poliedro convexo , el problema consiste en calcular un camino más corto que nunca abandone la superficie y conecte s con t. Esta es una generalización del problema de dos dimensiones, pero es mucho más fácil que el problema tridimensional.
Variantes
Existen variaciones de este problema, en las que los obstáculos tienen un peso determinado , es decir, se puede atravesar un obstáculo, pero se incurre en un coste adicional. El problema estándar es el caso especial en el que los obstáculos tienen un peso infinito. En la literatura, esto se denomina problema de la región ponderada .
^
J. Canny y JH Reif, "Nuevas técnicas de límite inferior para problemas de planificación de movimiento de robots", Proc. 28.° Simposio anual IEEE. Fundada en 1987, págs. 49-60.
Referencias
Aleksandrov, Lyudmil; Maheshwari, Anil; Sack, Joerg (2005), "Determinación de 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. 10.º 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 euclidianos más cortos 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 las rutas euclidianas más cortas entre obstáculos poligonales en el plano", Geometría discreta y computacional , 18 (4): 377–383, doi : 10.1007/PL00009323.
Lanthier, Mark; Maheshwari, Anil; Sack, Jörg-Rüdiger (2001), "Aproximación de los caminos más cortos en superficies poliédricas ponderadas", Algorithmica , págs. 527–562.
Lee, DT ; Preparata, FP (1984), "Caminos euclidianos más cortos 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", Computing , 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.
