# LIMITS OF NON-LOCAL APPROXIMATIONS TO THE EIKONAL EQUATION ON MANIFOLDS

JALAL FADILI, NICOLAS FORCADEL, AND RITA ZANTOUT

**ABSTRACT.** In this paper, we consider a non-local approximation of the time-dependent Eikonal equation defined on a Riemannian manifold. We show that the local and the non-local problems are well-posed in the sense of viscosity solutions and we prove regularity properties of these solutions in time and space. If the kernel is properly scaled, we then derive error bounds between the solution to the non-local problem and the one to the local problem, both in continuous-time and Forward Euler discretization. Finally, we apply these results to a sequence of random weighted graphs with $n$ vertices. In particular, we establish that the solution to the problem on graphs converges almost surely uniformly to the viscosity solution of the local problem as the kernel scale parameter decreases at an appropriate rate when the number of vertices grows and the time step vanishes.

## CONTENTS

<table><tr><td>1. Introduction</td><td>1</td></tr><tr><td>1.1. Problem statement</td><td>2</td></tr><tr><td>1.2. Contributions</td><td>4</td></tr><tr><td>1.3. Related work</td><td>5</td></tr><tr><td>1.4. Outline</td><td>5</td></tr><tr><td>2. Notations and prerequisites on Riemannian manifolds</td><td>5</td></tr><tr><td>2.1. Preliminaries on Riemannian manifolds</td><td>5</td></tr><tr><td>2.2. Properties of the Riemannian distance</td><td>6</td></tr><tr><td>2.3. Other notations</td><td>8</td></tr><tr><td>3. Well-posedness and regularity results</td><td>8</td></tr><tr><td>3.1. Problem (P)</td><td>8</td></tr><tr><td>3.2. Problem (P<sub>ε</sub>)</td><td>16</td></tr><tr><td>4. Consistency and error bounds</td><td>19</td></tr><tr><td>4.1. Continuous time non-local to local error bound</td><td>20</td></tr><tr><td>4.2. Forward Euler discrete time non-local to local error bound</td><td>25</td></tr><tr><td>5. Application to graph sequences</td><td>28</td></tr><tr><td>Appendix A. Well-posedness and regularity properties of (P<sub>ε</sub><sup>FD</sup>)</td><td>30</td></tr><tr><td>Appendix B. Covering number of M</td><td>31</td></tr><tr><td>References</td><td>32</td></tr></table>

## 1. INTRODUCTION

Nonlinear partial differential equations (PDEs) on graphs have found applications in a variety of areas such as, e.g., analysis, physics, economy, probability theory, biology and data science. In particular, a family of Hamilton-Jacobi equations on graphs called the Eikonal equation has been considered on weighted graphs for data processing in [12, 35], for semi-supervised learning on graphs [7, 32], and for data depth [7, 29]. They have been also used on topological networks in [8, 19].
In [34], Hamilton-Jacobi equations on graphs were also studied to derive discrete versions of some functional inequalities (log-Sobolev inequality and Talagrand's transport inequality).

In this paper, we are particularly interested in the case of geometric graphs whose vertices are points living on a compact Riemannian submanifold, which is relevant for many applications such as data depth [28], semi-supervised learning [4] and image and mesh processing [27, 30].

In order to transpose PDEs on graph, discrete calculus have been used in recent years using partial difference equations (PdEs) on graphs. PdEs are methods used to reformulate continuous problems by replacing differential operators by difference operators on graphs [14, 15, 18].

The main goal of this paper is to rigorously study continuum limits, i.e. as the number of data points tends to infinity, of the Eikonal equation defined on a weighted geometric graph embedded in a compact Riemannian submanifold. The motivation behind considering Eikonal equations in such a context is the ability to extend it to any discrete data that can be represented by weighted geometric graphs. In fact, many applications in numerical data analysis and processing or machine learning include data that can be defined on manifolds, or irregularly shaped domains, or network-like structures, or defined as high dimensional point clouds such as collections of features vectors. In a discrete setting, these data can be represented as weighted geometric graphs, where the vertices are drawn from the underlying domain (a manifold) and are connected by edges if sufficiently close in a certain ground metric. The edges are given weights (e.g., based on the distance between data points).

### 1.1. Problem statement.
In this paper, we will work with a Riemannian manifold $(\mathcal{M}, g)$ of dimension $m^*$, where $\mathcal{M}$ is a compact manifold and $g$ is a Riemannian metric (see Section 2 for precise definitions and properties). Let $G = (V, w)$ be a finite weighted (geometric) graph on $\mathcal{M}$, where $V \subset \mathcal{M}$ is the set of vertices, and $w: V \times V \to \mathbb{R}^+$ is the weight function. A natural Eikonal-type equation on graphs takes the form

$$ (1) \qquad \begin{cases} \max_{v \in V} \sqrt{w(u, v)}(f(v) - f(u))_{-} = \tilde{P}(u), & u \in V \setminus V_0, \\ f(u) = 0, & u \in V_0, \end{cases} $$

where $(\cdot)_{-} \stackrel{\text{def}}{=} -\min(\cdot, 0)$, $V_0 \subset V$ and $\tilde{P}$ is a given potential. This equation is an adaptation on weighted graphs of the Eikonal equation using the framework of PdEs and provides a tool for multiple front propagation problems on weighted graphs. This discrete form allows to handle any data that can be represented on graphs, e.g., in machine learning, data analysis and processing on graphs, on unstructured meshes or point clouds [7, 8, 12, 27, 32, 35].

Our goal in the paper is to study the behavior of the solution to problem (1) as the number of vertices goes to infinity. In fact, we will consider an even more general class of equations. More precisely, inspired by (1), we consider the non-local Eikonal equation in a time-dependent form

$$ (\mathcal{P}_{\varepsilon}) \qquad \left\{ \begin{array}{ll} \frac{\partial}{\partial t} f^{\varepsilon}(x, t) + |\nabla_{\eta_{\varepsilon}}^{\perp} f^{\varepsilon}(x, t)|_{\infty} = \tilde{P}(x), & (x, t) \in (\tilde{\mathcal{M}} \setminus \tilde{\Gamma}) \times ]0, T[, \\ f^{\varepsilon}(x, t) = f_{0}^{\varepsilon}(x), & (x, t) \in (\tilde{\Gamma} \times ]0, T[) \cup \tilde{\mathcal{M}} \times \{0\}, \end{array} \right. $$

where $\tilde{\mathcal{M}}$ is a subset of points of $\mathcal{M}$, $\tilde{\Gamma} \subset \tilde{\mathcal{M}}$ is the set of boundary points, $\tilde{P}$ is the potential function, and $f_0^\varepsilon$ is the boundary function. $\nabla_{\eta_\varepsilon}^\perp$ is a non-local operator coined the weighted directional internal gradient operator, introduced in [12] and studied theoretically in [16] in the Euclidean case. This operator is defined through

$$ |\nabla_{\eta_{\varepsilon}}^{\perp} f^{\varepsilon}(x, t)|_{\infty} = \max_{y \in \tilde{\mathcal{M}}} J_{\varepsilon}(x, y)(f^{\varepsilon}(y, t) - f^{\varepsilon}(x, t)), $$
where, given a length scale $\varepsilon > 0$, the $\varepsilon$-scaled kernel function $J_\varepsilon: \mathcal{M} \times \mathcal{M} \to \mathbb{R}_+$ is defined by

$$J_{\varepsilon}(x, y) = \frac{1}{C'_{\eta}} \eta_{\varepsilon}(\tilde{d}(x, y)) \quad \text{with} \quad \eta_{\varepsilon}(t) = \frac{1}{\varepsilon} \eta\left(\frac{t}{\varepsilon}\right),$$

and $\eta: [0, +\infty) \to [0, +\infty)$ is a radial kernel function, and

$$(2) \qquad C_{\eta} = \sup_{t \in \mathbb{R}_+} t\eta(t) > 0.$$

Since, from a practical point of view, computing intrinsic Riemannian distance is quite impossible in many cases due to the unknown geometry and curvature, we will work with $\tilde{d}$ which is an approximation of the intrinsic distance function (see Assumption (H.8) below). Observe that we can also write

$$(3) \qquad \left|\nabla_{\eta_{\varepsilon}}^{-} f^{\varepsilon}(x, t)\right|_{\infty} = \max_{y \in \tilde{M}} C_{\eta}^{-1} \eta_{\varepsilon}(\tilde{d}(x, y))(f^{\varepsilon}(x, t) - f^{\varepsilon}(y, t)).$$

The problem $(\mathcal{P}_\varepsilon)$ represents an Eikonal equation on weighted graphs with $n$ vertices when we properly instantiate the sets $\tilde{M}$ and $\tilde{\Gamma}$, see Section 5. Therefore, several natural questions arise from a numerical analysis perspective: (i) given $n$-dependent scaling $\varepsilon_n$, is there a continuum limit (and in which sense) of the solution to $(\mathcal{P}_\varepsilon)$ on graphs (and its time-discretized version as well) as $n \to +\infty$ (and time step goes 0)? (ii) at which rate this convergence happens? (iii) what are the main quantities that come into play in the error bounds? Our main contributions of this work is to settle these questions.

Towards this, we study the time-dependent local Eikonal equation on the Riemannian manifold $\mathcal{M}$

$$(\mathcal{P}) \qquad \begin{cases} \frac{\partial}{\partial t} f(x, t) + \|\mathrm{grad} f(x, t)\|_x = P(x), & (x, t) \in \mathcal{M} \setminus \Gamma \times ]0, T[, \\ f(x, t) = f_0(x), & (x, t) \in (\Gamma \times ]0, T[) \cup \mathcal{M} \times \{0\}, \end{cases}$$

where $\Gamma \subset \mathcal{M}$ is the set of boundary points, $P$ is the potential function, and $f_0$ is the boundary function. $\mathrm{grad} f(x, t) \in T_x \mathcal{M}$ is the Riemannian gradient in space of $f$ at a point $x$, where $T_x \mathcal{M}$ is the tangent space of $\mathcal{M}$ at $x$ and $\| \cdot \|_x$ is the norm induced by the Riemannian metric $g$ at $x$ (see Section 2 for definitions).

In the rest of the paper, we will work under the standing assumptions:

(H.1) $\mathcal{M}$ is a differentiable manifold of class $C^3$ which is compact, and geodesically strongly convex with $C^1$ boundary $\partial \mathcal{M}$.

(H.2) $\tilde{\mathcal{M}}$ is a finite subset of $\mathcal{M}$.

(H.3) $\Gamma \subset \mathcal{M}$ and $\tilde{\Gamma} \subset \tilde{\mathcal{M}}$ are closed sets with $\mathcal{M} \setminus \Gamma$ open and $\tilde{\mathcal{M}} \setminus \tilde{\Gamma} \subset \mathcal{M} \setminus \Gamma$.

(H.4) $P \in \mathrm{Lip}(\mathcal{M} \setminus \Gamma)$ and $\tilde{P} \in \mathrm{Lip}(\tilde{\mathcal{M}} \setminus \tilde{\Gamma})$ are non-negative potential functions.

(H.5) $f_0 \in \mathrm{Lip}(\mathcal{M})$ and $f_0^\varepsilon \in \mathrm{Lip}(\tilde{\mathcal{M}})$.

(H.6) There exists $a_0, d_0 > 0$ such that $\tilde{d}(\cdot, \Gamma)$ is $C^1$ on the neighbourhood $\mathcal{N}_\Gamma^{a_0} \setminus \Gamma$ where $\mathcal{N}_\Gamma^{a_0} \stackrel{\text{def}}{=} \{x \in \mathcal{M}, \tilde{d}(x, \Gamma) < a_0\}$, and $\|\mathrm{grad} \tilde{d}(x, \Gamma)\|_x \ge d_0$ for all $x \in \mathcal{N}_\Gamma^{a_0} \setminus \Gamma$.

(H.7) There exists $\delta > 0$ such that for all $x \in \mathcal{M}$, $\mathrm{Cut}(x) \cap \mathcal{N}_x^\delta = \emptyset$, where $\mathcal{N}_x^\delta = \{y \in \mathcal{M}, d_\mathcal{M}(x, y) \le \delta\}$ and $\mathrm{Cut}(x)$ is the cut locus of $x$ defined in Section 2.

(H.8) There exists a constant $C_\mathcal{M}$ and $\xi > 0$ such that $\max_{(x,y) \in \mathcal{M} \times \mathcal{M}} |\tilde{d}(x, y) - d_\mathcal{M}(x, y)| \le C_\mathcal{M} \varepsilon^{1+\xi}$.

Assumption (H.3) implies that $\partial \mathcal{M} \subseteq \Gamma$. In assumption (H.2), the fact that $\tilde{\mathcal{M}}$ is finite is quite natural since the main goal of this paper is to study Eikonal equation on graphs. However, this assumption is only required to prove the existence of a solution of the non-local problem $(\mathcal{P}_\varepsilon)$
(see Proposition 3.13) and is not used to show any other result. In the rest of the paper, this assumption can be replaced by the fact that $\tilde{M}$ is a compact subset of $M$. Assumption (H.6) is concerned with the regularity of the distance $\tilde{d}(\cdot, \Gamma)$. It is used to construct super-solutions that are compatible with the boundary conditions. Furthermore, assumption (H.7) guarantees local differentiability of the squared Riemannian distance. It means that for all $y \in \mathcal{N}_x^\delta$, for $\delta$ sufficiently small, $y \notin \text{Cut}(x)$, and thus $d_M^2(x, \cdot)$ is differentiable at $y$. Assumption (H.8) explains how $\tilde{d}$ approximates the Riemannian distance $d_M$. For example, $\tilde{d}(x, y)$ could be computed using the Euclidean distance in the $\bar{\xi}$-offset $\Omega_M^{\bar{\xi}} = \{x \in \mathbb{R}^m : d(x, M) \le \bar{\xi}\}$, where $\bar{\xi} = \varepsilon^{2+2\xi}$. In this case, $C_M$ depends on the dimension $m*$. We refer to the work of Mémoli and Sapiro in [27, Theorem 5] in which they studied the approximation of the Riemannian distance and constructed extrinsic approximation satisfying (H.8).

In the context of our study, it is important to illustrate concrete examples of manifolds that satisfy the hypothesis listed above, showing how our framework can be applied to various types of manifolds. Consider first the Euclidean sphere $S^n$, where $n \ge 2$. This manifold is compact and geodesically strictly convex. Being a smooth manifold of class $C^\infty$, it is also certainly of class $C^3$. Furthermore, our assumptions are met by the compact hyperbolic space $\mathbb{H}^n$. For instance, these manifolds can be constructed in various dimensions, including 3 dimensions exemplified by the Weeks and Thurston manifolds. Moreover, we can consider the three-dimensional torus $\mathbb{T}^3$ which is a compact manifold and of class $C^\infty$. The set $\Gamma$ can be chosen as an arbitrary closed set of each manifold. $\tilde{M}$ can be a finite set of points, as it is always possible to select a finite subset of a compact manifold. Similarly, $\tilde{\Gamma}$ can be chosen as a finite subset of $\tilde{M}$, and the properties of the sets $\Gamma$ and $\tilde{\Gamma}$ are satisfied.

The length scale parameter $\varepsilon$ allows us to consider the data density. In fact, scaling $\eta$ by $\varepsilon$ aims to give significant weight to pairs of points that are far apart up to distance $\varepsilon$. In order to capture proper interactions at scale $\varepsilon$, $\eta$ has to decay to zero at an appropriate rate. Our assumptions on $\eta$ are as follows:

(H.9) $\eta$ is a non-negative function.

(H.10) $\exists r_\eta > 0$ such that $\text{supp}(\eta) \subset [0, r_\eta]$.

(H.11) $\exists a \in ]0, r_\eta[$ such that $\eta$ is decreasing on $[0, a]$ and satisfies $\eta(a) > 0$. We denote by $c_\eta = \eta(a)$.

(H.12) $\eta$ is $L_\eta$-lipschitz continuous on its support.

These assumptions on the kernel are standard, see for example [6, 16].

**1.2. Contributions.** First, we show that the local Eikonal equation ($P$) and the non-local one ($P_\varepsilon$) are well-posed. In other terms, we prove that the solution to ($P$) and to ($P_\varepsilon$) exist and are unique in the sense of viscosity solutions using Perron's method and the comparison principle (see Proposition 3.5 and Proposition 3.13). Then we show regularity properties of these solutions in time and space (see Theorem 3.8 and Theorem 3.14). We then derive error bounds between the solution to the local problem ($P$) and the one to the non-local problem ($P_\varepsilon$) using the regularity properties (see Theorem 4.2). We then use the forward Euler scheme to discretize ($P_\varepsilon$) in time and we provide a consistency result that provides an error bound between the solution of the discretized problem ($P_\varepsilon^{\text{FD}}$) and ($P$) (see Theorem 4.3). Finally, we apply these results to a sequence of random geometric graphs with $n$ vertices (see Theorem 5.3). In particular, we establish that the solution to the time-discretized problem ($P_\varepsilon^{\text{FD}}$) converges almost surely uniformly to the viscosity solution to the local problem ($P$) as the kernel scale parameter decreases at an appropriate rate as $n \to +\infty$ and the time step $\Delta t \to 0$, hence answering all our questions asked above.
1.3. **Related work.** This work is in the continuity of our previous one [16] where we studied limits and consistency of non-local and graph approximations of the time-dependent Eikonal equation defined on Euclidean spaces. We here extend this work to the case of smooth Riemannian manifolds, which are in fact much more in line with realistic applications. This extension is far from trivial as it raises several difficulties and necessitates several new and careful estimates.

Though several works have considered Hamilton-Jacobi type equations on graphs whose vertices are defined on a manifold [7, 11, 12, 14, 27, 35], only a few of them have studied their continuum limits [7, 27]. Motivated by supervised learning and data depth applications, the authors of [7] studied the $p$-Eikonal equation on a random geometric graph where the vertices of the graph are i.i.d random variables on an open, bounded and connected subset of $\mathbb{R}^m$ with a $C^{1,1}$ boundary and the kernel is smooth, non-increasing and satisfies several conditions. They prove that the continuum limit of the non-local $p$-Eikonal equation is a state-constrained Eikonal equation that recovers a geodesic density weighted distance. A theoretical and computational framework was proposed for computing intrinsic distance functions and geodesics on hypersurfaces [26] and submanifolds [27] given by point clouds. For this, the authors proposed to replace the intrinsic Eikonal equation on the submanifold by the corresponding extrinsic Euclidean one on an offset band and proved that this approximation is consistent. Our work goes much beyond and tackles a more general Eikonal equation defined on arbitrary geometric weighted graphs whose vertices live on a compact Riemannian submanifold. We also offer a computational framework by Forward Euler discretization in time of $(P_\epsilon)$. Our framework also allows to cover a much wider spectrum of applications which include the previous ones as particular cases.

1.4. **Outline.** The paper is structured as follows. Section 2 provides prerequisites on Riemannian manifolds that are necessary to our exposition. Section 3 is dedicated to establishing well-posedness in the viscosity sense of problems $(\mathcal{P})$ and $(P_\epsilon)$. Section 4 contains the key results of this paper. Section 4.1 provides an error bound between the solutions to $(\mathcal{P})$ and $(P_\epsilon)$ in continuous time. Section 4.2 extends this to $(\mathcal{P})$ and $(P_\epsilon^{\text{FD}})$, where $(P_\epsilon^{\text{FD}})$ is a forward/explicit Euler discretization in time of $(P_\epsilon)$. Our results are finally specialized to the case of geometric weighted graphs on submanifolds in Section 5.

## 2. NOTATIONS AND PREREQUISITES ON RIEMANNIAN MANIFOLDS

2.1. Preliminaries on Riemannian manifolds. The definitions and results we are about to recall are well-known in Riemannian and differential geometry and we refer for example to [22, 23, 24, 31] for a detailed account.

**Definition 2.1 (C³-smooth manifold).** An $m^*$-dimensional manifold $\mathcal{M}$ is of class $C^3$ at a point $x \in \mathcal{M}$ if there exists a chart $(U, \varphi)$ around $x$ such that $U$ is an open set in $\mathcal{M}$ containing $x$ and $\varphi: U \to \mathbb{R}^{m^*}$ is a $C^3$-diffeomorphism. We say that $\mathcal{M}$ is of class $C^3$ if it is of class $C^3$ at each point $x \in \mathcal{M}$.

**Definition 2.2 (Riemannian metric and norm).** A Riemannian metric $g$ on $\mathcal{M}$ is a family of inner products on tangent spaces of $\mathcal{M}$. In other words, for each $x \in \mathcal{M}$, the mapping $g_x: T_x\mathcal{M} \times T_x\mathcal{M} \to \mathbb{R}$, where $T_x\mathcal{M}$ is the tangent space of $\mathcal{M}$ at the point $x$, is a bilinear symmetric positive definite form denoted by $g_x(u, v) = \langle u, v \rangle_x$ for any vectors $u, v \in T_x\mathcal{M}$. This Riemannian inner product induces a norm $\|\cdot\|_x$ on $T_x\mathcal{M}$ defined by $\|v\|_x = \sqrt{\langle v, v \rangle_x}$, for $v \in T_x\mathcal{M}$.

A (smooth) manifold whose tangent spaces are endowed with a smoothly varying inner product is called a Riemannian manifold. The smoothly varying inner product is called the Riemannian metric. Strictly speaking, a Riemannian manifold is thus a couple $(\mathcal{M}, g)$, where $\mathcal{M}$ is a manifold and $g$ is a Riemannian metric on $\mathcal{M}$. Nevertheless, when the Riemannian metric is unimportant, we simply talk about the Riemannian manifold $\mathcal{M}$.
In order to define viscosity solutions, we will need to give the definition of a differentiable function on a manifold as well as its differential and gradient.

**Definition 2.3** (Differentiable functions on $M$). Suppose that $M$ satisfies assumption (H.1). A real-valued function $f: M \to \mathbb{R}$ is called differentiable (resp. $C^1$) at a point $x \in M$ if there exists a chart $(U, \varphi)$ around $x$ such that $f \circ \varphi^{-1}: \varphi(U) \subset \mathbb{R}^{m^*} \to \mathbb{R}$ is differentiable (resp. $C^1$) at $\varphi(x)$, where $U$ is an open set in $M$ containing $x$ and $\varphi: U \to \mathbb{R}^{m^*}$ is a homeomorphism. The function $f$ is differentiable (resp. $C^1$) in $M$ if it is differentiable (resp. $C^1$) at every point in $M$.

We would like to note here that the definition of differentiability does not depend on the choice of the chart at $x$. Indeed, given any other chart $(V, \phi)$ around $x$ where $V$ is an open set in $M$ containing $x$ and $\phi: V \to \mathbb{R}^{m^*}$ is a homeomorphism, we have

$$f \circ \phi^{-1} = (f \circ \varphi^{-1}) \circ (\varphi \circ \phi^{-1}) : \phi(U \cap V) \to \mathbb{R}$$

is differentiable at $\phi(x)$ since $f \circ \varphi^{-1}$ is differentiable at $\varphi(x)$ and the transition map $\varphi \circ \phi^{-1}$ is differentiable at $\phi(x)$.

**Definition 2.4** (Differential and gradient of a differentiable function). Suppose that $M$ satisfies assumption (H.1). Let $f$ be a scalar-valued differentiable function at $x \in M$. The differential of $f$ at $x$ is the linear map

$$Df(x) : T_x M \to \mathbb{R}$$

$$v \mapsto Df(x)[v] = \left. \frac{d}{ds} f(\gamma(s)) \right|_{s=0},$$

where $\gamma: ]-1, 1[ \mapsto M$ is a differentiable curve in $M$ with $\gamma(0) = x$ and $\gamma'(0) = v$. The gradient of $f$ at $x$, denoted by $\mathrm{grad}f(x)$, is the unique element of $T_x M$ that satisfies

$$\langle \mathrm{grad}f(x), v \rangle_x = Df(x)[v], \quad \forall v \in T_x M.$$

When $f$ depends on several parameters and the variable with respect to which the gradient is computed is not clear from the context, we specify it as a subscript of grad.

**Remark 2.5.** Observe that $Df(x)$ is in the cotangent space $T_x^*M$ which is the dual space of the tangent space $T_x M$. Moreover, for a given tangent vector $v$, the directional derivative $Df(x)[v]$ is independent of the choice of the curve $\gamma$. In fact, if $\gamma_1$ and $\gamma_2$ are two curves such that $\gamma_1(0) = \gamma_2(0) = x$, and in any coordinate chart $\phi$, $\frac{d}{dt}\phi \circ \gamma_1|_{t=0} = \frac{d}{dt}\phi \circ \gamma_2|_{t=0}$, then by the chain rule, $f$ has the same directional derivative at $x$ along $\gamma_1$ and $\gamma_2$.

The gradient of a function $f$ has the following remarkable steepest-ascent property

$$\|\mathrm{grad}f(x)\|_x = \max \{Df(x)[v] : v \in T_x M, \|v\|_x \le 1\}.$$

This can also be equivalently written as

$$\|\mathrm{grad}f(x)\|_x = \max \{Df(x)[v] : v \in T_x M, \|v\|_x = 1\} = \sup \{Df(x)[v] : v \in T_x M, \|v\|_x < 1\}.$$

**2.2. Properties of the Riemannian distance.** The metric of the Riemannian manifold $(M, g)$ allows to define the length of a curve as follows.

**Definition 2.6** (Length of a curve). The length of a piecewise smooth curve segment $\gamma: [a, b] \to M$ on a Riemannian manifold $(M, g)$ is defined by

$$L(\gamma) = \int_a^b \|\dot{\gamma}(s)\|_{\gamma(s)} ds,$$

where $\dot{\gamma}(s)$ is the velocity vector of the curve $\gamma$ at $s$.
**Remark 2.7.** This length is independent of the parametrization. In other words, if $\tilde{\gamma}$ is any reparametrization of $\gamma$, i.e. $\tilde{\gamma} = \gamma \circ \varphi$, where $\varphi : [c, d] \to [a, b]$ is a diffeomorphism, then $L(\tilde{\gamma}) = L(\gamma)$ (see [24, Proposition 13.25]).

We are now ready to introduce the notion of Riemannian distance between any pair of points in $M$.

**Definition 2.8 (Riemannian distance).** The Riemannian distance between two points $x$ and $y$ in $M$, denoted by $d_M(x, y)$, is defined by

$$d_M(x, y) = \inf\{L(\gamma) : \gamma \text{ is a piecewise smooth curve segment on } \mathcal{M} \text{ joining } x \text{ and } y\}.$$

We define the closed Riemannian ball of center $x$ and radius $r > 0$ as

$$B_M(x, r) = \{y \in \mathcal{M} : d_M(x, y) \le r\}.$$

Since any pair of points in $M$ can be joined by a piecewise smooth curve segment ([24, Proposition 11.33]), the above is well-defined. The Riemannian distance function turns $M$ into a metric space whose topology is the same as the given manifold topology; see [24, Theorem 13.29].

Geodesics generalize the notion of straight lines on curved spaces. A geodesic $\gamma$ on a manifold $M$ endowed with an affine connection is a curve with zero acceleration (i.e., constant speed).

**Definition 2.9 (Exponential map).** The exponential map is the mapping

$$\operatorname{Exp}_x : T_x \mathcal{M} \to \mathcal{M} \\ v \mapsto \gamma(1),$$

where $\gamma$ is the unique geodesic such that $\gamma(0) = x$ and $\dot{\gamma}(0) = v$. Existence and uniqueness of the geodesic is ensured whenever $v \in B(0_x, \varepsilon) \subset T_x \mathcal{M}$ with $\varepsilon$ small enough so that for every $t \in [0, 1]$, $\operatorname{Exp}_x(tv) = \gamma(t)$.

The regularity of the distance function on a manifold is a classical and well-understood subject. For instance, the behavior of the distance function is closely related to the structure of the notion of the cut locus of a point.

**Definition 2.10 (Cut locus of a point).** A point $y$ of $M$ is in the cut locus of $x$, denoted by $\operatorname{Cut}(x)$, if and only if there is a minimal geodesic joining $x$ to $y$ whose every extension beyond $y$ is no longer minimal.

An equivalent characterization of the cut locus can be found in [37, Theorem 1].

**Example 2.11.** On the Euclidean sphere, the cut locus of a point $x$ is its antipodal point. On the surface of an infinitely long cylinder, the cut locus of a point consists of the line opposite to it.

The following proposition, proved in [1] and used in [2], provides us with some sufficient conditions for the distance function to be locally of class $C^\infty$.

**Proposition 2.12 (Local smoothness of the distance function [1, Proposition 3.9]).** Let $M$ be a compact Riemannian manifold. Then there exists a constant $r > 0$ such that for every $x \in M$, the exponential map $\operatorname{Exp}_x$ is defined on $B(0_x, r) \subset T_x M$ and provides a $C^\infty$ diffeomorphism

$$\operatorname{Exp}_x : B(0_x, r) \to B_M(x, r) \stackrel{\text{def}}{=} \operatorname{Exp}_x(B(0_x, r)).$$

Moreover, the distance function is given by

$$d_M(x, y) = \|\operatorname{Exp}_x^{-1}(y)\|_x \quad \text{for all } y \in B_M(x, r)$$

and for every $x \in M$, the distance map $y \in M \mapsto d_M(x, y)$ is of class $C^\infty$ on $B_M(x, r) \setminus \{x\}$.
The importance of the cut locus is that the distance function on $\mathcal{M}$ from a point $x$ is differentiable except on the cut locus of $x$ and $x$ itself. Moreover, we have the following useful result about its gradient given in [20].

**Lemma 2.13** (Gradient of the distance function). Let $x \in \mathcal{M}$. For any $y \in \mathcal{M} \setminus (\text{Cut}(x) \cup \{x\})$, if $\gamma$ is the unique minimal geodesic from $x$ to $y$, then the gradient of $d_{\mathcal{M}}(x, \cdot)$ (with respect to the second argument) at $y$ is given by

$$ \mathrm{grad}_y d_{\mathcal{M}}(x, y) = \dot{\gamma}(d_{\mathcal{M}}(x, y)). $$

The squared distance function from a point $y \in \mathcal{M}$ on a Riemannian manifold is smooth away from the cut locus of $y$, for a fixed point $x \in \mathcal{M}$ (see [37]). As a consequence of the Gauss lemma (see [13, Lemma 3.5]), a closed form of the gradient of the squared distance function can be obtained.

**Lemma 2.14** (Gradient of the squared distance [9, Lemma 4.43]). Let $x \in \mathcal{M}$. For any $y \in \mathcal{M} \setminus \text{Cut}\{x\}$, the gradient of $d_{\mathcal{M}}(x, \cdot)^2$ (with respect to the second argument) at $y$ is given by<fnref n="1" />

$$ \mathrm{grad}_y d_{\mathcal{M}}^2(x, y) = -2\mathrm{Exp}_y^{-1}(x) \in T_y \mathcal{M}. $$

**Remark 2.15.** Assumption (H.7) guarantees that $d_{\mathcal{M}}^2(x, \cdot)$ is continuously differentiable on $\mathcal{N}_x^\delta$ with a gradient given by Lemma 2.14.

2.3. **Other notations.** We denote by $|\cdot|$ the Euclidean norm in $\mathbb{R}^m$, where the dimension $m$ is to be understood from the context, Lip($A$) the space of Lipschitz continuous mappings on $A$ and $L_h$ the Lipschitz constant of $h \in \text{Lip}(A)$. Let $X$ and $Y$ be two non-empty subsets of $\mathcal{M}$. We define their Hausdorff distance as

$$ d_{\mathcal{H}}^{\mathcal{M}}(X, Y) = \max \left( \sup_{x \in X} d_{\mathcal{M}}(x, Y), \sup_{y \in Y} d_{\mathcal{M}}(y, X) \right). $$

If both $X$ and $Y$ are bounded, then $d_{\mathcal{H}}^{\mathcal{M}}(X, Y)$ is finite. Moreover, $d_{\mathcal{H}}^{\mathcal{M}}(X, Y) = 0$ if and only if $X$ and $Y$ have the same closure. The supremum norm on a domain $A \subset \mathcal{M}$ is denoted by $\|\cdot\|_{L^\infty(A)}$. We denote the space-time cylinders by $\mathcal{M}_T \stackrel{\mathrm{def}}{=} \mathcal{M} \times [0, T]$ and $\partial \mathcal{M}_T \stackrel{\mathrm{def}}{=} (\Gamma \times ]0, T[) \cup \mathcal{M} \times \{0\}$.

### 3. WELL-POSEDNESS AND REGULARITY RESULTS

In this section, we study the well-posedness in the viscosity sense as well as regularity properties of the solutions to the local Eikonal equation ($\mathcal{P}$) (see Section 3.1) and to the non-local Eikonal equation ($\mathcal{P}_\varepsilon$) (see Section 3.2). Existence can be obtained by the Perron's method recalled in Theorem 3.7 while uniqueness and continuity are based on a comparison principle, proved in Proposition 3.3 for the local problem and in Proposition 3.10 for the non-local one. Our work is based on the theory of viscosity solutions which was introduced by Crandall and Lions [10] for solving first-order Hamilton-Jacobi equations. We refer to [17] for a general introduction to viscosity solutions on Riemannian manifolds.

3.1. **Problem (P).** In order to define viscosity solution for problem (P), we first recall the definition of upper and lower semi-continuous envelope for a locally bounded function $f: \mathcal{M}_T \to \mathbb{R}$, respectively given by

$$ f^*(x, t) \stackrel{\mathrm{def}}{=} \limsup_{(y,s) \to (x,t)} f(y, s) \quad \text{and} \quad f_*(x, t) \stackrel{\mathrm{def}}{=} \liminf_{(y,s) \to (x,t)} f(y, s). $$

<footnote n="1">¹Of course, by symmetry, the role of $x$ and $y$ can be interchanged. This is the reason we did not indicate the variable as a subscript of grad.</footnote>
**Definition 3.1** (Viscosity solution for (P)). An upper semi-continuous (usc) function $f: \mathcal{M} \to \mathbb{R}$ is a viscosity sub-solution of (P) in $(\mathcal{M}\setminus\Gamma)\times]0, T[$ if for every point $(x_0, t_0) \in (\mathcal{M}\setminus\Gamma)\times]0, T[$ and every $C^1$ function $\varphi: \mathcal{N}_{(x_0,t_0)}^h \to \mathbb{R}$ where $\mathcal{N}_{(x_0,t_0)}^h = \{(y, s) \in (\mathcal{M}\setminus\Gamma)\times]0, T[, |t_0 - s| \le h$ and $d_{\mathcal{M}}(x_0, y) \le h\}$ such that $f - \varphi$ has a maximum point at $(x_0, t_0)$, we have

$$ \frac{\partial}{\partial t}\varphi(x_0, t_0) + \|\mathrm{grad}\varphi(x_0, t_0)\|_{x_0} \le P(x_0). $$

The function $f$ is a viscosity sub-solution of (P) in $\mathcal{M}_T$ if it satisfies moreover $f(x, t) \le f_0(x)$ for all $(x, t) \in \partial\mathcal{M}_T$.

A lower semi-continuous (lsc) function $f: \mathcal{M} \to \mathbb{R}$ is a viscosity super-solution of (P) in $(\mathcal{M}\setminus\Gamma)\times]0, T[$ if for every point $(x_0, t_0) \in (\mathcal{M}\setminus\Gamma)\times]0, T[$ and every $C^1$ function $\varphi: \mathcal{N}_{(x_0,t_0)}^h \to \mathbb{R}$ such that $f - \varphi$ has a minimum point at $(x_0, t_0)$, we have

$$ \frac{\partial}{\partial t}\varphi(x_0, t_0) + \|\mathrm{grad}\varphi(x_0, t_0)\|_{x_0} \ge P(x_0). $$

The function $f$ is a viscosity super-solution of (P) in $\mathcal{M}_T$ if it satisfies moreover $f(x, t) \ge f_0(x)$ for all $(x, t) \in \partial\mathcal{M}_T$.

Finally, a locally bounded function $f: \mathcal{M}_T \to \mathbb{R}$ is a viscosity solution of (P) in $\mathcal{M}_T$ (resp. in $(\mathcal{M}\setminus\Gamma)\times]0, T[$ if $f^*$ is a viscosity sub-solution in $\mathcal{M}_T$ (resp. in $(\mathcal{M}\setminus\Gamma)\times]0, T[$ and $f^*$ is a viscosity super-solution of (P) in $\mathcal{M}_T$ (resp. in $(\mathcal{M}\setminus\Gamma)\times]0, T[$).

**Remark 3.2.** In the definition 3.1, the test function $\varphi$ can be extended to a regular function $\psi$ defined on $\mathcal{M}_T$ such that

$$ \psi(x, t) = \begin{cases} \varphi(x, t) & \text{if } (x, t) \in \mathcal{N}_{(x,t)}^h, \\ \phi(x, t) & \text{otherwise,} \end{cases} $$

where $\varphi$ is $C^1$ on $\mathcal{N}_{(x,t)}^h$. Moreover,

$$ \|\mathrm{grad}\psi(x_0, t_0)\|_{x_0} = \|\mathrm{grad}\varphi(x_0, t_0)\|_{x_0}. $$

We begin with a comparison principle for problem (P).

**Proposition 3.3** (Comparison principle for (P)). Suppose that assumptions (H.1)-(H.5) and (H.7) hold. Let $f$, an usc function, be a sub-solution of (P) and $g$, a lsc function, be a super-solution of (P) in $\mathcal{M}_T$. Then

$$ f \le g \quad \text{on } \mathcal{M}_T. $$

The comparison principle can be proved using a variational principle as in [2, Theorem 10] which is valid for quite general Hamilton-Jacobi equations. Nevertheless, their proof is non-constructive and imposes other assumptions on the manifold and the Hamiltonian. For instance, the manifold is supposed to be complete with positive convexity and injectivity radii and the Hamiltonian has to be an intrinsically uniformly continuous function. However, they also state in [2, Remark 12] that their proof holds in other situations. Our equation is somewhat less general which allows to give an alternative and more transparent constructive proof.

*Proof.* We argue by contradiction and we suppose that there exists $(x, t) \in \mathcal{M}_T$ such that

$$ f(x, t) - g(x, t) > 0. $$

We consider the function $\Psi_\tau: (x, t) \in \mathcal{M}_T \to f(x, t) - g(x, t) - \frac{\tau}{T-t}$ for $\tau$ sufficiently small and we set

$$ M_{\tau} \stackrel{\text{def}}{=} \sup_{(x,t) \in \mathcal{M}_T} \Psi_{\tau}(x,t). $$
This function is upper semi-continuous on $\mathcal{M}_T$ which is compact by (H.1), then the supremum is actually a maximum and is attained at a point denoted by $(x_\tau, t_\tau) \in \mathcal{M}_T$. Moreover, $\Psi_\tau(x_\tau, t_\tau) > 0$ for $\tau > 0$ sufficiently small, from the positivity assumption. In order to be able to use the definition of viscosity solutions, we duplicate the variable by considering, for $\gamma > 0$, the test-function

$$ \Psi_{\tau,\gamma} : (x,t,y,s) \in \mathcal{M}_T^2 \to f(x,t) - g(y,s) - \frac{d_{\mathcal{M}}^2(x,y)}{2\gamma} - \frac{|t-s|^2}{2\gamma} - \frac{\tau}{T-t}, $$

and we set

$$ M_{\tau,\gamma} \stackrel{\text{def}}{=} \sup_{(x,t,y,s) \in \mathcal{M}_T^2} \Psi_{\tau,\gamma}(x,t,y,s). $$

Again by upper semi-continuity and compactness, the supremum $M_{\tau,\gamma}$ is actually a maximum attained at some point $(x_\gamma, t_\gamma, y_\gamma, s_\gamma) \in \mathcal{M}_T^2$. We also have for $\tau$ small enough

$$ M_{\tau,\gamma} = \Psi_{\tau,\gamma}(x_\gamma, t_\gamma, y_\gamma, s_\gamma) \geq \Psi_{\tau,\gamma}(x_\tau, t_\tau, x_\tau, t_\tau) = \Psi_\tau(x_\tau, t_\tau) = M_\tau > 0, $$

which implies that

$$ \frac{|t_\gamma - s_\gamma|^2}{2\gamma} + \frac{d_{\mathcal{M}}^2(x_\gamma, y_\gamma)}{2\gamma} \leq f(x_\gamma, t_\gamma) - g(y_\gamma, s_\gamma) \leq \|f\|_{L^\infty(\mathcal{M}_T)} + \|g\|_{L^\infty(\mathcal{M}_T)}. $$

We then get

$$ (4) \qquad |t_\gamma - s_\gamma|, \quad d_{\mathcal{M}}(x_\gamma, y_\gamma) \leq c\sqrt{\gamma}, $$

where $c$ is a constant depending only on $\|f\|_{L^\infty(\mathcal{M}_T)}$ and $\|g\|_{L^\infty(\mathcal{M}_T)}$. Using classical arguments (see, e.g. [3, Lemma 5.2]), we deduce that there exists $(\bar{x}, \bar{t}) \in \mathcal{M} \times [0, T[$ such that

$$ (5) \qquad \left\{ \begin{array}{ll} x_\gamma, y_\gamma \to \bar{x}, & \text{as } \gamma \to 0, \\ t_\gamma, s_\gamma \to \bar{t}, & \text{as } \gamma \to 0, \\ \Psi_\tau(\bar{x}, \bar{t}) = M_\tau. \end{array} \right. $$

If $\bar{t} = 0$, then

$$ 0 < M_\tau = f(\bar{x}, 0) - g(\bar{x}, 0) - \frac{\tau}{T} \leq f_0(\bar{x}) - f_0(\bar{x}) - \frac{\tau}{T} < 0, $$

leading to a contradiction. Then $\bar{t} > 0$, which implies, by (5) that $t_\gamma, s_\gamma > 0$, for $\gamma$ small enough. Moreover, if $\bar{x} \in \Gamma$, then

$$ 0 < M_\tau \leq f(\bar{x}, \bar{t}) - g(\bar{x}, \bar{t}) = f_0(\bar{x}) - f_0(\bar{x}) = 0, $$

which is again absurd. Thus $x_\gamma, y_\gamma \in \mathcal{M} \setminus \Gamma$ for $\gamma$ small enough.

The mapping $(x,t) \in \mathcal{M}_T \mapsto f(x,t) - \varphi_1(x,t)$, where

$$ \varphi_1(x,t) = g(y_\gamma, s_\gamma) + \frac{d_{\mathcal{M}}^2(x, y_\gamma)}{2\gamma} + \frac{|t - s_\gamma|^2}{2\gamma} + \frac{\tau}{T - t}, $$

is smooth on a small neighborhood $\mathcal{N}_{(x_\gamma, t_\gamma)}^\gamma$ (since $d_{\mathcal{M}}^2(\cdot, y_\gamma)$ is of class $C^1$, for $\gamma$ small enough, in view of (4) and (H.7), see Remark 2.15). Since $f$ is a viscosity sub-solution of (P) and $f - \varphi_1$ reaches a maximum at $(x_\gamma, t_\gamma)$, we deduce that

$$ \frac{t_\gamma - s_\gamma}{\gamma} + \frac{\tau}{T^2} \leq - \left\| \mathrm{grad}_x \left( \frac{d_{\mathcal{M}}^2(x_\gamma, y_\gamma)}{2\gamma} \right) \right\|_{x_\gamma} + P(x_\gamma). $$

Using Lemma 2.14 and Proposition 2.12, we deduce that

$$ (6) \qquad \frac{t_\gamma - s_\gamma}{\gamma} + \frac{\tau}{T^2} \leq - \frac{d_{\mathcal{M}}^2(x_\gamma, y_\gamma)}{\gamma} + P(x_\gamma). $$
Similarly, the mapping $(y, s) \in \mathcal{M}_T \mapsto g(y, s) - \varphi_2(y, s)$, where

$$ \varphi_2(y, s) = f(x_\gamma, t_\gamma) - \frac{d_{\mathcal{M}}^2(x_\gamma, y)}{2\gamma} - \frac{|t_\gamma - s|^2}{2\gamma} - \frac{\tau}{T - t_\gamma}, $$

is smooth on $\mathcal{N}_{(y_\gamma, s_\gamma)}^\gamma$. Since $g - \varphi_2$ attains a local minimum at $(y_\gamma, s_\gamma)$ and since $g$ is a viscosity super-solution of $(\mathcal{P})$, we obtain that

$$ (7) \qquad \frac{t_\gamma - s_\gamma}{\gamma} \geq -\frac{d_{\mathcal{M}}(x_\gamma, y_\gamma)}{\gamma} + P(y_\gamma). $$

Now subtracting (6) and (7), and then using (4), we obtain

$$ \frac{\tau}{T^2} \leq P(x_\gamma) - P(y_\gamma) \leq L_P d_{\mathcal{M}}(x_\gamma, y_\gamma) \leq L_P c \sqrt{\gamma}. $$

Passing to the limit as $\gamma \to 0$ leads to a contradiction. $\square$

We now turn to the existence of the solution. In order to do that, we will assume a compatibility property between the equation and the boundary conditions in order to construct solutions to $(\mathcal{P})$:

(H.13) There exists $\psi_b \in \text{Lip}(\mathcal{M})$, with $\psi_b(x) = f_0(x)$ for all $x \in \Gamma$, such that $\psi_b$ is a sub-solution of $(\mathcal{P})$ in $\mathcal{M}_T$.

Assumption (H.13) is satisfied, for instance, when $f_0 = 0$ and $P \ge 0$ in $(\mathcal{P})$. This setting corresponds to a time-dependent Eikonal equation whose solution can be interpreted as the minimal amount of time or distance required to travel from a point $x \in \mathcal{M}$ to the front $\Gamma$, where the travel speed is the inverse of $P$. For instance, it enables a fast calculation of geodesic distances using the fast marching method [21, 33].

**Remark 3.4.** Assumption (H.13) entails in particular that

$$ \|\text{grad } \psi_b(x)\|_x \le \|P\|_{L^\infty(\mathcal{M}\setminus\Gamma)}, $$

and thus the Lipschitz constant $L_{\psi_b}$ satisfies

$$ L_{\psi_b} \le \|P\|_{L^\infty(\mathcal{M}\setminus\Gamma)}. $$

We then have the following result.

**Proposition 3.5** (Existence and uniqueness for $(\mathcal{P})$). Suppose that assumptions (H.1)-(H.6) and (H.13) hold. Then, problem $(\mathcal{P})$ admits a unique viscosity solution $f$. Moreover, there exists a function $\bar{f} \in \text{Lip}(\mathcal{M}_T)$, with a Lipschitz constant depending on $a_0$, $d_0$, $L_{f_0}$ and $\|P\|_{L^\infty(\mathcal{M}\setminus\Gamma)}$, such that

$$ (8) \qquad \psi_b \le f \le \bar{f} \quad \text{on } \mathcal{M}_T. $$

In order to give the proof of this proposition, we need to define the notion of barrier solutions and then recall the Perron's method.

**Definition 3.6** (Barrier sub- and super-solution). An usc function $f: \mathcal{M}_T \to \mathbb{R}$ is a barrier sub-solution of $(\mathcal{P})$ if it is a viscosity sub-solution in $(\mathcal{M}\setminus\Gamma) \times ]0, T[$ and if it satisfies moreover

$$ \lim_{y \to x, s \to t} \underline{f}(y, s) = f_0(x) \quad \forall (x, t) \in \Gamma \times ]0, T]. $$

A lsc function $\bar{f}: \mathcal{M}_T \to \mathbb{R}$ is a barrier super-solution of $(\mathcal{P})$ if it is a viscosity super-solution in $(\mathcal{M}\setminus\Gamma) \times ]0, T[$ and if it satisfies moreover

$$ \lim_{y \to x, s \to t} \bar{f}(y, s) = f_0(x) \quad \forall (x, t) \in \Gamma \times ]0, T]. $$
**Theorem 3.7** (Perron's method). Assume that there exists a barrier sub-solution $f$ and a barrier super-solution $\bar{f}$ of (P). Then there exists a (possibly discontinuous) viscosity solution $f$ of (P) satisfying moreover

$$ \underline{f} \le f \le \bar{f} \quad \text{in } \mathcal{M}_T. $$

The proof of the Perron's method for Hamilton-Jacobi equations defined on manifolds can be found in [17, Theorem 8.2].

*Proof of Proposition 3.5.* By assumption (H.13), $\psi_b$ is a barrier sub-solution of (P). We then have to construct a barrier super-solution $\bar{f}$. Existence will then be a direct consequence of the Perron's method as recalled in Theorem 3.7 while uniqueness and continuity will be direct consequences of the comparison principle shown in Proposition 3.3.

Let

$$ \bar{f}_1(x, t) = f_0(x) + K_1 t, \quad \text{and} \quad \bar{f}_2(x, t) = f_0(x) + K_2 \tilde{d}(x, \Gamma), \quad (x, t) \in \mathcal{M}_T, $$

where $K_1 = \|P\|_{L^\infty(\mathcal{M}\setminus\Gamma)}$, and $K_2 > 0$ is a large enough constant to be determined later. We set

$$ (9) \qquad \bar{f}(x, t) = \min(\bar{f}_1(x, t), \bar{f}_2(x, t)) = \min(f_0(x) + K_1 t, f_0(x) + K_2 \tilde{d}(x, \Gamma)). $$

We claim that $\bar{f}$ is a barrier super-solution for $K_2$ well-chosen.

First, observe that

$$ L_{\bar{f}} \le \max(L_{\bar{f}_1}, L_{\bar{f}_2}) \le L_{f_0} + \max(\|P\|_{L^\infty(\mathcal{M}\setminus\Gamma)}, K_2), $$

since $f_0 \in \text{Lip}(\mathcal{M})$ by (H.5) and $L_{\tilde{d}(\cdot, \Gamma)} = 1$ as $\Gamma \ne \emptyset$. In particular, $\bar{f}$ is continuous.

Moreover, we have for $x \in \Gamma$,

$$ \bar{f}_2(x, t) = f_0(x) \le \bar{f}_1(x, t). $$

Hence

$$ (10) \qquad \bar{f}(x, t) = f_0(x), \quad \forall (x, t) \in \Gamma \times [0, T], $$

which shows, via continuity that the limit property required in Definition 3.6 holds. It remains to prove that $\bar{f}$ is a super-solution on $(\mathcal{M}\setminus\Gamma)\times]0, T[$ for $K_2$ large enough.

Observe first that by taking $K_2 \ge K_1T/a_0$, we have for all $x \in \mathcal{M}\setminus\mathcal{N}_\Gamma^{a_0}$ (recall that $a_0$ and $\mathcal{N}_\Gamma^{a_0}$ are defined in assumption (H.6)),

$$ \bar{f}_2(x, t) \ge f_0(x) + K_2 a_0 \ge f_0(x) + K_1 T \ge \bar{f}_1(x, t), $$

and thus (9) becomes

$$ (11) \qquad \bar{f}(x, t) = \begin{cases} \min(\bar{f}_1(x, t), \bar{f}_2(x, t)) & \text{if } (x, t) \in \mathcal{N}_\Gamma^{a_0} \times [0, T], \\ \bar{f}_1(x, t) & \text{if } (x, t) \in \mathcal{M}\setminus\mathcal{N}_\Gamma^{a_0} \times [0, T]. \end{cases} $$

Following Definition 3.1, consider $\varphi \in (\mathcal{M}\setminus\Gamma)\times]0, T[$ such that $\bar{f} - \varphi$ reaches a local minimum at some point $(x_0, t_0) \in (\mathcal{M}\setminus\Gamma)\times]0, T[$ and such that $\varphi \in C^1$ on a small neighborhood of $(x_0, t_0)$. This is equivalent to

$$ (12) \qquad \bar{f}(y, s) - \varphi(y, s) \ge \bar{f}(x_0, t_0) - \varphi(x_0, t_0), $$

for all $(y, s) \in (\mathcal{M}\setminus\Gamma)\times]0, T[$ sufficiently close to $(x_0, t_0)$. We now distinguish two cases.

**Case 1** $x_0 \in \mathcal{M}\setminus\mathcal{N}_\Gamma^{a_0}$. In this case, since $(\mathcal{M}\setminus\mathcal{N}_\Gamma^{a_0}) \subset (\mathcal{M}\setminus\Gamma)$, it follows from (11) and (12) that

$$ \bar{f}_1(y, s) - \varphi(y, s) \ge \bar{f}(y, s) - \varphi(y, s) \ge \bar{f}_1(x_0, t_0) - \varphi(x_0, t_0), $$

for all $(y, s) \in (\mathcal{M}\setminus\Gamma)\times]0, T[$ sufficiently close to $(x_0, t_0)$. As $]0, T[$ is open, we take $y = x_0$ and $s = t_0 + h \in]0, T[$ for $h > 0$ sufficiently small, which gives us

$$ (13) \qquad \varphi(x_0, t_0 + h) - \varphi(x_0, t_0) \le \bar{f}_1(x_0, t_0 + h) - \bar{f}_1(x_0, t_0) = K_1 h. $$
Dividing by $h$ and passing to the limit as $h \to 0^+$, we get

$$ (14) \qquad \frac{\partial}{\partial t} \varphi(x_0, t_0) \le K_1. $$

Embarking from (13) where we replace $h$ by $-h$ yields

$$ (15) \qquad \frac{\partial}{\partial t} \varphi(x_0, t_0) \ge K_1, $$

and thus

$$ (16) \qquad \frac{\partial}{\partial t} \varphi(x_0, t_0) = K_1. $$

We then deduce that

$$ (17) \qquad \frac{\partial}{\partial t} \varphi(x_0, t_0) + \|\mathrm{grad}\varphi(x_0, t_0)\| - P(x_0) \ge K_1 - P(x_0) \ge K_1 - \|P\|_{L^\infty(\mathcal{M}\setminus\Gamma)} = 0, $$

which shows the desired inequality in this case.

**Case 2** $x_0 \in \mathcal{N}_\Gamma^{a_0} \setminus \Gamma$. Let $I_0 \stackrel{\text{def}}{=} \{i \in \{1, 2\} : \bar{f}(x_0, t_0) = \bar{f}_i(x_0, t_0)\}$. Thus, for any $i_0 \in I_0$, we have from (12) that

$$ (18) \qquad \bar{f}_{i_0}(y, s) - \varphi(y, s) \ge \bar{f}(y, s) - \varphi(y, s) \ge \bar{f}(x_0, t_0) - \varphi(x_0, t_0) = \bar{f}_{i_0}(x_0, t_0) - \varphi(x_0, t_0) $$

for all $y \in \mathcal{N}_\Gamma^{a_0} \setminus \Gamma$ close enough to $x_0$. If $1 \in I_0$ we argue as in **Case 1** to get a contradiction. It remains to consider the case where $I_0 = \{2\}$. Embarking from (18) with $i_0 = 2$, arguing as we have done for $\bar{f}_1$ in **Case 1** to show (16), and using that $\bar{f}_2$ is actually $t$-independent, we get in this case that

$$ (19) \qquad \frac{\partial}{\partial t} \varphi(x_0, t_0) = 0. $$

On the other hand, let $v \in T_{x_0}\mathcal{M}$ where $\|v\|_{x_0} < 1$ and let $\gamma$ be a differentiable curve in $\mathcal{M}$ such that $\gamma(0) = x_0$ and $\dot{\gamma}(0) = v$. Since $\mathcal{N}_\Gamma^{a_0} \setminus \Gamma$ is open by (H.3) and (H.6), we can choose $h$ small enough so that $\gamma(h) \in \mathcal{N}_\Gamma^{a_0} \setminus \Gamma$ and $\|\dot{\gamma}(s)\|_{\gamma(s)} \le 1$ for all $s \in [0, h]$. This is obtained by the continuity of $t \mapsto \|\dot{\gamma}(t)\|$ and having that $\|\dot{\gamma}(0)\|_{x_0} < 1$. Thus, inequality (18) with $i_0 = 2$, $s = t_0$ and $y = \gamma(h)$ becomes

$$ \begin{aligned} \frac{(\varphi(\cdot, t_0) - K_2 \tilde{d}(\cdot, \Gamma))(\gamma(h)) - (\varphi(\cdot, t_0) - K_2 \tilde{d}(\cdot, \Gamma))(x_0)}{h} &\le \frac{f_0(\gamma(h)) - f_0(x_0)}{h} \\ &\le \frac{L_{f_0} d_{\mathcal{M}}(\gamma(0), \gamma(h))}{h} \\ &\le \frac{1}{h} L_{f_0} \int_0^h \|\dot{\gamma}(s)\|_{\gamma(s)} ds \\ &\le L_{f_0}. \end{aligned} $$

Passing to the limit as $h \to 0^+$ and taking the maximum over $v$, we get

$$ \|\mathrm{grad}\varphi(x_0, t_0) - K_2 \mathrm{grad}\tilde{d}(x_0, \Gamma)\|_{x_0} \le L_{f_0}. $$

Combining this inequality with (19) and (H.6), we get

$$ (20) \qquad \begin{aligned} &\frac{\partial}{\partial t} \varphi(x_0, t_0) + \|\mathrm{grad}\varphi(x_0, t_0)\|_{x_0} - P(x_0) \\ &\ge K_2 \|\mathrm{grad}\tilde{d}(x_0, \Gamma)\|_{x_0} - \|\mathrm{grad}\varphi(x_0, t_0) - K_2 \mathrm{grad}\tilde{d}(x_0, \Gamma)\|_{x_0} - P(x_0) \\ &\ge K_2 d_0 - L_{f_0} - \|P\|_{L^\infty(\mathcal{M}\setminus\Gamma)} \ge 0, \end{aligned} $$

for $K_2 \ge (L_{f_0} + \|P\|_{L^\infty(\mathcal{M}\setminus\Gamma)})/d_0$.
In summary, taking $K_2 \ge \max((L_{f_0} + \|P\|_{L^\infty(\mathcal{M}\setminus\Gamma)})/d_0, K_1T/a_0)$, inequalities (17) and (20) hold in each respective case, and thus the desired super-solution inequality is satisfied in all cases. We then conclude that $\bar{f}$ is a barrier super-solution. The existence of $f$ and the bound (8) are then direct consequences of Perron's method. □

We will now provide regularity results for the solution of (P). For the space regularity, we will need to use the regularity of the Riemannian distance.

**Theorem 3.8** (Regularity of the solution of (P)). Suppose that assumptions (H.1)-(H.7) and (H.13) hold. Then the viscosity solution to the problem (P) satisfies the following regularity properties

$$ (21) \qquad f(x, \cdot) \in \text{Lip}([0, T]) \quad \text{with} \quad L_{f(x, \cdot)} \le L_{f_0} + \|P\|_{L^\infty(\mathcal{M}\setminus\Gamma)}, \forall x \in \mathcal{M}. $$

For all $x, y$ such that $d_{\mathcal{M}}(x, y) \le \delta$ (with $\delta$ defined in assumption (H.7)), we have

$$ (22) \qquad |f(x,t) - f(y,t)| \le K d_{\mathcal{M}}(x,y) \quad \text{with} \quad K = L_{f_0} + 2\|P\|_{L^\infty(\mathcal{M}\setminus\Gamma)}, \forall t \in [0, T], $$

*Proof.* If $x \in \Gamma$, (21) obviously holds. We then consider the case $(x, t) \in (\mathcal{M}\setminus\Gamma) \times ]0, T[$, and we first show that for any $t \in [0, T[$,

$$ (23) \qquad |f(x,t) - f(x,0)| \le L t, $$

where $L = \|P\|_{L^\infty(\mathcal{M}\setminus\Gamma)} + L_{f_0}$. We define for $(x, t) \in \mathcal{M}_T$,

$$ f_1(x,t) = f_0(x) - Lt \quad \text{and} \quad f_2(x,t) = f_0(x) + Lt. $$

We claim that $f_1$ (resp. $f_2$) is a sub-solution (resp. super-solution) of (P). We have $f_1 \le f_0$ on $\partial\mathcal{M}_T$. Now define $\varphi \in (\mathcal{M}\setminus\Gamma) \times ]0, T[$ such that $f_1 - \varphi$ reaches a local maximum at some $(x_0, t_0) \in (\mathcal{M}\setminus\Gamma) \times ]0, T[$ and such that $\varphi \in C^1$ on a small neighborhood of $(x_0, t_0)$. This is equivalent to

$$ (24) \qquad \varphi(x_0, t_0) - \varphi(x, t) \le f_1(x_0, t_0) - f_1(x, t) $$

for all $(x, t) \in (\mathcal{M}\setminus\Gamma) \times ]0, T[$ sufficiently close to $(x_0, t_0)$. Since $]0, T[$ is open, we take $x = x_0$ and $t = t_0 - h \in ]0, T[$ for $h > 0$ sufficiently small, and we get

$$ (25) \qquad \varphi(x_0, t_0) - \varphi(x_0, t_0 - h) \le f_1(x_0, t_0) - f_1(x_0, t_0 - h) = -Lh $$

Dividing by $h$ and passing to the limit, we get

$$ (26) \qquad \frac{\partial}{\partial t} \varphi(x_0, t_0) \le -L. $$

On the other hand, let $v \in T_{x_0}\mathcal{M}$ with $\|v\|_{x_0} < 1$ and let $\gamma:] - 1, 1[ \to \mathcal{M}$ be a differentiable curve in $\mathcal{M}$ such that $\gamma(0) = x_0$ and $\dot{\gamma}(0) = v$. Since $\mathcal{M}\setminus\Gamma$ is open, we can choose $h$ small enough so that $\gamma(-h) \in \mathcal{M}\setminus\Gamma$ and $\|\dot{\gamma}(s)\|_{\gamma(s)} \le 1$ for all $s \in [-h, 0]$. This is obtained thanks to the continuity of $t \mapsto \|\dot{\gamma}(t)\|$ and having that $\|\dot{\gamma}(0)\|_{x_0} < 1$. By (24), taking $t = t_0$ and $x = \gamma(-h)$, we have

$$ \begin{aligned} \frac{\varphi(\gamma(0), t_0) - \varphi(\gamma(-h), t_0)}{h} &\le \frac{f_0(x_0) - f_0(\gamma(-h))}{h} \\ &\le L_{f_0} \frac{d_{\mathcal{M}}(\gamma(0), \gamma(-h))}{h} \\ &\le \frac{1}{h} L_{f_0} \int_{-h}^{0} \|\dot{\gamma}(s)\|_{\gamma(s)} ds \\ &\le L_{f_0}. \end{aligned} $$
Passing to the limit as $h \to 0$ and taking the maximum over $v$, we get

$$ \|\mathrm{grad}\varphi(x_0, t_0)\|_{x_0} \le L_{f_0}. $$

We then deduce that

$$ (27) \qquad \begin{aligned} \frac{\partial}{\partial t}\varphi(x_0, t_0) + \|\mathrm{grad}\varphi(x_0, t_0)\|_{x_0} - P(x_0) &\le -L + L_{f_0} - P(x_0) \\ &\le -L + L_{f_0} + \|P\|_{L^\infty(\mathcal{M}\setminus\Gamma)} \\ &\le 0. \end{aligned} $$

Therefore, this shows our claim on $f_1$. Arguing in the same way, we can prove that $f_2$ is a super-solution of (P). Applying the comparison principle Proposition 3.3 twice yields that for any $(x, t) \in \mathcal{M} \times [0, T[$,

$$ f_0(x) - Lt \le f(x, t) \le f_0(x) + Lt, $$

which shows (23). For $h > 0$ sufficiently small, we then consider the function $l(x, t) = f(x, t + h)$ for all $(x, t) \in \mathcal{M}_T$. Then it is easy to verify that $l$ satisfies (P). This implies that $f(x, t)$ and $f(x, t + h)$ are solutions of the same equation (P), with initial conditions respectively $f_0(x)$ and $f(x, h)$. Applying again the comparison result (see Proposition 3.3) and using (23), we obtain for any $(x, t) \in \mathcal{M} \times [0, T[$, that

$$ (28) \qquad \begin{aligned} |f(x, t + h) - f(x, t)| &\le |f(x, h) - f(x, 0)| \\ &\le Lh. \end{aligned} $$

Passing to the limit as $h \to 0$ shows the time regularity claim.

We now turn to the space regularity bound (22) and adapt the argument of [3, Theorem 8.2]. Let $\delta' < \delta$ and $x, y \in \mathcal{M}$ such that $d_{\mathcal{M}}(x, y) \le \delta'$. We introduce the test-function

$$ \Psi : (x, t, y) \in \mathcal{M}_T \times \mathcal{M} \mapsto f(x, t) - f(y, t) - K d_{\mathcal{M}}(x, y), $$

and we aim to show that this function is non-positive for every $K > \|P\|_{L^\infty(\mathcal{M}\setminus\Gamma)} + L$. We argue by contradiction and assume that

$$ \sup_{(x,t,y) \in \mathcal{M}_T \times \mathcal{M}} \Psi(x, t, y) > 0. $$

Since $\Psi$ is continuous over $\mathcal{M}_T \times \mathcal{M}$ which is compact, the supremum is actually a maximum attained at some point $(\bar{x}, \bar{t}, \bar{y}) \in \mathcal{M}_T \times \mathcal{M}$ with $\bar{x} \ne \bar{y}$ (otherwise $\Psi(\bar{x}, \bar{t}, \bar{y}) = 0$). In order to use viscosity solutions arguments, we introduce the function, for $\alpha > 0$,

$$ \Psi_{\alpha} : (x, t, y, s) \in \mathcal{M}_T^2 \mapsto f(x, t) - f(y, s) - K d_{\mathcal{M}}(x, y) - \frac{|t - s|^2}{2\alpha}. $$

Since $f$ is continuous and $\mathcal{M}_T$ is compact, the supremum of $\Psi_\alpha$ is actually a maximum attained at some point $(x_\alpha, t_\alpha, y_\alpha, s_\alpha) \in \mathcal{M}_T^2$. In particular, we have

$$ (29) \qquad \Psi_{\alpha}(x_{\alpha}, t_{\alpha}, y_{\alpha}, s_{\alpha}) \ge \Psi_{\alpha}(\bar{x}, \bar{t}, \bar{y}, \bar{t}) = \Psi(\bar{x}, \bar{t}, \bar{y}) > 0. $$

Observe also that for $\alpha$ sufficiently small, we cannot have $x_\alpha = y_\alpha$ as otherwise $\Psi_\alpha(x_\alpha, t_\alpha, y_\alpha, s_\alpha)$ would be negative, hence contradicting (29).

If $x_\alpha \in \Gamma$, then $f(x_\alpha, t_\alpha) = f_0(x_\alpha) = \psi_b(x_\alpha)$. Moreover by Proposition 3.5, $\psi_b(y_\alpha) \le f(y_\alpha, s_\alpha)$. It then follows that

$$ \begin{aligned} \Psi_{\alpha}(x_{\alpha}, t_{\alpha}, y_{\alpha}, s_{\alpha}) &\le \psi_{b}(x_{\alpha}) - f(y_{\alpha}, s_{\alpha}) - K d_{\mathcal{M}}(x_{\alpha}, y_{\alpha}) \\ &\le \psi_{b}(x_{\alpha}) - \psi_{b}(y_{\alpha}) - K d_{\mathcal{M}}(x_{\alpha}, y_{\alpha}) \\ &\le (L_{\psi_{b}} - K) d_{\mathcal{M}}(x_{\alpha}, y_{\alpha}) \\ &\le (\|P\|_{L^{\infty}(\mathcal{M}\setminus\Gamma)} - K) d_{\mathcal{M}}(x_{\alpha}, y_{\alpha}) \end{aligned} $$
where we used Remark 3.4. Since $K \ge \|P\|_{L^\infty(\mathcal{M}\setminus\Gamma)}$ we get a contradiction with the positivity of $\Psi_\alpha(x_\alpha, t_\alpha, y_\alpha, s_\alpha)$.

Consider in the rest the case $x_\alpha \in \mathcal{M}\setminus\Gamma$. Classical arguments (see, e.g., [3, Lemma 5.2]) show that $x_\alpha \to x$ and $y_\alpha \to y$. Since $d_{\mathcal{M}}(x, y) \le \delta'$, we can assume that $d_{\mathcal{M}}(x_\alpha, y_\alpha) \le \delta$, for $\alpha$ small enough. Therefore, (H.7) implies that $x_\alpha \notin \text{Cut}(y_\alpha)$. Moreover, $x_\alpha \ne y_\alpha$, and it follows that the function $(x, t) \mapsto f(y_\alpha, s_\alpha) + Kd_{\mathcal{M}}(x, y_\alpha) + \frac{|t-s_\alpha|^2}{2\alpha}$ is smooth at $(x_\alpha, t_\alpha)$. Since $f$ is a sub-solution we have

$$ (30) \qquad \frac{t_\alpha - s_\alpha}{\alpha} + K \le P(x_\alpha), $$

where we used Lemma 2.13 to assert that $\|\text{grad}_y d_{\mathcal{M}}(x_\alpha, y_\alpha)\|_{y_\alpha} = 1$.

On the other hand, since $(x_\alpha, t_\alpha, y_\alpha, s_\alpha)$ is a maximum point of $\psi_\alpha$, we have for any $t \in [0, T]$

$$ f(x_\alpha, t) - \frac{|t - s_\alpha|^2}{2\alpha} \le f(x_\alpha, t_\alpha) - \frac{|t_\alpha - s_\alpha|^2}{2\alpha}. $$

Choosing $t$ such that $t_\alpha - s_\alpha$ and $t_\alpha - t$ are of the same sign, and using (21), we get

$$ \begin{aligned} L|t - t_\alpha| &\ge f(x_\alpha, t_\alpha) - f(x_\alpha, t) \\ &\ge \frac{|t_\alpha - s_\alpha|^2}{2\alpha} - \frac{|t - s_\alpha|^2}{2\alpha}, \end{aligned} $$

now using the polarization identity $(\|X\|^2 + \|Y\|^2 - 2X.Y = \|X - Y\|^2)$, we obtain

$$ L|t - t_\alpha| \ge -\frac{|t - t_\alpha|^2}{2\alpha} + |t - t_\alpha| \frac{|t_\alpha - s_\alpha|}{\alpha}. $$

Dividing by $|t - t_\alpha|$ and taking $t \to t_\alpha$, we get

$$ \frac{|t_\alpha - s_\alpha|}{\alpha} \le L. $$

Injecting this estimate in (30), we arrive to

$$ K \le \|P\|_{L^\infty(\mathcal{M}\setminus\Gamma)} + L. $$

Since $K > \|P\|_{L^\infty(\mathcal{M}\setminus\Gamma)} + L$, we get again a contradiction of the positivity of $\Psi_\alpha(x_\alpha, t_\alpha, y_\alpha, s_\alpha)$ on $\mathcal{M}\setminus\Gamma$. The above proof shows then that

$$ f(x, t) - f(y, t) - Kd_{\mathcal{M}}(x, y) \le 0 $$

for all $(x, y, t) \in \mathcal{M}^2 \times [0, T]$ and every $K > 2\|P\|_{L^\infty(\mathcal{M}\setminus\Gamma)} + L_{f_0}$, i.e., $f(\cdot, t)$ is globally Lipschitz continuous uniformly in $t$, hence providing the bound (22) for $d_{\mathcal{M}}(x, y) \le \delta'$. Taking $\delta' \to \delta$ and $K \to 2\|P\|_{L^\infty(\mathcal{M}\setminus\Gamma)} + L_{f_0}$, we get the desired result. $\square$

### 3.2. Problem $(\mathcal{P}_\varepsilon)$. We begin by the definition of viscosity solution to problem $(\mathcal{P}_\varepsilon)$.

**Definition 3.9** (Viscosity solution for $(\mathcal{P}_\varepsilon)$). An usc function $f^\varepsilon: \widetilde{\mathcal{M}}_T \to \mathbb{R}$ is a viscosity sub-solution to $(\mathcal{P}_\varepsilon)$ in $(\widetilde{\mathcal{M}}\setminus\widetilde{\Gamma}) \times ]0, T[$ if for every $C^1$ function $\varphi: ]0, T[ \to \mathbb{R}$ and every point $(x_0, t_0) \in (\widetilde{\mathcal{M}}\setminus\widetilde{\Gamma}) \times ]0, T[$ such that $f^\varepsilon(x_0, \cdot) - \varphi$ has a local maximum point at $t_0 \in ]0, T[$, we have

$$ \frac{\partial}{\partial t} \varphi(t_0) + |\nabla_{\eta_\varepsilon} f^\varepsilon(x_0, t_0)|_\infty \le \tilde{P}(x_0). $$

The function $f^\varepsilon$ is a viscosity sub-solution to $(\mathcal{P}_\varepsilon)$ in $\widetilde{\mathcal{M}}_T$ if it satisfies moreover $f^\varepsilon(x, t) \le f_0^\varepsilon(x)$ for all $(x, t) \in \partial\widetilde{\mathcal{M}}_T$.
A lsc function $f^\epsilon: \tilde{M}_T \to \mathbb{R}$ is a viscosity super-solution to $(\mathcal{P}_\epsilon)$ in $(\tilde{M}\setminus\tilde{\Gamma})]0, T[$ if for every $C^1$ function $\varphi:]0, T[ \to \mathbb{R}$ and every point $(x_0, t_0) \in (\tilde{M}\setminus\tilde{\Gamma})]0, T[$ such that $f^\epsilon(x_0, \cdot) - \varphi$ has a local minimum point at $t_0$, we have

$$ \frac{\partial}{\partial t}\varphi(t_0) + |\nabla_{\eta_\epsilon} f^\epsilon(x_0, t_0)|_\infty \geq \tilde{P}(x_0). $$

The function $f^\epsilon$ is a viscosity super-solution to $(\mathcal{P}_\epsilon)$ in $\tilde{M}_T$ if it satisfies moreover $f^\epsilon(x, t) \geq f_0^\epsilon(x)$ for all $(x, t) \in \partial\tilde{M}_T$.

Finally, a locally bounded function $f^\epsilon: \tilde{M}_T \to \mathbb{R}$ is a viscosity solution to $(\mathcal{P}_\epsilon)$ in $\tilde{M}_T$ (resp. in $(\tilde{M}\setminus\tilde{\Gamma})]0, T[$ if $(f^\epsilon)^*$ is a viscosity sub-solution and $(f^\epsilon)_*$ is a viscosity super-solution to $(\mathcal{P}_\epsilon)$ in $\tilde{M}_T$ (resp. in $(\tilde{M}\setminus\tilde{\Gamma})]0, T[$).

**Proposition 3.10** (Comparison principle for $(\mathcal{P}_\epsilon)$). Suppose that assumptions (H.1)-(H.3) and (H.9) hold. Assume that $f^\epsilon$ is a bounded viscosity sub-solution to $(\mathcal{P}_\epsilon)$ and $g^\epsilon$ is a viscosity super-solution to $(\mathcal{P}_\epsilon)$. Then

$$ f^{\epsilon} \le g^{\epsilon} \quad \text{in } \tilde{M}_T. $$

*Proof.* Since problem $(\mathcal{P}_\epsilon)$ doesn't see the space differential of the solution, the proof is the same as the one of [16, Theorem 2.10] and we skip it. $\square$

In the same vein as for problem $(\mathcal{P})$, the following assumption is intended to impose compatibility properties between $(\mathcal{P}_\epsilon)$ and the boundary conditions on $\partial\tilde{M}_T$:

(H.14) There exists $\tilde{\psi}_b \in \text{Lip}(\tilde{M})$, with $\tilde{\psi}_b(x) = f_0^\epsilon(x)$ for all $x \in \tilde{\Gamma}$, such that $\tilde{\psi}_b$ is a sub-solution of $(\mathcal{P}_\epsilon)$ in $\tilde{M}_T$.

**Remark 3.11.** Likewise, assumption (H.14) entails that the Lipschitz constant $L_{\tilde{\psi}_b}$ satisfies

$$ L_{\tilde{\psi}_b} \le \|\tilde{P}\|_{L^\infty(\tilde{M}\setminus\tilde{\Gamma})}. $$

**Remark 3.12.** Referring to Remark 3.4, we can find a discussion concerning this assumption, which is similar to the one made in the local case. Specifically, when $f_0^\epsilon = 0$ and $\tilde{P} \ge 0$, (H.14) holds. This example, when applied to weighted graphs (see Section 5), corresponds to the computation of distances on data that can be represented as a weighted graph such that point clouds, discrete images and meshes. For further details, please refer to [11, 36] and references therein.

We are now ready to provide an existence result. As for the local case, the proof is based on Perron's method and the construction of barriers.

**Proposition 3.13** (Existence result for $(\mathcal{P}_\epsilon)$). Suppose that assumptions (H.1)-(H.5), (H.9)-(H.11) and (H.14) hold. Then, problem $(\mathcal{P}_\epsilon)$ admits a unique viscosity solution $f^\epsilon$ (which is in fact continuous). Moreover, there exists a function $\bar{f}^\epsilon \in \text{Lip}(\tilde{M})$ such that

$$ (31) \qquad \tilde{\psi}_b \le f^\epsilon \le \bar{f}^\epsilon \quad \text{in } \tilde{M}_T. $$

*Proof.* The proof is the same as the one of [16, Proposition 2.12] and we skip it. $\square$

**Theorem 3.14** (Time and space regularity properties for $(\mathcal{P}_\epsilon)$). Suppose that assumptions (H.1)-(H.5), (H.8)-(H.12) and (H.14) hold. Let $f^\epsilon$ be the bounded continuous viscosity solution to $(\mathcal{P}_\epsilon)$. Then

$$ (32) \qquad f^{\epsilon}(x, \cdot) \in \text{Lip}([0, T[ \text{ with } L_{f^{\epsilon}(x, \cdot)}} \le L, \quad \forall x \in \mathcal{M}, $$
where

$$L = L_{0}^{\epsilon} + \|\tilde{P}\|_{L^{\infty}(\tilde{M}\setminus\tilde{\Gamma})}.$$

Moreover, for all $(x, y) \in \tilde{M}^2$ and $t \in [0, T[$ such that $\tilde{d}(x, y) \le a\epsilon$, where a is defined in (H.11), we have

$$(33) \quad |f^{\epsilon}(x,t) - f^{\epsilon}(y,t)| \le \max \left( (a + C_M) \|\tilde{P}\|_{L^{\infty}(\tilde{M}\setminus\tilde{\Gamma})}, c_{\eta}^{-1} C_{\eta} (L + \|\tilde{P}\|_{L^{\infty}(\tilde{M}\setminus\tilde{\Gamma})}) \right) \epsilon.$$

Assume also that for $(x, y) \in \tilde{M}^2$, there exists $k(\epsilon) \in \mathbb{N}$ and a path $(x_1 = x, x_2, \dots, x_{k(\epsilon)} = y)$ with $\tilde{d}(x_i, x_{i+1}) \le a\epsilon$, $i = 1, \dots, k(\epsilon) - 1$. Then for all $t \in [0, T[$, we have

$$(34) \quad |f^{\epsilon}(x,t) - f^{\epsilon}(y,t)| \le \max \left( (a + C_M) \|\tilde{P}\|_{L^{\infty}(\tilde{M}\setminus\tilde{\Gamma})}, c_{\eta}^{-1} C_{\eta} (L + \|\tilde{P}\|_{L^{\infty}(\tilde{M}\setminus\tilde{\Gamma})}) \right) k(\epsilon) \epsilon.$$

*Proof.* The proof of (32) is the same as the proof of the first part of [16, Theorem 2.15]. We begin by the proof of the space regularity estimate (33). Let $(x, t) \in \tilde{M}_T$. If $x \in \partial \tilde{M}_T$, then

$$\begin{aligned} f^{\epsilon}(x,t) - f^{\epsilon}(y,t) &\le \tilde{\psi}_{b}(x) - \tilde{\psi}_{b}(y) \\ &\le L_{\tilde{\psi}_{b}} d_{M}(x,y) \\ &\le \|\tilde{P}\|_{L^{\infty}(\tilde{M}\setminus\tilde{\Gamma})} (\tilde{d}(x,y) + C_{M}\epsilon^{1+\xi}) \\ &\le (a + C_{M})\epsilon \|\tilde{P}\|_{L^{\infty}(\tilde{M}\setminus\tilde{\Gamma})}, \end{aligned}$$

and (33) holds. Assume now that $(x, t) \in (\tilde{M}\setminus\tilde{\Gamma}) \times ]0, T[$ is such that $f^{\epsilon}$ is differentiable in time at $(x, t)$. For such points, we have from $(P_{\epsilon})$ and (32) that

$$(35) \quad |\nabla_{\eta_{\epsilon}}^{-} f^{\epsilon}(x,t)|_{\infty} \le L + \|\tilde{P}\|_{L^{\infty}(\tilde{M}\setminus\tilde{\Gamma})}.$$

Let $y \in \tilde{M}$ be such that $\tilde{d}(x, y) \le a\epsilon$. We then have, recalling (H.11) and (H.12), that

$$\begin{aligned} c_{\eta}(\epsilon C_{\eta})^{-1} (f^{\epsilon}(x,t) - f^{\epsilon}(y,t)) &\le (\epsilon C_{\eta})^{-1} \eta \left( \frac{\tilde{d}(x,y)}{\epsilon} \right) (f^{\epsilon}(x,t) - f^{\epsilon}(y,t)) \\ &\le |\nabla_{\eta_{\epsilon}}^{-} f^{\epsilon}(x,t)|_{\infty} \\ &\le L + \|\tilde{P}\|_{L^{\infty}(\tilde{M}\setminus\tilde{\Gamma})}. \end{aligned}$$

Exchanging the roles of $x$ and $y$, we get that for all $(x, y) \in \tilde{M}^2$ and $t \in [0, T[$ such that $f^{\epsilon}(x, \cdot)$ is differentiable in time

$$|f^{\epsilon}(x,t) - f^{\epsilon}(y,t)| \le \max \left( (a + C_M) \|\tilde{P}\|_{L^{\infty}(\tilde{M}\setminus\tilde{\Gamma})}, c_{\eta}^{-1} C_{\eta} (L + \|\tilde{P}\|_{L^{\infty}(\tilde{M}\setminus\tilde{\Gamma})}) \right) \epsilon.$$

If $f^{\epsilon}(x, \cdot)$ is not differentiable at $t$, then since $f^{\epsilon}(x, \cdot)$ is differentiable almost everywhere, we can deduce that there exists a sequence $(t_n)_{n \in \mathbb{N}}$ such that $t_n$ converges to $t$ and $f^{\epsilon}(x, \cdot)$ is differentiable at $t_n$ for all $n$. By continuity of $f^{\epsilon}(x, \cdot)$ in time, we get the result for all $(x, y) \in \tilde{M}^2$ and $t \in [0, T[$.

The global estimate is now a direct consequence of (33). Indeed, we have

$$\begin{aligned} |f^{\epsilon}(x,t) - f^{\epsilon}(y,t)| &\le \sum_{i=1}^{k(\epsilon)-1} |f^{\epsilon}(x_{i+1},t) - f^{\epsilon}(x_i,t)| \\ &\le \max \left( (a + C_M) \|\tilde{P}\|_{L^{\infty}(\tilde{M}\setminus\tilde{\Gamma})}, c_{\eta}^{-1} C_{\eta} (L + \|\tilde{P}\|_{L^{\infty}(\tilde{M}\setminus\tilde{\Gamma})}) \right) \sum_{i=1}^{k(\epsilon)-1} \epsilon \\ &\le \max \left( (a + C_M) \|\tilde{P}\|_{L^{\infty}(\tilde{M}\setminus\tilde{\Gamma})}, c_{\eta}^{-1} C_{\eta} (L + \|\tilde{P}\|_{L^{\infty}(\tilde{M}\setminus\tilde{\Gamma})}) \right) k(\epsilon) \epsilon. \end{aligned}$$
□

**Lemma 3.15.** Suppose that assumptions (H.1)-(H.14) hold. Let $f^\epsilon$ be the bounded continuous viscosity solution to ($P_\epsilon$). Assume also that

$$ (36) \qquad \max_{x \in \mathcal{M}} d_{\mathcal{M}}(x, \tilde{\mathcal{M}}) \le a\epsilon/8. $$

Then, there exists $\epsilon_0 > 0$ such that for all $\epsilon \in (0, \epsilon_0]$ and for all $(x, y) \in \tilde{\mathcal{M}}^2$ and $t \in [0, T[$, the following holds

$$ (37) \qquad |f^\epsilon(x, t) - f^\epsilon(y, t)| \le K(d_{\mathcal{M}}(x, y) + \epsilon), \\ \text{where } K = 4a^{-1} \max \left( (a + C_{\mathcal{M}}) \|\tilde{P}\|_{L^\infty(\tilde{\mathcal{M}}\setminus\tilde{\Gamma})} c_\eta^{-1} C_\eta (L + \|\tilde{P}\|_{L^\infty(\tilde{\mathcal{M}}\setminus\tilde{\Gamma})}) \right). $$

*Proof.* Let $(x, y) \in \tilde{\mathcal{M}}^2$ and denoted by $\gamma_{xy}$ the geodesic in $\mathcal{M}$ joining $x$ and $y$. We then set $k(\epsilon) = \left[ \frac{4d_{\mathcal{M}}(x,y)}{a\epsilon} \right]$, where $[\cdot]$ denotes the ceiling. For $j \in \{0, \dots, k(\epsilon)\}$, we then define $\tilde{x}_j$ such that

$$ \tilde{x}_j \in \gamma_{xy} \quad \text{and} \quad d_{\mathcal{M}}(x, \tilde{x}_j) = j\delta, $$

where $\delta = d_{\mathcal{M}}(x, y)/k(\epsilon) \le a\epsilon/4$. In particular $\tilde{x}_0 = x$ and $\tilde{x}_{k(\epsilon)} = y$. Since $\gamma_{xy} \subset \mathcal{M}$, the condition (36) implies that for any $i \in \{1, \dots, k(\epsilon) - 1\}$, there exists $x_i \in \tilde{\mathcal{M}}$ such that $d_{\mathcal{M}}(\tilde{x}_i, x_i) \le a\epsilon/8$. We also set $x_0 = \tilde{x}_0 = x$ and $x_{k(\epsilon)} = \tilde{x}_{k(\epsilon)} = y$. We then have

$$ d_{\mathcal{M}}(x_i, x_{i+1}) \le d_{\mathcal{M}}(x_i, \tilde{x}_i) + d_{\mathcal{M}}(\tilde{x}_i, \tilde{x}_{i+1}) + d_{\mathcal{M}}(\tilde{x}_{i+1}, x_{i+1}) \le a\epsilon/4 + \delta \le a\epsilon/2. $$

In view of (H.8), for $\epsilon \le \epsilon_0$, where $\epsilon_0 = (a/(2C_{\mathcal{M}}))^{1/\xi}$, we then have that

$$ \tilde{d}(x_i, x_{i+1}) \le d_{\mathcal{M}}(x_i, x_{i+1}) + C_{\mathcal{M}}\epsilon^{1+\xi} \le a\epsilon. $$

This allows to infer that for any $(x, y) \in \tilde{\mathcal{M}}^2$, there exists a path $(x_0 = x, x_1, \dots, x_{k(\epsilon)} = y)$ such that $x_i \in \tilde{\mathcal{M}}$ and $\tilde{d}(x_i, x_{i+1}) \le a\epsilon$ for all $i$.

Injecting this in (34) and using the fact that

$$ k(\epsilon) \le \frac{4d_{\mathcal{M}}(x, y)}{a\epsilon} + 1, $$

we get the result.

□

**Remark 3.16.** A consequence of the proof of Lemma 3.15 is that, under assumption (36) and (H.8), since $a \le r_\eta$, we have

$$ (38) \qquad \forall x \in \tilde{\mathcal{M}}, \exists y \in \tilde{\mathcal{M}}, y \ne x \text{ such that } \tilde{d}(x, y) \in \epsilon \text{supp}(\eta), $$

This assumption is quite natural. It basically avoids that the non-local operator $|\nabla_{\eta_\epsilon}^{-} f^\epsilon(x, t)|_\infty$ is trivially zero for all $x \in \tilde{\mathcal{M}}$ when $\epsilon$ is too small. In particular, as $\tilde{\mathcal{M}}$ is finite, this condition imposes that $\tilde{\mathcal{M}}$ has to fill out $\mathcal{M}$ at least as fast as the rate at which $\epsilon$ goes to 0.

## 4. CONSISTENCY AND ERROR BOUNDS

In this section, we present some error bounds between the solution to the local problem ($P$) and the one to the non-local one ($P_\epsilon$). We start with a first technical lemma which will be used in the following proofs.
**Lemma 4.1** (Test function and space and time estimations). Suppose that assumptions (H.1)-(H.14) hold. Let $f$ and $f^\epsilon$ be the unique viscosity solutions to $(\mathcal{P})$ and $(\mathcal{P}_\epsilon)$ respectively and consider for $\gamma > 0$ and $\beta > 0$, the test-function

$$ (39) \qquad \Psi_{\gamma,\beta}(x,t,y,s) = f^\epsilon(x,t) - f(y,s) - \frac{d_{\mathcal{M}}^2(x,y)}{2\gamma} - \frac{|t-s|^2}{2\gamma} - \beta t, $$

defined on $\tilde{\mathcal{M}}_T \times \mathcal{M}_T$. Then there exists a maximum point $(\bar{x}, \bar{t}, \bar{y}, \bar{s}) \in \tilde{\mathcal{M}}_T \times \mathcal{M}_T$ of $\Psi_{\gamma,\beta}$. Moreover, there exists a constant $K > 0$ such that $(\bar{x}, \bar{t}, \bar{y}, \bar{s})$ satisfies

$$ (40) \qquad d_{\mathcal{M}}(\bar{x}, \bar{y}) \le K\gamma. $$

and

$$ (41) \qquad |\bar{t} - \bar{s}| \le K(1 + \beta)\gamma. $$

**Proof.** The test-function $\Psi_{\gamma,\beta}$ is continuous (by the continuity of $f$ and $f^\epsilon$) on $\tilde{\mathcal{M}}_T \times \mathcal{M}_T$ which is compact by (H.1)-(H.2). Hence it reaches a maximum at a point $(\bar{x}, \bar{t}, \bar{y}, \bar{s}) \in \tilde{\mathcal{M}}_T \times \mathcal{M}_T$. We have $\Psi_{\gamma,\beta}(\bar{x}, \bar{t}, \bar{y}, \bar{s}) \ge \Psi_{\gamma,\beta}(\bar{x}, \bar{t}, \bar{x}, \bar{s})$ since $\bar{x} \in \tilde{\mathcal{M}}_T \subset \mathcal{M}$ by (H.2). That entails, using (22) (see Theorem 3.8), that

$$ \frac{d_{\mathcal{M}}^2(\bar{x}, \bar{y})}{2\gamma} \le f(\bar{x}, \bar{s}) - f(\bar{y}, \bar{s}) \le K d_{\mathcal{M}}(\bar{x}, \bar{y}), $$

therefore, we obtain that

$$ d_{\mathcal{M}}(\bar{x}, \bar{y}) \le K\gamma. $$

Similarly, we have $\Psi_{\gamma,\beta}(\bar{x}, \bar{t}, \bar{y}, \bar{s}) \ge \Psi_{\gamma,\beta}(\bar{x}, \bar{s}, \bar{y}, \bar{s})$. This implies, using (32) (see Theorem 3.14), that

$$ \frac{|\bar{t} - \bar{s}|^2}{2\gamma} - \beta|\bar{t} - \bar{s}| \le f^\epsilon(\bar{x}, \bar{t}) - f^\epsilon(\bar{x}, \bar{s}) \le K|\bar{t} - \bar{s}|, $$

thus, we get

$$ |\bar{t} - \bar{s}| \le K(1 + \beta)\gamma. $$

□

**4.1. Continuous time non-local to local error bound.** In this section, we provide an error estimate between viscosity solutions to problems $(\mathcal{P}_\epsilon)$ and $(\mathcal{P})$. This estimate will be instrumental in deriving the remaining error bounds. For this, we need to strengthen (36) by assuming:

(H.15) There exists $\nu > 0$ such that $\max_{x \in \mathcal{M}} d_{\mathcal{M}}(x, \tilde{\mathcal{M}}) \le a\epsilon^{1+\nu}/8$.

**Theorem 4.2** (Error bound between the solutions to $(\mathcal{P})$ and $(\mathcal{P}_\epsilon)$). Let $T > 0$ and $\epsilon \in ]0, \epsilon_0]$ where $\epsilon_0 = \min(1, 1/(2r_\eta)^2, (a/(2C_\mathcal{M}))^{1/\xi})$. Suppose that assumptions (H.1)-(H.15) hold, and let $f$ and $f^\epsilon$ be respectively the unique viscosity solutions to $(\mathcal{P})$ and $(\mathcal{P}_\epsilon)$. Then, there exists a constant $K > 0$, depending only on $C_\mathcal{M}$, $\|f_0\|_{L^\infty(\mathcal{M})}$, $\|P\|_{L^\infty(\mathcal{M}\setminus\Gamma)}$, $L_{f_0}$, $L_{f_0^\epsilon}$, $L_P$, $L_{\tilde{P}}$, $\|\eta\|_{L^\infty}$, $L_\eta$, $C_\eta$ and $c_\eta$, such that

$$ \|f^\epsilon - f\|_{L^\infty(\tilde{\mathcal{M}} \times [0, T])} \le K(T+1) \left( \epsilon^{\min(\nu, \xi, 1/2)} + \|P - \tilde{P}\|_{L^\infty(\tilde{\mathcal{M}} \setminus \tilde{\Gamma})} \right) + \|f_0^\epsilon - f_0\|_{L^\infty(\tilde{\mathcal{M}})} + K d_{\tilde{H}}^{\mathcal{M}}(\Gamma, \tilde{\Gamma}). $$

In particular, if $d_{\tilde{H}}^{\mathcal{M}}(\Gamma, \tilde{\Gamma}) = O(\epsilon^{\min(\nu, \xi, 1/2)})$, then

$$ \|f^\epsilon - f\|_{L^\infty(\tilde{\mathcal{M}} \times [0, T])} \le K(T+1) \left( \epsilon^{\min(\nu, \xi, 1/2)} + \|P - \tilde{P}\|_{L^\infty(\tilde{\mathcal{M}} \setminus \tilde{\Gamma})} \right) + \|f_0^\epsilon - f_0\|_{L^\infty(\tilde{\mathcal{M}})}. $$

The fastest convergence rate in $\epsilon$ is then achieved when $\nu = 1/2$ and $\xi = 1/2$ provided that $d_{\tilde{H}}^{\mathcal{M}}(\mathcal{M}, \tilde{\mathcal{M}}) = O(\epsilon^{3/2})$ and $d_{\tilde{H}}^{\mathcal{M}}(\Gamma, \tilde{\Gamma}) = O(\epsilon^{1/2})$.
Proof. The proof is quite similar to the one of [16, Theorem 3.2]. The difference is that in Riemannian space, one is no longer able to use properties that are well-known in Euclidean space e.g. Cauchy-Schwarz inequality, the remarkable identities, and many other properties. The main idea is to replace the Riemannian distance between two points x and y in $\mathcal{M}$ with $\|\text{Exp}^{-1}(y)\|_x$ defined on the tangent space $T_x\mathcal{M}$. Hence, once we are on the tangent space, we can use all the properties locally. In the following, $K$ indicates a positive constant that can change from one line to the other depending on the data.

Step 1. Test-function and maximum point.

According to Lemma 4.1, the test function $\psi_{\gamma,\beta}$ defined by

$$ \Psi_{\gamma,\beta}(x,t,y,s) = f^{\varepsilon}(x,t) - f(y,s) - \frac{d_{\mathcal{M}}^{2}(x,y)}{2\gamma} - \frac{|t-s|^{2}}{2\gamma} - \beta t, $$

attains a maximum point $(\bar{x}, \bar{t}, \bar{y}, \bar{s}) \in \widetilde{\mathcal{M}}_T \times \mathcal{M}_T$. Moreover, we have the following estimates

$$ (42) \qquad d_{\mathcal{M}}(\bar{x}, \bar{y}) \le K\gamma \quad \text{and} \quad |\bar{t} - \bar{s}| \le K(1 + \beta)\gamma. $$

Step 2. Excluding interior points from the maximum.

We show that for $\beta$ large enough, we have either $(\bar{x}, \bar{t}) \in (\mathcal{N}_{\Gamma}^{\alpha} \cap \widetilde{\mathcal{M}}) \times [0, T[ \cup \widetilde{\mathcal{M}} \times \{0\}$ or $(\bar{y}, \bar{s}) \in \mathcal{N}_{\Gamma}^{\alpha} \times [0, T[ \cup \mathcal{M} \times \{0\}$, for $\alpha = \varepsilon^{1/2}$ so that $\alpha > \varepsilon r_{\eta}$ for $\varepsilon \le \varepsilon_0$. We argue by contradiction, assuming that $(\bar{x}, \bar{t}) \in (\widetilde{\mathcal{M}} \setminus \mathcal{N}_{\Gamma}^{\alpha}) \times ]0, T[ \text{ and } (\bar{y}, \bar{s}) \in (\mathcal{M} \setminus \mathcal{N}_{\Gamma}^{\alpha}) \times ]0, T[$. For $\gamma \le \gamma_0$, small enough, $y \mapsto d_{\mathcal{M}}^2(\bar{x}, y)$ is of class $C^1$ by assumption (H.7). Since $(\bar{y}, \bar{s})$ is a minimum point of the function $(y, s) \mapsto f(y, s) - \varphi^1(y, s)$, where

$$ \varphi^1(y, s) = f^{\varepsilon}(\bar{x}, \bar{t}) - \frac{d_{\mathcal{M}}^2(\bar{x}, y)}{2\gamma} - \frac{|\bar{t} - s|^2}{2\gamma} - \beta \bar{t} $$

which is of class $C^1$, for $\gamma$ small enough, and since $f$ is a super-solution of (P), we get

$$ \frac{\bar{t} - \bar{s}}{\gamma} \ge - \frac{\|\text{grad}_y d_{\mathcal{M}}^2(\bar{x}, \bar{y})\|_{\bar{y}}}{2\gamma} + P(\bar{y}). $$

But according to Lemma 2.14 and Proposition 2.12, we have that

$$ \left\| \frac{1}{2} \text{grad}_y d_{\mathcal{M}}^2(\bar{x}, \bar{y}) \right\|_{\bar{y}} = \| - \text{Exp}_{\bar{y}}^{-1}(\bar{x}) \|_{\bar{y}} = d_{\mathcal{M}}(\bar{x}, \bar{y}). $$

We then obtain

$$ (43) \qquad \frac{\bar{t} - \bar{s}}{\gamma} \ge - \frac{d_{\mathcal{M}}(\bar{x}, \bar{y})}{\gamma} + P(\bar{y}). $$

Similarly, since $\bar{t}$ is a maximum point of the function $t \mapsto f^{\varepsilon}(\bar{x}, t) - \varphi^2(t)$, where

$$ \varphi^2(t) = f(\bar{y}, \bar{s}) + \frac{d_{\mathcal{M}}^2(\bar{x}, \bar{y})}{2\gamma} + \frac{|t - \bar{s}|^2}{2\gamma} + \beta t, $$

which is of class $C^1$ and since $f^{\varepsilon}$ is a viscosity sub-solution to (P$_{\varepsilon}$), we get

$$ (44) \qquad \beta + \frac{\bar{t} - \bar{s}}{\gamma} \le - \left| \nabla_{\eta_{\varepsilon}} f^{\varepsilon}(\bar{x}, \bar{t}) \right|_{\infty} + \widetilde{P}(\bar{x}). $$

On the other hand, since $(\bar{x}, \bar{t}, \bar{y}, \bar{s})$ is a maximizer of $\Psi_{\gamma,\beta}$, we have for any $z \in \widetilde{\mathcal{M}}$

$$ (45) \qquad \Psi_{\gamma,\beta}(\bar{x}, \bar{t}, \bar{y}, \bar{s}) - \Psi_{\gamma,\beta}(z, \bar{t}, \bar{y}, \bar{s}) = f^{\varepsilon}(\bar{x}, \bar{t}) - f^{\varepsilon}(z, \bar{t}) - \frac{d_{\mathcal{M}}^2(\bar{x}, \bar{y}) - d_{\mathcal{M}}^2(z, \bar{y})}{2\gamma} \ge 0. $$

By (H.7) and (42), we get that $\bar{y} \notin \text{Cut}\{\bar{x}\}$ and so there exists a unique geodesic $c$ such that $c(0) = \bar{x}$, $c(1) = \bar{y}$ and $L(c) = d_{\mathcal{M}}(\bar{x}, \bar{y})$. Let $0 \le \bar{r}_{\eta} \le r_{\eta}$ such that $C_{\eta} = \bar{r}_{\eta}\eta(\bar{r}_{\eta})$.
We define $\bar{z} = c(s)$ such that $d_M(\bar{x}, \bar{z}) = \varepsilon \bar{r}_\eta$, for $s \in [0, 1]$. In particular $d_M(\bar{x}, \bar{y}) = d_M(\bar{x}, \bar{z}) + d_M(\bar{z}, \bar{y})$. Define $\lambda \in [0, 1]$ such that $d_M(\bar{x}, \bar{z}) = \lambda d_M(\bar{x}, \bar{y})$. We then have

$$d_M(\bar{z}, \bar{y}) = (1 - \lambda)d_M(\bar{x}, \bar{y}).$$

We now fix $\tilde{z} \in \tilde{\mathcal{M}}$ such that $d_M(\tilde{z}, \tilde{z}) \le a\varepsilon^{1+\nu}/8$ (see (H.15)). Using (45), we then have

$$ \begin{aligned} 2\gamma (f^\varepsilon(\bar{x}, \bar{t}) - f^\varepsilon(\tilde{z}, \tilde{t})) &\ge d_M^2(\bar{x}, \bar{y}) - d_M^2(\tilde{z}, \bar{y}) \\ &\ge d_M^2(\bar{x}, \bar{y}) - (d_M(\tilde{z}, \bar{z}) + d_M(\tilde{z}, \bar{y}))^2 \\ &= d_M^2(\bar{x}, \bar{y}) - d_M^2(\tilde{z}, \bar{y}) - d_M^2(\tilde{z}, \tilde{z}) - 2d_M(\tilde{z}, \bar{y})d_M(\tilde{z}, \tilde{z}) \\ &= d_M^2(\bar{x}, \bar{y}) - (1 - \lambda)^2 d_M^2(\bar{x}, \bar{y}) - d_M^2(\tilde{z}, \tilde{z}) - 2d_M(\tilde{z}, \bar{y})d_M(\tilde{z}, \tilde{z}) \\ &= 2\lambda d_M^2(\bar{x}, \bar{y}) - \lambda^2 d_M^2(\bar{x}, \bar{y}) - d_M^2(\tilde{z}, \tilde{z}) - 2d_M(\tilde{z}, \bar{y})d_M(\tilde{z}, \tilde{z}). \end{aligned} \tag{46} $$

It then follows that

$$ \begin{aligned} |\nabla_{\eta\varepsilon}^{-} f^{\varepsilon}(\bar{x}, \bar{t})|_{\infty} &\ge J_{\varepsilon}(\bar{x}, \bar{z})(f^{\varepsilon}(\bar{x}, \bar{t}) - f^{\varepsilon}(\tilde{z}, \tilde{t})) \\ &= J_{\varepsilon}(\bar{x}, \bar{z})(f^{\varepsilon}(\bar{x}, \bar{t}) - f^{\varepsilon}(\tilde{z}, \tilde{t})) + (J_{\varepsilon}(\bar{x}, \bar{z}) - J_{\varepsilon}(\bar{x}, \bar{z})) (f^{\varepsilon}(\bar{x}, \bar{t}) - f^{\varepsilon}(\tilde{z}, \tilde{t})) \\ &\ge \gamma^{-1} \underbrace{\lambda J_{\varepsilon}(\bar{x}, \bar{z}) d_M^2(\bar{x}, \bar{y})}_{\text{T}_1} - (2\gamma)^{-1} \underbrace{\lambda^2 d_M^2(\bar{x}, \bar{y}) J_{\varepsilon}(\bar{x}, \bar{z})}_{\text{T}_2} \\ &\quad - (2\gamma)^{-1} \underbrace{d_M^2(\bar{z}, \tilde{z}) J_{\varepsilon}(\bar{x}, \bar{z})}_{\text{T}_3} - \gamma^{-1} \underbrace{d_M(\bar{z}, \bar{y}) d_M(\bar{z}, \tilde{z}) J_{\varepsilon}(\bar{x}, \bar{z})}_{\text{T}_4} \\ &\quad + \underbrace{(J_{\varepsilon}(\bar{x}, \bar{z}) - J_{\varepsilon}(\bar{x}, \bar{z})) (f^{\varepsilon}(\bar{x}, \bar{t}) - f^{\varepsilon}(\tilde{z}, \tilde{t}))}_{\text{T}_5}. \end{aligned} \tag{47} $$

We now treat each term $T_1, \dots, T_5$. For $T_1$, using $C_\eta = \max_{0 \le t \le r_\eta} t\eta(t) = \bar{r}_\eta\eta(\bar{r}_\eta)$, we have

$$ \begin{aligned} T_1 &= \lambda d_M(\bar{x}, \bar{y}) J_{\varepsilon}(\bar{x}, \bar{z}) d_M(\bar{x}, \bar{y}) \\ &= (\varepsilon C_{\eta})^{-1} \eta \left( \frac{\tilde{d}(\bar{x}, \bar{z})}{\varepsilon} \right) d_M(\bar{x}, \bar{z}) d_M(\bar{x}, \bar{y}) \\ &\ge (\varepsilon C_{\eta})^{-1} \eta \left( \eta \left( \frac{d_M(\bar{x}, \bar{z})}{\varepsilon} \right) - C_M L_{\eta} \varepsilon^{\xi} \right) d_M(\bar{x}, \bar{z}) d_M(\bar{x}, \bar{y}) \\ &= C_{\eta}^{-1} \eta(\bar{r}_{\eta}) \bar{r}_{\eta} d_M(\bar{x}, \bar{y}) - C_{\eta}^{-1} \bar{r}_{\eta} C_M L_{\eta} \varepsilon^{\xi} d_M(\bar{x}, \bar{y}) \\ &= d_M(\bar{x}, \bar{y}) - K \varepsilon^{\xi} \gamma. \end{aligned} \tag{48} $$

Likewise, we have

$$ \begin{aligned} T_2 &= J_{\varepsilon}(\bar{x}, \bar{z}) \lambda^2 d_M^2(\bar{x}, \bar{y}) \\ &= (\varepsilon C_{\eta})^{-1} \eta \left( \frac{\tilde{d}(\bar{x}, \bar{z})}{\varepsilon} \right) d_M^2(\bar{x}, \bar{z}) \\ &\le (\varepsilon C_{\eta})^{-1} \eta \left( \frac{\tilde{d}(\bar{x}, \bar{z})}{\varepsilon} \right) \left( \tilde{d}(\bar{x}, \bar{z}) + C_M \varepsilon^{1+\xi} \right) d_M(\bar{x}, \bar{z}) \\ &\le d_M(\bar{x}, \bar{z}) + K \varepsilon^{\xi} d_M(\bar{x}, \bar{z}) \\ &\le \varepsilon r_{\eta} + K \varepsilon^{1+\xi} \\ &\le K \varepsilon. \end{aligned} \tag{49} $$
Now we turn to bound $T_3$. Using the definition of $\tilde{z}$ and the fact that $\eta$ is bounded, we have

$$ (50) \qquad \begin{aligned} T_3 &= d_{\mathcal{M}}^2(\bar{z}, \tilde{z}) J_{\varepsilon}(\bar{x}, \bar{z}) \\ &\le K(\varepsilon C_{\eta})^{-1} \eta \left( \frac{\tilde{d}(\bar{x}, \bar{z})}{\varepsilon} \right) \varepsilon^{2+2\nu} \\ &\le K \varepsilon^{1+2\nu}. \end{aligned} $$

To bound $T_4$, we have, using (42), the definition of $\tilde{z}$ and the fact that $\eta$ is bounded,

$$ (51) \qquad \begin{aligned} T_4 &= d_{\mathcal{M}}(\bar{z}, \bar{y}) d_{\mathcal{M}}(\bar{z}, \tilde{z}) J_{\varepsilon}(\bar{x}, \bar{z}) \\ &\le K(1-\lambda) d_{\mathcal{M}}(\bar{x}, \bar{y}) \varepsilon^{1+\nu} \varepsilon^{-1} \\ &\le K \gamma \varepsilon^{\nu}. \end{aligned} $$

We now turn to $T_5$. Using (37), (42), (H.12) and (H.15), we have

$$ (52) \qquad \begin{aligned} |T_5| &= (\varepsilon C_{\eta})^{-1} \left| \eta \left( \frac{\tilde{d}(\bar{x}, \tilde{z})}{\varepsilon} \right) - \eta \left( \frac{\tilde{d}(\bar{x}, \bar{z})}{\varepsilon} \right) \right| \cdot |f^{\varepsilon}(\bar{x}, \bar{t}) - f^{\varepsilon}(\tilde{z}, \bar{t})| \\ &\le K \varepsilon^{-2} |\tilde{d}(\bar{x}, \tilde{z}) - \tilde{d}(\bar{x}, \bar{z})| (d_{\mathcal{M}}(\bar{x}, \tilde{z}) + \varepsilon) \\ &\le K \varepsilon^{-2} (d_{\mathcal{M}}(\bar{z}, \tilde{z}) + C_{\mathcal{M}} \varepsilon^{1+\xi}) (d_{\mathcal{M}}(\bar{x}, \bar{z}) + d_{\mathcal{M}}(\tilde{z}, \tilde{z}) + \varepsilon) \\ &\le K \varepsilon^{-2} (K \varepsilon^{1+\nu} + C_{\mathcal{M}} \varepsilon^{1+\xi}) (\varepsilon r_{\eta} + K \varepsilon^{1+\nu} + \varepsilon) \\ &\le K \varepsilon^{\min(\nu, \xi)}. \end{aligned} $$

Injecting (48), (49), (50), (51) and (52) into (47), we arrive at

$$ |\nabla_{\eta_{\varepsilon}}^{-} f^{\varepsilon}(\bar{x}, \bar{t})|_{\infty} \ge \frac{d_{\mathcal{M}}(\bar{x}, \bar{y})}{\gamma} - K \left( \frac{\varepsilon}{\gamma} + \varepsilon^{\min(\nu, \xi)} \right). $$

Injecting this bound into (44) and combining with (43), we deduce that if $(\bar{x}, \bar{t}) \in (\tilde{\mathcal{M}} \setminus \tilde{\mathcal{N}}_{\Gamma}^{\alpha}) \times ]0, T[$ and $(\bar{y}, \bar{s}) \in (\mathcal{M} \setminus \mathcal{N}_{\Gamma}^{\alpha}) \times ]0, T[$, then

$$ \begin{aligned} \beta &< 2K \left( \varepsilon^{\min(\nu, \xi)} + \frac{\varepsilon}{\gamma} \right) + \tilde{P}(\bar{x}) - P(\bar{y}) \\ &\le K \left( \varepsilon^{\min(\nu, \xi)} + \frac{\varepsilon}{\gamma} \right) + L_P d_{\mathcal{M}}(\bar{x}, \bar{y}) + \|P - \tilde{P}\|_{L^{\infty}(\tilde{\mathcal{M}} \setminus \tilde{\Gamma})} \\ &\le K \left( \varepsilon^{\min(\nu, \xi)} + \frac{\varepsilon}{\gamma} \right) + L_P K \gamma + \|P - \tilde{P}\|_{L^{\infty}(\tilde{\mathcal{M}} \setminus \tilde{\Gamma})} \\ &\le K \left( \varepsilon^{\min(\nu, \xi)} + \frac{\varepsilon}{\gamma} + \gamma \right) + \|P - \tilde{P}\|_{L^{\infty}(\tilde{\mathcal{M}} \setminus \tilde{\Gamma})} \stackrel{\text{def}}{=} \bar{\beta}, \end{aligned} $$

for large enough constant $K > 0$, where we used (H.3) and (H.4) in the second inequality and estimate (42) in the third one. Then we conclude that for $\beta \ge \bar{\beta}$ either $(\bar{x}, \bar{t}) \in \mathcal{N}_{\Gamma}^{\alpha} \times ]0, T[ \cup \tilde{\mathcal{M}} \times \{0\}$ or $(\bar{y}, \bar{s}) \in \mathcal{N}_{\Gamma}^{\alpha} \times ]0, T[ \cup \mathcal{M} \times \{0\}$.
Step 3. Conclusion.

We take $\beta \ge \bar{\beta}$. Assume first that $(\bar{y}, \bar{s}) \in \mathcal{N}_{\Gamma}^{\alpha} \times [0, T[ \cup \mathcal{M} \times \{0\}$. If $\bar{s} = 0$, then

$$
\begin{align*}
\Psi_{\gamma,\beta}(\bar{x}, \bar{t}, \bar{y}, \bar{s}) &\le f^{\varepsilon}(\bar{x}, \bar{t}) - f_0(\bar{y}) \\
&= (f^{\varepsilon}(\bar{x}, \bar{t}) - f^{\varepsilon}(\bar{x}, 0)) + (f_0^{\varepsilon}(\bar{x}) - f_0(\bar{x})) + (f_0(\bar{x}) - f_0(\bar{y})) \\
&\le K\bar{t} + \|f_0^{\varepsilon} - f_0\|_{L^{\infty}(\tilde{\mathcal{M}})} + L_{f_0}d_{\mathcal{M}}(\bar{x}, \bar{y}) \\
&\le K(\beta + 1)\gamma + \|f_0^{\varepsilon} - f_0\|_{L^{\infty}(\tilde{\mathcal{M}})},
\end{align*}
$$

where, in the second inequality, we used (32) in Theorem 3.14 to get the first term, and (H.1) and (H.5) to get the last two terms. In the last inequality, we invoked (42). In the same way, if $\bar{y} \in \mathcal{N}_{\Gamma}^{\alpha}$ and $\bar{s} > 0$, let $\tilde{y} \in \text{Proj}_{\tilde{\Gamma}}(\bar{y})$, i.e.,

$$
d_{\mathcal{M}}(\bar{y}, \tilde{y}) = d_{\mathcal{M}}(\bar{y}, \tilde{\Gamma}) \le d_{\mathcal{H}}^{\mathcal{M}}(\Gamma, \tilde{\Gamma}) + \alpha.
$$

Such $\tilde{y}$ exists by closedness of $\tilde{\Gamma}$, see (H.3). Since (36) is in force under (H.15), (37)
holds (see Theorem 3.14 and Lemma 3.15). Using this with (H.5) and (42), we obtain

$$
\begin{align*}
\Psi_{\gamma,\beta}(\bar{x}, \bar{t}, \bar{y}, \bar{s}) &\le f^{\varepsilon}(\bar{x}, \bar{t}) - f_0(\bar{y}) \\
&= (f^{\varepsilon}(\bar{x}, \bar{t}) - f^{\varepsilon}(\bar{y}, \bar{t})) + (f_0^{\varepsilon}(\bar{y}) - f_0(\bar{y})) + (f_0(\bar{y}) - f_0(\bar{y})) \\
&\le K(d_{\mathcal{M}}(\bar{x}, \bar{y}) + \varepsilon) + \|f_0^{\varepsilon} - f_0\|_{L^{\infty}(\tilde{\mathcal{M}})} + L_{f_0}d_{\mathcal{M}}(\bar{y}, \bar{y}) \\
&\le K(d_{\mathcal{M}}(\bar{x}, \bar{y}) + \varepsilon) + \|f_0^{\varepsilon} - f_0\|_{L^{\infty}(\tilde{\mathcal{M}})} + Kd_{\mathcal{M}}(\bar{y}, \bar{y}) + L_{f_0}d_{\mathcal{M}}(\bar{y}, \bar{y}) \\
&\le K(\gamma + \varepsilon) + \|f_0^{\varepsilon} - f_0\|_{L^{\infty}(\tilde{\mathcal{M}})} + K(d_{\mathcal{H}}^{\mathcal{M}}(\Gamma, \tilde{\Gamma}) + \alpha).
\end{align*}
$$

We conclude that for all $(\bar{y}, \bar{s}) \in \mathcal{N}_{\Gamma}^{\alpha} \times [0, T[ \cup \mathcal{M} \times \{0\}$, and for $\beta \ge \bar{\beta}$, we have

$$
\Psi_{\gamma,\beta}(\bar{x}, \bar{t}, \bar{y}, \bar{s}) \le K(\gamma + \varepsilon) + \|f_0^{\varepsilon} - f_0\|_{L^{\infty}(\tilde{\mathcal{M}})} + K(d_{\mathcal{H}}^{\mathcal{M}}(\Gamma, \tilde{\Gamma}) + \alpha) + K\beta\gamma.
$$

The same bound holds for $(\bar{x}, \bar{t}) \in (\mathcal{N}_{\Gamma}^{\alpha} \cap \tilde{\mathcal{M}}) \times [0, T[ \cup \tilde{\mathcal{M}} \times \{0\}$ when $\beta \ge \bar{\beta}$. Indeed, if $\bar{t} = 0$ then

$$
\begin{align*}
\Psi_{\gamma,\beta}(\bar{x}, \bar{t}, \bar{y}, \bar{s}) &\le f_0^{\varepsilon}(\bar{x}) - f(\bar{y}, \bar{s}) \\
&= (f_0^{\varepsilon}(\bar{x}) - f_0(\bar{x})) + (f_0(\bar{x}) - f_0(\bar{y})) + (f(\bar{y}, 0) - f(\bar{y}, \bar{s})) \\
&\le \|f_0^{\varepsilon} - f_0\|_{L^{\infty}(\tilde{\mathcal{M}})} + L_{f_0}d_{\mathcal{M}}(\bar{x}, \bar{y}) + K\bar{s} \\
&\le K(\beta + 1)\gamma + \|f_0^{\varepsilon} - f_0\|_{L^{\infty}(\tilde{\mathcal{M}})},
\end{align*}
$$

where we have now invoked (21) in Theorem 3.8. If $\bar{x} \in (\mathcal{N}_{\Gamma}^{\alpha} \cap \tilde{\mathcal{M}})$ and $\bar{t} > 0$, choose $\hat{x} \in \Gamma$
in the projection of $\bar{x}$ on $\Gamma$. Thus, using (22) in Theorem 3.8, we arrive at

$$
\begin{align*}
\Psi_{\gamma,\beta}(\bar{x}, \bar{t}, \bar{y}, \bar{s}) &\le f_0^{\varepsilon}(\bar{x}) - f(\bar{y}, \bar{s}) \\
&= (f_0^{\varepsilon}(\bar{x}) - f_0(\bar{x})) + (f_0(\bar{x}) - f_0(\hat{x})) + (f(\hat{x}, \bar{s}) - f(\bar{y}, \bar{s})) \\
&\le \|f_0^{\varepsilon} - f_0\|_{L^{\infty}(\tilde{\mathcal{M}})} + L_{f_0}d_{\mathcal{M}}(\bar{x}, \hat{x}) + K d_{\mathcal{M}}(\hat{x}, \bar{y}) \\
&\le \|f_0^{\varepsilon} - f_0\|_{L^{\infty}(\tilde{\mathcal{M}})} + L_{f_0}\alpha + K(\alpha + \gamma) \\
&\le K(\alpha + \gamma) + \|f_0^{\varepsilon} - f_0\|_{L^{\infty}(\tilde{\mathcal{M}})}.
\end{align*}
$$

Thus, taking $\beta = \bar{\beta}$ and $(x, t) \in \tilde{\mathcal{M}}_T$ we have from above that,

$$
\begin{align*}
f^{\varepsilon}(x,t) - f(x,t) - \bar{\beta}T &\le \Psi_{\gamma,\beta}(\bar{x}, \bar{t}, \bar{y}, \bar{s}) \\
&\le K(\gamma + \varepsilon) + \|f_0^{\varepsilon} - f_0\|_{L^{\infty}(\tilde{\mathcal{M}})} + K(d_{\mathrm{H}}^{\mathrm{M}}(\Gamma, \tilde{\Gamma}) + \alpha) + K\bar{\beta}\gamma.
\end{align*}
$$
Before concluding, we look at what happens when we revert the role of $f$ and $f^\varepsilon$. In this case, our reasoning remains valid with only a few changes. The main ingredient is to redefine $\Psi_{\gamma,\beta}$ as follows

$$ \Psi_{\gamma,\beta}(x,t,y,s) = f(y,s) - f^\varepsilon(x,t) - \frac{d_{\mathcal{M}}^2(x,y)}{2\gamma} - \frac{|t-s|^2}{2\gamma} - \beta t. $$

Then all our bounds remain true and with even simpler arguments (see the proof of Theorem 4.3 which used the same kind of arguments and where we revert the role of $f$ and $f^\varepsilon$). We leave the details to the reader for the sake of brevity. Overall, we have shown that

$$ |f^\varepsilon(x,t) - f(x,t)| \le K(\gamma + \varepsilon) + \|f_0^\varepsilon - f_0\|_{L^\infty(\tilde{\mathcal{M}})} + K(d_H^{\mathcal{M}}(\Gamma, \tilde{\Gamma}) + \alpha) + K\bar{\beta}(\gamma + T). $$

With the optimal choice $\gamma = \varepsilon^{1/2}$, taking the supremum over $(x, t)$ and after rearrangement, we get (recalling that $\alpha = \varepsilon^{1/2}$)

$$ \|f^\varepsilon - f\|_{L^\infty(\tilde{\mathcal{M}} \times [0, T])} \le K \left( (T+1)\varepsilon^{\min(\nu, \xi, 1/2)} + \varepsilon \right) + K(T + \varepsilon^{1/2}) \|P - \tilde{P}\|_{L^\infty(\tilde{\mathcal{M}} \setminus \tilde{\Gamma})} \\ + \|f_0^\varepsilon - f_0\|_{L^\infty(\tilde{\mathcal{M}})} + K(d_H^{\mathcal{M}}(\Gamma, \tilde{\Gamma}) + \varepsilon^{1/2}), $$

which implies the claimed bound.

□

## 4.2. Forward Euler discrete time non-local to local error bound.
In this section, we consider the time-discrete approximation of $(\mathcal{P}_\varepsilon)$ using Forward Euler discretization. Then we show an error estimate between this approximation and the viscosity solution to $(\mathcal{P})$.

For a time interval $[0, T]$ and $N_T \in \mathbb{N}$, we use the shorthand notation $\partial \tilde{\mathcal{M}}_{N_T} = (\tilde{\Gamma} \times \{t_1, \dots, t_{N_T}\} \cup \tilde{\mathcal{M}} \setminus \tilde{\Gamma} \times \{0\})$. Using the Forward/Explicit Euler discretization scheme, a time-discrete counterpart of $(\mathcal{P}_\varepsilon)$ is given by

$$ (\mathcal{P}_\varepsilon^{\text{FD}}) \quad \begin{cases} \frac{f^\varepsilon(x,t) - f^\varepsilon(x,t-\Delta t)}{\Delta t} + |\nabla_{\eta_\varepsilon}^- f^\varepsilon(x,t-\Delta t)|_\infty = \tilde{P}(x), & (x,t) \in (\tilde{\mathcal{M}} \setminus \tilde{\Gamma}) \times \{t_1, \dots, t_{N_T}\}, \\ f^\varepsilon(x,t) = f_0^\varepsilon(x), & (x,t) \in \partial \tilde{\mathcal{M}}_{N_T}, \end{cases} $$

where $t_i = i\Delta t$ for all $i \in \{0, \dots, N_T\}$.

We include in Appendix A the proof of the well-posedness of the equation $(\mathcal{P}_\varepsilon^{\text{FD}})$. Indeed, Lemma A.3 shows the existence and regularity properties in time and space of a discrete-time solution of $(\mathcal{P}_\varepsilon^{\text{FD}})$ (in the sense of Definition A.1). The comparison principle given in Lemma A.2 provides uniqueness.

We are now in a position to state the following error estimate.

**Theorem 4.3** (Error bound between the solutions to $(\mathcal{P})$ and $(\mathcal{P}_\varepsilon^{\text{FD}})$). Let $T > 0$ and $\varepsilon \in ]0, \varepsilon_0]$ where $\varepsilon_0 = \min(1, 1/(2r_\eta)^2, (a/(2C_\mathcal{M}))^{1/\xi})$. Suppose that assumptions (H.1)-(H.15) hold, and that $d_H^{\mathcal{M}}(\Gamma, \tilde{\Gamma}) = O(\varepsilon^{\min(\nu, \xi, 1/2)})$. Let $f$ be the unique viscosity solution to $(\mathcal{P})$ and $f^\varepsilon$ be the solution to $(\mathcal{P}_\varepsilon^{\text{FD}})$. Assume also that

$$ (54) \qquad 0 < \Delta t \le \frac{\varepsilon C_\eta}{\sup_{t \in \mathbb{R}_+} \eta(t)}. $$
Then, there exists a constant $K > 0$ depending only on $C_M$, $\|f_0\|_{L^\infty(M)}$, $\|P\|_{L^\infty(M\setminus\Gamma)}$, $L_{f_0}$, $L_{f_0^\varepsilon}$, $L_P$, $L_{\tilde{P}}$, $\|\eta\|_{L^\infty}$, $L_\eta$, $C_\eta$ and $c_\eta$ such that for any $\varepsilon$ small enough

$$ \|f^{\varepsilon} - f\|_{L^{\infty}(\tilde{M} \times \{0, \dots, t_{N_T}\})} \le K(T+1) \left( \varepsilon^{\min(\nu, \xi, 1/2)} + \Delta t^{1/2} + \frac{\Delta t}{\varepsilon} + \|P - \tilde{P}\|_{L^{\infty}(\tilde{M} \setminus \tilde{\Gamma})} \right) \\ + \|f_0^{\varepsilon} - f_0\|_{L^{\infty}(\tilde{M})}. $$

In particular, if $\tilde{P} = P$ on $\tilde{M}\setminus\tilde{\Gamma}$ and $f_0^\varepsilon = f_0$ on $\tilde{M}$, then we have

$$ \|f^{\varepsilon} - f\|_{L^{\infty}(\tilde{M} \times \{0, \dots, t_{N_T}\})} \le K(T+1) \left( \varepsilon^{\min(\nu, \xi, 1/2)} + \Delta t^{1/2} + \frac{\Delta t}{\varepsilon} \right). $$

The fastest convergence rate in $\varepsilon$ is then achieved when $\Delta t = O(\varepsilon^{3/2})$, $\nu = 1/2$ and $\xi = 1/2$ provided that $d_H^M(M, \tilde{M}) = O(\varepsilon^{3/2})$ and $d_H^M(\Gamma, \tilde{\Gamma}) = O(\varepsilon^{1/2})$.

**Proof.** The proof of this theorem is similar to the one of Theorem 4.2. We just point out the steps where we need to correctly process the discrete time approximation. Moreover, we revert the role of $f$ and $f^\varepsilon$ to complete the details provided in the proof of Theorem 4.2. Therefore, we will need to use the Lipschitz regularity properties of $f^\varepsilon$ in time and space (see Lemma A.3). Again, $K$ will denote in this proof any positive constant that depends only on the data but may change from one line to another.

**Step 1. Test-function and maximum point.**

For $\gamma > 0$ and $\beta > 0$, we consider maximizing over $M_T \times \tilde{M}_{NT}$ the test-function

$$ \Psi_{\gamma, \beta}(x, t, y, s) = f(x, t) - f^{\varepsilon}(y, s) - \frac{d_{M}^{2}(x, y)}{2\gamma} - \frac{|t-s|^{2}}{2\gamma} - \beta t. $$

Exactly as in the proof of Lemma 4.1, the maximum is achieved at some point $(\bar{x}, \bar{t}, \bar{y}, \bar{t}_i) \in M_T \times \tilde{M}_{NT}$ and this maximum satisfies the following properties

$$ (55) \qquad d_M(\bar{x}, \bar{y}) \le K\gamma \quad \text{and} \quad |\bar{t} - \bar{t}_i| \le K(1 + \beta)\gamma. $$

**Step 2. Excluding interior points from the maximum.**

We show that for $\beta$ large enough, we have either $(\bar{x}, \bar{t}) \in \partial M_T$ or $(\bar{y}, \bar{t}_i) \in \partial \tilde{M}_{NT}$. We argue again by contradiction and assume that $(\bar{x}, \bar{t}) \in M\setminus\Gamma \times [0, T]$ and $(\bar{y}, \bar{t}_i) \in \tilde{M}\setminus\tilde{\Gamma} \times \{t_1, \dots, t_{N_T}\}$. The function $(x, t) \mapsto f(x, t) - \varphi^1(x, t)$, where

$$ \varphi^1(x, t) = f^{\varepsilon}(\bar{y}, \bar{t}_i) + \frac{d_{M}^{2}(x, \bar{y})}{2\gamma} + \frac{|t - \bar{t}_i|^2}{2\gamma} + \beta t, $$

reaches a maximum point at $(\bar{x}, \bar{t})$. Using that $\varphi^1$ is $C^1$ on a small neighborhood of $(\bar{x}, \bar{t})$, for $\gamma$ small enough, (see (55), Assumption (H.7) and Remark 2.15), the fact that $f$ is a viscosity sub-solution to (P) and the fact that $\|\mathrm{grad}_x d_M^2(\bar{x}, \bar{y})\|_{\bar{x}} = 2d_M(\bar{x}, \bar{y})$ (see Proposition 2.12 and Lemma 2.13), we have

$$ (56) \qquad \beta + \frac{\bar{t} - \bar{t}_i}{\gamma} \le -\frac{d_M(\bar{x}, \bar{y})}{\gamma} + P(\bar{x}). $$

We have $\Psi_{\gamma, \beta}(\bar{x}, \bar{t}, \bar{y}, \bar{t}_i) \ge \Psi_{\gamma, \beta}(\bar{x}, \bar{t}, \bar{y}, \bar{t}_i - \Delta t)$ since $(\bar{x}, \bar{t}, \bar{y}, \bar{t}_i)$ is a maximum point of $\Psi_{\gamma, \beta}$. This implies that

$$ (57) \qquad \frac{f^{\varepsilon}(\bar{y}, \bar{t}_i) - f^{\varepsilon}(\bar{y}, \bar{t}_i - \Delta t)}{\Delta t} \le \frac{\bar{t} - \bar{t}_i}{\gamma} + \frac{\Delta t}{2\gamma}. $$
Similarly, we have $\Psi_{\gamma,\beta}(\bar{x}, \bar{t}, \bar{y}, \bar{t}_i) \ge \Psi_{\gamma,\beta}(\bar{x}, \bar{t}, z, \bar{t}_i)$, hence we get

$$f^{\varepsilon}(\bar{y}, \bar{t}_i) - f^{\varepsilon}(z, \bar{t}_i) \le \frac{d_{\mathcal{M}}^2(\bar{x}, z) - d_{\mathcal{M}}^2(\bar{x}, \bar{y})}{2\gamma}, \quad \forall z \in \tilde{\mathcal{M}}.$$

On the other hand, using that $\bar{t}_i > 0$ and that $f^{\varepsilon}$ is a solution to $(P_{\varepsilon}^{\text{FD}})$, see Definition A.1, we have

$$(58) \qquad \frac{f^{\varepsilon}(\bar{y}, \bar{t}_i) - f^{\varepsilon}(\bar{y}, \bar{t}_i - \Delta t)}{\Delta t} = -|\nabla_{\eta_{\varepsilon}} f^{\varepsilon}(\bar{y}, \bar{t}_i - \Delta t)|_{\infty} + \tilde{P}(\bar{y}).$$

We now estimate the right hand side of (58)

$$(59) \qquad \begin{aligned} \left|\nabla_{\eta_{\varepsilon}} f^{\varepsilon}(\bar{y}, \bar{t}_i - \Delta t)\right|_{\infty} &= \max_{z \in \tilde{\mathcal{M}}, \tilde{d}(\bar{y}, z) \in \varepsilon\text{supp}(\eta)} J_{\varepsilon}(\bar{y}, z) (f^{\varepsilon}(\bar{y}, \bar{t}_i - \Delta t) - f^{\varepsilon}(z, \bar{t}_i - \Delta t)) \\ &= \max_{z \in \tilde{\mathcal{M}}, \tilde{d}(\bar{y}, z) \in \varepsilon\text{supp}(\eta)} J_{\varepsilon}(\bar{y}, z) (f^{\varepsilon}(\bar{y}, \bar{t}_i - \Delta t) - f^{\varepsilon}(\bar{y}, \bar{t}_i) + f^{\varepsilon}(\bar{y}, \bar{t}_i) - f^{\varepsilon}(z, \bar{t}_i) \\ &\quad + f^{\varepsilon}(z, \bar{t}_i) - f^{\varepsilon}(z, \bar{t}_i - \Delta t)) \\ &\le \max_{z \in \tilde{\mathcal{M}}, \tilde{d}(\bar{y}, z) \in \varepsilon\text{supp}(\eta)} J_{\varepsilon}(\bar{y}, z) (K \Delta t + f^{\varepsilon}(\bar{y}, \bar{t}_i) - f^{\varepsilon}(z, \bar{t}_i)) \\ &\le \max_{z \in \tilde{\mathcal{M}}, \tilde{d}(\bar{y}, z) \in \varepsilon\text{supp}(\eta)} J_{\varepsilon}(\bar{y}, z) (K \Delta t + (2\gamma)^{-1} (d_{\mathcal{M}}^2(\bar{x}, z) - d_{\mathcal{M}}^2(\bar{x}, \bar{y}))) \\ &\le K \Delta t \max_{z \in \tilde{\mathcal{M}}, \tilde{d}(\bar{y}, z) \in \varepsilon\text{supp}(\eta)} J_{\varepsilon}(\bar{y}, z) + (2\gamma)^{-1} \max_{z \in \tilde{\mathcal{M}}, \tilde{d}(\bar{y}, z) \in \varepsilon\text{supp}(\eta)} J_{\varepsilon}(\bar{y}, z) \\ &\quad (d_{\mathcal{M}}(\bar{x}, z) - d_{\mathcal{M}}(\bar{x}, \bar{y})) (d_{\mathcal{M}}(\bar{x}, z) - d_{\mathcal{M}}(\bar{x}, \bar{y}) + 2d_{\mathcal{M}}(\bar{x}, \bar{y})) \\ &\le K \frac{\Delta t}{\varepsilon} \sup_{t \in \mathbb{R}_+} \eta(t) + (2\gamma)^{-1} \max_{z \in \tilde{\mathcal{M}}, \tilde{d}(\bar{y}, z) \in \varepsilon\text{supp}(\eta)} J_{\varepsilon}(\bar{y}, z) d_{\mathcal{M}}(\bar{y}, z) (d_{\mathcal{M}}(\bar{y}, z) + 2d_{\mathcal{M}}(\bar{x}, \bar{y})) \\ &\le K \frac{\Delta t}{\varepsilon} + \frac{d_{\mathcal{M}}(\bar{x}, \bar{y})}{\gamma} \max_{z \in \tilde{\mathcal{M}}, \tilde{d}(\bar{y}, z) \in \varepsilon\text{supp}(\eta)} (\varepsilon C_{\eta})^{-1} \left(\tilde{d}(\bar{y}, z) + K \varepsilon^{1+\xi}\right) \eta \left(\frac{\tilde{d}(\bar{y}, z)}{\varepsilon}\right) \\ &\quad + (2\gamma)^{-1} \max_{z \in \tilde{\mathcal{M}}, \tilde{d}(\bar{y}, z) \in \varepsilon\text{supp}(\eta)} (\varepsilon C_{\eta})^{-1} \left(\tilde{d}(\bar{y}, z) + K \varepsilon^{1+\xi}\right)^2 \eta \left(\frac{\tilde{d}(\bar{y}, z)}{\varepsilon}\right) \\ &\le K \frac{\Delta t}{\varepsilon} + \frac{d_{\mathcal{M}}(\bar{x}, \bar{y})}{\gamma} (1 + K \varepsilon^{\xi}) + (2\gamma)^{-1} \max_{z \in \tilde{\mathcal{M}}, \tilde{d}(\bar{y}, z) \in \varepsilon\text{supp}(\eta)} \left(\tilde{d}(\bar{y}, z) \right. \\ &\quad \left. + K \varepsilon^{1+\xi} (\varepsilon C_{\eta})^{-1} \tilde{d}(\bar{y}, z) \eta \left(\frac{\tilde{d}(\bar{y}, z)}{\varepsilon}\right) + K \varepsilon^{2+2\xi} (\varepsilon C_{\eta})^{-1} \eta \left(\frac{\tilde{d}(\bar{y}, z)}{\varepsilon}\right) \right) \\ &\le K \frac{\Delta t}{\varepsilon} + \frac{d_{\mathcal{M}}(\bar{x}, \bar{y})}{\gamma} + K \varepsilon^{\xi} + (2\gamma)^{-1} (K \varepsilon + K \varepsilon^{1+\xi} + K \varepsilon^{1+2\xi}) \\ &\le K \left(\frac{\Delta t}{\varepsilon} + \frac{\varepsilon}{\gamma} + \varepsilon^{\xi}\right) + \frac{d_{\mathcal{M}}(\bar{x}, \bar{y})}{\gamma}. \end{aligned}$$

Plugging (57) and (59) into (58) we get

$$(60) \qquad \frac{\bar{t} - \bar{t}_i}{\gamma} + \frac{\Delta t}{2\gamma} \ge -K \left( \frac{\Delta t}{\varepsilon} + \frac{\varepsilon}{\gamma} + \varepsilon^{\xi} \right) - \frac{d_{\mathcal{M}}(\bar{x}, \bar{y})}{\gamma} + \tilde{P}(\bar{y}).$$

From (56) and (60), we finally obtain
$$
\begin{align*}
\beta &\le K \left( \frac{\Delta t + \varepsilon}{\gamma} + \frac{\Delta t}{\varepsilon} + \varepsilon \xi \right) + P(\bar{x}) - \tilde{P}(\bar{y}) \\
&\le K \left( \frac{\Delta t + \varepsilon}{\gamma} + \frac{\Delta t}{\varepsilon} + \varepsilon \xi \right) + K d_{\mathcal{M}}(\bar{x}, \bar{y}) + \|P - \tilde{P}\|_{L^{\infty}(\tilde{\mathcal{M}} \setminus \tilde{\Gamma})} \\
&< K \left( \frac{\Delta t + \varepsilon}{\gamma} + \gamma + \frac{\Delta t}{\varepsilon} + \varepsilon \xi \right) + \|P - \tilde{P}\|_{L^{\infty}(\tilde{\mathcal{M}} \setminus \tilde{\Gamma})} \stackrel{\text{def}}{=} \bar{\beta}.
\end{align*}
$$

We then conclude that either $(\bar{x}, \bar{t}) \in \partial \mathcal{M}_T$ or $(\bar{y}, \bar{t}_i) \in \partial \tilde{\mathcal{M}}_{N_T}$, for $\beta \ge \bar{\beta}$. When reverting the roles of $f^\varepsilon$ and $f$, only $\bar{\beta}$ will be changed taking the additional term $\varepsilon^{\min(\nu, \xi)}$ (see the proof of Theorem 4.2). We finally use the regularity properties of $f^\varepsilon$ (see Lemma A.3) and of $f$ (see Theorem 3.8) to conclude, following Step 3. in the proof of Theorem 4.2.
□

5. APPLICATION TO GRAPH SEQUENCES

Let $G_n = (V_n, E_n, w_n)$ be a finite weighted graph where $V_n$ is the set of $n$ vertices $\{u_1, \dots, u_n\}$,
$E_n \subset V_n \times V_n$ is the set of edges and $w_n(u_i, u_j)$ is the weight of any edge $(u_i, u_j)$. The latter can
be defined with a kernel function at scale $\varepsilon_n$ as $w_n(u_i, u_j) = (\varepsilon C_\eta)^{-1} \eta \left( \frac{\tilde{d}(u_i, u_j)}{\varepsilon} \right)$.

Let $\Gamma_n \subset V_n$. For a time interval $[0, T]$ and $N_T \in \mathbb{N}$, we use the shorthand notation $(V_n \setminus \Gamma_n)_{N_T} = (V_n \setminus \Gamma_n) \times \{t_1, \dots, t_{N_T}\}$ and $\partial(V_n)_{N_T} = (\Gamma_n \times \{t_1, \dots, t_{N_T}\}) \cup V_n \times \{0\}$. We now consider the fully discretized Eikonal equation on $G_n$ with a forward Euler time-discretization as

$$
(\mathcal{P}_{G_n}^{\text{FD}}) \quad \begin{cases} \frac{f^n(u,t) - f^n(u,t - \Delta t)}{\Delta t} + |\nabla_{\eta_\varepsilon} f^n(u, t - \Delta t)|_\infty = \tilde{P}(u), & (u,t) \in (V_n \setminus \Gamma_n)_{N_T}, \\ f^n(u,t) = f_0^n(u), & (u,t) \in \partial(V_n)_{N_T}, \end{cases}
$$

where $t_i = i\Delta t$ for all $i \in \{0, \dots, N_T\}$.

In the notation of ($\mathcal{P}_{\varepsilon}^{\text{FD}}$), it is easy to identify $V_n$ with $\tilde{\mathcal{M}}$ and $\Gamma_n$ with $\tilde{\Gamma}$. We observe that by construction, $V_n$ and $\Gamma_n$ are compact sets and that $V_n \setminus \Gamma_n \subset \mathcal{M} \setminus \Gamma$. Our aim in this section is to establish consistency of solutions to ($\mathcal{P}_{G_n}^{\text{FD}}$) as $n \to +\infty$ and $\Delta t \to 0$.

In practice, the construction of vertices $V_n$ in a graph is beyond our direct control. The specific
arrangement of points may not be known, or the points can be obtained by sampling through
an acquisition device (e.g., point clouds), or derived from a learning or modeling process (e.g.,
images). Consequently, it is more realistic to consider graphs $G_n$ on random point configurations
$V_n$, and then conveniently estimate the probability of achieving a prescribed level of consistency as
a function of $n$.

To achieve this goal, we will consider a random graph model whose nodes are latent random variables independently and identically sampled on $\mathcal{M}$. This random graph model is inspired from [5] and is quite standard. More precisely, we construct $V_n$ and the boundary $\Gamma_n$ as follows:

**Definition 5.1** (Construction of $V_n$ and $\Gamma_n$). Given a probability measure $\mu$ over $\mathcal{M}$ and $\varepsilon_n > 0$ :

(1) draw the vertices in $V_n$ as a sequence of independent and identically distributed variables $(u_i)_{i=1}^n$ taking values in $\mathcal{M}$ and whose common distribution is $\mu$;

(2) set $\Gamma_n = \{u_i \in V_n : d_M(u_i, \Gamma) \le a\varepsilon_n^{1+\nu}/2\}, \nu > 0$.

From now on, we assume that

(H.16) $\mu$ has a density $\rho$ on $\mathcal{M}$ with respect to the volume measure, and $\inf_{\mathcal{M}} \rho > 0$.
Before stating the main result of this section, the following lemma gives a proper choice of $\epsilon_n$ for which the construction of Definition 5.1 ensures that the key assumption (H.15) is in force together with $\Gamma_n \neq \emptyset$ and $d_H^M(\Gamma, \Gamma_n) = O(\epsilon_n^{1+\nu})$ with high probability. To lighten notation, we define the event

$$ (61) \qquad \mathcal{E}_n = \{ (\text{H.15}) \text{ holds and } d_H^M(\Gamma, \Gamma_n) \le a\epsilon_n^{1+\nu}/2 \}. $$

Before stating the next Lemma, we need to introduce the following assumption on the radius $\delta$ of the covering of $\mathcal{M}$

(H.17) The radius of the covering of $\mathcal{M}$ satisfies $\delta < \min\{\mathrm{inj}_g(\mathcal{M}), \frac{\pi}{\sqrt{r}}, 2\pi\}$, where $r$ is the infimum of the sectional curvature of $\mathcal{M}$ and $\mathrm{inj}_g$ is the injectivity radius of $(\mathcal{M}, g)$ and where we have set $\frac{\pi}{\sqrt{r}} = +\infty$ whenever $r \le 0$.

The definitions of the sectional curvature and the injectivity radius of $\mathcal{M}$ are given in Appendix B. As for the examples mentioned in the introduction, they satisfy this assumption. In fact, the Euclidean sphere $S^n$ possesses a constant positive sectional curvature equal to $1/R^2$, where $R$ is its radius. Therefore, the infimum of its sectional curvature $r$ is strictly positive. Thus assumption (H.17) is satisfied. Furthermore, the hyperbolic manifold $\mathbb{H}^n$ has a constant negative sectional curvature, while the sectional curvature of the torus is identically zero, ensuring the validity of the condition on $\delta$ for this two examples.

**Lemma 5.2.** Let $V_n$ and $\Gamma_n$ generated according to Definition 5.1 where $\mu$ satisfies (H.16). Assume that $\delta$ satisfies assumption (H.17). Then, there exist two constants $K_1 > 0$ and $K_2 > 0$ that depend only on $a$, vol($\mathcal{M}$) and vol($B_\mathcal{M}(0)$), and for any $\tau > 0$ there exists $n(\tau) \in \mathbb{N}$ such that for $n \ge n(\tau)$, taking

$$ (62) \qquad \epsilon_n^{1+\nu} = K_1(1+\tau)^{1/m^*} \left(\frac{\log n}{n}\right)^{1/m^*}, $$

the event $\mathcal{E}_n$ in (61) holds with probability at least $1 - K_2 n^{-\tau}$.

*Proof.* The proof follows a similar approach as in [16, Appendix D], with the exception that the covering number of $\mathcal{M}$ is distinct here. We will use again compactness of $\mathcal{M}$ and a covering argument with a finite $\delta$-net consisting of $N(\mathcal{M}, \delta)$ points. Let $S_\delta = \{x_1, x_2, \dots, x_{N(\mathcal{M}, \delta)}\}$ be a $\delta$-net of $\mathcal{M}$ such that for all $x \in \mathcal{M}$, there exists $x_j \in S_\delta$ such that $d_\mathcal{M}(x, x_j) \le \delta$, i.e., $\mathcal{M} \subseteq \bigcup_{x_j \in S_\delta} B_\mathcal{M}(x_j, \delta)$. We then have, following the same lines as in the proof of [16, Lemma 4.2] that

$$ \mathrm{Pr} \left( \max_{x \in \mathcal{M}} d_{\mathcal{M}}(x, V_n) > 2\delta \right) \le N(\mathcal{M}, \delta) \left(1 - c\delta^{m^*} \mathrm{vol}(B_{\mathcal{M}}(0))\right)^n. $$

Using the result obtained in [25], we have that

$$ N(\mathcal{M}, \delta) \le C \mathrm{vol}(\mathcal{M}) \delta^{-m^*}. $$

We therefore arrive at the bound

$$ \begin{aligned} \mathrm{Pr} \left( \max_{x \in \mathcal{M}} d_{\mathcal{M}}(x, V_n) > 2\delta \right) &\le C \mathrm{vol}(\mathcal{M}) \delta^{-m^*} \left(1 - c \delta^{m^*} \mathrm{vol}(B_{\mathcal{M}}(0))\right)^n \\ &\le C \mathrm{vol}(\mathcal{M}) \delta^{-m^*} e^{-nc \delta^{m^*} \mathrm{vol}(B_{\mathcal{M}}(0))}. \end{aligned} $$
Take $\delta^{m*} = \frac{(1+\tau)}{c\mathrm{vol}(B_{\mathcal{M}}(0))} \frac{\log n}{n}$, for any $\tau > 0$. Thus the above bound becomes

$$ \begin{aligned} \mathrm{Pr} \left( \max_{x \in \Omega} d(x, V_n) > 2\delta \right) &\le C \mathrm{vol}(\mathcal{M}) \mathrm{vol}(B_{\mathcal{M}}(0)) e^{-(1+\tau) \log n - \log(1+\tau) - \log \log n + \log n} \\ &\le C \mathrm{vol}(\mathcal{M}) \mathrm{vol}(B_{\mathcal{M}}(0)) e^{-\tau \log n} \\ &= C \mathrm{vol}(\mathcal{M}) \mathrm{vol}(B_{\mathcal{M}}(0)) n^{-\tau}. \end{aligned} $$

Thus, taking

$$ \varepsilon_n^{1+\nu} = 16a^{-1} \left( \frac{(1+\tau)}{c\mathrm{vol}(B_{\mathcal{M}}(0))} \right)^{1/m^*} \left( \frac{\log n}{n} \right)^{1/m^*}, $$

we have $a\varepsilon_n^{1+\nu}/8 \ge \delta$, and therefore (H.15) holds with probability at least $1 - K_2 n^{-\tau}$. The proof of the estimation of the probability of the event $\{d_H^{\mathcal{M}}(\Gamma, \Gamma_n) \le a\varepsilon_n^{1+\nu}/2\}$ aligns with that presented in [16, Appendix D], and for brevity, we skip it. $\square$

We are now ready to establish a quantified version of uniform convergence in probability of $f^n$ towards $f$.

**Theorem 5.3.** Let $T$, $\nu > 0$, and $V_n$ and $\Gamma_n$ be constructed according to Definition 5.1 where $\mu$ satisfies (H.16). Suppose that assumptions (H.1)-(H.15) and (H.17) hold. Let $f$ be the unique viscosity solution to $(\mathcal{P})$ and $f^n$ be a solution to $(\mathcal{P}_{G_n}^{\mathrm{FD}})$. Take $\Delta t = \varepsilon_n^{1+\zeta}$ where $\varepsilon_n$ is as given in (62). Then, there exist two constants $K > 0$ and $K_2 > 0$ that depend only on $C_{\mathcal{M}}$, $a$, $\mathrm{diam}(\mathcal{M})$, $\|f_0\|_{L^\infty(\mathcal{M})}$, $\|P\|_{L^\infty(\mathcal{M}\setminus\Gamma)}$, $L_{f_0}$, $L_{f_0^n}$, $L_P$, $L_{\tilde{P}}$, $c_\eta$, $C_\eta$, $L_\eta$, $\|\eta\|_{L^\infty}$ and $\nu$, and for any $\tau > 0$, there exists $n(\tau) \in \mathbb{N}$ such that for $n \ge n(\tau)$,

$$ \|f^n - f\|_{L^\infty(V_n \times \{0, \dots, t_{N_T}\})} \le K(T+1) \left( (1+\tau)^{\frac{\min(\nu, \xi, 1/2, \zeta)}{(1+\nu)m^*}} \left(\frac{\log n}{n}\right)^{\frac{\min(\nu, \xi, 1/2, \zeta)}{(1+\nu)m^*}} \right. \\ \left. + \|P - \tilde{P}\|_{L^\infty(V_n \setminus \Gamma_n)} \right) + \|f_0^n - f_0\|_{L^\infty(V_n)}. $$

with probability at least $1 - K_2 n^{-\tau}$. In particular, if $\varepsilon_n$ is chosen with $\tau > 1$, $\tilde{P} = P$ on $V_n \setminus \Gamma_n$ and $f_0^n = f_0$ on $V_n$, then

$$ \lim_{n \to +\infty} \|f^n - f\|_{L^\infty(V_n \times \{0, \dots, t_{N_T}\})} = 0 \quad \text{almost surely.} $$

The best convergence rate is $O\left(\frac{\log n}{n}\right)^{\frac{1}{3m^*}}$ obtained for $\nu = 1/2$, $\xi = 1/2$ and $\zeta = 1/2$.

*Proof.* The proof of this theorem is similar to the one of [16, Theorem 4.3] and we skip it. $\square$

## APPENDIX A. WELL-POSEDNESS AND REGULARITY PROPERTIES OF $(\mathcal{P}_{\varepsilon}^{\mathrm{FD}})$

We recall the notions of discrete sub- and super-solution defined in [16].

**Definition A.1 (Discrete sub- and super-solution).** We say that $f^\varepsilon$ is a sub-solution to $(\mathcal{P}_\varepsilon^{\mathrm{FD}})$ if for all $(x, t) \in (\tilde{\mathcal{M}} \setminus \tilde{\Gamma}) \times \{t_1, \dots, t_{N_T}\}$

$$ \frac{f^\varepsilon(x, t) - f^\varepsilon(x, t - \Delta t)}{\Delta t} + |\nabla_{\eta_\varepsilon} f^\varepsilon(x, t - \Delta t)|_\infty \le \tilde{P}(x), $$

and if for all $(x, t) \in \partial \tilde{\mathcal{M}}_{N_T}$,

$$ f^\varepsilon(x, t) \le f_0^\varepsilon(x). $$
In the same way, we say that $f^\epsilon$ is a super-solution to $(\mathcal{P}_\epsilon^{\text{FD}})$ if for all $(x,t) \in (\tilde{\mathcal{M}}\setminus\tilde{\Gamma}) \times \{t_1, \dots, t_{N_T}\}$

$$ \frac{f^\epsilon(x,t) - f^\epsilon(x, t - \Delta t)}{\Delta t} + |\nabla_{\eta_\epsilon} f^\epsilon(x, t - \Delta t)|_\infty \ge \tilde{P}(x), $$

and if for all $(x,t) \in \partial\tilde{\mathcal{M}}_{N_T}$,

$$ f^\epsilon(x, t) \ge f_0^\epsilon(x). $$

$f^\epsilon$ is a discrete solution to $(\mathcal{P}_\epsilon^{\text{FD}})$ if it is both a discrete sub-solution and super-solution.

We recall the comparison principle, proved in [16, Lemma B.2]

**Lemma A.2** (Comparison principle for the scheme $(\mathcal{P}_\epsilon^{\text{FD}})$). Assume that (H.1)-(H.3) and (H.9) hold, and that $f^\epsilon, g^\epsilon$ are respectively bounded sub- and super-solution to $(\mathcal{P}_\epsilon^{\text{FD}})$. Assume also that the CFL condition (54) holds. Then

$$ (63) \qquad \sup_{\tilde{\mathcal{M}} \times \{0, \dots, t_{N_T}\}} (f^\epsilon - g^\epsilon) \le \sup_{\tilde{\Gamma} \times \{t_1, \dots, t_{N_T}\} \cup \tilde{\mathcal{M}} \times \{0\}} |f^\epsilon - g^\epsilon|. $$

We now establish the existence and the regularity properties of a discrete solution.

**Lemma A.3** (Existence and Lipschitz regularity properties in time and space for the scheme $(\mathcal{P}_\epsilon^{\text{FD}})$). Assume that assumptions (H.1)-(H.5), (H.8)-(H.11) and (H.14)-(H.15) hold. Then there exists a discrete solution $f^\epsilon$ to $(\mathcal{P}_\epsilon^{\text{FD}})$ and for all $(x, y) \in \tilde{\mathcal{M}} \times \tilde{\mathcal{M}}$ and $t \in \{t_1, \dots, t_{N_T}\}$, the following holds

$$ (64) \qquad |f^\epsilon(x, t) - f^\epsilon(x, t - \Delta t)| \le L\Delta t, $$

$$ (65) \qquad |f^\epsilon(x, t) - f^\epsilon(y, t)| \le K (d_{\mathcal{M}}(x, y) + \epsilon), $$

where $L = L_{f_0^\epsilon} + \|\tilde{P}\|_{L^\infty(\tilde{\mathcal{M}}\setminus\tilde{\Gamma})}$ and $K = 4a^{-1} \max((a + C_{\mathcal{M}})\|\tilde{P}\|_{L^\infty(\tilde{\mathcal{M}}\setminus\tilde{\Gamma})}, c_\eta^{-1}C_\eta(L + \|\tilde{P}\|_{L^\infty(\tilde{\mathcal{M}}\setminus\tilde{\Gamma})}))$.

*Proof.* The proof is the same as the one in [16, Lemma B.3] and we skip it. $\square$

<figure><img src="image_1.png" /></figure>

# APPENDIX B. COVERING NUMBER OF $\mathcal{M}$

We will give a lower bound of the covering number of the manifold $\mathcal{M}$ that will be needed in the proof of Lemma 5.2. We first recall that a $\delta$-covering number $N(\mathcal{M}, \delta)$ of a manifold $\mathcal{M}$ is the smallest number of (geodesic) balls of radius $\delta$ needed to cover $\mathcal{M}$. The condition of the radius is linked with the geometry of the manifold, including its curvature. One of the ways to describe the curvature of Riemannian manifolds is the sectional curvature $K(\sigma_p)$, which depends on a two-dimensional linear subspace $\sigma_p$ of the tangent space at a point $p$ on the manifold. More precisely, given two linearly independent tangent vectors at the same point, $u$ and $v$, we can define

$$ K(u, v) = \frac{\langle R(u, v)v, u \rangle}{\langle u, u \rangle \langle v, v \rangle - \langle u, v \rangle^2}. $$

Here $R$ is the Riemannian curvature tensor, defined by $R(u, v)w = \nabla_u \nabla_v w - \nabla_v \nabla_u w - \nabla_{[u, v]} w$. For example, the sectional curvature of a $n$-sphere of radius $r$ is $K = 1/r^2$. As for the injectivity radius at a point $x \in \mathcal{M}$, it is the supremum of all positive real numbers for which the exponential map is a diffeomorphism when restricted to the open ball of radius $r$ centered at $x$ in the tangent space $T_x\mathcal{M}$. Moreover, the injectivity radius of $\mathcal{M}$ is the infimum of the injectivity radii at all points in $\mathcal{M}$. In [25], the authors have shown that if $\delta$ satisfies assumption (H.17), then there exists a strictly positive constant $C$ such that

$$ N(\mathcal{M}, \delta) \le C \text{vol}(\mathcal{M}) \delta^{-m*}. $$
**Acknowledgment.** This research was partially funded by l'Agence Nationale de la Recherche (ANR), project ANR-22-CE40-0010. For the purpose of open access, the authors have applied a CC-BY public copyright license to any Author Accepted Manuscript (AAM) version arising from this submission.

## REFERENCES

[1] D. AZAGRA, J. FERRERA, AND F. LÓPEZ-MESAS, *Nonsmooth analysis and Hamilton–Jacobi equations on Riemannian manifolds*, Journal of Functional Analysis, 220 (2005).

[2] D. AZAGRA, J. FERRERA, AND F. LÓPEZ-MESAS, *A maximum principle for evolution Hamilton–Jacobi equations on Riemannian manifolds*, Journal of Mathematical Analysis and Applications, 323 (2006), pp. 473–480.

[3] G. BARLES, *First-order Hamilton–Jacobi equations and applications*, CIME Course, (2011).

[4] M. BELKIN AND P. NIYOGI, *Semi-supervised learning on Riemannian manifolds*, Machine learning, 56 (2004), pp. 209–239.

[5] B. BOLLOBÁS, S. JANSON, AND O. RIORDAN, *The phase transition in inhomogeneous random graphs*, Random Structures & Algorithms, 31 (2007), pp. 3–122.

[6] J. CALDER, *Consistency of Lipschitz learning with infinite unlabeled data and finite labeled data*, SIAM Journal on Mathematics of Data Science, 1 (2019), pp. 780–812.

[7] J. CALDER AND M. ETTEHAD, *Hamilton–jacobi equations on graphs with applications to semi-supervised learning and data depth*, Journal of Machine Learning Research, 23 (2022), pp. 1–62.

[8] F. CAMILLI, A. FESTA, AND D. SCHIEBORN, *An approximation scheme for a Hamilton–Jacobi equation defined on a network*, Applied Numerical Mathematics, 73 (2013), pp. 33–47.

[9] B. CHOW, S.-C. CHU, D. GLICKENSTEIN, C. GUENTHER, J. ISENBERG, T. IVEY, D. KNOPF, P. LU, F. LUO, AND L. NI, *The Ricci flow: techniques and applications*, vol. 135, American Mathematical Society Providence, 2007.

[10] M. G. CRANDALL AND P.-L. LIONS, *On existence and uniqueness of solutions of Hamilton–Jacobi equations*, Nonlinear Analysis: Theory, Methods & Applications, 10 (1984), pp. 353–370.

[11] X. DESQUESNES AND A. ELMOATAZ, *Nonmonotonic front propagation on weighted graphs with applications in image processing and high-dimensional data classification*, IEEE Journal of Selected Topics in Signal Processing, 11 (2017), pp. 897–907.

[12] X. DESQUESNES, A. ELMOATAZ, AND O. LÉZORAY, *Eikonal equation adaptation on weighted graphs: fast geometric diffusion process for local and non-local image and data processing*, Journal of Mathematical Imaging and Vision, 46 (2013), pp. 238–257.

[13] M. P. DO CARMO AND J. FLAHERTY FRANCIS, *Riemannian geometry*, vol. 6, Springer, 1992.

[14] A. ELMOATAZ, O. LEZORAY, AND S. BOUGLEUX, *Nonlocal discrete regularization on weighted graphs: a framework for image and manifold processing*, IEEE transactions on Image Processing, 17 (2008), pp. 1047–1060.

[15] A. ELMOATAZ, O. LEZORAY, S. BOUGLEUX, AND V. T. TA, *Unifying local and nonlocal processing with partial difference operators on weighted graphs*, in International Workshop on Local and Non-Local Approximation in Image Processing, 2008, pp. 11–26.

[16] J. FADILI, N. FORCADEL, T. T. NGUYEN, AND R. ZANTOUT, *Limits and consistency of non-local and graph approximations to the Eikonal equation*, IMA Journal of Numerical Analysis, (2023).

[17] A. FATHI, *Weak kam from a PDE point of view: viscosity solutions of the Hamilton–Jacobi equation and Aubry set*, Proceedings of the Royal Society of Edinburgh Section A: Mathematics, 142 (2012), pp. 1193–1236.

[18] L. GRADY AND J. POLIMENI, *Discrete calculus: Applied analysis on graphs for computational science*, Springer Science & Business Media, 2010.
[19] C. IMBERT, R. MONNEAU, AND H. ZIDANI, *A Hamilton-Jacobi approach to junction problems and application to traffic flows*, ESAIM: Control, Optimisation and Calculus of Variations, 19 (2013), pp. 129–166.

[20] J.-I. ITOH AND T. SAKAI, *Cut loci and distance functions*, Mathematical Journal of Okayama University, 49 (2007), pp. 65–92.

[21] R. KIMMEL AND J. A. SETHIAN, *Computing geodesic paths on manifolds*, Proceedings of the national academy of Sciences, 95 (1998), pp. 8431–8435.

[22] S. LANG, *Fundamentals of differential geometry*, vol. 191, Springer Science & Business Media, 2012.

[23] J. M. LEE, *Manifolds and differential geometry*, vol. 643, American Mathematical Society, 2009.

[24] J. M. LEE, *Introduction to smooth manifolds*, Springer, second ed., 2013.

[25] J.-M. LOUBES AND B. PELLETIER, *A kernel-based classifier on a Riemannian manifold*, Statistics & Decisions, 26 (2008), pp. 35–51.

[26] F. MÉMOLI AND G. SAPIRO, *Fast computation of weighted distance functions and geodesics on implicit hyper-surfaces*, Journal of Computational Physics, 173 (2001), pp. 730–764.

[27] F. MÉMOLI AND G. SAPIRO, *Distance functions and geodesics on submanifolds of $\mathbb{R}^d$ and point clouds*, SIAM Journal on Applied Mathematics, 65 (2005), pp. 1227–1260.

[28] M. MOLINA-FRUCTUOSO AND R. MURRAY, *Eikonal depth: an optimal control approach to statistical depths*, arXiv preprint arXiv:2201.05274, (2022).

[29] ——, *Tukey depths and Hamilton-Jacobi differential equations*, SIAM Journal on Mathematics of Data Science, 4 (2022), pp. 604–633.

[30] S. OSHER, Z. SHI, AND W. ZHU, *Low dimensional manifold model for image processing*, SIAM Journal on Imaging Sciences, 10 (2017), pp. 1669–1690.

[31] P. PETERSEN, *Riemannian geometry*, vol. 171, Springer, 2006.

[32] T. ROITH AND L. BUNGERT, *Continuum limit of Lipschitz learning on graphs*, Foundations of Computational Mathematics, (2022), pp. 1–39.

[33] J. A. SETHIAN AND A. VLADIMIRSKY, *Fast methods for the Eikonal and related Hamilton-Jacobi equations on unstructured meshes*, Proceedings of the National Academy of Sciences, 97 (2000), pp. 5699–5703.

[34] Y. SHU, *Hamilton-Jacobi equations on graphs and applications*, Potential Analysis, 48 (2018), pp. 125–157.

[35] V.-T. TA, A. ELMOATAZ, AND O. LÉZORAY, *Adaptation of Eikonal equation over weighted graph*, in International conference on scale space and variational methods in computer vision, Springer, 2009, pp. 187–199.

[36] M. TOUTAIN, A. ELMOATAZ, F. LOZES, AND A. MANSOURI, *Non-local discrete $\infty$-poisson and Hamilton-Jacobi equations: From stochastic game to generalized distances on images, meshes, and point clouds*, Journal of Mathematical Imaging and Vision, 55 (2016), pp. 229–241.

[37] F.-E. WOLTER, *Distance function and cut loci on a complete Riemannian manifold*, Archiv der Mathematik, 32 (1979), pp. 92–96.

RITA ZANTOUT: INSA ROUEN NORMANDIE, NORMANDIE UNIV, LMI UR 3226, F-76000 ROUEN, FRANCE.
*Email address: rita.zantout@insa-rouen.fr*

NICOLAS FORCADEL: INSA ROUEN NORMANDIE, NORMANDIE UNIV, LMI UR 3226, F-76000 ROUEN, FRANCE.
*Email address: nicolas.forcadel@insa-rouen.fr*

JALAL FADILI: NORMANDIE UNIV, ENSICAEN, CNRS, GREYC, FRANCE.
*Email address: Jalal.Fadili@greyc.ensicaen.fr*