Technical Reports

The ICICS/CS Reading Room


UBC CS TR-2006-27 Summary

FAST MARCHING METHODS FOR A CLASS OF ANISOTROPIC STATIONARY HAMILTON-JACOBI EQUATIONS, January 16, 2007 Ken Alton and Ian M. Mitchell, 38 pages

The Fast Marching Method (FMM) has proved to be a very efficient algorithm for solving the isotropic Eikonal equation. Because it is a minor modification of Dijkstra’s algorithm for finding the shortest path through a discrete graph, FMM is also easy to implement. In this paper we describe a new class of Hamilton-Jacobi (HJ) PDEs with axis-aligned anisotropy which satisfy a causality condition for standard finite difference schemes on orthogonal grids and can hence be solved using the FMM; the only modification required to the algorithm is in the local update equation for a node. Since our class of HJ PDEs and grids permit asymmetries, we also examine some methods of improving the efficiency of the local update that do not require symmetric grids and PDEs. This class of HJ PDEs has applications in robotic path planning, and a brief example is included. In support of this and similar applications, we also include explicit update formulas for variations of the Eikonal equation that use the Manhattan, Euclidean and infinity norms on orthogonal grids of arbitrary dimension and with variable node spacing.


If you have any questions or comments regarding this page please send mail to help@cs.ubc.ca.