Vol. 95, pp. 8431–8435, July 1998 | R. Kimmel* and J. A. Sethian†
The paper by R. Kimmel and J. A. Sethian extends the Fast Marching Method, a numerical algorithm for solving the Eikonal equation on rectangular orthogonal grids in \(O(M \log M)\) steps, to triangulated domains. The method is designed to maintain the same computational complexity. The authors provide an optimal algorithm for computing geodesic distances and shortest paths on triangulated manifolds. The extension involves constructing monotone update procedures for acute and general (nonacute) triangulations, ensuring that the solution is consistent and accurate. The algorithm is validated through various examples, including regular triangulations, polyhedra, and manifolds with nonacute triangulations, demonstrating its effectiveness in computing minimal geodesics.The paper by R. Kimmel and J. A. Sethian extends the Fast Marching Method, a numerical algorithm for solving the Eikonal equation on rectangular orthogonal grids in \(O(M \log M)\) steps, to triangulated domains. The method is designed to maintain the same computational complexity. The authors provide an optimal algorithm for computing geodesic distances and shortest paths on triangulated manifolds. The extension involves constructing monotone update procedures for acute and general (nonacute) triangulations, ensuring that the solution is consistent and accurate. The algorithm is validated through various examples, including regular triangulations, polyhedra, and manifolds with nonacute triangulations, demonstrating its effectiveness in computing minimal geodesics.