Anisotropic Fast-Marching on Cartesian Grids Using Lattice Basis Reduction
Jean-Marie Mirebeau · SIAM Journal on Numerical Analysis · 2014
We introduce a modification of the fast-marching algorithm, which solves the anisotropic eikonal equation associated to an arbitrary continuous Riemannian metric ${\cal M}$ on a two- or three-dimensional domain. The algorithm has a complexity ${\cal O}(N \ln N + N \ln \kappa({\cal M}))$, where $N$ is the discrete domain cardinality. The logarithmic dependency in the maximum anisotropy ratio $\kappa({\cal M})$ of the Riemannian metric allows us to handle extreme anisotropies for a limited numerical cost. We prove the convergence of the algorithm and illustrate its efficiency by numerical experiments. The algorithm relies on the computation at each grid point $z$ of a special system of coordinates: a reduced basis of the lattice ${\Bbb Z}^m$, with respect to the symmetric positive definite matrix ${\cal M}(z)$ encoding the desired anisotropy at this point.