Problema del camino más corto de Euclides

Archivo:Euclidean Shortest Path KernelCAD Screenshot.jpg

Ejemplo del camino más corto en un espacio Euclideo tridimensional

El problema del camino más corto de Euclides es un problema en geometría computacional: dado un conjunto de obstáculos poliédricos en un espacio Euclídeo, y dos puntos, encontrar el camino más corto entre los puntos que no intersecte ninguno de los obstáculos.

En dos dimensiones, el problema puede resolverse en tiempo polinómico en un modelo de cmputación que permita sumar y comparar números reales, a pesar de las dificultades teóricas que implica la precisión numérica necesaria para realizar dichos cálculos. Estos algoritmos se basan en dos principios diferentes, ya sea realizando un algoritmo que de el camino más corto como el algoritmo de Dijkstra en un grafo de visibilidad derivado de los obstáculos o propagando un frente de onda desde uno de los puntos hasta que se encuentra con el otro.

En tres dimensiones (y mayores) el problema es NP-Hard en el caso general, 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 gráfico de visibilidad utilizando estos puntos de muestra.

Hay muchos resultados en el cálculo de las trayectorias más cortas 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 salga de 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, hay variaciones de este problema, donde los obstáculos son pesados, es decir, uno puede pasar a través de un obstáculo, pero esto tiene un costo extra para pasar a través ese obstáculo. El problema estándar es el caso especial en el que los obstáculos tienen un peso infinito. Esto se denomina el problema de la región pesada.

Véase también

• Problema del camino más corto

Referencias

• Aleksandrov, Lyudmil; Maheshwari, Anil; Sack, Joerg (2005), «Determining approximate shortest paths in weighted polyhedral surfaces», Journal of the ACM 52: 25-53, doi:10.1145/1044731.1044733 ..
• Chiang, Yi-Jen; Mitchell, Joseph S. B. (1999), «Two-point Euclidean shortest path queries in the plane», Proc. 10th ACM-SIAM Symposium on Discrete Algorithms (SODA 1999), pp. 215-224 ..
• Choi, Joonsoo; Sellen, Jürgen; Yap, Chee-Keng (1994), «Approximate Euclidean shortest path in 3-space», Proc. 10th ACM Symposium on Computational Geometry, pp. 41-48, ISBN 0-89791-648-4, doi:10.1145/177424.177501 ..
• Hershberger, John; Suri, Subhash (1999), «An optimal algorithm for Euclidean shortest paths in the plane», SIAM Journal on Computing 28 (6): 2215-2256, doi:10.1137/S0097539795289604 ..
• Kapoor, S.; Maheshwari, S. N. (1988), «Efficient algorithms for Euclidean shortest path and visibility problems with polygonal obstacles», Proc. 4th ACM Symposium on Computational Geometry, pp. 172-182, ISBN 0-89791-270-5, doi:10.1145/73393.73411 ..
• Kapoor, S.; Maheshwari, S. N.; Mitchell, Joseph S. B. (1997), «An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane», Discrete and Computational Geometry 18 (4): 377-383, doi:10.1007/PL00009323 ..
• Lanthier, Mark; Maheshwari, Anil; Sack, Joerg (2001), «Approximating shortest paths on weighted polyhedral surfaces», Algorithmica, pp. 527-562 ..
• Lee, D. T.; Preparata, F. P. (1984), «Euclidean shortest paths in the presence of rectilinear barriers», Networks 14 (3): 393-410, doi:10.1002/net.3230140304 ..
• Li, Fajie; Klette, Reinhard (2011), Euclidean Shortest Paths: Exact or Approximate Algorithms, Springer-Verlag, ISBN 978-1-4471-2255-5, doi:10.1007/978-1-4471-2256-2 ..
• Samuel, David; Toussaint, Godfried T. (1990), «Computing the external geodesic diameter of a simple polygon», Computing 44 (1): 1-19, doi:10.1007/BF02247961 ..
• Toussaint, Godfried T. (1989), «Computing geodesic properties inside a simple polygon», Revue D'Intelligence Artificielle 3 (2): 9-42 ..