Jalal Fadili

Nicolas Forcadel

AND Thi Tuyen Nguyen

LIMITS AND CONSISTENCY OF NON-LOCAL AND GRAPH APPROXIMATIONS TO THE EIKONAL EQUATION

Keywords: 2000 Mathematics Subject Classification. 70H20, 49L25, 65N15, 58J32, 60D05, 05C90 Eikonal equation, Non-local, Viscosity solution, Error bounds, Continuum limits, Weighted graphs

In this paper, we study a non-local approximation of the time-dependent (local) Eikonal equation with Dirichlet-type boundary conditions, where the kernel in the non-local problem is properly scaled. Based on the theory of viscosity solutions, we prove existence and uniqueness of the viscosity solutions of both the local and non-local problems, as well as regularity properties of these solutions in time and space. We then derive error bounds between the solution to the non-local problem and that of the local one, both in continuous-time and Forward Euler time discretization. We then turn to studying continuum limits of non-local problems defined on random weighted graphs with n vertices. In particular, we establish that if the kernel scale parameter decreases at an appropriate rate as n grows, then almost surely, the solution of the problem on graphs converges uniformly to the viscosity solution of the local problem as the time step vanishes and the number vertices n grows large.

I

In recent years, nonlinear partial differential equations (PDEs) on graphs and networks have attracted increasing interest since they naturally arise in many practical problems in mathematics, physics, biology, economy and data science (e.g., internet and vehicular traffic, social networks, population dynamics, image processing and computer vision, machine learning); see [START_REF] Berkolaiko | Introduction to Quantum Graphs[END_REF][START_REF] Elmoataz | Nonlocal discrete regularization on weighted graphs: a framework for image and manifold processing[END_REF][START_REF] Garavello | Traffic flow on networks[END_REF][START_REF] Pokornyi | Differential equations on networks (geometric graphs)[END_REF] and references therein. Among those PDEs, Hamilton-Jacobi equations, including Eikonal-type equations, have been considered in [START_REF] Desquesnes | Non-monotonic front propagation on weighted graphs with applications in image processing and high-dimensional data classification[END_REF][START_REF] Desquesnes | Eikonal equation adaptation on weighted graphs: fast geometric diffusion process for local and non-local image and data processing[END_REF][START_REF] Juan | Nonlinear elliptic partial differential equations and p-harmonic functions on graphs[END_REF][START_REF] Ta | Adaptation of eikonal equation over weighted graphs[END_REF][START_REF] Ta | Nonlocal PDEs-based morphology on weighted graphs for image and data processing[END_REF][START_REF] Toutain | Non-local discrete ∞-Poisson and Hamilton-Jacobi equations: From stochastic game to generalized distances on images, meshes, and point clouds[END_REF] on weighted graphs for data processing, and in [START_REF] Achdou | Hamilton-Jacobi equations constrained on networks[END_REF][START_REF] Camilli | Shortest paths and Eikonal equations on a graph[END_REF][START_REF] Camilli | An approximation scheme for a Hamilton-Jacobi equation defined on a network[END_REF][START_REF] Imbert | A Hamilton-Jacobi approach to junction problems and application to traffic flows[END_REF][START_REF] Schieborn | Viscosity solutions of Eikonal equations on topological networks[END_REF] on topological networks or other very special types of networks. From a different motivation, Hamilton-Jacobi equations on graphs were also studied in [START_REF] Shu | Hamilton-Jacobi equations on graph and applications[END_REF] to derive discrete versions of some functional inequalities.

Our main goal in this paper is to rigorously study continuum limits of the Eikonal equation defined on weighted graphs, as the number of vertices goes to infinity. The motivation behind considering the Eikonal equation on graphs is the ability to extend it to any discrete data that can be represented by weighted graphs. In such a setting, data points are vertices of the graph, and are connected by edges if sufficiently close in a certain ground metric. The edges are assigned weights (e.g., based on the distances between data points). Several works have considered the approximation of the Eikonal equation on triangular, unstructured meshes or grids; see [START_REF] Barth | Numerical schemes for the Hamilton-Jacobi and level set equations on triangulated domains[END_REF][START_REF] Carlini | A generalized fast marching method on unstructured triangular meshes[END_REF][START_REF] Kimmel | Computing geodesic paths on manifolds[END_REF] and references therein. Adaptation of the Eikonal equation on graphs for discrete data processing has been proposed in [START_REF] Ta | Adaptation of eikonal equation over weighted graphs[END_REF][START_REF] Desquesnes | Eikonal equation adaptation on weighted graphs: fast geometric diffusion process for local and non-local image and data processing[END_REF]; see [START_REF] Achdou | Hamilton-Jacobi equations constrained on networks[END_REF]. This has led to many applications including semisupervised clustering and classification on meshes, point clouds, or images [START_REF] Ta | Adaptation of eikonal equation over weighted graphs[END_REF][START_REF] Desquesnes | Eikonal equation adaptation on weighted graphs: fast geometric diffusion process for local and non-local image and data processing[END_REF][START_REF] Toutain | Non-local discrete ∞-Poisson and Hamilton-Jacobi equations: From stochastic game to generalized distances on images, meshes, and point clouds[END_REF][START_REF] Desquesnes | Non-monotonic front propagation on weighted graphs with applications in image processing and high-dimensional data classification[END_REF]; see also [START_REF] Mémoli | Distance functions and geodesics on submanifolds of R d and point clouds[END_REF] which proposed a framework dedicated to solve the Eikonal equation on point clouds. Despite availability of compelling numerical evidence for the efficiency of (1) for these tasks, a clear theoretical understanding of its solutions is lacking and no results on its consistency are available to the best of our knowledge. In particular it is largely open to determine whether solutions of the graph-based Eikonal equation converge, as the number of available data points/vertices increases, to a solution of a limiting equation in the continuum setting. It is our aim in this paper to settle this question. Assumptions (H.1)-(H.2) imply that ∂Ω ⊆ Γ. The fact that Ω is finite in assumption (H.1) is only required to get the existence of a solution for the non-local problem (P ε ) (see Proposition 2.12). The rest of our results, for instance our error bounds, do not need this finiteness assumption. Nevertheless, since our primary motivation in this paper is the study of the Eikonal equation on graphs, this assumption is quite natural. Let us also point out that the existence in the case of a continuous set Ω should be obtained by a discretization of this set. The regularity assumption (H.5) on the distance function is classically ensured when, for instance, Γ is a compact smooth embedded manifold without boundary, in which case d 0 = 1; see Appendix A for a discussion. Thus, in the light of the previous observation that ∂Ω ⊆ Γ, (H.5) holds for instance if Ω is a smooth manifold and Γ is a disjoint union of ∂Ω and a smooth embedded manifold without boundary. We also remark that readers familiar with the theory of viscosity solutions of Hamilton-Jacobi equations may have recognized that (H.5) is indeed very useful to construct super-solutions that are compatible with boundary conditions.

Let G = (V, w) be a finite undirected weighted graph without parallel edges, where V ⊂ Ω is the vertex set and every edge (u, v) ∈ V 2 is given a weight w(u, v), where w : V 2 → R + is the weight function. It is understood that w(u, v) = 0 whenever (u, v) are not connected. In [START_REF] Desquesnes | Eikonal equation adaptation on weighted graphs: fast geometric diffusion process for local and non-local image and data processing[END_REF], the authors proposed the following Eikonal equation on a weighted graph G (1)

max v∈V w(u, v)(f (v) -f (u)) -= P (u), u ∈ V \ V 0 , f (u) = 0 u ∈ V 0 ,
where (•) - def = -min(•, 0), and V 0 ⊂ V corresponds to the set of initial seed vertices. By analogy to the continuous setting, (1) describes the evolution of a "propagation front" V 0 on the graph G.

In this paper, inspired by [START_REF] Achdou | Hamilton-Jacobi equations constrained on networks[END_REF], we propose to study the general non-local Eikonal equation in a timedependent form:

(P ε )    ∂ ∂t f ε (u, t) = -∇ - Jε f ε (u, t) ∞ + P (u), (u, t) ∈ ( Ω \ Γ)×]0, T [, f ε (u, t) = ψ(u), (u, t) ∈ ( Γ×]0, T [) ∪ Ω × {0} .
The stationary solution of (P ε ) would satisfy a corresponding Eikonal equation. There are many applications motivating [START_REF] Achdou | Hamilton-Jacobi equations constrained on networks[END_REF], for instance in data processing, analysis and machine learning on graphs, on unstructured meshes or grids, and on point clounds; see [START_REF] Barth | Numerical schemes for the Hamilton-Jacobi and level set equations on triangulated domains[END_REF][START_REF] Carlini | A generalized fast marching method on unstructured triangular meshes[END_REF][START_REF] Desquesnes | Non-monotonic front propagation on weighted graphs with applications in image processing and high-dimensional data classification[END_REF][START_REF] Desquesnes | Eikonal equation adaptation on weighted graphs: fast geometric diffusion process for local and non-local image and data processing[END_REF][START_REF] Kimmel | Computing geodesic paths on manifolds[END_REF][START_REF] Juan | Nonlinear elliptic partial differential equations and p-harmonic functions on graphs[END_REF][START_REF] Mémoli | Distance functions and geodesics on submanifolds of R d and point clouds[END_REF][START_REF] Ta | Adaptation of eikonal equation over weighted graphs[END_REF][START_REF] Ta | Nonlocal PDEs-based morphology on weighted graphs for image and data processing[END_REF][START_REF] Toutain | Non-local discrete ∞-Poisson and Hamilton-Jacobi equations: From stochastic game to generalized distances on images, meshes, and point clouds[END_REF] with different choices made for the potential P , boundary points and data ( Γ, ψ).

In (P ε ), we have defined

∇ - Jε f ε (u, t) ∞ = max v∈ Ω ∇ - Jε f ε (u, v, t),
where ∇ - Jε is a non-local operator coined the weighted directional internal gradient operator, introduced in [START_REF] Desquesnes | Eikonal equation adaptation on weighted graphs: fast geometric diffusion process for local and non-local image and data processing[END_REF], and reads

∇ - Jε f ε (u, v, t) = J ε (u, v)(f ε (v, t) -f ε (u, t)) -,
where, for ε > 0, J ε : R m × R m → R + is an ε-scaled kernel function,

J ε (u, v) = 1 ε J u ε , v ε with J(u, v) = 1 C g g(|u -v|),
where C g > 0 will be defined in Remark 1.1. The above says that the kernel J is isotropic and g : R + → R + is its radial profile. It is easy to see that ∇ - Jε f ε (u, t) ∞ can be equivalently rewritten as

(2) ∇ - Jε f ε (u, t) ∞ = max v∈ Ω J ε (u, v)(f ε (u, t) -f ε (v, t)).
In the above, ε is a length scale parameter allowing to take into account data density. Indeed, scaling J by ε is intended to give significant weight to pairs of points up to distance ε. To capture properly interactions at scale ε, g has to decay to zero at an appropriate rate. More precisely, our set of admissible kernels will have to satisfy the following requirements:

(H.6) g is a non-negative function. (H.7) ∃r g > 0 such that supp(g) ⊂ [0, r g ].
(H.8) ∃a ∈]0, r g [ such that g is decreasing on [0, a] and satisfies g(a) > 0. We denote by c g def = g(a). (H.9) g is L g -Lipschitz continuous on its support. These assumptions on the kernel are mild and rather standard.

Remark 1.1. We define

C g def = sup t∈R + tg(t),
C g is definitely bounded by (H.7) and (H.9). Moreover, in our proof, it turns out that the support compactness assumption (H.7) is not mandatory. In fact, what is really important is that the supremum in C g is attained in [0, r g ] and that g is bounded. Nevertheless, to make the proofs simpler to follow, we avoid delving into these technicalities and impose (H.7).

(P ε ) covers the case of weighted graphs with n vertices as a special case by properly instantiating the sets ( Ω, Γ); see Section 4. Having this in mind, for a given n-dependent scaling ε n , we will eventually pose the question of consistency on graphs as the continuum limit of the solution to (P ε ) as n → +∞, as well as its time discretized versions. We will therefore consider the time-dependent form of the local Eikonal equation on the continuum:

(P)    ∂ ∂t f (x, t) = -|∇f (x, t)| + P (x), (x, t) ∈ (Ω \ Γ)×]0, T [, f (x, t) = ψ(x), (x, t) ∈ (Γ×]0, T [) ∪ Ω × {0}
where ∇f (x, t) denotes the (weak) gradient of f in the space variable x. Before going further, let us perform an easy yet informative calculation just to convince the reader that it is reasonable to hope for a convergence result of a solution of (P ε ) to that of (P). More precisely, let us look at the behaviour of the non-local directional internal gradient operator as ε is sent to 0. For simplicity, we assume that Ω = Ω and Γ = ∂Ω. Though this case does not comply with assumption (H.1), it gives a fair idea of the computations we will have to carry out rigorously, and we will explain in Section 3.1 how to handle properly the case of a discrete Ω. Let u ∈ Ω \ ∂Ω. To avoid trivialities, we assume that ∃v ∈ Ω such that |u -v| ∈ εsupp(g) (this assumption will be discussed in detail later, see Sections 3.1 and 4). If f is differentiable at u, then we have for ε sufficiently small,

∇ - Jε f (u, t) ∞ = max v∈Ω,|u-v|∈εsupp(g) J ε (u, v)(f (u, t) -f (v, t)) = max v∈Ω,|u-v|∈εsupp(g) (εC g ) -1 g |u -v| ε (f (u, t) -f (v, t)) = max v∈Ω,|u-v|∈εsupp(g) (εC g ) -1 g |u -v| ε ∇f (u, t), u -v + o(1) = max τ ∈[0,rg] (εC g ) -1 g(τ ) max v∈Ω,|u-v|=ετ ∇f (u, t), u -v + o(1).
For ε small enough, we have B εrg (u) ⊂ Ω. This entails that

∇ - Jε f (u, t) ∞ = max τ ∈[0,rg] (εC g ) -1 g(τ ) max v∈Bετ (u) ∇f (u, t), v -u + o(1) = max τ ∈[0,rg] (εC g ) -1 g(τ )ετ |∇f (u, t)| + o(1) = |∇f (u, t)| + o(1).
It is our aim in this paper to give this formal calculation a rigorous meaning and to derive convergence rates.

In particular, an important issue in the the previous computation is that the choice of ε depends on the point u. We will explain in Section 3.1 how to resolve this difficulty.

Contributions and relation to prior work.

In this work we intend to provide two related contributions. Their combination allow to quantitatively analyze the Eikonal equation on graph sequences and their continuum limiting behaviour. Our work relies on the important theory of viscosity solutions [START_REF] Barles | First-order Hamilton-Jacobi equations and applications[END_REF]. We start by showing that both the local problem (P) and the non-local one (P ε ) are well-posed, i.e., existence and uniqueness of their viscosity solutions (see Proposition 2.5 and Proposition 2.12). We then establish the regularity properties of these solutions in time and space in Theorem 2.8 and Theorem 2.15. Capitalizing on this, our first consistency result provides error bounds between the viscosity solutions of (P ε ) and (P) (Theorem 3.1). This is extended to the case where (P ε ) is discretized in time using forward Euler schemes (Theorem 3.2). Though we focus on finite differences in time, due to their popularity and simplicity, we believe that our proof can be adapted to other schemes such as those of semi-Lagrangian type. We finally apply these error bounds to a sequence of random weighted graphs (Theorem 4.3). This entails in particular that the time-discretized solution on a weighted graph with n vertices and an appropriately decreasing scale parameter ε n , converges almost surely uniformly to the viscosity solution of (P) as n → +∞ and the time step goes to 0.

Studying consistency and continuum limits of certain evolution and variational problems on graphs and networks is an active research area; see [START_REF] Hafiene | Nonlocal p-Laplacian evolution problems on graphs[END_REF][START_REF] Hafiene | Continuum limit of the nonlocal p-Laplacian evolution problem on random inhomogeneous graphs[END_REF][START_REF] Pérez-Llanos | Numerical approximations for a nonlocal evolution equation[END_REF][START_REF] Medvedev | The nonlinear heat equation on dense graphs[END_REF][START_REF] Medvedev | The nonlinear heat equation on W -random graphs[END_REF][START_REF] García Trillos | Consistency of Cheeger and ratio graph cuts[END_REF][START_REF] García Trillos | Continuum limit of total variation on point clouds[END_REF][START_REF] Slepčev | Analysis of p-Laplacian regularization in semi-supervised learning[END_REF][START_REF] Caroccia | Mumford-Shah functionals on graphs and their asymptotics[END_REF] for a non-exhaustive list and references therein. In particular, the authors in [START_REF] Calder | Consistency of Lipschitz learning with infinite unlabeled data and finite labeled data[END_REF][START_REF] Roith | Continuum limit of Lipschitz learning on graphs[END_REF] studied continumm limits of Lipschitz learning on graphs. The Euler-Lagrange equation for Lipschitz learning, as considered in [START_REF] Calder | Consistency of Lipschitz learning with infinite unlabeled data and finite labeled data[END_REF], correspond to a stationary special case of (P ε ), where the operator (2) is replaced by the ∞-Laplacian on graphs, P ≡ 0, Ω is a set of n points in the flat torus T m = R m /Z m , and Γ ⊂ Ω is a fixed finite collection of points. In such a setting, it is proved in [START_REF] Calder | Consistency of Lipschitz learning with infinite unlabeled data and finite labeled data[END_REF] that the solution of the discrete problem converges uniformly to the unique viscosity solution of an ∞-Laplace type equation on the flat torus, as ε n → 0 when n → +∞. The limit equation turns out to be the stationary version of (P) where Ω = T m , P ≡ 0, ψ = ψ, Γ = Γ, and |∇•| is replaced with the ∞-Laplacian. While finalizing our paper, we also became aware of the recent work of [START_REF] Roith | Continuum limit of Lipschitz learning on graphs[END_REF] who used tools from Γ-convergence theory to prove asymptotic consistency of Lipschitz learning on graphs (though the Γ-limit is not unique), allowing moreover that Ω to be a sufficiently smooth closed set and Γ possibly different from Γ. In both [START_REF] Calder | Consistency of Lipschitz learning with infinite unlabeled data and finite labeled data[END_REF][START_REF] Roith | Continuum limit of Lipschitz learning on graphs[END_REF], for consistency to hold, it is required that the Hausdorff distance between Ω and Ω (and also between Γ and Γ) is o(ε α ) (α = 3/2 in [START_REF] Calder | Consistency of Lipschitz learning with infinite unlabeled data and finite labeled data[END_REF] and α = 1 in [START_REF] Roith | Continuum limit of Lipschitz learning on graphs[END_REF]). Some of their assumptions are different or stronger from those we require in this paper. In addition, we are not aware of any work which establishes continuum limits for an Eikonal equation on weighted graphs of the form (P ε ). We also provide and analyze convergence of a concrete forward Euler discrete-time scheme to solve (P ε ). It is also important to stress the fact that our primary interest is in providing error bounds and non-asymptotic convergence rates. This is known to be more challenging than deriving mere asymptotic consistency results.

Motivated by a continuous version of the shortest path problem, numerical approximations of the Hamilton-Jacobi equations of Eikonal-type defined on a topological network were studied in [START_REF] Camilli | Shortest paths and Eikonal equations on a graph[END_REF][START_REF] Camilli | An approximation scheme for a Hamilton-Jacobi equation defined on a network[END_REF]. A topological network is basically a graph embedded in Euclidean space, i.e., it is a collection of pairwise different points (vertices) in a Euclidean space connected by differentiable, non self-intersecting curves (smooth edges). This is a very special network structure far different from the weighted graph setting we study here.

1.3. Paper organization. The paper is organized as follows. In Section 2, we show that (P) and (P ε ) are well-posed in the sense of viscosity solutions, and we establish some important regularity results that will be central in our error bounds. Section 3 states the main results of this paper. We start with a key error bound between solutions of problems (P ε ) and (P) in both time-continuous case and time-discrete cases using explicit/forward Euler schemes. We then turn to applying these results to weighted graphs in Section 4.

Notations.

In what follows, we will denote •, • the scalar product on R m , and B r (x) the Euclidean ball centered at x ∈ R m of radius r. For a non-empty and closed subset X ∈ R m and x ∈ R m , we denote by Proj X (x) the projection of x on X, i.e., the set of nearest points of x in X:

Proj X (x) = {z ∈ X : |x -z| = d(x, X)} .
Since X is non-empty and closed, Proj X (x) is non-empty at any x ∈ R m but is not necessarily singlevalued. The diameter of X is diam(X) = sup (x,z)∈X 2 |x -z|. Let X and Y be two non-empty subsets of R m . Their Hausdorff distance is defined as

d H (X, Y ) = max sup x∈X d(x, Y ), sup y∈Y d(y, X) .
It is finite when X and Y are bounded, and when X and Y are closed, then d H (X, Y ) = 0 ⇐⇒ X = Y .

We will denote • L ∞ (Σ) , the supremum norm on a domain Σ ⊂ R m .

To lighten notation, we denote the bounded space-time cylinders Ω T = Ω×[0, T ] and ∂Ω T = (Γ×]0, T [)∪ Ω × {0}. We define similarly ΩT and ∂ ΩT . For a time interval [0, T [ and N T ∈ N, we also use the shorthand notation ΩN T = Ω × {0, . . . , t N T } and ∂ ΩN T = Γ × {t 1 , . . . , t N T } ∪ Ω × {0}.

W -

2.1. Problem (P). Since we will work with viscosity solutions, we refer to [START_REF] Barles | First-order Hamilton-Jacobi equations and applications[END_REF][START_REF] Crandall | User's guide to viscosity solutions of second order partial differential equations[END_REF][START_REF] Crandall | On existence and uniqueness of solutions of Hamilton-Jacobi equations[END_REF][START_REF] Ishii | Existence and uniqueness of solutions of Hamilton-Jacobi equations[END_REF] for a good introduction. The notion of viscosity solutions was introduced by Crandall and Lions [START_REF] Crandall | Viscosity solutions of Hamilton-Jacobi equations[END_REF] as a notion of weak solutions for a class of partial differential equations of Hamilton-Jacobi type. In this theory, the derivatives of the unknown are replaced by the derivative of some test functions (see definition below). In order to give the definition of viscosity solution for problem (P), we first recall the definition of upper and lower semi-continuous envelope for a locally bounded function f : Ω T → R, respectively given by

f * (x, t) def = lim sup (y,s)→(x,t) f (y, s) and f * (x, t) def = lim inf (y,s)→(x,t)
f (y, s).

Definition 2.1 (Viscosity solution for (P)). An upper semi-continuous function (usc) function

f : Ω T → R is a viscosity sub-solution of (P) in (Ω \ Γ)×]0, T [ if for any ϕ ∈ C 1 ((Ω \ Γ)×]0, T [) such that f -ϕ reaches a local maximum point at (x 0 , t 0 ) ∈ (Ω \ Γ)×]0, T [, one has ∂ ∂t ϕ(x 0 , t 0 ) ≤ -|∇ϕ(x 0 , t 0 )| + P (x 0 ).
The function f is a viscosity sub-solution of (P) in Ω T if it satisfies moreover f (x, t) ≤ ψ(x) for all (x, t) ∈ ∂Ω T . A lower semi-continuous (lsc) function f : Ω T → R is a viscosity super-solution of (P) in

(Ω \ Γ)×]0, T [ if for any ϕ ∈ C 1 ((Ω\Γ)×]0, T [) such that f -ϕ attains a local minimum point at (x 0 , t 0 ) ∈ (Ω\Γ)×]0, T [, one has ∂ ∂t ϕ(x 0 , t 0 ) ≥ -|∇ϕ(x 0 , t 0 )| + P (x 0 ).
The function f is a viscosity super-solution of (P) in Ω T if it satisfies moreover f (x, t) ≥ ψ(x) for all (x, t) ∈ ∂Ω T . Finally, a locally bounded function f : Ω T → R is a viscosity solution of (P) in

(Ω \ Γ)×]0, T [ (resp. in Ω T ) if f * is a viscosity sub-solution and f * is a viscosity super-solution of (P) in (Ω \ Γ)×]0, T [ (resp. in Ω T ).
We continue with a comparison principle for problem (P). Proposition 2.2 (Comparison principle for (P)). Suppose that assumptions (H.1)-(H.4) hold. Let f , an usc function, be a sub-solution of (P) and g, a lsc function, be a super-solution of (P). Then

f ≤ g in Ω T .
Proof. The proof can be found in [4, Theorem 5.1, Remark 5.1].

It is well-known that (P), which accounts for a "Dirichlet-type" boundary condition, cannot be solved for any function ψ; see e.g., [START_REF] Barles | Solutions de viscosité des équations de Hamilton-Jacobi[END_REF]Section 2.6.3]. Thus, in order to construct solutions to (P), compatibility properties between the equation and the boundary conditions are necessary. This is precisely what we impose through the following assumption: (H.10) There exists ψ b ∈ Lip(Ω), with ψ b (x) = ψ(x) for all x ∈ Γ, such that ψ b is a sub-solution of (P) in Ω T .

Remark 2.3. To give better intuition and insight of (H.10), let's give relevant examples of problems that satisfy this assumption. First consider the simplified model, posed in R and without dependence in time:

|u | = 1 in ] -1, 1[ u(x) = Kx for x ∈ {-1, 1},
for some constant K. Clearly, if |K| > 1, it is not possible to construct a solution satisfying the boundary condition in a strong sense. However, it is still possible to construct a solution satisfying the boundary condition in a weak sense (i.e. either the boundary condition or the equation is satisfied at the boundary; see [START_REF] Barles | Solutions de viscosité des équations de Hamilton-Jacobi[END_REF]) but this is not what we want to do here. This is the reason why we have to impose a kind of compatibility condition between the boundary conditions and the equation. For this example, assumption (H.10) is ensured as soon as |K| ≤ 1.

Another prominent example where assumption (H.10) is satisfied is when ψ = 0 and P ≥ 0 in (P). This setting corresponds to a time-dependent Eikonal equation where the steady state solution can be interpreted as the shortest traveling time or distance of a point x ∈ Ω to front Γ, where the travel inverse speed is P . This example plays an important role for computing distance functions which is a key step in numerous applications including image processing or computational computational geometry [START_REF] Osher | Fronts propagating with curvature-dependent speed-algorithms based on hamilton-jacobi formulations[END_REF][START_REF] Sethian | A fast marching level-set method for monotonically advancing fronts[END_REF][START_REF] Sethian | Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry[END_REF].

Remark 2.4. Assumption (H.10) entails in particular that

|∇ψ b (x)| ≤ P L ∞ (Ω\Γ) ,
and thus the Lipschitz constant L ψ b satisfies

L ψ b ≤ P L ∞ (Ω\Γ) .
We then have the following result which gives the existence and uniqueness of viscosity solution for problem (P).

Proposition 2.5 (Existence and uniqueness for (P)). Suppose that assumptions (H.1)-(H.5) and (H.10) hold.

Then, problem (P) admits a unique viscosity solution f (which is in fact continuous). Moreover, there exists a function f ∈ Lip(Ω T ), with a Lipschitz constant depending on a 0 , d 0 , L ψ and P L ∞ (Ω\Γ) , such that

(3) ψ b ≤ f ≤ f in Ω T .
Before giving the proof of this proposition, we first define the notion of barrier solutions and then recall Perron's method.

Definition 2.6 (Barrier sub-and super-solution). An usc function

f : Ω T → R is a barrier sub-solution of (P) if it is a viscosity sub-solution in (Ω \ Γ)×]0, T [ and if it satisfies moreover lim y→x,s→t f (y, s) = ψ(x) ∀(x, t) ∈ Γ × [0, T ]. A lsc function f : Ω T → R is a barrier super-solution of (P) if it is a viscosity super-solution in (Ω \ Γ)×]0, T [ and if it satisfies moreover lim y→x,s→t f (y, s) = ψ(x) ∀(x, t) ∈ Γ × [0, T ].
Theorem 2.7 (Perron's method [START_REF] Ishii | Perron's method for Hamilton-Jacobi equations[END_REF]). Assume that there exists a barrier sub-solution f and a barrier supersolution f of (P). Then there exists a (possibly discontinuous) viscosity solution f of (P) satisfying moreover

f ≤ f ≤ f in Ω T .
We are now ready to prove Proposition 2.5.

Proof of Proposition 2.5. By assumption (H.10), ψ b is a barrier sub-solution of (P). We then have to construct a barrier super-solution f . Existence will then be a direct consequence of Perron's method as recalled in Theorem 2.7 while uniqueness and continuity will be direct consequences of the comparison principle shown in Proposition 2.2. Let

f 1 (x, t) = ψ(x) + K 1 t, (x, t) ∈ Ω T ,
where K 1 = P L ∞ (Ω\Γ) , and

f 2 (x, t) = ψ(x) + K 2 d(x, Γ), (x, t) ∈ Ω T ,
with K 2 > 0 large enough to be determined later. We set

(4) f (x, t) = min(f 1 (x, t), f 2 (x, t)) = min(ψ(x) + K 1 t, ψ(x) + K 2 d(x, Γ)).
We claim that f is a barrier super-solution.

First, observe that

L f ≤ max L f 1 , L f 2 ≤ L ψ + max P L ∞ (Ω\Γ) , K 2 , since ψ ∈ Lip(Ω) by (H.4) and L d(•,Γ) = 1 as Γ = ∅. In particular, f is continuous. Moreover, we have for x ∈ Γ, f 2 (x, t) = ψ(x) ≤ f 1 (x, t). Hence (5) f (x, t) = ψ(x), ∀(x, t) ∈ Γ × [0, T ],
which shows, via continuity that the limit property required in Definition 2.6 holds. It remains to prove that f is a super-solution on

(Ω \ Γ)×]0, T [ for K 2 large enough.
Observe first that by taking

K 2 ≥ K 1 T /a 0 , we have for all x ∈ Ω \ N a 0 Γ (recall that N a 0 Γ is defined in assumption (H.5)), f 2 (x, t) ≥ ψ(x) + K 2 a 0 ≥ ψ(x) + K 1 T ≥ f 1 (x, t),
and thus (4) becomes 6) and ( 7) that

(6) f (x, t) = min(f 1 (x, t), f 2 (x, t)) if (x, t) ∈ N a 0 Γ × [0, T ], f 1 (x, t) if (x, t) ∈ Ω \ N a 0 Γ × [0, T ]. Following Definition 2.1, let ϕ ∈ C 1 ((Ω \ Γ)×]0, T [) such that f -ϕ reaches a local minimum at some (x 0 , t 0 ) ∈ (Ω \ Γ)×]0, T [. This is equivalent to (7) f (y, s) -ϕ(y, s) ≥ f (x 0 , t 0 ) -ϕ(x 0 , t 0 ), for all (y, s) ∈ (Ω \ Γ)×]0, T [ sufficiently close to (x 0 , t 0 ). We now distinguish different cases. Case 1 x 0 ∈ Ω \ N a 0 Γ . In this case, since (Ω \ N a 0 Γ ) ⊂ (Ω \ Γ), it follows from (
f 1 (y, s) -ϕ(y, s) ≥ f (y, s) -ϕ(y, s) ≥ f 1 (x 0 , t 0 ) -ϕ(x 0 , t 0 ), for all (y, s) ∈ (Ω \ Γ)×]0, T [ sufficiently close to (x 0 , t 0 ). As ]0, T [ is open, we take y = x 0 and s = t 0 + h ∈]0, T [ for h > 0 sufficiently small, which gives us (8) ϕ(x 0 , t 0 + h) -ϕ(x 0 , t 0 ) ≤ f 1 (x 0 , t 0 + h) -f 1 (x 0 , t 0 ) = K 1 h.
Dividing by h and passing to the limit as h → 0 + , we get

∂ ∂t ϕ(x 0 , t 0 ) ≤ K 1 . (9)
Embarking from [START_REF] Calder | Consistency of Lipschitz learning with infinite unlabeled data and finite labeled data[END_REF] where we replace h by -h yields (10)

∂ ∂t ϕ(x 0 , t 0 ) ≥ K 1 ,
and thus

∂ ∂t ϕ(x 0 , t 0 ) = K 1 . (11)
We then deduce that1 (12)

∂ ∂t ϕ(x 0 , t 0 ) + |∇ϕ(x 0 , t 0 )| -P (x 0 ) ≥ K 1 -P (x 0 ) ≥ K 1 -P L ∞ (Ω\Γ) = 0,
which shows the desired inequality in this case 2 .

Case 2 x 0 ∈ N a 0 Γ \ Γ. Let I 0 def = i ∈ {1, 2} : f (x 0 , t 0 ) = f i (x 0 , t 0
) . Thus, for any i 0 ∈ I 0 , we have from ( 7) that ( 13)

f i 0 (y, s) -ϕ(y, s) ≥ f (y, s) -ϕ(y, s) ≥ f (x 0 , t 0 ) -ϕ(x 0 , t 0 ) = f i 0 (x 0 , t 0 ) -ϕ(x 0 , t 0 )
for all y ∈ N a 0 Γ \ Γ close enough to x 0 . If 1 ∈ I 0 then we are done thanks to Case 1. It remains to consider the case where I 0 = {2}. Embarking from [START_REF] Caroccia | Mumford-Shah functionals on graphs and their asymptotics[END_REF] with i 0 = 2, and arguing as we have done for f 1 in Case 1 to show [START_REF] Canino | On p-convex sets and geodesics[END_REF], and using that f 2 is actually t-independent, we get in this case that ( 14)

∂ ∂t ϕ(x 0 , t 0 ) = 0.
On the other hand, since N a 0 Γ \ Γ is open by (H.2) and (H.5), we have y = x 0 + hz ∈ N a 0 Γ \ Γ for h > 0 small enough and any z ∈ R m such that |z| = 1. Thus, in view of (H.5), inequality ( 13

) becomes (ϕ(•, t 0 ) -K 2 d(•, Γ))(x 0 + hz) -(ϕ(•, t 0 ) -K 2 d(•, Γ))(x 0 ) h ≥ ψ(x 0 + hz) -ψ(x 0 ) h ≥ -L ψ .
Passing to the limit as h → 0 + , we get ∇ϕ(x 0 , t 0 ) -K 2 ∇d(x 0 , Γ), z ≥ -L ψ .

If ∇ϕ(x 0 , t 0 ) -K 2 ∇d(x 0 , Γ) = 0, we have from ( 14) and (H.5) that

∂ ∂t ϕ(x 0 , t 0 ) + |∇ϕ(x 0 , t 0 )| -P (x 0 ) = K 2 ∇d(x 0 , Γ) -P (x 0 ) ≥ K 2 d 0 -P L ∞ (Ω\Γ) ≥ 0 (15) for K 2 ≥ P L ∞ (Ω\Γ) /d 0 .
In the case where ∇ϕ(x 0 , t 0 ) -K 2 ∇d(x 0 , Γ) = 0, we choose

z = ± ∇ϕ(x 0 , t 0 ) -K 2 ∇d(x 0 , Γ) |∇ϕ(x 0 , t 0 ) -K 2 ∇d(x 0 , Γ)| to arrive at |∇ϕ(x 0 , t 0 ) -K 2 ∇d(x 0 , Γ)| ≤ L ψ .
Combining this inequality with ( 14) and (H.5), we get

∂ ∂t ϕ(x 0 , t 0 ) + |∇ϕ(x 0 , t 0 )| -P (x 0 ) ≥K 2 |∇d(x 0 , Γ)| -|∇ϕ(x 0 , t 0 ) -K 2 ∇d(x 0 , Γ)| -P (x 0 ) ≥K 2 d 0 -L ψ -P L ∞ (Ω\Γ) ≥0 (16) for K 2 ≥ (L ψ + P L ∞ (Ω\Γ) )/d 0 .
In summary, taking K 2 ≥ max (L ψ + P L ∞ (Ω\Γ) )/d 0 , K 1 T /a 0 , the inequalities ( 12), ( 15) and ( 16) hold in each respective case, and thus the desired super-solution inequality is satisfied in all cases. We then conclude that f is a barrier super-solution. The existence of f and the bound (3) are then direct consequences of Perron's method.

We finish this section by a regularity result.

Theorem 2.8 (Regularity of the solution of (P)). Suppose that assumptions (H.1)-(H.5) and (H.10) hold.

Then the unique viscosity solution to the problem (P) satisfies the following regularity properties

f (x, •) ∈ Lip([0, T [) with L f (x,•) ≤ P L ∞ (Ω\Γ) + L ψ , ∀x ∈ Ω, (17) f (•, t) ∈ Lip(Ω) with L f (•,t) ≤ 2 P L ∞ (Ω\Γ) + L ψ , ∀t ∈ [0, T ]. (18) Proof. When x ∈ Γ, (17) obviously holds. It remains to consider the case (x, t) ∈ (Ω \ Γ) × [0, T [. Let h > 0 sufficiently small and set l(x, t) = f (x, t + h) for all (x, t) ∈ Ω T . One then has l(x, 0) = f (x, h) for all (x, t) ∈ (Γ×]0, T [) ∪ Ω × {0} and thus it is easy to verify that l satisfies    ∂ ∂t l(x, t) = -|∇l(x, t)| + P (x), (x, t) ∈ (Ω \ Γ)×]0, T [, l(x, t) = f (x, h), (x, t) ∈ (Γ×]0, T [) ∪ Ω × {0}.
This entails that f (x) and f (x, t + h) are solutions of the same equation (P), respectively with initial conditions ψ and f (x, h). Applying again the comparison result of Proposition 2.2 we have

(19) |f (x, t + h) -f (x, t)| ≤ |f (x, h) -ψ(x)|.
To conclude, it remains to show that the right hand side of ( 19) is O(h). Let us define, for

(x, t) ∈ Ω T , f 1 (x, t) = ψ(x) -Lt; f 2 (x, t) = ψ(x) + Lt,
where L = P L ∞ (Ω\Γ) + L ψ . Arguing in the same way as we have done for f 1 in the proof of Proposition 2.5, we get that f 1 and f 2 are respectively a sub-and a super-solution of (P). Hence, by the comparison principle in Proposition 2.2, we obtain

ψ(x) -Lt ≤ f (x, t) ≤ ψ(x) + Lt, whence we get |f (x, t) -ψ(x)| ≤ Lt, (20)
Combining [START_REF]The Courant-Friedrichs-Lewy (CFL) condition: 80 Years After Its Discovery[END_REF] and [START_REF] Desquesnes | Non-monotonic front propagation on weighted graphs with applications in image processing and high-dimensional data classification[END_REF]

yields |f (x, t + h) -f (x, t)| ≤ Lh.
We now turn to the space regularity bound [START_REF] Crandall | On existence and uniqueness of solutions of Hamilton-Jacobi equations[END_REF] and adapt the argument of [START_REF] Barles | First-order Hamilton-Jacobi equations and applications[END_REF]Theorem 8.1]. We introduce the test-function

Ψ : (x, t, y) ∈ Ω T × Ω → f (x, t) -f (y, t) -K|x -y|,
and we aim at showing that Ψ is negative for sufficiently large K > 0. When t = 0 or (x, y) ∈ Γ 2 , we can choose K ≥ L ψ to have that ( 18) holds. We argue by contradiction, assuming that sup

(x,t,y)∈Ω T ×Ω Ψ(x, t, y) > 0.
Continuity of f and compactness of Ω T × Ω entail that the supremum of Ψ is actually a maximum attained at some point (x, t, ȳ) ∈ Ω T × Ω. In order to use viscosity solutions arguments, we use the classical doubling of the variable in time, and introduce the function, for α > 0,

Ψ α : (x, t, y, s) ∈ Ω 2 T → f (x, t) -f (y, s) -K|x -y| - |t -s| 2 2α .
This function has a maximum attained at some point in Ω 2 T , say (x α , t α , y α , s α ). We obviously have

(21) Ψ α (x α , t α , y α , s α ) ≥ Ψ α (x, t, ȳ, t) = Ψ(x, t, ȳ) > 0.
Observe also that for α sufficiently small, we cannot have x α = y α as otherwise Ψ α (x α , t α , y α , s α ) would be negative, hence contradicting [START_REF] Desquesnes | Eikonal equation adaptation on weighted graphs: fast geometric diffusion process for local and non-local image and data processing[END_REF].

If x α ∈ Γ, then f (x α , t α ) = ψ(x α ) = ψ b (x α ). Moreover, by Proposition 2.5, ψ b (y α ) ≤ f (y α , s α ). It then follows that Ψ α (x α , t α , y α , s α ) ≤ψ b (x α ) -f (y α , s α ) -K|x α -y α | ≤ψ b (x α ) -ψ b (y α ) -K|x α -y α | ≤(L ψ b -K)|x α -y α | ≤( P L ∞ (Ω\Γ) -K)|x α -y α |
where we used Remark 2.4.

Taking K ≥ P L ∞ (Ω\Γ) contradicts positivity of Ψ α (x α , t α , y α , s α ) on Γ.
Consider in the rest the case

x α ∈ Ω \ Γ. Since x α = y α , the function (x, t) → f (y α , s α ) + K|x -y α | + |t-sα| 2 2α
is smooth at (x α , t α ) and since f is sub-solution, we have

t α -s α α + K ≤ P (x α ).
On the other hand, maximality of Ψ α at (x α , t α , y α , s α ) implies, for all t ∈ [0, T ]

f (x α , t) - |t -s α | 2 2α ≤ f (x α , t α ) - |t α -s α | 2 2α .
Choosing t such that t α -s α and t α -t are of same sign, and using [START_REF] Crandall | Two approximations of solutions of Hamilton-Jacobi equations[END_REF], we get

L|t -t α | ≥f (x α , t α ) -f (x α , t) ≥ |t α -s α | 2 2α - |t -s α | 2 2α = - |t -t α | 2 2α + |t -t α | |t α -s α | α .
Dividing by |t -t α | and taking t → t α , we get

|t α -s α | α ≤ L.
Hence,

K ≤ P L ∞ (Ω\Γ) + L.
Choosing K > P L ∞ (Ω\Γ) + L we get again a contradiction of the positivity of Ψ α (x α , t α , y α , s α ) on Ω \ Γ. The above proof shows then that

f (x, t) -f (y, t) -K|x -y| ≤ 0 fo all (x, y, t) ∈ Ω 2 × [0, T ] and every K > 2 P L ∞ (Ω\Γ) + L ψ , i.e., f (•, t
) is globally Lipschitz continuous uniformly in t, hence providing the bound (18).

Problem (P ε

). We begin by the definition of viscosity solution for problem (P ε ).

Definition 2.9 (Viscosity solution for (P ε )). An usc function

f ε : ΩT → R is a viscosity sub-solution of (P ε ) in ( Ω \ Γ)×]0, T [ if for any (u 0 , t 0 ) ∈ ( Ω \ Γ)×]0, T [ and ϕ ∈ C 1 (]0, T [) such that f ε (u 0 , •) -ϕ attains a local maximum point at t 0 ∈]0, T [, one has ∂ ∂t ϕ(t 0 ) ≤ -∇ - Jε f ε (u 0 , t) ∞ + P (u 0 ).
The function f ε is a viscosity sub-solution of

(P ε ) in ΩT if it satisfies moreover f ε (u, t) ≤ ψ(u) for all (u, t) ∈ ∂ ΩT . A lsc function f ε : ΩT → R is a viscosity super-solution of (P ε ) in ( Ω \ Γ)×]0, T [ if for any (u 0 , t 0 ) ∈ ( Ω \ Γ)×]0, T [ and ϕ ∈ C 1 (]0, T [) such that f ε (u 0 , •) -ϕ attains a local minimum point at t 0 , one has ∂ ∂t ϕ(t 0 ) ≥ -∇ - Jε f ε (u 0 , t) ∞ + P (u 0 ).
The function f ε is a viscosity super-solution of

(P ε ) in ΩT if it satisfies moreover f ε (u, t) ≥ ψ(u) for all (u, t) ∈ ∂ ΩT . Finally, a locally bounded function f ε : ΩT → R is a viscosity solution of (P ε ) in ( Ω \ Γ)×]0, T [ (resp. in ΩT ) if (f ε ) * is a viscosity sub-solution and (f ε ) * is a viscosity super-solution of (P ε ) in ( Ω \ Γ)×]0, T [ (resp. in ΩT ).
We define barrier sub-solution and super-solution of (P ε ) in a similar way as we have done for the local case in Definition 2.6, just replacing by the non-local notion of viscosity sub-and super-solution defined above.

We start by providing a comparison result for problem (P ε ).

Proposition 2.10 (Comparison principle for (P ε )). Suppose that assumptions (H.1)-(H.2) and (H.6) hold.

Assume that f ε (resp. g ε ) is a bounded viscosity sub-(resp. super-) solution of (P ε ). Then

f ε ≤ g ε in ΩT .
Proof. We argue by contradiction and suppose that there exists some point (z, s) ∈ ΩT such that

f ε (z, s) -g ε (z, s) > 0.
For η > 0 sufficiently small, we introduce the function

Ψ η : (u, t) ∈ ΩT → f ε (u, t) -g ε (u, s) -η T -t and denote M η = sup (u,t)∈ ΩT Ψ η (u, t).
By upper semi-continuity and compactness, M η is actually a maximum attained at some point on ΩT , say (ũ * , t * ). Moreover, from the positivity assumption, we have M η > 0 for η > 0 small enough. We now duplicate the time variable and consider, for γ > 0, the function

Ψ η,γ : (u, t, s) ∈ Ω × [0, T ] 2 → f ε (u, t) -g ε (u, s) - |t -s| 2 2γ - η T -t ,
and we denote M γ,η = sup

(u,t,s)∈ Ω×[0,T ] 2 Ψ η,γ (u, t, s).
Again, upper semi-continuity and compactness entails that the supremum is actually a maximum which is attained at some point (ū γ , tγ , sγ ) ∈ Ω × [0, T ] 2 . We also have for η sufficiently small

M γ,η ≥ Ψ η,γ (ũ * , t * , t * ) = Ψ η (ũ * , t * ) = M η > 0.
Using classical arguments (see, e.g., [4, Lemma 5.2]), we deduce that there exists (u

* , t * ) ∈ Ω × [0, T [ such that (22)      ūγ → u * as γ → 0, tγ , sγ → t * as γ → 0, Ψ η (u * , t * ) = M η .
Note that if t * = 0, then we would have

0 < M η = f ε (u * , 0) -g ε (u * , 0) - η T ≤ ψ(u * ) -ψ(u * ) = 0,
which is absurd. Hence t * > 0 which, in view of [START_REF] Elmoataz | Nonlocal discrete regularization on weighted graphs: a framework for image and manifold processing[END_REF], implies that tγ > 0 for γ small enough. Moreover, if ūγ ∈ Γ, then

0 < M γ,η ≤ f ε (ū γ , tγ ) -g ε (ū γ , sγ ) ≤ ψ(ū γ ) -ψ(ū γ ) = 0,
which is again absurd. Hence ūγ ∈ Ω \ Γ.

The function t → g ε (ū γ , sγ ) + |t-sγ | 2 2γ
+ η T -t is smooth at tγ > 0, and reaches a maximum in tγ . Since f ε is a viscosity sub-solution of (P ε ), we deduce that tγ -sγ

γ + η T 2 + ∇ - Jε f ε (ū γ , tγ ) ∞ -P (ū γ ) ≤ 0.
Arguing in the same way, but now on g ε , and using it is a viscosity super-solution of (P ε ), we get that tγ -sγ

γ + ∇ - Jε g ε (ū γ , sγ ) ∞ -P (ū γ ) ≥ 0.
Subtracting the last two inequalities, we obtain

η T 2 ≤ ∇ - Jε g ε (ū γ , sγ ) ∞ -∇ - Jε f ε (ū γ , tγ ) ∞ . ( 23
)
We now use the fact that (ū γ , tγ , sγ ) is a maximum point of Ψ γ,η defined above. This implies in particular that

f ε (v, tγ ) -g ε (v, sγ ) - | tγ -sγ | 2 2γ - η T -tγ ≤ f ε (ū γ , tγ ) -g ε (ū γ , sγ ) - | tγ -sγ | 2 2γ - η T -tγ ,
whence we get

g ε (ū γ , sγ ) -g ε (v, sγ ) ≤ f ε (ū γ , tγ ) -f ε (v, tγ ).
Multiplying both sides of this inequality by J ε , which is non-negative by (H.6), taking the maximum over v ∈ Ω and recalling (2), ( 23) becomes η T 2 ≤ 0 leading to a contradiction.

In the same vein as for problem (P), the following assumption is intended to impose compatibility properties between (P ε ) and the boundary conditions on ∂ ΩT : (H.11) There exists ψb ∈ Lip( Ω), with ψb (u) = ψ(u) for all u ∈ Γ, such that ψb is a sub-solution of (P ε ) in ΩT .

Remark 2.11. We refer to Remark 2.3 for a discussion on this assumption, which is similar to the one made in the local case. For instance, (H.11) holds when ψ = 0 and P ≥ 0. This example, when considered on weighted graphs (see Section 4), corresponds to computing distances on discrete images, meshes, point clouds, or any data that can be represented as a weighted graph; see [START_REF] Toutain | Non-local discrete ∞-Poisson and Hamilton-Jacobi equations: From stochastic game to generalized distances on images, meshes, and point clouds[END_REF][START_REF] Desquesnes | Non-monotonic front propagation on weighted graphs with applications in image processing and high-dimensional data classification[END_REF] and references therein.

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

Proposition 2.12 (Existence result for (P ε )). Suppose that assumptions (H.1)-(H.4), (H.6)-(H.8) and (H.11)

hold. Then, problem (P ε ) admits a unique viscosity solution f ε (which is in fact continuous). Moreover, there exists a function f ε ∈ Lip( Ω) such that [START_REF] Garavello | Traffic flow on networks[END_REF] ψb ≤ f ε ≤ f ε in ΩT .

Remark 2.13. A close inspection of the forthcoming proof reveals that the Lipschitz constant estimate of the barrier super-solution f ε depends on the minimal distance between two points of Ω and can be very large. This is rather pessimistic but seems the price to pay to construct a barrier super-solution. On the other hand, and fortunately, this estimate will not enter our error bounds.

Remark 2.14. The authors of [START_REF] Juan | Nonlinear elliptic partial differential equations and p-harmonic functions on graphs[END_REF][START_REF] Desquesnes | Non-monotonic front propagation on weighted graphs with applications in image processing and high-dimensional data classification[END_REF] proved existence and uniqueness of the solution (not a viscosity one) in the special case of (1).

Proof. The proof follows the same lines as the one of Proposition 2.5, but adapted to the non-local setting. By assumption (H.11), ψb is a barrier sub-solution of (P ε ). We then have to construct a barrier super-solution.

Existence will then be a direct consequence of the Perron's method while uniqueness and continuity will be direct consequences of the comparison principle provided in Proposition 2.10. Let

f ε 1 (u, t) = ψ(u) + K 1 t and f ε 2 (u, t) = ψ(u) + K 2 d(u, Γ), (u, t) ∈ ΩT , where K 1 = P L ∞ ( Ω\ Γ)
and K 2 large enough to be determined. We then define

(25) f ε (u, t) = min(f ε 1 (u, t), f ε 2 (u, t)
). We will show that f ε is a barrier super-solution of (P ε ). Arguing similarly to the proof of Proposition 2.5, one has that f ε is (Lipschitz) continuous, hence lsc, and that the limit property required in Definition 2.6 holds since for u ∈ Γ, we have

f ε 2 (u, t) = ψ(u) ≤ f ε 1 (u, t), ∀(u, t) ∈ Γ × [0, T ], and thus f ε (u, t) = ψ(u), ∀(u, t) ∈ Γ × [0, T ].
It remains to show that f ε is a super-solution on ( Ω \ Γ)×]0, T [ for K 2 large enough.

Let N η Γ def = u ∈ Ω : d(u, Γ) ≤ η , for η small enough to be chosen shortly. Taking

K 2 ≥ K 1 T /η, we have for any u ∈ Ω \ N η Γ f ε 2 (u, t) ≥ ψ(x) + K 2 η ≥ ψ(u) + K 1 T ≥ f ε 1 (u, t).
In turn,

f ε = f ε 1 on Ω \ N η Γ × [0, T ]. Let ϕ ∈ C 1 (]0, T [) and u 0 ∈ Ω \ Γ × [0, T ] such that f ε (u 0 , •) -ϕ attains a local minimum at some t 0 ∈]0, T [. If u 0 ∈ Ω \ N η Γ , then f ε (u 0 , t 0 ) = f ε 1 (u 0 , t 0 ).
One easily shows following the same steps as for f 1 in the proof of Proposition 2.5, that

∂ ∂t ϕ(t 0 ) = K 1 .
It then follows that

∂ ∂t ϕ(t 0 ) + |∇ - J ε f ε 1 (u 0 , t 0 )| ∞ -P (u) ≥ K 1 -P (u) ≥ K 1 -P L ∞ ( Ω\ Γ) = 0.
If u 0 ∈ N η Γ \ Γ, we have two cases. Either f ε (u 0 , t 0 ) = f ε 1 (u 0 , t 0 ), and we are done, or f ε (u 0 , t 0 ) = f ε 2 (u 0 , t 0 ). In this case, we have (see again the proof of Proposition 2.5) that ∂ ∂t ϕ(t 0 ) = 0, and thus, for every v ∈ Γ, we have

∂ ∂t ϕ(t 0 ) + |∇ - J ε f ε 2 (u 0 , t 0 )| ∞ -P (u 0 ) ≥ J ε (u 0 , v)(f ε 2 (u 0 , t 0 ) -f ε 2 (v, t 0 )) -P (u 0 ) = 1 ε C -1 g g |u 0 -v| ε ( ψ(u 0 ) + K 2 d(u 0 , Γ) -ψ(v)) -P (u 0 ). ( 26
)
Denoted by d0 the minimal distance between two points of Ω (note that, since u 0 ∈ N η Γ \ Γ, d0 ≤ η), we get that there exists v 0 ∈ Γ such that

d(u 0 , Γ) = |u 0 -v 0 | ∈ [ d0 , η].
Since Γ ⊂ Ω, and in view of Remark 1.1 and (H.8), we can choose

K 2 ≥ C g c -1 g ε d-1 0 P L ∞ ( Ω\ Γ)
+ L ψ and η = aε (recall the definition of a from assumption (H.8)). Then continuing from [START_REF] García Trillos | Consistency of Cheeger and ratio graph cuts[END_REF], and using (H.8), we get

∂ ∂t ϕ(t 0 ) + |∇ - J ε f ε 2 (u 0 , t 0 )| ∞ -P (u 0 ) ≥ C -1 g |u 0 -v 0 | ε g |u 0 -v 0 | ε (K 2 -L ψ) -P (u 0 ) (27) ≥ C -1 g d0 ε g(a)(K 2 -L ψ) -P L ∞ ( Ω\ Γ) = C -1 g c g d0 ε (K 2 -L ψ) -P L ∞ ( Ω\ Γ) ≥ 0.
To summarize, taking η = aε and

K 2 ≥ max C g c -1 g ε d-1 0 P L ∞ ( Ω\ Γ) + L ψ, K 1 T /η
, we conclude that the desired super-solution inequality is satisfied in all cases. We then conclude that f ε is indeed a barrier super-solution as claimed. Existence and uniqueness then follow from Perron's method and the comparison principle.

We now establish regularity properties for the solution of (P ε ).

Theorem 2.15. Suppose that assumptions (H.1)-(H.4), (H.6)-(H.8) and (H.11) hold. Let f ε be the bounded continuous viscosity solution of (P ε ). Then

f ε (u, •) ∈ Lip([0, T [) with L f ε (u,•) ≤ L, ∀u ∈ Ω, (28) where L = L ψ + P L ∞ ( Ω\ Γ) .
Moreover, for all (u, v) ∈ Ω2 and t ∈ [0, T [ such that |u -v| ≤ aε, where a is defined in (H.8), we have

|f ε (u, t) -f ε (v, t)| ≤ c -1 g C g L + P L ∞ ( Ω\ Γ) ε. ( 29
)
Assume also that for (u, v) ∈ Ω2 , there exists k(ε) ∈ N and a path (

u 1 = u, u 2 , . . . , u k(ε) = v) with |u i+1 -u i | ≤ aε, i = 1, . . . , k(ε) -1. Then for all t ∈ [0, T [, we have |f ε (u, t) -f ε (v, t)| ≤ c -1 g C g L + P L ∞ ( Ω\ Γ) k(ε)ε. ( 30
)
Proof. For u ∈ Γ, (28) trivially holds. We consider hereafter u ∈ Ω \ Γ, and we first show that for any t ∈ [0, T [,

|f ε (u, t) -f ε (u, 0)| ≤ Lt. ( 31
)
We define for (u, t) ∈ ΩT

f ε 1 (u, t) = ψ(u) -Lt; f ε 2 (u, t) = ψ(u) + Lt. We claim that f ε 1 (resp. f ε 2
) is a sub-solution (resp. super-solution) of (P ε ). Since f ε 1 and f ε 2 are smooth in time, it's enough to prove it pointwise.

We have f ε 1 ≤ ψ on ∂ ΩT , and for all (u, t)

∈ ( Ω \ Γ)×]0, T [, (32)
∂ ∂t f ε 1 (u, t) + ∇ - Jε f ε 1 (u, t) ∞ -P (u) = -L + max v∈ Ω (εC g ) -1 g |u -v| ε ( ψ(u) -ψ(v)) -P (u) ≤ -L + L ψ max v∈ Ω C -1 g |u -v| ε g |u -v| ε + P L ∞ ( Ω\ Γ) ≤ 0,
where we used (H.4) in the first inequality and Remark 1.1 in the last one. Therefore, this shows our claim on f ε 1 . A similar argument shows also that f ε 2 is a super-solution of (P ε ). Now, for any (u, t) ∈ ∂ ΩT , we have

f ε 1 (u, t) ≤ ψ(u) = f ε (u, t) ≤ f ε 2 (u, t).
Hence, since f ε 1 and f ε 2 are bounded and continuous (by assumption on ψ), and so is f ε , applying the comparison principle of Proposition 2.10 twice yields that for any (u, t)

∈ Ω × [0, T [, f ε (u, 0) -Lt = ψ(u) -Lt ≤ f ε (u, t) ≤ ψ(u) + Lt = f ε (u, 0) + Lt,
which shows [START_REF] Ishii | Perron's method for Hamilton-Jacobi equations[END_REF]. We now apply this estimate to prove [START_REF] Hafiene | Nonlocal p-Laplacian evolution problems on graphs[END_REF]. Let h > 0 sufficiently small. We have that f ε is a solution of (P ε ) with initial condition f ε (•, 0) and f ε (•, • + h) is also a solution of (P ε ) with initial condition f ε (•, h). Applying again the comparison principle of Proposition 2.10 and using [START_REF] Ishii | Perron's method for Hamilton-Jacobi equations[END_REF], we obtain for any (u, t)

∈ Ω × [0, T [, |f ε (u, t + h) -f ε (u, t)| ≤ |f ε (u, h) -f ε (u, 0)| ≤ Lh.
Passing to the limit as h → 0 yields the desired time regularity claim. Let us turn to the space regularity estimate [START_REF] Imbert | A Hamilton-Jacobi approach to junction problems and application to traffic flows[END_REF]. Let (u, t)

∈ ΩT . If u ∈ ∂ Ωt , then f ε (u, t) -f ε (v, t) ≤ ψ b (u) -ψ b (v) ≤ L ψ b |u -v| and (29) holds. Assume now that (u, t) ∈ ( Ω \ Γ)×]0, T [ is such that f ε is differentiable in time at (u, t).
For such points, we have from (P ε ) and ( 28) that

∇ - Jε f ε (u, t) ∞ ≤ L + P L ∞ ( Ω\ Γ) .
Let v ∈ Ω be such that |u -v| ≤ aε. We then have, recalling (H.8), that

c g (εC g ) -1 (f ε (u, t) -f ε (v, t)) ≤ (εC g ) -1 g |u -v| ε (f ε (u, t) -f ε (v, t)) = J ε (u, v) (f ε (u, t) -f ε (v, t)) ≤ ∇ - Jε f ε (u, t) ∞ ≤ L + P L ∞ ( Ω\ Γ) .
Exchanging the role of u and v, we get the result. The global estimate is now a direct consequence of [START_REF] Imbert | A Hamilton-Jacobi approach to junction problems and application to traffic flows[END_REF]. Indeed, we have

f ε (u, t) -f ε (v, t) ≤ k(ε)-1 i=1 f ε (u i+1 , t) -f ε (u i , t) ≤ c -1 g C g L + P L ∞ ( Ω\ Γ) k(ε)-1 i=1 ε ≤ c -1 g C g L + P L ∞ ( Ω\ Γ) k(ε)ε.
The following lemma gives a sufficient condition under which the requirements of the global estimate of Theorem 2.15 hold true.

Lemma 2.16. Suppose that assumptions (H.1)-(H.4), (H.6)-(H.8) and (H.11) hold

. Let f ε be the bounded continuous viscosity solution of (P ε ). Assume also that [START_REF] Kimmel | Computing geodesic paths on manifolds[END_REF] max

x∈Ω d(x, Ω) < aε/(4 √ m).
Then for all (u, v) ∈ Ω2 and t ∈ [0, T [, the following holds

|f ε (u, t) -f ε (v, t)| ≤ K (|u -v| + ε) , ( 34
)
where K = 2c -1 g C g L + P L ∞ ( Ω\ Γ) m 3/2 .
Proof. We use a discretization argument3 through the notion of δ-nets. Consider Ω as a metric space endowed with the metric induced by the | • | ∞ -norm. A δ-net of Ω is a set {x 1 , x 2 , . . . , x N } def = S δ ⊂ Ω such that for all x ∈ Ω, there exists y ∈ S δ such that |x -y| ∞ ≤ δ. This is equivalent here to saying that Ω can be covered by hypercubes of side length 2δ centered at the points in S δ . It is known that Ω is compact if and only if S δ is finite.

Choose δ = aε/(4 √ m). Thus, using that S δ ⊂ Ω, we get

max x∈S δ min y∈ Ω |x -y| ∞ ≤ max x∈S δ d(x, Ω) ≤ max x∈Ω d(x, Ω) = d H (Ω, Ω),
where the last identity follows from the fact that Ω ⊂ Ω. It then follows from [START_REF] Kimmel | Computing geodesic paths on manifolds[END_REF] that max

x∈S δ min y∈ Ω |x -y| ∞ < aε/(4 √ m),
whence we deduce that each hypercube of the δ-covering contains at least one point in Ω. This in turn entails that for any (u, v) ∈ Ω2 that belong to two horizontally or vertically adjacent hypercubes in the δ-covering, centered say at respectively x i and x j in S δ , one has

u -v ≤ u -x i + x i -x j + v -x j ≤ √ m (δ + 2δ + δ) = aε.
This allows to infer that for any (u, v) ∈ Ω2 , there exists a path (u 1 = u, u 2 , u 3 , . . . , u k = v), where u i ∈ Ω and |u i+1 -u i | ≤ aε for all i. Moreover, we have the simple estimate

k ≤ mε -1 2 √ m|u -v| + ε .
Injecting this in [START_REF] Ishii | Existence and uniqueness of solutions of Hamilton-Jacobi equations[END_REF], we get the result.

Remark 2.17. A consequence of the proof of Lemma 2.16 is that, under assumption [START_REF] Kimmel | Computing geodesic paths on manifolds[END_REF], since a ≤ r g , we have

(35) ∀u ∈ Ω, ∃v ∈ Ω, v = u such that |u -v| ∈ εsupp(g).
This assumption is quite natural. It basically avoids that the non-local operator ∇ - Jε f ε (u, s) ∞ is trivially zero for all u ∈ Ω when ε is too small. In particular, as Ω is finite, this condition imposes that Ω has to fill out Ω at least as fast as the rate at which ε goes to 0.

C

Continuous time non-local to local error bound.

In this section we provide an estimate that compares viscosity solutions of (P ε ) and (P). This estimate will be instrumental to derive the remaining error bounds. For this, we need to strenghthen (33) by assuming:

(H.12) max x∈Ω d(x, Ω) ≤ aε 1+ν /(4 √ m), ν > 0.
Theorem 3.1. Let T > 0, ε 0 = min(1/(2r g ) 2 , 1) and ε ∈]0, ε 0 ]. Suppose that assumptions (H.1)-(H.12) hold, and let f and f ε be the unique viscosity solutions of respectively (P) and (P ε ), given in Proposition 2.5 and Proposition 2.12. Then, there exists a constant K > 0 depending only on the dimension m, ψ L ∞ (Ω) , P L ∞ (Ω\Γ) , L ψ , L ψ, L P , L P , L g , C g and c g such that

f ε -f L ∞ ( Ω×[0,T [) ≤K(T + 1) ε min(ν,1/2) + P -P L ∞ ( Ω\ Γ) + ψ -ψ L ∞ ( Ω) + Kd H (Γ, Γ), In particular, if d H (Γ, Γ) = O(ε min(ν,1/2) ), then f ε -f L ∞ ( Ω×[0,T [) ≤ K(T + 1) ε min(ν,1/2) + P -P L ∞ ( Ω\ Γ) + ψ -ψ L ∞ ( Ω) .
The fastest convergence rate in ε is then achieved when

ν = 1/2 provided that d H (Ω, Ω) = O(ε 3/2 ) and d H (Γ, Γ) = O(ε 1/2 ).
Proof. The idea of the proof is inspired by that in [START_REF] Crandall | Two approximations of solutions of Hamilton-Jacobi equations[END_REF] and revisited in [START_REF] Forcadel | An error estimate for a new scheme for mean curvature motion[END_REF] for non-local equations. The main difficulties in our case come from the fact that the sets and the boundaries in the two equations are different and from the fact that Ω is finite. In the following, K denotes any positive constant that depends only on the data, but may change from one line to another. The proof is divided into three steps:

• In the first step, we use the classical doubling of variables argument by introducing the test-function

(36) Ψ γ,η (u, s, x, t) = f (u, s) -f (x, t) - |x -u| 2 2γ - |t -s| 2 2γ -ηs,
for γ > 0 and η > 0, and we show that the maximum point is attained at (ū, s, x, t) ∈ ΩT × Ω T .

We also show some estimates on this point of maximum.

• In the second step, we show that the maximum point (ū, s, x, t) is actually achieved on the boundary for η large enough; we have either (ū, s)

∈ N α Γ ×[0, T [ ∪ Ω×{0} or (x, t) ∈ N α Γ ×[0, T [ ∪ Ω×{0}.
This step is the most complicated and the most technical one.

• Finally, in the last step, we show, for η large enough and using the estimates over the maximum points, the claimed bound.

Step 1. Test-function and maximum point.

The function Ψ γ,η being continuous (since f and f ε are) on the compact set ΩT × Ω T (see (H.1)), it achieves its maximum at a point which we denote by (ū, s, x, t) ∈ ΩT × Ω T . At this point, we have Ψ γ,η (ū, s, x, t) ≥ Ψ γ,η (ū, s, ū, t) since ū ∈ Ω ⊂ Ω by (H.1). This implies, in view of [START_REF] Crandall | On existence and uniqueness of solutions of Hamilton-Jacobi equations[END_REF]

) (see Theorem 2.8), that |x -ū| 2 2γ ≤ f (ū, t) -f (x, t) ≤ K|x -ū|,
and thus, [START_REF] Osher | Fronts propagating with curvature-dependent speed-algorithms based on hamilton-jacobi formulations[END_REF] |x -ū| ≤ Kγ.

In the same way, using that Ψ γ,η (ū, s, x, t) ≥ Ψ γ,η (ū, t, x, t), we get using ( 28), (

) | t -s| ≤ (K + η)γ. 38
Step 2. Excluding interior points from the maximum.

We fix α = ε 1/2 so that ε < α/r g for ε ≤ ε 0 . We show that for η large enough, we have either

(ū, s) ∈ N α Γ × [0, T [ ∪ Ω × {0} or (x, t) ∈ N α Γ × [0, T [ ∪ Ω × {0}. We argue by contradiction, assuming that (ū, s) ∈ ( Ω \ N α Γ )×]0, T [ and (x, t) ∈ (Ω \ N α Γ )×]0, T [.
Using that s is a maximum point of the function s → Ψ γ,η (ū, s, x, t) and the fact that f ε is a viscosity sub-solution of (P ε ), we get [START_REF] Pisier | The volume of convex bodies and Banach space geometry[END_REF] η + s -

t γ ≤ -∇ - Jε f ε (ū, s) ∞ + P (ū),
In the same way, using that (x, t) is a minimum point of the function (x, t) → -Ψ γ,η (ū, s, x, t) and the fact that f is a super-solution of (P), we get (40)

s - t γ ≥ - |x -ū| γ + P (x).
Observe that ∀v ∈ Ω, we have

Ψ γ,η (ū, s, x, t) -Ψ γ,η (v, s, x, t) = f ε (ū, s) -f ε (v, s) + |x -v| 2 -|x -ū| 2 2γ . (ū, s, x, t) being a maximizer of Ψ γ,η , we have for any v ∈ Ω 2γ (f ε (ū, s) -f ε (v, s)) ≥ |x -ū| 2 -|x -v| 2 = -|ū -v| 2 + 2 v -ū, x -ū .
It then follows that (41)

∇ - Jε f ε (ū, s) ∞ = max v∈ Ω∩Bεr g (ū) J ε (ū, v)(f ε (ū, s) -f ε (v, s)) ≥ (2γ) -1 max v∈ Ω∩Bεr g (ū) J ε (ū, v) -|ū -v| 2 + 2 v -ū, x -ū ≥ (2γ) -1 2 max v∈ Ω∩Bεr g (ū) J ε (ū, v) v -ū, x -ū T 1 - max v∈ Ω∩Bεr g (ū) J ε (ū, v)|ū -v| 2 T 2 .
To bound the term T 2 , we have, using (H.6), Remark 1.1 and Remark 2.17 (see ( 35)) ( 42)

T 2 ≤ max v∈Bεr g (ū) J ε (ū, v)|ū -v| 2 = max τ ∈[0,rg] max |ū-v|=ετ (εC g ) -1 g |ū -v| ε |ū -v| 2 = ε max τ ∈[0,rg] τ 2 C -1 g g(τ ) ≤ r g ε.
Let us now turn to bounding T 1 . Observe that T 1 ≥ 0 since ū ∈ Ω ∩ B εrg (ū). We then decompose T 1 as ( 43)

T 1 = max v∈Ω∩Bεr g (ū) J ε (ū, v) v -ū, x -ū T 3 + max v∈ Ω∩Bεr g (ū) J ε (ū, v) v -ū, x -ū - max v∈Ω∩Bεr g (ū) J ε (ū, v) v -ū, x -ū .
Note that T 3 is also non-negative. Since d(ū, Γ) ≥ α, we have, for ε ≤ ε 0 , B εrg (ū) ⊂ Ω, and in turn,

T 3 = max v∈Bεr g (ū) J ε (ū, v) v -ū, x -ū = max τ ∈[0,rg] max |ū-v|=ετ (εC g ) -1 g |ū -v| ε v -ū, x -ū = max τ ∈[0,rg] (εC g ) -1 g(τ )ετ |x -ū| = |x -ū|. (44)
On the other hand, one can bound T 3 from above as follows. Let β = aε 1+ν /(4 √ m). In view of (H.12), we have Ω ⊂ Ω + B β (0), and thus for ε small enough so that β < and using (H.9) (45)

0 ≤ T 3 ≤ max v∈( Ω+B β (0))∩Bεr g (ū) J ε (ū, v) v -ū, x -ū ≤ max v∈( Ω∩B ε(rg +1) (ū))+B β (0) J ε (ū, v) v -ū, x -ū = (εC g ) -1 max v∈ Ω∩B ε(rg +1) (ū),w∈B β (0) g |v -ū + w| ε v -ū + w, x -ū = (εC g ) -1 max v∈ Ω∩B ε(rg +1) (ū),w∈B β (0) g |v -ū| ε + L g |w| ε v -ū + w, x -ū = max v∈ Ω∩B ε(rg +1) (ū),w∈B β (0) J ε (ū, v) + L g C -1 g |w| ε 2 v -ū + w, x -ū ≤ max v∈ Ω∩Bεr g (ū) J ε (ū, v) v -ū, x -ū + max v∈ Ω∩Bεr g (ū),w∈B β (0) J ε (ū, v) w, x -ū + L g C -1 g max v∈ Ω∩B ε(rg +1) (ū),w∈B β (0) |w| ε 2 v -ū, x -ū + L g C -1 g max w∈B β (0) |w| ε 2 w, x -ū .
We have using again (H.9) and ( 37), ( 46)

max v∈ Ω∩Bεr g (ū),w∈B β (0) J ε (ū, v) w, x -ū = max v∈ Ω∩Bεr g (ū) J ε (ū, v) max w∈B β (0) w, x -ū ≤ β|x -ū| max τ ∈[0,rg],|v-ū|=τ ε (εC g ) -1 g(0) + L g |v -ū| ε ≤ K β ε γ ≤ Kε ν γ.
Similar computation gives (47)

L g C -1 g max v∈ Ω∩B ε(rg +1) (ū),w∈B β (0) |w| ε 2 v -ū, x -ū ≤ K β ε γ ≤ Kε ν γ and L g C -1 g max w∈B β (0) |w| ε 2 w, x -ū ≤ K β ε 2 γ ≤ Kε ν γ.
Plugging ( 46) and ( 47) into [START_REF] Sethian | A fast marching level-set method for monotonically advancing fronts[END_REF], and then combining with ( 44) and ( 43), we get

T 1 ≥ |x -ū| -Kε ν γ.
Injecting this and ( 42) into [START_REF] Poly | Fonction distance et sigularités[END_REF], we arrive at

∇ - Jε f ε (ū, s) ∞ ≥ |x -ū| 2γ -K ε ν + ε γ .
Injecting this bound into (40) and combining with (39), we deduce that if (ū, s)

∈ ( Ω \ N α Γ )×]0, T [ and (x, t) ∈ (Ω \ N α Γ )×]0, T [, then η ≤ K ε ν + ε γ + P (ū) -P (x) ≤ K ε ν + ε γ + L P |x -ū| + P -P L ∞ ( Ω\ Γ) < 2K ε ν + ε γ + L P Kγ + P -P L ∞ ( Ω\ Γ) ≤ K ε ν + ε γ + γ + P -P L ∞ ( Ω\ Γ) def = η, (48)
for large enough constant K > 0, where we used (H.2) and (H.3) in the second inequality and estimate [START_REF] Osher | Fronts propagating with curvature-dependent speed-algorithms based on hamilton-jacobi formulations[END_REF] in the third one. Then we conclude that for η ≥ η either (ū, s)

∈ N α Γ ×[0, T [ ∪ Ω×{0} or (x, t) ∈ N α Γ × [0, T [ ∪ Ω × {0}. Step 3. Conclusion. We take η ≥ η. Assume first that (x, t) ∈ N α Γ × [0, T [ ∪ Ω × {0}. If t = 0, then Ψ γ,η (ū, s, x, t) ≤ f ε (ū, s) -ψ(x) = (f ε (ū, s) -f ε (ū, 0)) + ( ψ(ū) -ψ(ū)) + (ψ(ū) -ψ(x)) ≤ K s + ψ -ψ L ∞ ( Ω) + L ψ |x -ū| ≤ K(η + 1)γ + ψ -ψ L ∞ ( Ω) ,
where, in the second inequality, we used (28) in Theorem 2.15 to get the first term, and (H.1) and (H.4) to get the last two terms. In the last inequality, we invoked [START_REF] Osher | Fronts propagating with curvature-dependent speed-algorithms based on hamilton-jacobi formulations[END_REF] and [START_REF] Pérez-Llanos | Numerical approximations for a nonlocal evolution equation[END_REF]. In the same way, if

x ∈ N α Γ and t > 0, let ũ ∈ Proj Γ(x), i.e., |x -ũ| = d(x, Γ) ≤ d H (Γ, Γ) + α.
Such ũ exists by closedness of Γ, see (H.2). Since [START_REF] Kimmel | Computing geodesic paths on manifolds[END_REF] is in force under (H.12), ( 34) holds (see Theorem 2.15 and Lemma 2.16). Using this with (H.4) and [START_REF] Osher | Fronts propagating with curvature-dependent speed-algorithms based on hamilton-jacobi formulations[END_REF], we obtain (49)

Ψ γ,η (ū, s, x, t) ≤ f ε (ū, s) -ψ(x) = (f ε (ū, s) -f ε (ũ, s)) + ( ψ(ũ) -ψ(ũ)) + (ψ(ũ) -ψ(x)) ≤ K(|ū -ũ| + ε) + ψ -ψ L ∞ ( Ω) + L ψ |x -ũ| ≤ K(|x -ū| + ε) + ψ -ψ L ∞ ( Ω) + K|x -ũ| + L ψ |x -ũ| ≤ K(γ + ε) + ψ -ψ L ∞ ( Ω) + K(d H (Γ, Γ) + α).
We conclude that for all (x, t)

∈ N α Γ × [0, T [ ∪ Ω × {0}
, and for η ≥ η, we have

Ψ γ,η (ū, s, x, t) ≤ K(γ + ε) + ψ -ψ L ∞ ( Ω) + K(d H (Γ, Γ) + α) + Kηγ.
The same bound holds for (ū, s)

∈ N α Γ × [0, T [ ∪ Ω × {0} whenever η ≥ η. Indeed, if s = 0 then Ψ γ,η (ū, s, x, t) ≤ ψ(ū) -f (x, t) = ( ψ(ū) -ψ(ū)) + (ψ(ū) -ψ(x)) + (f (x, 0) -f (x, t)) ≤ ψ -ψ L ∞ ( Ω) + L ψ |x -ū| + K t ≤ K(η + 1)γ + ψ -ψ L ∞ ( Ω) ,
where we have now invoked [START_REF] Crandall | Two approximations of solutions of Hamilton-Jacobi equations[END_REF] in Theorem 2.8. If ū ∈ N α Γ and s > 0, define x ∈ Γ in the projection of ū on Γ. Thus, using (18) in Theorem 2.8, we arrive at

Ψ γ,η (ū, s, x, t) ≤ ψ(ū) -f (x, t) = ( ψ(ū) -ψ(ū)) + (ψ(ū) -ψ(x)) + (f (x, t) -f (x, t)) ≤ ψ -ψ L ∞ ( Ω) + L ψ |x -ū| + K|x -x| ≤ ψ -ψ L ∞ ( Ω) + L ψ α + K(α + γ) ≤ K(α + γ) + ψ -ψ L ∞ ( Ω) .
Thus, taking η = η and (u, s) ∈ ΩT we have from above that

f ε (u, s) -f (u, s) -ηT ≤Ψ γ,η (ū, s, x, t) ≤K(γ + ε) + ψ -ψ L ∞ ( Ω) + K(d H (Γ, Γ) + α) + K ηγ.
Before concluding, we look at what happens when we revert the role of f and f ε . In this case, our reasoning remains valid with only a few changes. The main ingredient is to redefine Ψ γ,η as follows

Ψ γ,η (u, s, x, t) = f (x, t) -f ε (u, s) - |x -u| 2 2γ - |t -s| 2 2γ -ηt.
Then all our bounds remain true, and with even simpler arguments 4 . We leave the details to the reader for the sake of brevity. Overall, we have shown that

|f ε (u, s) -f (u, s)| ≤ K(γ + ε) + ψ -ψ L ∞ ( Ω) + K(d H (Γ, Γ) + α) + η(γ + T ).
With the optimal choice γ = ε 1/2 , taking the supremum over (u, s) and after rearrangement, we get

f ε -f L ∞ ( Ω×[0,T [) ≤K (T + 1)ε min(ν,1/2) + ε + K(T + ε 1/2 ) P -P L ∞ ( Ω\ Γ) + ψ -ψ L ∞ ( Ω) + K(d H (Γ, Γ) + α),
which is the claimed bound since ε ∈]0, 1] and α = ε 1/2 .

3.2. Forward Euler discrete time non-local to local error bound. We consider the time-discrete approximation of (P ε ) using forward Euler discretization. Then we will show an error estimate between a solution of this equation with the continuous viscosity solution of (P).

Using the forward/explicit Euler discretization scheme, a time-discrete counterpart of (P ε ) reads

(P FD ε ) f ε (u,t)-f ε (u,t-∆t) ∆t = -∇ - Jε f ε (u, t -∆t) ∞ + P (u), (u, t) ∈ ( Ω \ Γ) × {t 1 , . . . , t N T } , f ε (u, t) = ψ(u), (u, t) ∈ ∂ ΩN T ,
where t i = i∆t for all i ∈ {0, . . . , N T }.

In Appendix B, we prove that (P FD ε ) is well-posed. Indeed, Lemma B.3 shows existence and regularity of a discrete-time solution (in the sense of Definition B.1). Uniqueness follows from the comparison principle in Lemma B.2.

We are now in position to state the following error estimate. Theorem 3.2. Let T > 0, ε 0 = min(1/(2r g ) 2 , 1) and ε ∈]0, ε 0 ]. Suppose that assumptions (H.1)-(H.12) hold, and that d H (Γ, Γ) = O(ε min(ν,1/2) ). Let f be the unique viscosity solution of (P) and f ε be a solution of (P FD ε ). Assume also that

0 < ∆t ≤ εC g sup t∈R + g(t) . ( 50
)
Then there exists a constant K > 0 depending only on the dimension m, ψ L ∞ (Ω) , P L ∞ (Ω\Γ) , L ψ , L ψ, L P , L P , L g , C g and c g such that for any ε small enough

f ε -f L ∞ ( Ω×{0,...,t N T }) ≤K(T + 1) ε min(ν,1/2) + ∆t 1/2 + ∆t ε + P -P L ∞ ( Ω\ Γ) + ψ -ψ L ∞ ( Ω) .
In particular, if P = P on Ω \ Γ and ψ = ψ on Ω, then for ∆t = o(ε), we have

lim ε→0,∆t→0 f ε -f L ∞ ( Ω×{0,...,t N T }) = 0.
The fastest convergence rate in ε is then achieved when ∆t = O(ε 3/2 ) and

ν = 1/2 provided that d H (Ω, Ω) = O(ε 3/2 ) and d H (Γ, Γ) = O(ε 1/2 ).
Remark 3.3. It is worth noting that (50) is a CFL condition; see [START_REF]The Courant-Friedrichs-Lewy (CFL) condition: 80 Years After Its Discovery[END_REF] for a recent overview. Obviously, we have sup t∈R + g(t) < +∞ under our assumptions since g is a continuous function on its compact support. It is also possible to discretize (P ε ) in time using a backward/implicit Euler scheme:

(P BD ε ) f ε (u,t)-f ε (u,t-∆t) ∆t = -∇ - Jε f ε (u, t) ∞ + P (u), (u, t) ∈ ( Ω \ Γ) × {t 1 , . . . , t N T } , f ε (u, t) = ψ(u), (u, t) ∈ ∂ ΩN T ,
In that case, the CFL condition [START_REF] Ta | Adaptation of eikonal equation over weighted graphs[END_REF] is not required anymore and we can prove the following error estimate

f ε -f L ∞ ( Ω×{0,...,t N T }) ≤ K(T + 1) ε min(ν,1/2) + ∆t 1/2 + P -P L ∞ ( Ω\ Γ) + ψ -ψ L ∞ ( Ω) .
The proof is completely similar to the one of Theorem 3.2, the only difference is that η in the proof will be independent of the term ∆t/ε. It is worth noting that in the backward Euler scheme, the difficulty is to construct a discrete solution. This is done for the reader's convenience in Lemma C.1 in the appendix.

The proof of Theorem 3.2 is quite similar to the one of Theorem 3.1. We highlight only the steps where we have to handle properly the discrete time approximation. For instance, we will need the Lipschitz regularity properties of f ε both in time and space (see Lemma B.3).

Proof. Again, K will denote in this proof any positive constant that depends only on the data, but may change from one line to another. Here we focus on the case f -f ε on purpose to complement the details provided in the proof Theorem 3.1.

Step 1. Test-function and maximum point.

For γ > 0 and η > 0, we consider maximizing over Ω T × ΩN T the test-function

Ψ γ,η (x, t, u, s) = f (x, t) -f ε (u, s) - |x -u| 2 2γ - |t -s| 2 2γ -ηt.
Since Ω T × ΩN T is compact and Ψ γ,η is continuous, the maximum is attained at some point (x, t, ū, ti ). Exactly as in the proof of Theorem 3.1, we have |x -ū| ≤ Kγ and ( 51)

| t -ti | ≤ (K + η)γ. (52)
Step 2. Excluding interior points from the maximum.

We show that for η large enough, we have either (x, t) ∈ ∂Ω T or (ū, ti ) ∈ ∂ ΩN T . We argue again by contradiction and assume that (x, t) ∈ Ω \ Γ×]0, T [ and (ū, ti ) ∈ Ω \ Γ × {t 1 , . . . , t N T }. Using that (x, t) is a maximum point of the function (x, t) → Ψ γ,η (x, t, ū, ti ) and the fact that f is a viscosity sub-solution of (P), we have

η + t -ti γ ≤ - |x -ū| γ + P (x). ( 53
)
Using now that ti > 0 and that f ε is a solution of (P FD ε ), we have (54)

f ε (ū, ti ) -f ε (ū, ti -∆t) ∆t = -∇ - Jε f ε (ū, ti -∆t) ∞ + P (ū).
We set ϕ : (u, s)

∈ ΩN T → f (x, t) -|x-u| 2 2γ -| t-s| 2 2γ -η t.
In particular, (ū, ti ) is the minimum point of f ε -ϕ over ΩN T . This implies that

f ε (ū, ti ) -f ε (ū, ti -∆t) ≤ ϕ(ū, ti ) -ϕ(ū, ti -∆t),
and so

f ε (ū, ti ) -f ε (ū, ti -∆t) ∆t ≤ t -ti γ + ∆t 2γ . (55)
(x, t, ū, ti ) is a maximizer of Ψ γ,η , whence we get

f ε (ū, ti ) -f ε (v, ti ) ≤ |x -v| 2 -|x -ū| 2 2γ , ∀v ∈ Ω.
Thus we estimate the right hand side of (54) to show that (56)

∇ - Jε f ε (ū, ti -∆t) ∞ = max v∈ Ω,|ū-v|∈εsupp(g) J ε (ū, v)(f ε (ū, ti -∆t) -f ε (v, ti -∆t)) = max v∈ Ω,|ū-v|∈εsupp(g) J ε (ū, v)(f ε (ū, ti -∆t) -f ε (ū, ti ) + f ε (ū, ti ) -f ε (v, ti ) + f ε (v, ti ) -f ε (v, ti -∆t)) ≤ max v∈ Ω,|ū-v|∈εsupp(g) J ε (ū, v)(K∆t + f ε (ū, ti ) -f ε (v, ti )) ≤ max v∈ Ω,|ū-v|∈εsupp(g) J ε (ū, v) K∆t + (2γ) -1 |x -v| 2 -|x -ū| 2 ≤ K∆t max v∈ Ω,|ū-v|∈εsupp(g) J ε (ū, v) + (2γ) -1 max v∈ Ω,|ū-v|∈εsupp(g) J ε (ū, v) |x -v| -|x -ū| |x -v| -|x -ū| + 2|x -ū| ≤ K ∆t ε sup t∈R + g(t) + (2γ) -1 max v∈ Ω,|ū-v|∈εsupp(g) J ε (ū, v)|ū -v| |ū -v| + 2|x -ū| ≤ K ∆t ε + max v∈ Ω,|ū-v|∈εsupp(g) |x -ū| γ |ū -v| C g ε g |ū -v| ε + max v∈ Ω,|ū-v|∈εsupp(g) |ū -v| 2 2γC g ε g |ū -v| ε ≤ K ∆t ε + |x -ū| γ + r g ε 2γ .
Plugging (55) and ( 56) into (54) we get

t -ti γ + ∆t 2γ ≥ -K ∆t ε - |x -ū| γ -K ε γ + P (ū). (57)
From ( 53) and (57), we finally obtain

η ≤ K ∆t + ε γ + ∆t ε + P (x) -P (ū) ≤ K ∆t + ε γ + ∆t ε + K|x -ū| + P -P L ∞ ( Ω\ Γ) < K ∆t + ε γ + γ + ∆t ε + P -P L ∞ ( Ω\ Γ) def = η.
We then conclude that either (x, t) ∈ ∂Ω T or (ū, ti ) ∈ ∂ ΩN T for η ≥ η. When reverting the roles of f ε and f , only η will be changed taking the additional terms ε ν and α (see the proof of Theorem 3.1). The rest of the proof is exactly the same as Step 3. in the proof of Theorem 3.1, where we now invoke Lemma B.3.

A

Let G n = (V n , w n ) be a finite weighted graph with non-negative edge weights w n . Here V n is the set of n vertices/nodes {u 1 , . . . , u n } ⊂ Ω, E n ⊂ V 2 n is the set of edges, and the weights w n are given by the kernel J at scale ε n , i.e., w n (u i , v j ) = J εn (u i , v j ).

Let Γ n ⊂ V n . For a time interval [0, T [ and N T ∈ N, we use the shorthand notation

(V n \ Γ n ) N T = (V n \ Γ n ) × {t 1 , . . . , t N T } and ∂(V n ) N T = (Γ n × {t 1 , . . . , t N T }) ∪ V n × {0}.
We now consider the fully discretized Eikonal equation on G n with a forward Euler time-discretization as

(P FD Gn ) f n (u,t)-f n (u,t-∆t) ∆t = -∇ - wn f n (u, t -∆t) ∞ + P (u), (u, t) ∈ (V n \ Γ n ) N T , f n (u, t) = ψ(u), (u, t) ∈ ∂(V n ) N T ,
where t i = i∆t for all i ∈ {0, . . . , N T }.

In the notation of (P FD ε ), it is easy to identify V n with Ω and Γ n with Γ. Our aim in this section is to establish consistency of solutions to (P FD Gn ) as n → +∞ and ∆t → 0.

In practice, we do not have that much control over the way the vertices V n in the graph are constructed; the precise configuration of points may not be known, or the points can be obtained by sampling through an acquisition device (e.g., point clouds), or given from a learning or modeling process (e.g., images). It then appears 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.

Towards this goal, we will consider a random graph model whose nodes are latent random variables independently and identically sampled on Ω. This random graph model is inspired from [START_REF] Bollobás | The phase transition in inhomogeneous random graphs[END_REF] and is quite standard. More precisely, we construct V n and the boundary Γ n as follows: Definition 4.1. Given a probability measure µ over Ω and ε n > 0:

(1) draw the vertices in V n as a sequence of independent and identically distributed variables

(u i ) n i=1
taking values in Ω and whose common distribution is µ;

(2) set Γ n = u i ∈ V n : d(u i , Γ) ≤ aε 1+ν n /(2 √ m) , ν > 0.
From now on, we assume that (H.13) µ has a density ρ on Ω with respect to the volume measure, and inf Ω ρ > 0.

A typical example is that of the uniform probability distribution on Ω, in which case ρ(u) = ( Ω dvol(x)) -1 for u ∈ Ω, where dvol is the volume measure. Though we will focus on this setting, our results can be extended following the developments hereafter to other sampling models, in particular those adapted to the manifold geometry, in which case the covering arguments that we will use will be done with geodesic balls. We will not elaborate more on this in this paper. We observe in passing that by construction, V n and Γ n are compact sets, and that V n \ Γ n ⊂ Ω \ Γ. Before stating the main result of this section, the following lemma gives a proper choice of ε n for which the construction of Definition 4.1 ensures that the key assumption (H.12) is in force together with

Γ n = ∅ and d H (Γ, Γ n ) = O(ε 1+ν
n ) with high probability. To lighten notation, we define the event (58)

E n = (H.12) holds and

d H (Γ, Γ n ) ≤ aε 1+ν n /(2 √ m) .
Lemma 4.2. Let V n and Γ n generated according to Definition 4.1 where µ satisfies (H.13). Then, there exists two constants K 1 > 0 and K 2 > 0 that depend only on m, a and diam(Ω), and for any τ > 0 there exists n(τ ) ∈ N such that for n ≥ n(τ ), taking

(59) ε 1+ν n = K 1 (1 + τ ) 1/m log n n 1/m
, the event E n in (58) holds with probability at least 1 -K 2 n -τ .

See Appendix D for the proof.

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

In the same way, we say that f ε is a super-solution of (P

FD ε ) if for all (u, t) ∈ ( Ω \ Γ) × {t 1 , . . . , t N T } f ε (u, t) -f ε (u, t -∆t) ∆t ≥ -∇ - Jε f ε (u, t -∆t) ∞ + P (u),
and if for all (u, t) ∈ ∂ ΩN T , f ε (u, t) ≥ ψ(u). f ε is a discrete solution of (P FD ε ) if it is both a discrete sub-solution and super-solution.

We start with a comparison principle, which is a direct consequence of the monotonicity.

Lemma B.2 (Comparison principle for the scheme (P FD ε )). Assume that (H.1), (H.2) and (H.6) hold, and that f ε , g ε are respectively bounded sub-and super-solution of (P FD ε ). Assume also that the CFL condition (50) holds. Then sup Ω×{0,...,t N T }

(f ε -g ε ) ≤ sup Γ×{t 1 ,...,t N T }∪ Ω×{0} |f ε -g ε |. (61)
Proof. Since the scheme is invariant by addition of constant, we can assume that f ε ≤ g ε on Γ×{t 1 , . . . , t N T }∪ Ω × {0}, and prove that f ε ≤ g ε on Ω × {0, . . . , t N T }.

We argue by contradiction, and suppose that for η > 0 small enough, we have

M η = sup (u,t)∈ Ω×{0,...,t N T } f ε (u, t) -g ε (u, t) -ηt > 0. ( 62
)
By upper semi-continuity of the objective and compactness of Ω×{0, . . . , t N T }, the supremum is actually a maximum achieved at some point (ū, t). Since f ε ≤ g ε on Γ × {t 1 , . . . , t N T } ∪ Ω × {0} and M η > 0 for η small enough, we deduce that (ū, t) ∈ ( Ω \ Γ) × {t 1 , . . . , t N T }. At the maximum point, we have

f ε (ū, t) -g ε (ū, t) -η t ≥ f ε (ū, t -∆t) -g ε (ū, t -∆t) -η( t -∆t) and f ε (ū, t) -g ε (ū, t) -η t ≥ f ε (y, t -∆t) -g ε (y, t -∆t) -η( t -∆t)
Moreover, using that f ε , g ε are respectively sub-and super-solution of (P FD ε ) and remarking that (50) implies in particular that ∆t ≤ min y∈ Ω 1 J ε (ū, y)

, we get

0 ≥ f ε (ū, t) -f ε (ū, t -∆t) ∆t + max y∈ Ω J ε (ū, y)(f ε (ū, t -∆t) -f ε (y, t -∆t)) -P (ū) i.e. 0 ≥ f ε (ū, t) + max y∈ Ω (-f ε (ū, t -∆t) + ∆tJ ε (ū, y)(f ε (ū, t -∆t) -f ε (y, t -∆t))) -∆t P (ū) = f ε (ū, t) + max y∈ Ω (-(1 -∆tJ ε (ū, y))f ε (ū, t -∆t) -∆tJ ε (ū, y)f ε (y, t -∆t)) -∆t P (ū) ≥ f ε (ū, t) + max y∈ Ω (1 -∆tJ ε (ū, y)) g ε (ū, t) -g ε (ū, t -∆t) + η∆t -f ε (ū, t) + ∆tJ ε (ū, y) g ε (ū, t) -g ε (y, t -∆t) + η∆t -f ε (ū, t) -∆t P (ū) = η∆t + ∆t g ε (ū, t) -g ε (ū, t -∆t) ∆t + max y∈ Ω J ε (ū, y)(g ε (ū, t -∆t) -g ε (y, t -∆t)) -P (ū) ≥ η∆t + 0 > 0,
which is a contradiction.

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

Lemma B.3 (Existence and Lipschitz regularity properties in time and space for the scheme (P FD ε )). Assume that assumptions (H.1)-(H.4), (H.6)-(H.8) and (H.11)-(H.12) hold. Then there exists a discrete solution f ε of (P FD ε ) and for all (u, v) ∈ Ω2 and t ∈ {t 1 , . . . , t N T }, the following holds

|f ε (u, t) -f ε (u, t -∆t)| ≤ L∆t, (63) |f ε (u, t) -f ε (v, t)| ≤ K (|u -v| + ε) , (64)
where

L = L ψ + P L ∞ ( Ω\ Γ) and K = 2c -1 g C g L + P L ∞ ( Ω\ Γ) m 3/2 .
Proof. The existence of a solution is trivial. Moreover, since ψb and f ε are respectively sub-and supersolution of (P FD ε ) and satisfy the boundary conditions, we get, by Lemma B.2, that ψb ≤ f ε ≤ f ε . For the Lipschitz regularity, we begin by showing that for any 0

< t ∈ {t 1 , . . . , t N T } , u ∈ Ω, |f ε (u, t) -f ε (u, 0)| ≤ Lt.
To do this, we define

f ε 1 (u, t) = ψ(u) -Lt and f ε 2 (u, t) = ψ(u) + Lt. In particular, f ε 1 , f ε 2
are respectively sub-and super-solution of (P FD ε ). Indeed, on the one hand, we have

f ε 1 (u, t) -f ε 1 (u, t -∆t) ∆t = ψ(u) -Lt -ψ(u) + L(t -∆t) ∆t = -L. (65)
On the other hand, we have (66) = -L Therefore, from (65) and (66) we get the conclusion. The proof for f ε 2 is similar and we skip it. Moreover, for any (u, t) ∈ Γ × {t 1 , . . . , t N T } ∪ Ω × {0} we have

-max v∈ Ω J ε (u, v)(f ε 1 (u, t -∆t) -f ε 1 (v, t -
f ε 1 (u, t) ≤ f ε (u, t) = ψ(u) ≤ f ε 2 (u, t). (67)
Hence, by the comparison principle in Lemma B.2, we get that for any u ∈ Ω, t ≥ 0,

f ε (u, 0) -Lt ≤ f ε (u, t) ≤ f ε (u, 0) + Lt.
We now apply this estimate to get (63). Let u ∈ Ω \ Γ, t ∈ {t 1 , . . . t N T } (the result being trivial if u ∈ Γ) and set s = t -∆t. We have that f ε (u, s) is a solution of (P FD ε ) with initial condition f ε (u, 0) and f ε (u, s + ∆t) is also a solution of (P FD ε ) with initial condition f ε (u, ∆t). Then by comparison principle Lemma B.2 and (67), we obtain for any u ∈ Ω, t > 0,

|f ε (u, t) -f ε (u, t -∆t)| = |f ε (u, s + ∆t) -f ε (u, s)| ≤ |f ε (u, ∆t) -f ε (u, 0)| ≤ L∆t.
The proof of the space regularity estimate is the same as that of [START_REF] Medvedev | The nonlinear heat equation on dense graphs[END_REF]. For the reader's convenience, we establish the existence of a discrete solution for (P BD ε ).

Lemma C.1 (Existence of discrete solution of (P BD ε )). Assume that assumptions (H.1)-(H.4), (H.6)-(H.8) and (H.11) hold. Then there exists a discrete solution f ε of (P BD ε ).

Proof. The proof is very close to the one of Proposition 2.12 (and we recall all the notations there), and we therefore give here only a sketch of the proof. First, it is easy to check that ψb and f ε are respectively suband super-solution of (P BD ε ) and satisfy the boundary conditions. We assume that there exists a solution f n at step n and we will construct a solution f n+1 at step n + 1. Let us define f n+1 = sup w sub-solution at step n + 1 s.t w ≤ f ε .

In particular, this set is nonempty since ψb belongs to it. Moreover, we remark, by monotonicity, that if f n+1,i i∈N is a family of discrete sub-solutions at step n+1, then f n+1 = sup i f n+1,i is still a sub-solution. Hence f n+1 is a discrete sub-solution. Let us prove that f n+1 is a super-solution. By contradiction, assume that there exists ū ∈ ( Ω \ Γ n ) × {t 1 , . . . , t N T } such that (with the notation f n (u) = f (u, t n ))

f n+1 (ū) -f n (ū) ∆t < -∇ - Jε f n (ū) ∞ + P (ū).
This implies in particular that f n+1 (ū) < f ε (ū, t n+1 ). Now, let us consider the solution w ū of

w ū -f n (ū) ∆t = -max v∈ Ω J ε (ū, v)(w ū -f n+1 (v)) + P (ū).
The existence of such a solution comes from the fact that the left hand-side is increasing in w ū while the right-hand side is non-increasing. Then, using the monotonicity of the scheme, it is easy to prove that w ū > f n+1 (ū) and w defined by

w(u) = w ū if u = ū f n+1 (u) otherwise
is a discrete sub-solution of (P BD ε ) at step n + 1. This contradicts the definition of f n+1 . The proof is completed.

A D. P L .

We will use again compactness of Ω and a covering argument with a finite δ-net consisting of N (Ω, δ) points, and conclude by the union bound, after using a standard estimate of N (Ω, δ) (called the covering number of Ω). We denote for short [N ] = {1, . . . , N } for any N ∈ N * .

Let S δ = x 1 , x 2 , . . . , x N (Ω,δ) be a δ-net Ω in the Euclidian distance, i.e., Ω ⊆ x∈S δ B δ (x). We then have

max x∈Ω d(x, V n ) ≤ max j∈[N (Ω,δ)] max x∈B δ (x j ) d(x, V n ).
For each j ∈ [N (Ω, δ)], let Z j be the number of random variables (u i ) n i=1 falling into B δ (x j ). Obviously, Z j is a Binomial random variable with parameters (n, p j ), where p j = µ(B δ (x j )) ≥ cvol(B δ (0)) = cδ m vol(B(0)), where c = inf Ω ρ > 0 by (H.13), and we used the shorthand notation B(0) for the unit Euclidian ball. Thus, using the union bound, we get First, with the construction of Definition 4.1, one can assert that Γ n = ∅ with probability larger than 1 -c(3r) m vol(B(0))n -τ . To show this, we argue by contradiction, assuming that ∀u ∈ V n , d(u, Γ) > 2δ, which entails that |u -x| > 2δ, ∀(u, x) ∈ V n × Γ.

Let j ∈ [N (Ω, δ)] such that Γ ∩ B δ (x j ) = ∅ (which exists by definition of the δ-net). We have shown above that with probability at least 1 -c(3r) m vol(B(0))n -τ , each ball B δ (x j ) contains at least one point u ∈ V n , and thus, for such a point, |u -x| ≤ 2δ for all x ∈ Γ ∩ B δ (x j ), leading to a contradiction. In turn, we deduce that with the same probability, we have max To conclude, it remains to show that max

x∈Γ d(x, Γ n ) ≤ 2δ,
with the same probability. For this, let {x j ∈ S δ : Γ ∩ B δ (x j ) = ∅}. This is a subcover of Ω which is a δ-net of Γ. Thus Arguing as we did above to bound max x∈Ω d(x, V n ), we get the claimed bound. Finally, the bound on d H (Γ, Γ n ) follows from above using the union bound. The latter also yields that the event E n holds with the given probability.

1. 1 .

 1 Problem statement. Here and in the rest of the paper we use | • | to denote the euclidean norm in R m , Lip(Σ) is the space of Lipschitz continuous mappings on Σ, and for any h ∈ Lip(Σ), L h denotes its Lipschitz constant. For a non-empty closed subset X ∈ R m , the distance to X is the functiond(•, X) : x ∈ R m → min z∈X |x -z| ∈ [0, +∞[.See also Section 1.4 for the rest of notations. Throughout, we will work with the following sets and functions satisfying the standing assumptions: (H.1) Ω, Ω are compact subsets of R m , with Ω a finite subset of Ω; (H.2) Γ ⊂ Ω and Γ ⊂ Ω are closed sets with Ω \ Γ open and Ω \ Γ ⊂ Ω \ Γ; (H.3) P ∈ Lip(Ω \ Γ) and P ∈ Lip( Ω \ Γ) are non-negative potential functions; (H.4) ψ ∈ Lip(Ω) and ψ ∈ Lip( Ω). (H.5) There exists a 0 , d 0 > 0 such that d(•, Γ) is C 1 on N a 0 Γ \ Γ where N a 0 Γ def = {x ∈ Ω, d(x, Γ) < a 0 }, and |∇d(x, Γ)| ≥ d 0 for all x ∈ N a 0 Γ \ Γ.

  ∆t)) + P (u) = -max v∈ Ω g |u-v| ε εC g ( ψ(u) -ψ(v)) + P (u) ≥ -max v∈ Ω g |u-v| ε εC g L ψ|u -v| -P L ∞ ( Ω\ Γ)

.( 1 - 2 e, we have aε 1+ν n /( 4 √

 124 , V n ) > 2δ ≤ Pr max j∈[N (Ω,δ)] max x∈B δ (x j ) d(x, V n ) > 2δ ≤ j∈[N (Ω,δ)]Pr maxx∈B δ (x j ) d(x, V n ) > 2δ ≤ j∈[N (Ω,δ)] Pr (Z j = 0) = j∈[N (Ω,δ)] (1 -p j ) n ≤ N (Ω, δ) (1 -cδ m vol(B(0))) n .Since Ω is compact, there exists r > 0 such that Ω ⊆ rB(0). It then follows from standard estimates, see[START_REF] Pisier | The volume of convex bodies and Banach space geometry[END_REF] Lemma 4.10] thatN (Ω, δ) = N (Ω/r, δ/r) ≤ 1 + 2r δ mWe therefore arrive at the boundPr max x∈Ω d(x, V n ) > 2δ ≤ 1 + 2r δ m cδ m vol(B(0))) n ≤ e -ncδ m vol(B(0))+m log(1+ 2r δ ) .Take δ m = (1+τ ) cvol(B(0) log n n , for any τ > 0. Thus, for n large enough, one has δ ≤ r, and in turn the above bound becomes Pr max x∈Ω d(x, V n ) > 2δ ≤ c(3r) m vol(B(0))e -(1+τ ) log n-log(1+τ )-log log n+log n ≤ c(3r) m vol(B(0))e -τ log n = c(3r) m vol(B(0))n -τ . By the Stirling formula, we have vol(B(0)) = 2π m/2 mΓ(m/2) θ(m/2)/(6m)with θ(m/2) ∈ [0, 1]. Thus, taking m) ≥ δ, and thus (H.12) holds with probability at least 1 -K 2 n -τ .Let us turn to the estimating the probability of the eventd H (Γ, Γ n ) ≤ aε 1+ν n

Actually, only the lower bound inequality[START_REF] Camilli | An approximation scheme for a Hamilton-Jacobi equation defined on a network[END_REF] is needed here.

In fact, this portion of the proof shows that f 1 is a super-solution of (P) in (Ω \ Γ)×]0, T [.

A similar argument is implicitly underlying the proof of [8,Lemma 15] for the special case where Ω is the flat torus and Ω is discrete.

This is the case for the analogous version of (41) which will be derived by a simple triangle inequality (see also (56)). This asymmetry in the proofs when reverting the roles of f ε and f is intriguing but not surprising.

It is clear that our assumptions (H.1)-(H.2) concern only Ω and Γ and not Vn and Γn which comply with (H.1)-(H.2) by construction.

Acknowledgement. This work was supported by the Normandy Region grant MoNomads, and partly by the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 777826 (NoMADS). We would like also to thank A. El Moataz for fruitful discussions. R

Theorem 4.3. Let T, ν > 0, and V n and Γ n be constructed according to Definition 4.1 where µ satisfies (H. [START_REF] Caroccia | Mumford-Shah functionals on graphs and their asymptotics[END_REF]. Suppose that assumptions (H.1)-(H.11) hold 5 . Let f be the unique viscosity solution of (P) and f n be a solution of (P FD Gn ). Take ∆t = o(ε n ) where ε n is as given in (59). Then, the following holds. (i) There exists two constants K > 0 and K 2 > 0 that depend only on m, a, diam(Ω), ψ L ∞ (Ω) , P L ∞ (Ω\Γ) , L ψ , L ψ, L P , L P , c g , C g , L g and ν, and for any τ > 0, there exists n(τ ) ∈ N such that for n ≥ n(τ ),

.

with probability at least 1-K 2 n -τ . The best convergence rate is

Proof.

(i) To get the error bound (60), combine Theorem 3.2 and Lemma 4.2 and observe that

n with the stated probability. (ii) We have

The claim then follows from the (first) Borel-Cantelli lemma.

(iii) In this case, we have

for a possibly higher constant K. Define the event

For any δ > 0, q > 1 and n large enough, we have by the Tchebychev inequality that

for some constant K τ,T,m,q > 0, and where we used the fact that f n -f L ∞ (Vn×{0,...,tN T }) is almost surely bounded by some constant C > 0. Since q > 1, the right-hand side is summable for any τ > 1. The claim then follows using again the (first) Borel-Cantelli lemma.

Remark 4.4. One can also easily derive from (60) a bound in expectation. Indeed arguing as in the proof of the third claim of Theorem 4.3, we have

When P = P and ψ = ψ on V n \Γ n and Ω n respectively, we again conclude that f n -f L ∞ (Vn×{0,...,tN T }) converges to 0 in expectation as n → +∞.

A A. S

The regularity of the distance function to a set from that of the set itself is a classical and well understood subject. Indeed, characterizing some classes of C p -smooth submanifolds of an arbitrary Hilbert space via some smoothness properties of square distance functions (or projection mappings) has been studied by many authors [START_REF] Poly | Fonction distance et sigularités[END_REF][START_REF] Canino | On p-convex sets and geodesics[END_REF][START_REF] Shapiro | Existence and differentiability of metric projections in Hilbert spaces[END_REF][START_REF] Salas | On characterizations of submanifolds via smoothness of the distance function in Hilbert spaces[END_REF]; see also the survey [START_REF] Colombo | Prox-regular sets and applications[END_REF]. On R m , such results can be found in [START_REF] Ambrosio | Level set approach to mean curvature flow in arbitrary codimension[END_REF]. We summarise this in the following proposition.

Proposition A.1. Let p ≥ 1 be an integer and Γ ∈ R m be a compact C p+1 -smooth submanifold without boundary. Then there is

We first define the notions of discrete sub-and super-solution.

Definition B.1 (Discrete sub-and super-solution). We say that f ε is a sub-solution of (P