Solving anisotropic eikonal equations with non-causal schemes and quasi-linear complexity

We introduce a numerical algorithm for solving anisotropic eikonal equations, whose complexity O(N ln^2 (N/eps)) is quasi-linear with respect to the number N of discretization points, and logarithmic w.r.t. the numerical tolerance eps>0, with explicit constants depending on the metric defining the PDE geometry. In contrast with the fast-marching method, our algorithm does \emph{not} rely on the causality property, and for this reason it can be applied to a variety of schemes: semi-Lagrangian, upwind-differences, or based on a Lax-Friedrichs relaxation of the eikonal PDE - allowing a non-convex Hamiltonian. Our method uses a narrow band to compute the eikonal front propagation, whose thickness is tuned depending on the properties of the discretization scheme and of the metric. The algorithm depends on four parameters whose theoretical value is unfortunately excessively pessimistic, hence we also provide heuristic parameter values leading to a simple, robust and efficient numerical method in practice, even though some guarantees no longer apply. Numerical experiments, involving anisotropic metrics arising in differential games, seismology, image segmentation and motion planning, show that the method retains a quasi-linear complexity in difficult test cases where the cost of alternative approaches often becomes super-linear.