  The fast marching algorithm, and its variants, solves numerically the
generalized eikonal equation associated to an underlying riemannian metric. A
major challenge for these algorithms is the non-isotropy of the riemannian
metric. Applications of the eikonal equation to image processing often involve
pronounced anisotropies, which motivated the design of new algorithms.
  A recently introduced variant of the fast marching algorithm addresses the
problem of large anisotropies using an algebraic tool named lattice basis
reduction. The numerical complexity of this algorithm is insensitive to
anisotropy, under weak assumptions. We establish in this paper, in the
simplified setting of a constant riemannian metric, that the accuracy of this
algorithm is also extremely robust to anisotropy : in an average sense, it is
independent of the anisotropy ratio. We also extend this algorithm to higher
dimension.

Numerical Analysis