Numerical Hopf-Lax formulae for Hamilton-Jacobi equations on unstructured geometries

We consider a scheme of Semi-Lagrangian (SL) type for the numerical solution of Hamilton-Jacobi (HJ) equation on unstructured triangular grids. As it is well known, SL schemes are not well suited for unstructured grids, due to the cost of the point location phase; this drawback is augmented by the need for repeated minimization. In this work, we propose a scheme that works only on the basis of node values and connectivity of the grid. In a first version, we obtain a monotone scheme; then, applying a quadratic refinement to the numerical solution, we improve accuracy at the price of some extra computational cost. The scheme can be applied to both time-dependent and stationary HJ equations; in the latter case, we also study the construction of a fast policy iteration solver. We perform a theoretical analysis of the two versions, and validate them with an extensive set of examples, both in the time-dependent and in the stationary case.