A linear finite-difference scheme for approximating Randers distances on Cartesian grids

Frédéric Bonnans (1) , Guillaume Bonnet (2) , Jean-Marie Mirebeau (3, 4)

1 DISCO - Dynamical Interconnected Systems in COmplex Environments
2 LMO - Laboratoire de Mathématiques d'Orsay
3 CB - CB - Centre Borelli - UMR 9010
4 CNRS - Centre National de la Recherche Scientifique

Randers distances are an asymmetric generalization of Riemannian distances, and arise in optimal control problems subject to a drift term, among other applications. We show that Randers eikonal equation can be approximated by a logarithmic transformation of an anisotropic second order linear equation, generalizing Varadhan's formula for Riemannian manifolds. Based on this observation, we establish the convergence of a numerical method for computing Randers distances, from point sources or from a domain's boundary, on Cartesian grids of dimension two and three, which is consistent at order two thirds, and uses tools from low-dimensional algorithmic geometry for best efficiency. We also propose a numerical method for optimal transport problems whose cost is a Randers distance, exploiting the linear structure of our discretization and generalizing previous works in the Riemannian case. Numerical experiments illustrate our results.

Domaines: Analyse numérique [math.NA]; Equations aux dérivées partielles [math.AP]

Frédéric Bonnans, Guillaume Bonnet, Jean-Marie Mirebeau. A linear finite-difference scheme for approximating Randers distances on Cartesian grids. ESAIM: Control, Optimisation and Calculus of Variations, 2022, 28, ⟨10.1051/cocv/2022043⟩. ⟨hal-03125879v3⟩