# zbMATH — the first resource for mathematics

An ordered upwind method with precomputed stencil and monotone node acceptance for solving static convex Hamilton-Jacobi equations. (English) Zbl 1256.65099
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.

##### MSC:
 65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs 35F21 Hamilton-Jacobi equations 49L25 Viscosity solutions to Hamilton-Jacobi equations in optimal control and differential games 65N50 Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs
Algorithm 360
Full Text: