Computing geodesic paths on

The Fast Marching Method is a numerical algorithm for solving the Eikonal equation on a rectangular orthogonal mesh in O(MlogM) steps, where M is the to- tal 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 dis- tances and thereby extracting shortest paths on triangulated manifolds. Sethian's Fast Marching Method (1), is a numerical algorithm for solving the Eikonal equation on a rectangular orthogonal mesh in O(MlogM) steps, where M is the total number of grid points in the domain. The technique hinges on producing numerically consistent approximations to the operators in the Eikonal equation that select the correct viscosity solution; this is done through the use of upwind finite difference operators. The structure of this upwinding is then used to systematically construct the solution to the Eikonal equation through an op- timal ordering of points during the update. The optimal order- ing is executed using a heap operator to extract the next point in the update sweep. As such, the technique is a reminiscent of Dijkstra's method (2); however, the resulting approxima- tion is consistent in that it produces the correct shortest path on an orthogonal grid. For details about Fast Marching Meth- ods, see refs. 1 and 3. Barth and Sethian (4) have recently constructed opera- tors for viscosity solutions to both the Eikonal equation and Hamilton-Jacobi equations on arbitrary triangulated domains. These operators exploit the upwind nature to construct the correct entropy-satisfying weak solutions. In this paper, we extend these ideas and build a Fast Marching Method for tri- angulated domains. As an application, we provide an optimal algorithm for computing the geodesic distances and thereby extracting shortest paths on triangulated manifolds. The outline of this paper is as follows. First, we review the Fast Marching Method for orthogonal grids. Then, for mo- tivational reasons, we analyze the structure of this method on a triangulated planar grid constructed directly from an or- thogonal grid. We then follow with a general procedure for computing the solution of the Eikonal equation on arbitrary acute triangulated domains, followed by an extension to gen- eral (nonacute) triangulations. As an application, we com- pute geodesic distances and minimal geodesic paths on mani- folds.