Fast-Marching Methods for Curvature Penalized Shortest Paths

We introduce numerical schemes for computing distances and shortest paths with respect to several planar paths models, featuring curvature penalization and data-driven velocity: the Dubins car, the Euler/Mumford elastica, and a two variants of the Reeds–Shepp car. For that purpose, we design monotone and causal discretizations of the associated Hamilton–Jacobi–Bellman PDEs, posed on the three-dimensional domain R2×S1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb R}^2 \times {\mathbb S}^1$$\end{document}. Our discretizations involve sparse, adaptive and anisotropic stencils on a cartesian grid, built using techniques from lattice geometry. A convergence proof is provided, in the setting of discontinuous viscosity solutions. The discretized problems are solvable in a single pass using a variant of the fast-marching algorithm. Numerical experiments illustrate the applications of our schemes in motion planning and image segmentation.