An ordered upwind method with precomputed stencil and monotone node acceptance for solving static convex Hamilton-Jacobi equations (Q2276405)

The authors present three simple criteria for the \(\delta\)-causality of the discretization of a static convex Hamilton-Jacobi partial differential equation (HJ PDE). They show that with respect to a node, \(\delta\)-anisotropy-angle-boundedness of a simplex \(\delta\)-negative-gradient-acuteness of the simplex, which in turn implies \(\delta\)-causality of the equation for the node value update from the simplex. A monotone acceptance ordered upwind method (MAOUM), that first determines a consistent, \(\delta \)-causal stencil for each grid node and then solves the discrete equation in a single-pass through the nodes, is developed. MAOUM is suited to solving HJ PDEs efficiently on highly-nonuniform grids, since the stencil size adjusts to the level of grid refinement. This strength of MAOUM is demonstrated in a problem with a homogeneous rectangular speed profile and in a robot navigation problem involving wind and obstacles. MAOUM is a Dijkstra-like algorithm that computes the solution in increasing the value order by using a heap to sort proposed node values.