Fast Marching Methods for Computing Distance Maps and Shortest Paths
Ron Kimmel · eScholarship (California Digital Library) · 1996
In this paper, we present a fast technique for computing both paths of minimal cost, and minimal geodesics on surfaces.The technique exploits the fast marching method introduced in [15,16] for solving the Eikonal equation and its extension to general static Hamiltonian-Jacobi equations given in [1].The solution to the appropriate static Hamiltonian provides the arrival time of the shortest path, and is then coupled to high order ordinary differential equation solvers to construct the path itself.The resulting technique is an O(N log N) procedure, where N is the total number of grid points.The technique works without change in any number of space dimensions.We provide upwind approximation schemes for the relevant Hamiltonian, and a series of examples of the construction of such geodesics, as well as additional comments about the use of such schemes in computing general distance maps and shape-offsetting.