High-order Semi-Lagrangian schemes and applications to Hamilton-Jacobi equations and Level Set Method

We present numerical methods based on high-order semi-Lagrangian schemes coupled with Essentially Non-Oscillatory interpolation techniques, in the field of the Level Set Method and Hamilton-Jacobi equations. The first application arises in the context of surface reconstruction from point clouds, where we consider a variational formulation with a curvature constraint that minimizes a suitable functional in order to reconstruct an unknown surface from a set of unorganized points. The level set formulation of this model consists in solving an equivalent advection-diffusion equation that evolves until steady-state an initial surface described implicitly by a level set function, actually a signed distance one. In order not to be prohibitively limited by a parabolic-type time-stepping constraint, the semi-Lagrangian approach is employed, coupled with a multi-linear interpolator and a Weighted Essentially Non-oscillatory one to get a high-quality reconstruction. To concentrate the computational effort, this method is also presented in the framework of Adaptive Mesh Refinement based on octrees, since either the semi-Lagrangian approach and the Level Set Method are apt to be exploited for local refinement. In both cases, an extensive list of numerical tests, in two and three dimensions, is presented. On the other hand, the second application is devoted to high-order numerical schemes for time-dependent first-order Hamilton-Jacobi-Bellman equations. In particular, we propose to resort to a Central Weighted Non-Oscillatory interpolation and we prove a convergence result in the case of state- and time-independent Hamiltonians. Moreover, the expected computational advantages of the central reconstruction, compared to the traditional one, are validated by numerical simulations in one and two dimensions, also for more general state- and time-dependent Hamiltonians. Special attention is paid to the parallel implementation of the algorithms presented in this thesis, especially in the surface reconstruction application, where the three-dimensionality of the problem could make the computations extremely expensive.