1998/07/21 by Ron Kimmel, James A. Sethian · 2 citations
Computer Science · Engineering · Mathematics · #Computational Geometry and Mesh Generation #Data Management and Algorithms #Human Motion and Animation #Fast marching method #Geodesic #Eikonal equation #Grid #Marching cubes #Computer science #Mathematics #Polygon mesh #Algorithm #Geometry #Mathematical analysis #Visualization #Artificial intelligence
paper · doi:10.1073/pnas.95.15.8431
openalex publication_date 1998/07/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/09
The Fast Marching Method is a numerical algorithm for solving the Eikonal equation on a rectangular orthogonal mesh in O(M log M) steps, where M is the total number of grid points. In this paper we extend the Fast Marching Method to triangulated domains with the same computational complexity. As an application, we provide an optimal time algorithm for computing the geodesic distances and thereby extracting shortest paths on triangulated manifolds.