ANISOTROPIC FAST-MARCHING ON CARTESIAN GRIDS USING LATTICE BASIS REDUCTION~*

摘要

We introduce a modification of the fast-marching algorithm, which solves the anisotropic eikonal equation associated to an arbitrary continuous Riemannian metric M on a twoor three-dimensional domain. The algorithm has a complexity O(N lnN + N ln κ(M)), where N is the discrete domain cardinality. The logarithmic dependency in the maximum anisotropy ratio κ(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 ?~m, with respect to the symmetric positive definite matrix M(z) encoding the desired anisotropy at this point.