Algoritmo para el camino más corto en un colector

Question

¿Cuáles son algunos de los algoritmos utilizados para encontrar el camino más corto entre 2 puntos de un colector (riemanniano) (el colector puede tener una frontera lisa)?

Hasta ahora he tenido 3 ideas, ninguna de las cuales parece tan buena:

1) (Principio de la banda elástica) Encuentra cualquier trayectoria entre los dos puntos, luego dibuja la trayectoria tensa como una banda elástica estirada con algo de amortiguación.

2) (Análogo al trazado de rayos) Dispara rayos geodésicos desde un punto en todas direcciones. Si un rayo alcanza el objetivo, hemos terminado. Si el rayo golpea el límite y no está cerca de la tangente, ignóralo. Si el rayo golpea el límite aproximadamente tangente, entonces sigue la geodésica en el límite en esa dirección, disparando rayos tangentes de vez en cuando.

3) (Discretización) Triangular/tetrahedralizar/etc el colector, y construir un grafo ponderado donde los nodos correspondan a los puntos centrales de cada tetraedro, las aristas correspondan a tetraedros que se tocan, y los pesos correspondan a la distancia entre centros de tetraedros. A continuación, calcular el camino más corto en el gráfico.

La mayor parte de lo que he visto en la bibliografía se refiere a la existencia teórica de la trayectoria más que a su cálculo real. ¿Cómo se encuentra el camino más corto en la práctica?

Answer 1

Existen muchos algoritmos para calcular los caminos más cortos en los 2manifolds poliédricos. Con un estudiante calculé los caminos más cortos que se muestran a continuación con uno de ellos, el algoritmo de Chen-Han. Los algoritmos abren en abanico los caminos más cortos a un frontera imitando la estructura (pero no los detalles) de Algoritmo de Dijkstra para los caminos más cortos de un grafo. A veces, el método se denomina método "continuo de Dijkstra". Estos algoritmos (todos en $\mathbb{R}^3$ ) se describen en muchos lugares, entre ellos el libro Algoritmos de plegado geométrico: Enlaces, Origami, Poliedros Capítulo 24.

Supongo que el mismo planteamiento funcionará para las variedades trianguladas en dimensiones arbitrarias, pero, por supuesto, su aplicación será mucho más complicada.