Computing geodesic paths on manifolds

Computing geodesic paths on manifolds

July 1998 | R. KIMMEL AND J. A. SETHIAN
This paper presents an extension of the Fast Marching Method (FMM) for solving the Eikonal equation on triangulated domains, maintaining the same computational complexity of $ O(M \log M) $, where M is the number of grid points. The FMM is a numerical algorithm that computes geodesic distances and shortest paths on triangulated manifolds. The method is based on upwind finite difference operators and uses a heap structure to efficiently select the next point to update. The algorithm systematically advances the front in an upwind fashion, ensuring that the solution is consistent and produces the correct shortest path on an orthogonal grid. The paper first reviews the FMM for orthogonal grids, then extends it to triangulated domains. The key idea is to construct a monotone update procedure on the triangulated mesh. For acute triangulations, the method computes a possible value for T from each triangle that includes the center point as a vertex. The update is performed in a way that ensures the gradient of the solution points into the triangle from which it is updated. For general triangulations, the method handles obtuse angles by splitting them into acute ones and using virtual directional edges to maintain the monotonicity and consistency of the solution. The algorithm is applied to compute geodesic distances and minimal geodesic paths on triangulated manifolds. The method is validated on various examples, including regular triangulations of surfaces and polyhedrons with different speed functions. The results show that the algorithm can handle both acute and non-acute triangulations efficiently, with computational complexity remaining optimal at $ O(M \log M) $. The method is consistent, converges to the viscosity solution, and provides accurate results for computing shortest paths on manifolds.This paper presents an extension of the Fast Marching Method (FMM) for solving the Eikonal equation on triangulated domains, maintaining the same computational complexity of $ O(M \log M) $, where M is the number of grid points. The FMM is a numerical algorithm that computes geodesic distances and shortest paths on triangulated manifolds. The method is based on upwind finite difference operators and uses a heap structure to efficiently select the next point to update. The algorithm systematically advances the front in an upwind fashion, ensuring that the solution is consistent and produces the correct shortest path on an orthogonal grid. The paper first reviews the FMM for orthogonal grids, then extends it to triangulated domains. The key idea is to construct a monotone update procedure on the triangulated mesh. For acute triangulations, the method computes a possible value for T from each triangle that includes the center point as a vertex. The update is performed in a way that ensures the gradient of the solution points into the triangle from which it is updated. For general triangulations, the method handles obtuse angles by splitting them into acute ones and using virtual directional edges to maintain the monotonicity and consistency of the solution. The algorithm is applied to compute geodesic distances and minimal geodesic paths on triangulated manifolds. The method is validated on various examples, including regular triangulations of surfaces and polyhedrons with different speed functions. The results show that the algorithm can handle both acute and non-acute triangulations efficiently, with computational complexity remaining optimal at $ O(M \log M) $. The method is consistent, converges to the viscosity solution, and provides accurate results for computing shortest paths on manifolds.
Reach us at info@futurestudyspace.com