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, encuentre el camino más corto entre los puntos que no se cruza con ninguno de los obstáculos.
En dos dimensiones, el problema se puede resolver en tiempo polinomial en un modelo de cálculo que permite sumar y comparar 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 otro.
En tres (y más) dimensiones 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 del obstáculo y realizar una cálculo del gráfico de visibilidad utilizando estos puntos de muestra.
Hay muchos resultados al calcular las rutas más cortas que permanecen en una superficie poliédrica. Dados dos puntos syt, digamos en la superficie de un poliedro convexo , el problema es calcular un camino más corto que nunca abandone la superficie y conecte s con t. Esta es una generalización del problema de 2 dimensiones, pero es mucho más fácil que el problema de 3 dimensiones.
Además, existen variaciones de este problema, donde los obstáculos son ponderados , es decir, se puede atravesar un obstáculo, pero tiene un costo extra atravesar un obstáculo. El problema estándar es el caso especial donde los obstáculos tienen un peso infinito. Esto se denomina problema de región ponderada en la literatura.
Ver también
Notas
- ^ J. Canny y JH Reif, "[ https://www.researchgate.net/profile/John_Canny2/publication/4355151_New_lower_bound_techniques_for_robot_motion_planning_problems/links/5581e03708ae6cf036c16ff3/New-lann-lowproblems. pdf Nuevas técnicas de límite inferior para problemas de planificación del movimiento de robots] ", Proc. 28th Annu. Simposios IEEE. Encontró. Computación. Sci., 1987, págs. 49-60.
Referencias
- Aleksandrov, Lyudmil; Maheshwari, Anil; Sack, Joerg (2005), "Determinar caminos más cortos aproximados en superficies poliédricas ponderadas", Journal of the ACM , 52 : 25–53, doi : 10.1145 / 1044731.1044733.
- 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) , págs. 215-224.
- Choi, Joonsoo; Sellen, Jürgen; Yap, Chee-Keng (1994), "Camino euclidiano más corto aproximado en 3 espacios", Proc. Décimo Simposio de ACM sobre geometría computacional , págs. 41–48, doi : 10.1145 / 177424.177501 , ISBN 0-89791-648-4.
- Hershberger, John; Suri, Subhash (1999), "Un algoritmo óptimo para trayectos 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 (1988), "Algoritmos eficientes para el camino más corto euclidiano y problemas de visibilidad con obstáculos poligonales", Proc. 4to Simposio de ACM sobre geometría computacional , págs. 172–182, doi : 10.1145 / 73393.73411 , ISBN 0-89791-270-5.
- Kapoor, S .; Maheshwari, SN; Mitchell, Joseph SB (1997), "Un algoritmo eficiente para caminos euclidianos más cortos 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, Joerg (2001), "Aproximación de caminos más cortos en superficies poliédricas ponderadas" , Algorithmica , pp. 527–562.
- Lee, DT ; Preparata, FP (1984), "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), Rutas más cortas euclidianas: 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), "Calcular el diámetro geodésico externo de un polígono simple" , Computación , 44 (1): 1–19, doi : 10.1007 / BF02247961.
- Toussaint, Godfried T. (1989), "Calcular propiedades geodésicas dentro de un polígono simple" (PDF) , Revue d'Intelligence Artificielle , 3 (2): 9–42.
enlaces externos
- Implementación del algoritmo Euclidean Shortest Path en el software KernelCAD