Adina Ciomaga Cmla

ON THE STRONG MAXIMUM PRINCIPLE FOR SECOND ORDER NONLINEAR PARABOLIC INTEGRO-DIFFERENTIAL EQUATIONS

Keywords: nonlinear parabolic integro-differential equations, strong maximum principle, viscosity solutions AMS Subject Classification: 35R09, 35K55, 35B50, 35D40

This paper is concerned with the study of the Strong Maximum Principle for semicontinuous viscosity solutions of fully nonlinear, second-order parabolic integro-differential equations. We study separately the propagation of maxima in the horizontal component of the domain and the local vertical propagation in simply connected sets of the domain. We give two types of results for horizontal propagation of maxima: one is the natural extension of the classical results of local propagation of maxima and the other comes from the structure of the nonlocal operator. As an application, we use the Strong Maximum Principle to prove a Strong Comparison Result of viscosity sub and supersolution for integro-differential equations.

Introduction

We investigate the Strong Maximum Principle for viscosity solutions of second-order nonlinear parabolic integro-differential equations of the form u t + F (x, t, Du, D 2 u, I[x, t, u]) = 0 in Ω × (0, T ) (1.1) where Ω ⊂ R N is an open bounded set, T > 0 and u is a real-valued function defined on R N × [0, T ]. The symbols u t , Du, D 2 u stand for the derivative with respect to time, respectively the gradient and the Hessian matrix with respect to x. I[x, t, u] is an integro-differential operator, taken on the whole space R N . Although the nonlocal operator is defined on the whole space, we consider equations on a bounded domain Ω. Therefore, we assume that the function u = u(x, t) is a priori defined outside the domain Ω. The choice corresponds to prescribing the solution in Ω c × (0, T ), as for example in the case of Dirichlet boundary conditions.

The nonlinearity F is a real-valued, continuous function in Ω × [0, T ] × R N × S N × R, (S N being the set of real symmetric N × N matrices) and degenerate elliptic, i.e.

F (x, t, p, X, l 1 ) ≤ F (x, t, p, Y, l 2 ) if X ≥ Y, l 1 ≥ l 2 , (1.2)
for all (x, t) ∈ Ω × [0, T ], p ∈ R N \ {0}, X, Y ∈ S N and l 1 , l 2 ∈ R.

Throughout this work, we consider integro-differential operators of the type

I[x, t, u] = R N (u(x + z, t) -u(x, t) -Du(x, t) • z1 B (z))µ x (dz) (1.3)
where 1 B (z) denotes the indicator function of the unit ball B and {µ x } x∈Ω is a family of Lévy measures, i.e. non-negative, possibly singular, Borel measures on Ω such that sup x∈Ω R N min(|z| 2 , 1)µ x (dz) < ∞.

1

In particular, Lévy-Itô operators are important special cases of nonlocal operators and are defined as follows

J [x, t, u] = R N
(u(x + j(x, z), t)u(x, t) -Du(x, t) • j(x, z)1 B (z))µ(dz) (1.4) where µ is a Lévy measure and j(x, z) is the size of the jumps at x satisfying

|j(x, z)| ≤ C 0 |z|, ∀x ∈ Ω, ∀z ∈ R N
with C 0 a positive constant.

We denote by U SC(R N × [0, T ]) and LSC(R N × [0, T ]) the set of respectively upper and lower semi-continuous functions in R N × [0, T ]. By Strong Maximum and Minimum Principle for equation (1.1) in an open set Ω × (0, T ) we mean the following.

SMaxP: any u ∈ U SC(R N × [0, T ]) viscosity subsolution of (1.1) that attains a maximum at

(x 0 , t 0 ) ∈ Ω × (0, T ) is constant in Ω × [0, t 0 ].
The Strong Maximum Principle follows from the horizontal and vertical propagation of maxima, that we study separately. By horizontal propagation of maxima we mean the following; if the maximum is attained at some point (x 0 , t 0 ) then the function becomes constant in the connected component of the domain Ω × {t 0 } which contains the point (x 0 , t 0 ). By local vertical propagation we understand that if the maximum is attained at some point (x 0 , t 0 ) then at any time t < t 0 one can find another point (x, t) where the maximum is attained. This will further imply the propagation of maxima in the region Ω × (0, t 0 ).

We set Q T = Ω × (0, T ] and for any point P 0 = (x 0 , t 0 ) ∈ Q T , we denote by S(P 0 ) the set of all points Q ∈ Q T which can be connected to P 0 by a simple continuous curve in Q T and by C(P 0 ) we denote the connected component of Ω × {t 0 } which contains P 0 .

The horizontal propagation of maxima in C(P 0 ) requires two different perspectives. An almost immediate result follows from the structure of the nonlocal operator. More precisely, we show that Strong Maximum Principle holds for PIDEs involving nonlocal operators in the form (1.3) whenever the whole domain (not necessarily connected) can be covered by translations of measure supports, starting from a maximum point. This is the case for example of a pure nonlocal diffusion u t -I[x, t, u] = 0 in R N × (0, T ) (1.5) where I is an isotropic Lévy operator of form (1.3), integrated against the Lévy measure associated with the fractional Laplacian (-∆) β/2 :

µ(dz) = dz |z| N +β .
The result is the natural extension to PIDEs of the maximum principle for nonlocal operators generated by nonnegative kernels obtained by Coville in [START_REF] Coville | Remarks on the strong maximum principle for nonlocal operators[END_REF].

Nevertheless, there are equations for which maxima do not propagate just by translating measure supports, such as pure nonlocal equations with nonlocal terms associated with the fractional Laplacian, but whose measure supports are defined only on half space. Mixed integrodifferential equations, i.e. equations for which local diffusions occur only in certain directions and nonlocal diffusions on the orthogonal ones cannot be handled by simple techniques, as they might be degenerate in both local or nonlocal terms but the overall behavior might be driven by their interaction (the two diffusions cannot cancel simultaneously). We have in mind equations of the type

u t -I x 1 [u] - ∂ 2 u ∂x 2 2 = 0 in R 2 × (0, T ) (1.6) for x = (x 1 , x 2 ) ∈ R 2 .
The diffusion term gives the ellipticity in the direction of x 2 , while the nonlocal term gives it in the direction of x 1

I x 1 [u] = R (u(x 1 + z 1 , x 2 ) -u(x) - ∂u ∂x 1 (x) • z 1 1 [-1,1] (z 1 ))µ x 1 (dz 1 )
where {µ x 1 } x 1 is a family of Lévy measures. However, we manage to show that under some nondegeneracy and scaling assumptions on the nonlinearity F , if a viscosity subsolution attains a maximum at P 0 = (x 0 , t 0 ) ∈ Q T , then u is constant (equal to the maximum value) in the horizontal component C(P 0 ). We then prove the local propagation of maxima in the cylindrical region Ω × (0, T ] and thus extend to parabolic integro-differential equations the results obtained by Da Lio in [START_REF] Da | Remarks on the strong maximum principle for viscosity solutions to fully nonlinear parabolic equations[END_REF] and Bardi and Da Lio in [START_REF] Bardi | Propagation of maxima and strong maximum principle for viscosity solutions of degenerate elliptic equations[END_REF] and [START_REF] Bardi | Propagation of maxima and strong maximum principle for viscosity solutions of degenerate elliptic equations[END_REF] for fully nonlinear degenerate elliptic convex and concave Hamilton Jacobi operators. For helpful details of Strong Maximum Principle results for Hamilton Jacobi equations we refer to [START_REF] Barles | Solutions de viscosité des équations de Hamilton-Jacobi[END_REF]. Yet, it is worth mentioning that Strong Maximum Principle for linear elliptic equations goes back to Hopf in the 20s and to Nirenberg, for parabolic equations [START_REF] Nirenberg | A strong maximum principle for parabolic equations[END_REF].

In the last part we use Strong Maximum Principle to prove a Strong Comparison Result of viscosity sub and supersolution for integro-differential equations of the form (1.1) with the Dirichlet boundary condition

u = ϕ on Ω c × [0, T ] (1.7)
where ϕ is a continuous function.

Nonlocal equations find many applications in mathematical finance and occur in the theory of Lévy jump-diffusion processes. The theory of viscosity solutions has been extended for a rather long time to Partial Integro-Differential Equations (PIDEs). Some of the first papers are due to Soner [START_REF] Halil | Optimal control with state-space constraint[END_REF], [START_REF] Halil | Optimal control with state-space constraint[END_REF], in the context of stochastic control jump diffusion processes. Following his work, existence and comparison results of solutions for first order PIDEs were given by Sayah in [START_REF] Sayah | Équations d'Hamilton-Jacobi du premier ordre avec termes intégro-différentiels. I. Unicité des solutions de viscosité[END_REF] and [START_REF] Sayah | Équations d'Hamilton-Jacobi du premier ordre avec termes intégro-différentiels. II. Existence de solutions de viscosité[END_REF].

Second-order degenerate PIDEs are more complex and required careful studies, according to the nature of the integral operator (often reflected in the singularity of the Lévy measure against which they are integrated). When these equations involve bounded integral operators, general existence and comparison results for semi-continuous and unbounded viscosity solutions were found by Alvarez and Tourin [START_REF] Alvarez | Viscosity solutions of nonlinear integro-differential equations[END_REF]. Amadori extended the existence and uniqueness results for a class of Cauchy problems for integro-differential equations, starting with initial data with exponential growth at infinity [START_REF] Lisa | Nonlinear integro-differential evolution problems arising in option pricing: a viscosity solutions approach[END_REF] and proved a local Lipschitz regularity result.

Systems of parabolic integro-differential equations dealing with second order nonlocal operators were connected to backwards stochastic differential equations in [START_REF] Barles | Backward stochastic differential equations and integralpartial differential equations[END_REF] and existence and comparison results were established. Pham connected the optimal stopping time problem in a finite horizon of a controlled jump diffusion process with a parabolic PIDE in [START_REF] Pham | Optimal stopping of controlled jump diffusion processes: a viscosity solution approach[END_REF] and proved existence and comparison principles of uniformly continuous solutions. Existence and comparison results were also provided by Benth, Karlsen and Reikvam in [START_REF] Benth | Optimal portfolio selection with consumption and nonlinear integro-differential equations with gradient constraint: a viscosity solution approach[END_REF] where a singular stochastic control problem is associated to a nonlinear second-order degenerate elliptic integro-differential equation subject to gradient and state constraints, as its corresponding Hamilton-Jacobi-Bellman equation.

Jakobsen and Karlsen in [START_REF] Espen | A "maximum principle for semicontinuous functions" applicable to integro-partial differential equations[END_REF] used the original approach due to Jensen [START_REF] Jensen | The maximum principle for viscosity solutions of fully nonlinear second order partial differential equations[END_REF], Ishii [START_REF] Ishii | On uniqueness and existence of viscosity solutions of fully nonlinear second-order elliptic PDEs[END_REF], Ishii and Lions [START_REF] Ishii | Viscosity solutions of fully nonlinear second-order elliptic partial differential equations[END_REF], Crandall and Ishii [START_REF] Michael | The maximum principle for semicontinuous functions[END_REF] and Crandall, Ishii and Lions [START_REF] Michael | User's guide to viscosity solutions of second order partial differential equations[END_REF] for proving comparison results for viscosity solutions of nonlinear degenerate elliptic integro-partial differential equations with second order nonlocal operators. Parabolic versions of their main results were given in [START_REF] Espen | Continuous dependence estimates for viscosity solutions of integro-PDEs[END_REF]. They give an analogous of Jensen-Ishii's Lemma, a keystone for many comparison principles, but they are restricted to subquadratic solutions. The viscosity theory for general PIDEs has been recently revisited and extended to solutions with arbitrary growth at infinity by Barles and Imbert [START_REF] Barles | Second-order elliptic integro-differential equations: viscosity solutions' theory revisited[END_REF]. The authors provided as well a variant of Jensen Ishii's Lemma for general integro-differential equations. The notion of viscosity solution generalizes the one introduced by Imbert in [START_REF] Imbert | A non-local regularization of first order Hamilton-Jacobi equations[END_REF] for first-order Hamilton Jacobi equations in the whole space and Arisawa in [START_REF] Arisawa | A new definition of viscosity solutions for a class of second-order degenerate elliptic integrodifferential equations[END_REF], [START_REF] Arisawa | Corrigendum for the comparison theorems in: "A new definition of viscosity solutions for a class of second-order degenerate elliptic integro-differential equations[END_REF] for degenerate integro-differential equations on bounded domains.

The paper is organized as follows. In section §2 we study separately the propagation of maxima in C(P 0 ) and in the region Ω × (0, t 0 ). In section §3 similar results are given for Lévy Itô operators. Examples are provided in section §4. In section §5 we prove a Strong Comparison Result for the Dirichlet Problem, based on the Strong Maximum Principle for the linearized equation.

Strong Maximum Principle for general nonlocal operators

The aim of this section is to prove the local propagation of maxima of viscosity solutions of (1.1) in the cylindrical region Q T . As announced, we study separately the propagation of maxima in the horizontal domains Ω × {t 0 } and the local vertical propagation in regions Ω × (0, t 0 ). Each case requires different sets of assumptions.

In the sequel, we refer to integro-differential equations of the form (1.1) where the function u is a priori given outside Ω. Assume that F satisfies

(E) F is continuous in Ω × [0, T ] × R N × S N × R and degenerate elliptic.
Results are presented for general nonlocal operators

I[x, t, u] = R N (u(x + z, t) -u(x, t) -Du(x, t) • z1 B (z))µ x (dz)
where {µ x } x∈Ω is a family of Lévy measures. We assume it satisfies assumption (M ) there exists a constant Cµ > 0 such that, for any x ∈ Ω,

B |z| 2 µ x (dz) + R N \B µ x (dz) ≤ Cµ .
To overcome the difficulties imposed by the behavior at infinity of the measures (µ x ) x , we often need to split the nonlocals term into

I 1 δ [x, t, u] = |z|≤δ (u(x + z, t) -u(x, t) -Du(x, t) • z1 B (z))µ(dz) I 2 δ [x, t, p, u] = |z|>δ (u(x + z, t) -u(x, t) -p • z1 B (z))µ(dz)
with 0 < δ < 1 and p ∈ R N .

There are several equivalent definitions of viscosity solutions, but we will mainly refer to the following one.

Definition 2.1 (Viscosity solutions). An usc function

u : R N × [0, T ] → R is a subsolution of (1.1) if for any φ ∈ C 2 (R N ×[0, T ]) such that u-φ attains a global maximum at (x, t) ∈ Ω×(0, T ) φ t (x, t) + F (x, t, φ(x, t), Dφ(x, t), D 2 φ(x, t), I 1 δ [x, t, φ] + I 2 δ [x, t, Dφ(x, t), u]) ≤ 0. A lsc function u : R N × [0, T ] → R is a supersolution of (1.1) if for any test function φ ∈ C 2 (R N × [0, T ]) such that u -φ attains a global minimum at (x, t) ∈ Ω × (0, T ) φ t (x, t) + F (x, t, φ(x, t), Dφ(x, t), D 2 φ(x, t), I 1 δ [x, t, φ] + I 2 δ [x, t, Dφ(x, t), u]) ≥ 0.
2.1. Horizontal propagation of maxima coming from translations of measure supports. Maximum principle results for nonlocal operators generated by nonnegative kernels defined on topological groups acting continuously on a Hausdorff space were settled out by Coville in [START_REF] Coville | Remarks on the strong maximum principle for nonlocal operators[END_REF]. In the following, we present similar results for integro-differential operators in the setting of viscosity solutions. It can be shown that Maximum Principle holds for nonlocal operators given by (1.3) whenever the whole domain can be covered by translations of measure supports, starting from a maximum point.

An additional assumption is required with respect to the nonlinearity F . More precisely we require that (E ′ ) F is continuous, degenerate elliptic and for x, p ∈ R N and l ∈ R

F (x, t, 0, O, l) ≤ 0 ⇒ l ≥ 0.
For the sake of precision, the following result is given for integro-differential equations defined in R N . We explain in Remark 2.2 what happens when we restrict to some open set Ω. Theorem 2.1. Assume the family of measures {µ x } x∈Ω satisfies assumption (M ). Let F satisfy (E ′ ) in R N × [0, T ] and u ∈ U SC(R N × [0, T ]) be a viscosity solution of (1.1) in R N × (0, T ). If u attains a global maximum at (x 0 , t 0 ) ∈ R N × (0, T ), then u is constant on n≥0 A n , with

A 0 = {x 0 }, A n+1 = x∈An (x + supp(µ x )).
(2.8)

Proof. Assume that u is a viscosity subsolution for the given equation. Consider the test-function ψ ≡ 0 and write the viscosity inequality at point (x 0 , t 0 ) F (x 0 , t 0 , 0, O, I 1 δ [x 0 , t 0 , ψ] + I 2 δ [x 0 , t 0 , Dψ(x 0 , t 0 ), u]) ≤ 0. This implies according to assumption (E ′ ), that

I 2 δ [x 0 , t 0 , u] = |z|≥δ (u(x 0 + z, t 0 ) -u(x 0 , t 0 ))µ x 0 (dz) ≥ 0.
But u attains its maximum at (x 0 , t 0 ) and thus u(x 0 + z, t 0 )u(x 0 , t 0 )) ≤ 0. Letting δ go to zero we have u(z, t 0 ) = u(x 0 , t 0 ), for all z ∈ x 0 + supp(µ x 0 ). Arguing by induction, we obtain

u(z, t 0 ) = u(x 0 , t 0 ), ∀z ∈ n≥0 A n .
Take now z 0 ∈ n≥0 A n . Then, there exists a sequence of points (z n ) n ⊂ n≥0 A n converging to z 0 . Since u is upper semicontinuous, we have

u(z 0 , t 0 ) ≥ lim sup zn→z 0 u(z n , t 0 ) = u(x 0 , t 0 ).
But (x 0 , t 0 ) is a maximum point and the converse inequality holds. Therefore

u(z, t 0 ) = u(x 0 , t 0 ), ∀z ∈ n≥0 A n .
Remark 2.1. In particular when supp(µ x ) = supp(µ) = B, with µ being a Lévy measure and B the unit ball, R N can be covered by translations of supp(µ) starting at x 0

R N = x 0 + n≥0 supp(µ) + ... + supp(µ) n . and thus u(•, t 0 ) is constant in R N .
Remark 2.2. Whenever the equation is restricted to Ω, with the corresponding Dirichlet condition outside the domain, then iterations must be taken for all the points in Ω, i.e.

A n+1 = x∈Ω∩An (x + supp(µ x )) In particular, if Ω ⊂ n≥0 A n , then u(•, t 0 ) is constant in Ω.
Remark 2.3. The domain Ω may not necessarily be connected and still maxima might propagate, since jumps from one connected component to another might occur when measure supports overlap two or more connected components.

The previous result has an immediate corollary. If all measure supports have nonempty (topological) interior and contain the origin, strong maximum principle holds.

Corollary 2.1. Let Ω be connected, F be as before and u ∈ U SC(R N × [0, T ]) be a viscosity subsolution of (1.1) in Ω × (0, T ). Assume that {µ x } x∈Ω satisfies (M ) and in addition that the origin belongs to the topological interiors of all measure supports

0 ∈ ˚ supp(µ x ), ∀x ∈ Ω.
(2.9)

If u attains a global maximum at (x 0 , t 0 ) ∈ Ω × (0, T ), then u(•, t 0 ) is constant in Ω.
Proof. Consider the iso-level

Γ x 0 = {x ∈ Ω; u(x, t 0 ) = u(x 0 , t 0 )}.
Then the set is simultaneously open since 0 ∈ ˚ supp(µ x ) implies, by Theorem 2.1, together with Remark 2.2 that for any x ∈ Γ x 0 we have

x + ˚ supp(µ x ) ∩ Ω ⊂ Γ x 0
and closed because for any x ∈ Γx 0 we have by the upper-semicontinuity of u u(x, t 0 ) ≥ lim sup y→x, y∈Γx 0 u(y, t 0 ) = max y∈Ω u(y, t 0 ) thus u(x, t 0 ) = u(x 0 , t 0 ). Therefore, Γ x 0 = Ω since Ω is connected.

Horizontal propagation of maxima under nondegeneracy conditions.

There are cases when conditions (2.8) and (2.9) fail, such as measures whose supports are contained in half space or nonlocal terms acting in one direction, as we shall see in section §4. However, we manage to show that, if a viscosity subsolution attains a maximum at P 0 = (x 0 , t 0 ) ∈ Q T , then the maximum propagates in the horizontal component C(P 0 ). This result is based on nondegeneracy and scaling properties on the nonlinearity F :

(N ) For any x ∈ Ω and 0 < t 0 < T there exist R 0 > 0 small enough and 0 ≤ η < 1 such that for any 0 < R < R 0 and c > 0

F (x, t, p, I -γp ⊗ p, Cµ -cγ Cη,γ (p) p • z 2 µ x (dz)) → +∞ as γ → +∞ uniformly for |x -x| ≤ R and |t -t 0 | ≤ R, R/2 ≤ |p| ≤ R, where C η,γ (p) = {z; (1 -η)|z||p| ≤ |p • z| ≤ 1/γ}
and Cµ appears in (M ). (S) There exist some constants R 0 > 0, ε 0 > 0 and γ 0 > 0 s.t. for all 0 < R < R 0 , ε < ε 0 and γ ≥ γ 0 the following condition holds for all |x -x| ≤ R and |t -

t 0 | ≤ R, R/2 ≤ |p| ≤ R, F (x, t, εp, ε(I -γp ⊗ p), εl) ≥ εF (x, t, p, I -γp ⊗ p, l).
As we shall see in §4 the assumption (M ) which states that the measure µ x is bounded at infinity, uniformly with respect to x and the possible singularity at the origin is of order |z| 2 is not sufficient to ensure condition (N ). The following assumption is in general needed, provided that the nonlinearity F is nondegenerate in the nonlocal term. (M c ) For any x ∈ Ω there exist 1 < β < 2, 0 ≤ η < 1 and a constant C µ (η) > 0 such that the following holds

Cη,γ (p)

|z| 2 µ x (dz) ≥ C µ (η)γ β-2 , ∀γ ≥ 1
with C η,γ (p) as before.

As pointed out in section §4, (M c ) holds for a wide class of Lévy measures as well as (N ) -(S) for a class of nonlinearities F .

Theorem 2.2. Assume the family of measures {µ x } x∈Ω satisfies assumptions (M ). Let u ∈ U SC(R N × [0, T ]) be a viscosity subsolution of (1.1) that attains a global maximum at P 0 = (x 0 , t 0 ) ∈ Q T . If F satisfies (E), (N ), and (S) then u is constant in C(P 0 ).

Proof. We proceed as for locally uniformly parabolic equations and argue by contradiction.

1. Suppose there exists a point P 1 = (x 1 , t 0 ) such that u(P 1 ) < u(P 0 ). The solution u being upper semi-continuous, by classical arguments we can construct for fixed t 0 a ball B(x, R) where

u(x, t 0 ) < M = max R N (u(•, t 0 )), ∀x ∈ B(x, R).
In addition there exists x * ∈ ∂B(x, R) such that u(x * , t 0 ) = M . Translating if necessary the center x in the direction x *x, we can choose R < R 0 , with R 0 given by condition (N ).

Moreover we can extend the ball to an ellipsoid

E R (x, t 0 ) := {(x, t); |x -x| 2 + λ|t -t 0 | 2 < R 2 } with λ large enough the function u satisfies u(x, t) < M, for (x, t) ∈ E R (x, t 0 ) s.t. |x -x| ≤ R/2. Remark that (x * , t 0 ) ∈ ∂E R (x, t 0 ) with u(x * , t 0 ) = M.

Introduce the auxiliary function

v(x, t) = e -γR 2 -e -γ(|x-x| 2 +λ|t-t 0 | 2 )
where γ > 0 is a large positive constant, yet to be determined. Note that v = 0 on ∂E R (x, t 0 ) and -1

< v < 0, in E R (x, t 0 ). Denote d(x, t) = |x -x| 2 + λ|t -t 0 | 2 . Direct computations give v t (x, t) = 2γe -γd(x,t) λ(t -t 0 ) Dv(x, t) = 2γe -γd(x,t) (x -x) D 2 v(x, t) = 2γe -γd(x,t) (I -2γ(x -x) ⊗ (x -x)).
In upcoming Proposition 2.1 we show there exist two positive constants c = c(η, R) and γ 0 > 0 such that for γ ≥ γ 0 , the following estimate of the nonlocal term holds

I[x, t, v] ≤ 2γe -γd(x,t) Cµ -cγ Cη,γ (x-x) (x -x) • z 2 µ x (dz) in the subdomain D R (x, t 0 ) := {(x, t) ∈ E R (x, t 0 ); |x -x| > R/2}.
3. From the nondegeneracy condition (N ) and scaling assumption (S) we get that v is a strict supersolution at points (x, t) in D R (x, t 0 ). Indeed, for γ large enough

F x, t, x -x, I -2γ(x -x) ⊗ (x -x), Cµ -cγ Cη,γ (x-x) (x -x) • z 2 µ x (dz) > 0 which implies v t (x, t) + F (x, t, Dv(x, t), D 2 v(x, t), I[x, t, v]) = 2γe -γd(x,t) λ(t -t 0 ) + F x, t, 2γe -γd(x,t) (x -x), 2γe -γd(x,t) (I -2γ(x -x) ⊗ (x -x) , ..., 2γe -γd(x,t) Cµ -cγ Cη,γ (x-x) (x -x) • z 2 µ x (dz) ) ≥ 2γe -γd(x,t) λ(t -t 0 ) + F x, t, x -x, I -2γ(x -x) ⊗ (x -x), ..., Cµ -cγ Cη,γ (x-x) (x -x) • z 2 µ x (dz) > 0.
Furthermore, the scaling assumption (S) ensures the existence of a constant ε 0 > 0 such that for all ε < ε 0 , εv is a strict supersolution of (1.1) in D R (x, t 0 ). Indeed we have

εv t (x, t) + F (x, t, εDv(x, t), εD 2 v(x, t), εI[x, t, v]) ≥ ε v t (x, t) + kF (x, t, Dv(x, t), D 2 v(x, t), I[x, t, v]) > 0. 4. Remark that v ≥ 0 in E c R (x, t 0 ) u < M in E R (x, t 0 ) \ D R (x, t 0 ).
Therefore, there exists some ε 0 > 0 such that for all ε < ε 0 outside the domain D R (x, t 0 ) u(x, t) ≤ u(x * , t 0 ) + εv(x, t).

Then we claim that the inequality holds inside D R (x, t 0 ). Indeed, if u ≤ u(x * , t 0 ) + εv does not hold, then max R N (u -Mεv) > 0 would be attained in D R (x, t 0 ) at say, (x ′ , t ′ ). Since u is a viscosity subsolution the following would hold

εv t (x ′ , t ′ ) + F (x ′ , t ′ , εDv(x ′ , t ′ ), εD 2 v(x ′ , t ′ ), I[x ′ , t ′ , εv]) ≤ 0
arriving thus to a contradiction with the fact that M + εv is a strict supersolution of (1.1).

5. The function u(x, t)εv(x, t) has therefore a global maximum at (x * , t 0 ). Since u is a viscosity subsolution of (1.1), we have

εv t (x * , t 0 ) + F (x * , t 0 , εDv(x * , t 0 ), εD 2 v(x * , t 0 ), I[x * , t 0 , εv]) ≤ 0.
As before, we arrived at a contradiction because εv is a strict supersolution and thus the converse inequality holds at (x * , t 0 ). Consequently, the assumption made is false and u is constant in the horizontal component of P 0 .

In the following we give the estimate for the nonlocal operator acting on the auxiliary function. We use the same notations as before.

Proposition 2.1. Let R > 0, λ > 0, γ > 0 and consider the smooth function

v(x, t) = e -γR 2 -e -γd(x,t) d(x, t) = |x -x| 2 + λ|t -t 0 | 2
Then there exist two constants c = c(η, R) and γ 0 > 0 such that for γ ≥ γ 0 the nonlocal operator satisfies

I[x, t, v] ≤ 2γe -γd(x,t)
Cµcγ

{(1-η)|z||x-x|≤|(x-x)•z|≤1/γ} (x -x) • z 2 µ x (dz) for all R/2 < |x -x| < R.
Proof. In order to estimate the nonlocal term I[x, t, v], we split the domain of integration into three pieces and take the integrals on each of these domains. Namely we part the unit ball into the subset

C η,γ (x -x) = {z; (1 -η)|z||x -x| ≤ |(x -x) • z| ≤ 1/γ}
and its complementary. Indeed C η,γ (xx) lies inside the unit ball, as for |x -x| ≥ R/2 and for γ large enough

|z| ≤ 1 γ(1 -η)|x -x| ≤ 2 γ(1 -η)R ≤ 1.
(2.10)

Thus we write the nonlocal term as the sum

I[x, t, v] = T 1 [x, t, v] + T 2 [x, t, v] + T 3 [x, t, v]
with

T 1 [x, t, v] = |z|≥1 (v(x + z, t) -v(x, t))µ x (dz) T 2 [x, t, v] = B\Cη,γ (x-x) (v(x + z, t) -v(x, t) -Dv(x, t) • z)µ x (dz) T 3 [x, t, v] = Cη,γ (x-x) (v(x + z, t) -v(x, t) -Dv(x, t) • z)µ x (dz).
In the sequel, we show that each integral term is controlled from above by an exponential term of the form γe -γd(x,t) . In addition, the last integral is driven by a nonpositive quadratic nonlocal term.

Lemma 2.1. We have

T 1 [x, t, v] ≤ e -γd(x,t) |z|≥1 µ x (dz), ∀(x, t) ∈ Ω × [0, T ].
Proof. The estimate is due to the uniform bound of the measures µ x away from the origin. Namely

T 1 [x, t, v] = |z|≥1
(-e -γd(x+z,t) + e -γd(x,t) )µ x (dz)

≤ |z|≥1 e -γd(x,t) µ x (dz) = e -γd(x,t) |z|≥1 µ x (dz) ≤ e -γd(x,t) Cµ .
Lemma 2.2. We have

T 2 [x, t, v] ≤ γe -γd(x,t) B |z| 2 µ x (dz), ∀(x, t) ∈ Ω × [0, T ]. Proof. Note that T 2 [x, t, v] = -T 2 [x, t, e -γd ]. From Lemma 6.1 in Appendix T 2 [x, t, e -γd ] ≥ e -γd(x,t) T 2 [x, t, -γd] = -γe -γd(x,t) T 2 [x, t, d].
Taking into account the expression for d(x, t), we get that

T 2 [x, t, v] ≤ γe -γd(x,t) B\Cη,γ (x-x) (d(x + z, t) -d(x, t) -Dd(x, t) • z)µ x (dz) = γe -γd(x,t)
B\Cη,γ (x-x)

|z| 2 µ x (dz) ≤ γe -γd(x,t) B |z| 2 µ x (dz) ≤ γe -γd(x,t)
Cµ .

Lemma 2.3. There exist two positive constants c = c(η, R) and γ 0 > 0 such that for γ ≥ γ 0

T 3 [x, t, v] ≤ e -γd(x,t) γ B |z| 2 µ x (dz) -2cγ 2 Cη,γ (x-x) (x -x) • z 2 µ x (dz) , ∀(x, t) ∈ D R .
Proof. Rewrite equivalently the integral as

T 3 [x, t, v] = T 3 [x, t, v -e -γR 2 ] = -T 3 [x, t, e -γd ].
We apply then Lemma 6.2 in Appendix to the function e -γd and get that for all δ > 0 there exists c = c(η, R) > 0 such that

T 3 [x, t, e -γd ] ≥ e -γd(x,t) T 3 [x, t, -γd] + 2cγ 2 Cη,γ (x-x) d(x + z, t) -d(x, t) 2 µ x (dz) = -γe -γd(x,t) T 3 [x, t, d] -2cγ Cη,γ (x-x) d(x + z, t) -d(x, t) 2 µ x (dz) . Remark that C η,γ (x -x) ⊆ D δ for δ = 2 + 2 (1-η)R , with D δ = {z; γ d(x + z, t) -d(x, t) ≤ δ} = {z; γ(2(x -x) • z + |z| 2 ) ≤ δ}.
We have thus

T 3 [x, t, v] ≤ γe -γd(x,t) T 3 [x, t, d] -2cγ Cη,γ (x-x) d(x + z, t) -d(x, t) 2 µ x (dz) .
Taking into account the expression of d(x, t), direct computations give

T 3 [x, t, d] = Cη,γ (x-x) d(x + z, t) -d(x, t) -Dd(x, t) • z µ x (dz) = Cη,γ (x-x) |z| 2 µ x (dz) ≤ B |z| 2 µ x (dz),
while the quadratic term is bounded from below by

Cη,γ (x-x) d(x + z, t) -d(x, t) 2 µ x (dz) = Cη,γ (x-x) 2(x -x) • z + |z| 2 2 µ x (dz) ≥ Cη,γ (x-x) (x -x) • z 2 µ x (dz). Indeed, recall that |x -x| ≥ R/2 and see that for all z ∈ C η,γ (x -x) (1 -η)|x -x||z| ≤ 1/γ ⇒ |z| ≤ 2 γR(1 -η) (1 -η)|x -x||z| ≤ |(x -x) • z| ⇒ |z| ≤ 2|(x -x) • z| R(1 -η)
Then for γ 0 = 4/R 2 (1η) 2 and γ ≥ γ 0 we have the estimate

2(x -x) • z + |z| 2 ≥ 2|(x -x) • z| -|z| 2 ≥ 2|(x -x) • z| - 4|(x -x) • z| γR 2 (1 -η) 2 = |(x -x) • z| 2 - 4 γR 2 (1 -η) 2 ≥ |(x -x) • z|.
Therefore, we obtain the upper bound for the integral term

T 3 [x, t, v] ≤ γe -γd(x,t) Cη,γ (x-x) |z| 2 µ x (dz) -2cγ Cη,γ (x-x) (x -x) • z 2 µ x (dz) .
From the three lemmas estimating the integral terms we deduce that

I[x, t, v] ≤ e -γd(x,t) |z|≥1 µ x (dz) + 2γ B |z| 2 µ x (dz) -2cγ 2 Cη,γ (x-x) (x -x) • z 2 µ x (dz) ≤ 2γe -γd(x,t) Cµ -cγ Cη,γ (x-x) (x -x) • z 2 µ x (dz) .

2.3.

Local vertical propagation of maxima. We show that if u ∈ U SC(R N × [0, T ]) is a viscosity subsolution of (1.1) which attains a maximum at P 0 = (x 0 , t 0 ) ∈ Q T , then the maximum propagates locally in rectangles, say,

R(x 0 , t 0 ) = {(x, t)||x i -x i 0 | ≤ a i , t 0 -a 0 ≤ t ≤ t 0 }
where we have denoted x = (x 1 , x 2 , ..., x N ). Denote by R 0 (x 0 , t 0 ) the rectangle R(x 0 , t 0 ) less the top face {t = t 0 }.

Local vertical propagation of maxima occurs under softer assumptions on the nondegeneracy and scaling conditions. More precisely, we suppose the following holds:

(N ′ ) For any (x 0 , t 0 ) ∈ Q T there exists λ > 0 such that λ + F (x 0 , t 0 , 0, I, Cµ ) > 0 where Cµ is given by assumption (M ). (S ′ ) There exist two constants r 0 > 0, ε 0 > 0 such that for all ε < ε 0 and 0 < r < r 0 the following condition holds for all (x, t) ∈ B((x 0 , t 0 ), r), |p| ≤ r, l ≤ Cµ F (x, t, εp, εI, εl) ≥ εF (x, t, p, I, l).

Theorem 2.3. Let u ∈ U SC(R N × [0, T ]
) be a viscosity subsolution of (1.1) that attains a maximum at P 0 = (x 0 , t 0 ) ∈ Q T . If F satisfies (E), (N ′ ) and (S ′ ) then for any rectangle R(x 0 , t 0 ), R 0 (x 0 , t 0 ) contains a point P = P 0 such that u(P ) = u(P 0 ).

Proof. Similarly to the horizontal propagation of maxima, we argue by contradiction.

1. Suppose there exists a rectangle R(x 0 , t 0 ) on which u(x, t) < M = u(x 0 , t 0 ), with R 0 (x 0 , t 0 ) ⊆ Ω × [0, t 0 ). Denote

h(x, t) = 1 2 |x -x 0 | 2 + λ(t -t 0 )
with λ > 0 a constant yet to be determined. Consider the auxiliary function v(x, t) = 1e -h(x,t) .

Direct calculations give

v t (x, t) = λe -h(x,t) Dv(x, t) = e -h(x,t) (x -x 0 ) D 2 v(x, t) = e -h(x,t) (I -(x -x 0 ) ⊗ (x -x 0 )), Note that v(x 0 , t 0 ) = 0 v t (x 0 , t 0 ) = λ Dv(x 0 , t 0 ) = 0 D 2 v(x 0 , t 0 ) = I.
The nonlocal term is written as the sum of two integral operators:

I[x, t, v] = T 1 [x, t, v] + T 2 [x, t, v],
where

T 1 [x, t, v] = |z|≥1 (v(x + z, t) -v(x, t))µ x (dz) T 2 [x, t, v] = B (v(x + z, t) -v(x, t) -Dv(x, t) • z)µ x (dz).
Similarly to Lemma 2.1 we obtain the estimate: Lemma 2.4. We have

T 1 [x, t, v] ≤ e -h(x,t) |z|≥1 µ x (dz), ∀(x, t) ∈ Ω × [0, T ].
On the other hand, the estimate obtained for the second integral term is softer than the estimate obtained in the case of the horizontal propagation of maxima.

Lemma 2.5. We have

T 2 [x, t, v] ≤ e -h(x,t) B |z| 2 µ x (dz), ∀(x, t) ∈ Ω × [0, T ].
Proof. From Lemma 6.1 we have

T 2 [x, t, v] = -T 2 [x, t, e -h ] ≤ e -h(x,t) T 2 [x, t, h].
We then use a second-order Taylor expansion for h and get

T 2 [x, t, h] = 1 2 B sup θ∈(-1,1) D 2 h(x + θz, t)z • z µ x (dz) = 1 2 B |z| 2 µ x (dz) ≤ 1 2 B |z| 2 µ x (dz),
from where the conclusion.

We now go back to the proof of the theorem and see that

I[x, t, v] ≤ e -h(x,t) Cµ .
In particular I[x 0 , t 0 , v] ≤ Cµ .

2. From the nondegeneracy assumption (N ′ ) we have that there exists λ > 0 such that v t (x 0 , t 0 ) + F (x 0 , t 0 , Dv(x 0 , t 0 ), D 2 v(x 0 , t 0 ), I[x 0 , t 0 , v])

≥ v t (x 0 , t 0 ) + F (x 0 , t 0 , Dv(x 0 , t 0 ), D 2 v(x 0 , t 0 ), Cµ ) = λ + F (x 0 , t 0 , 0, I, Cµ ) > 0.
Hence v is a strict supersolution of (1.1) at (x 0 , t 0 ). By the continuity of F , there exists r < r 0 such that ∀(x, t) ∈ B((x 0 , t 0 ), r)

⊆ Q T v t (x, t) + F (x, t, Dv(x, t), D 2 v(x, t), I[x, t, v]) ≥ C > 0.
Consider then the set S = B((x 0 , t 0 ), r) ∩ {(x, t)|v(x, t) < 0}. By (S ′ ) there exists ε 0 > 0 such that ∀ε < ε 0 , εv is a strict supersolution of (1.1) in S. Indeed

εv t (x, t) + F (x, t, εDv(x, t), εD 2 v(x, t), εI[x, t, v]) ≥ ε v t (x, t) + F (x, t, Dv(x, t), D 2 v(x, t), I[x, t, v]) > 0
3. Let ε 0 be sufficiently small such that u(x, t)u(x 0 , t 0 ) ≤ εv(x, t), ∀(x, t) ∈ ∂S.

Then, arguing as in the case of horizontal propagation of maxima we get u(x, t)u(x 0 , t 0 ) ≤ εv(x, t), ∀(x, t) ∈ S.

Thus (x 0 , t 0 ) is a maximum of uεv with Dv(x 0 , t 0 ) = λ > 0. Since u is a subsolution, we have εv t (x 0 , t 0 ) + F (x 0 , t 0 , εv(x 0 , t 0 ), εDv(x 0 , t 0 ), εD 2 v(x 0 , t 0 ), I[x 0 , t 0 , εv]) ≤ 0.

We arrived at a contradiction with the fact that εv is a strict supersolution. Thus, the supposition is false and the rectangle contains a point P = P 0 such that u(P ) = u(P 0 ).

Example 2.1. Non-local first order Hamilton Jacobi equations describing the dislocation dynamics

u t = (c(x) + M [u(t, •)])|Du| (2.
11) where M is a zero order nonlocal operator defined by

M [u(t, •)](x) = R N u(x + z) -u(x))µ(dz)
with µ(dz) = g( z |z| ) dz |z| N+1 have vertical propagation of maxima. Indeed, they do not satisfy any of the sets of assumptions required by Theorems 2.1 and 2.2. Particularly nondegeneracy condition (N ) c(x) + Cµ |p| ≤ 0 fails if c(x) ≥ 0 and holds whenever c(x) ≥ -Cµ . Hence, one cannot conclude on horizontal propagation of maxima.

On the other hand we have local vertical propagation of maxima, since (N ′ ) is immediate and (S ′ ) is satisfied by F = -c(x)|p|, the linear approximation of the nonlinearity F :

-c(x) + εl)|εp| = -εc(x)|p| + o(ε 2 ).
2.4. Strong Maximum Principle. When both horizontal and local vertical propagation of maxima occur for a viscosity subsolution of (1.1) which attains a global maximum at an interior point, the function is constant in any rectangle contained in the domain Ω × [0, t 0 ] passing through the maximum point. Proposition 2.2. Let u ∈ U SC(R N × [0, T ]) be a viscosity subsolution of (1.1) that attains a global maximum at

P 0 = (x 0 , t 0 ) ∈ Q T . If F satisfies (E), (N ) -(N ′ ), and (S) -(S ′ ), then u is constant in any rectangle R(x 0 , t 0 ) ⊆ Ω × [0, t 0 ].
From the horizontal and local vertical propagation of maxima one can derive the Strong Maximum Principle. The proof is based on geometric arguments and is identical to that for fully nonlinear second order partial differential equations.

Theorem 2.4 (Strong Maximum Principle). Assume the family of measures {µ

x } x∈Ω satisfies assumption (M ). Let u ∈ U SC(R N × [0, T ]
) be a viscosity subsolution of (1.1) that attains a global maximum at P 0 = (x 0 , t 0 ) ∈ Q T . If F satisfies (E), (S) -(S ′ ), and (N ) -(N ′ ), then u is constant in S(P 0 ).

Similarly the following holds.

Theorem 2.5 (Strong Maximum Principle). Let u ∈ U SC(R N ×[0, T ]) be a viscosity subsolution of (1.1) in R N × (0, T ) that attains a global maximum at (x 0 , t 0 ) ∈ R N × (0, T ]. Assume the family of measures {µ x } x∈Ω satisfies assumption (M ) and F satisfies (E ′ ), (S ′ ) and (N ′ ). Then u is constant in n≥0 A n × [0, t 0 ] with {A n } n given by (2.8).

Strong Maximum Principle for Lévy-Itô operators

The results established for general nonlocal operators remain true for Lévy-Itô operators. We translate herein the corresponding assumptions and theorems on the Strong Maximum Principle for second order integro-differential equations associated to Lévy-Itô operators

J [x, t, u] = R N (u(x + j(x, z), t) -u(x, t) -Du(x, t) • j(x, z)1 B (z))µ(dz),
where µ is a Lévy measure. In the sequel we assume that F respects the scaling assumption (S) and the nondegeneracy condition (N LI ) For any x ∈ Ω and 0 < t 0 < T there exist R 0 > 0 small enough and 0 < η < 1 such that for any 0 < R < R 0 and c > 0

F (x, t, p, I -γp ⊗ p, Cµ -cγ Cη,γ (p) p • j(x, z) 2 µ(dz)) → ∞ as γ → ∞ uniformly for |x -x| ≤ R and |t -t 0 | ≤ R, R/2 ≤ |p| ≤ R, where C η,γ (p) = {z; (1 -η)|j(x, z)||p| ≤ |p • j(x, z)| ≤ 1/γ}.
and that the Lévy measure µ satisfies assumptions (M LI ) there exists a constant Cµ > 0 such that for any x ∈ Ω,

B |j(x, z)| 2 µ(dz) + R N \B µ(dz) ≤ Cµ ;
(M c LI ) For any x ∈ Ω there exist 1 < β < 2, 0 ≤ η < 1 and a constant C µ (η) > 0 such that the following holds

Cη,γ (p) |j(x, z)| 2 µ(dz) ≥ C µ (η)γ β-2 , ∀γ ≥ 1.
Theorem 2.1 holds for Lévy-Itô operators, since Lévy Itô measures can be written as pushforwards of some Lévy measure μ µ x = (j(x, •) * (μ)) defined for measurable functions φ as

R N φ(x)µ(dz) = R N φ(j(x, z))μ(dz).
Hence it is sufficient to replace supp(µ x ) = j(x, supp(μ)) in order to get the corresponding result. Theorem 3.1. Assume the family of measures {µ x } x∈R N satisfies assumptions (M LI ). Let u ∈ U SC(R N × [0, T ]) be a viscosity subsolution of (1.1) that attains a maximum at P 0 = (x 0 , t 0 ) ∈ Q T . If F satisfies (E), (S), and (N LI ) then u is constant in C(P 0 ).

Proof. Since the proof is technically the same, we just point out the main differences, namely the estimate of the nonlocal term. Consider as before the smooth function v(x, t) = e -γR 2e -γd(x,t) where d(x, t) = |x -x| 2 + λ|tt 0 | 2 , for large γ > γ 0 . Write similarly the nonlocal term as the sum

J [x, t, v] = T 1 [x, t, v] + T 2 [x, t, v] + T 3 [x, t, v]

Examples

In this section we discuss the validity of the Strong Maximum Principle on several examples. 4.1. Horizontal propagation of maxima coming from translations of measure supports. As pointed out in section 2, translations of measure supports starting at any maximum point x 0 lead to horizontal propagation of maxima. In particular, Theorem 2.1 holds for nonlocal terms integrated against Lévy measures whose supports are the whole space R N .

Example 4.1. Consider a pure nonlocal diffusion

u t -I[x, t, u] = 0 in R N × (0, T ) (4. 12
)
where I is the Lévy operator integrated against the Lévy measure associated with the fractional Laplacian (-∆) β/2 :

µ(dz) = dz |z| N +β .
Then the support of the measure is the whole space and thus horizontal propagation of maxima holds for equation (4.12) by Theorem 2.1.

Example 4.2. Let N = 2 and consider equation (4.12) with {µ x } x a family of Lévy measures charging two axis meeting at the origin

µ x (dz) = 1 {z 1 =±αz 2 } ν x (dz),
with α > 0 and supp(ν x ) = R 2 , for all x ∈ R 2 . Even though zero is not an interior point of the support, translations of measure supports starting at any point x 0 cover the whole space, propagating thus maxima all over R 2 .

Similarly, horizontal propagation of maxima holds if measures charge a cone

µ x (dz) = 1 {|z 1 |>α|z 2 |} ν x (dz),
with α > 0 and supp(ν x ) = R 2 .

Strong Maximum Principle driven by the nonlocal term under nondegeneracy conditions.

There are equations for which propagation of maxima does not propagate just by translating measure supports, but cases when it requires a different set of assumptions. Nondegeneracy and scaling conditions of the nonlinearity F need to be satisfied in order to have a Strong Maximum Principle. But to ensure condition (N ), one has to assume (M c ).

Example 4.3. Consider as before equation (4.12) and let µ be the Lévy measure associated to the fractional Laplacian and but restricted to half space

µ(dz) = 1 {z 1 ≥0} (z) dz |z| N +β , β ∈ (1, 2).
where z = (z 1 , z ′ ) ∈ R × R N -1 . Then R N can not be covered by translations of the measure support and therefore one cannot conclude the function u is constant on the whole domain, except for particular cases like the periodic case. However, C 0,α regularity results hold (cf. [START_REF] Barles | Hölder continuity of solutions of second-order non-linear elliptic integro-differential equations[END_REF]) and we expect to have Strong Maximum Principle.

We show that the nondegeneracy and scaling assumptions are satisfied in the case of Example 4.3. Before proceeding to the computations, remark that

C η,γ (p) = {z; (1 -η)|p||z| ≤ |p • z| ≤ 1/γ} = {z; (1 -η)|p||γz| ≤ |p • γz| ≤ 1} = γ -1 C η,1 (p) γ Cη,γ (p)∩{z 1 ≥0} |p • z| 2 dz |z| N +β = γ -1 C η,1 (p)∩{z 1 ≥0} γ β |p • z| 2 dz |z| N +β ≥ γ β-1 |p| 2 (1 -η) 2 C η,1 (p)∩{z 1 ≥0} |z| 2 dz |z| N +β = C(η)γ β-1 |p| 2 where C(η) = (1 -η) 2 C η,1 (p)∩{z 1 ≥0} |z| 2 dz/|z| N +β
is a positive constant. This further implies nondegeneracy condition (N). Indeed, there exist R 0 > 0 small enough and 0 ≤ η < 1 such that for any 0 < R < R 0 and for all R/2 < |p| < R

-Cµ + cγ Cη,γ (p)∩{z 1 ≥0} |p • z| 2 dz |z| N +β ≥ -Cµ + C(η)γ β-1 |p| 2 → ∞ as γ → ∞
as long as β > 1. The rest of assumptions follow immediately.

Similar results hold for the following PIDE arising in the context of growing interfaces [START_REF] Wojbor | Lévy processes in the physical sciences[END_REF]:

u t + 1 2 |Du| 2 -I[x, t, u] = 0, in R N × (0, T ) (4.13)
with I is a general nonlocal operator of form (1.3). Scaling conditions (S) and (S ′ ) are satisfied by the nonlinearity

F |εp| 2 2 -εl = ε |p| 2 2 -l + o (1).
Remark 4.1. For integro-differential equations of the type

u t + b(x, t)|Du| m -I[x, t, u] = 0 in R N × (0, T ) (4.14
u t + trace(A(x, t)D 2 u) -I[x, t, u] = 0 in R N × (0, T ) (4.15)
with A(x, t) satisfying

a 0 (x, t)I ≤ A(x, t) ≤ a 1 (x, t)I, a 1 (x, t) ≥ a 0 (x, t) > 0 satisfy Strong Maximum Principle.
We check the nondegeneracy and scaling conditions for this equation.

(N ) -trace(A(x, t)(I -γp ⊗ p)) -Cµ + cγ Cγ |p • z| 2 µ x (dz) = -trace(A(x, t)) + γtrace(A(x, t)p ⊗ p)) -Cµ + cγ Cγ |p • z| 2 µ x (dz) ≥ -a 1 (x, t)N + a 0 (x, t)γ|p| 2 -Cµ ≫0, for γ large + cγ Cγ |p • z| 2 µ x (dz) ≥0 . (N ′ ) λ -trace(A(x, t)) -Cµ ≥ λ -a 1 (x, t)N -Cµ > 0.
The scaling properties are immediate since the nonlinearity is 1-homogeneous.

Remark 4.2. More generally, one can consider equations of the form

u t + F (x, t, Du, D 2 u) -I[x, t, u] = 0 (4.16)
for which the corresponding differential operator F satisfies the nondegeneracy and scaling assumptions. The nonlocal term is driven by the second order derivatives and thus Strong Maximum Principle holds.

4.4.

Strong Maximum Principle for mixed differential-nonlocal terms. We consider mixed integro-differential equations, i.e. equations for which local diffusions occur only in certain directions and nonlocal diffusions on the orthogonal ones, and show they satisfy Strong Maximum Principle. This is quite interesting, as the equations might be degenerate in both local or nonlocal terms, but the overall behavior is driven by their interaction (the two diffusions cannot cancel simultaneously).

u t -∆ x 2 u -I x 1 [u] = 0 in R N × (0, T ) (4.17) for x = (x 1 , x 2 ) ∈ R d × R N -d .
The diffusion term gives the ellipticity in the direction of x 2 , while the nonlocal term gives it in the direction of x 1

I x 1 [u] = R d (u(x 1 + z 1 , x 2 ) -u(x) - ∂u ∂x 1 (x) • z 1 1 B (z 1 ))µ x 1 (dz 1 )
where µ x 1 is a Lévy measure satisfying (M ) with C1 µ . The payoff for the Strong Maximum Principle to hold is assumption (M c ), with β > 1; then Theorem 2.4 applies.

Indeed the nondegeneracy conditions (N ) and (N ′ ) hold, because when γ is large enough and β > 1 the following holds

(N ) -I N -d + γp 2 ⊗ p 2 -C1 µ + cγ C 1 η,γ (p 1 ) |p 1 • z 1 | 2 µ x 1 (dz 1 ) ≥ -(N -d) + γ|p 1 | 2 -C1 µ + cγ(1 -η) 2 |p 1 | 2 C 1 η,γ (p 1 ) |z 1 | 2 µ x 1 (dz 1 ) ≥ -(N -d + C1 µ ) + γ|p 1 | 2 + C1 (η)γ β-1 |p 1 | 2 ≥ -c 0 + c 1 γ β-1 |p 1 | 2 + |p 2 | 2
where C1 (η), c 0 and c 1 are positive constants and

C 1 η,γ (p 1 ) = {z 1 ∈ R d ; (1 -η)|p 1 ||z 1 | ≤ |p 1 • z 1 | ≤ 1/γ}.
As far as the scaling assumptions are concerned it is sufficient to see that the nonlinearity is 1-homogeneous. Indeed, F is 1-homogeneous and (N) holds:

Remark 4.3. In general, linear integro-differential equations of the form

u t -a(x)I x 1 [u] -c(x) ∂ 2 u ∂x 2 2 = 0 in R N × (0, T ) (4.18) or u t -a(x)I x 1 [u] -c(x)I x 2 [u] = 0 in R N × (0, T ) (4.
c(x) -I N -d + γp 2 ⊗ p 2 + a(x) -C2 µ + cγ Cη,γ (p 1 ) |p 1 • z 1 | 2 µ x 1 (dz 1 ) ≥ ≥ -c 0 (a(x) + c(x)) + c 1 γ β-1 a(x)|p 1 | 2 + c(x)|p 2 | 2 respectively a(x) -C1 µ + cγ Cη,γ (p 1 ) |p 1 • z 1 | 2 µ x 1 (dz 1 ) + c(x) -C2 µ + cγ Cη,γ (p 2 ) |p 2 • z 2 | 2 µ x 2 (dz 2 ) ≥ ≥ -c 0 (a(x) + c(x)) + c 1 γ β-1 a(x)|p 1 | 2 + c(x)|p 2 | 2 .
where C η,γ (p i ) = {z i ; |p i • z i | ≤ 1/γ}, for i = 1, 2.

Strong Comparison Principle

Let Ω ⊂ R N be a bounded, connected domain. In this section, we use Strong Maximum Principle to prove a Strong Comparison Result of viscosity sub and supersolution for integrodifferential equations of the form (1.1)

u t + F (x, t, Du, D 2 u, J [x, t, u]) = 0, in Ω × (0, T ) (5.20)
with the Dirichlet boundary condition

u = ϕ on Ω c × [0, T ] (5.21)
where ϕ is a continuous function.

Let µ be a Lévy measure satisfying (M LI ). Assume that the function j appearing in the definition of J has the following property: there exists C 0 > 0 such that for all x, y ∈ Ω and |z| ≤ δ

|j(x, z)| ≤ C 0 |z| |j(x, z) -j(y, z)| ≤ C 0 |z||x -y|.
We will need some additional assumptions on the equation, that we state in the following. Suppose the nonlinearity F is Lipschitz continuous with respect to the variables p, X and l and for each 0 < R < ∞ there exist a function ω R (r) → 0, as r → 0, c R a positive constant and 0 ≤ λ R < Λ R such that (H) F (y, s, q, Y, l 2 ) -F (x, t, p, X, l

1 ) ≤ ω R (|(x, t) -(y, s)|) + c R |p -q| + M + R (X -Y ) + c R (l 1 -l 2 ), for all x, y ∈ Ω, t, s ∈ [0, T ], X, Y ∈ S N (Ω) satisfying for some ε > 0 X 0 0 -Y ≤ 1 ε I -I -I I + Z 0 0 0 , with Z ∈ S N (Ω).
and |p|, |q| ≤ R and l 1 , l 2 ∈ R, where M - R is Pucci's minimal operator:

M -(X) = λ R λ j >0 λ j + Λ R λ j <0
λ j with λ j being the eigenvalues of X. (5.21). Suppose one of the following conditions holds:

(a) F satisfies (H) with w R and c R independent of R or (b) u(•, t), v(•, t) ∈ Lip(Ω), ∀t ∈ [0, T ) and F satisfies (H). If uv attains a maximum at P 0 = (x 0 , t 0 ) ∈ Ω × (0, T ), then uv is constant in C(P 0 ).

Proof. The proof relies on finding the equation for which w = uv ∈ U SC(R N × [0, T ]) is a viscosity subsolution and applying strong maximum principle results for the latter. However, the conclusion is not immediate as linearizion does not go hand in hand with the viscosity solution theory approach and difficulties imposed by the behavior of the measure near the singularity might appear.

1. Let w = uv and consider φ a smooth test-function such that wφ has a strict global maximum at (x 0 , t 0 ). We penalize the test function around the maximum point, by doubling the variables, i.e. we consider the auxiliary function

Ψ ε,η (x, y, t, s) = u(x, t) -v(y, s) - |x -y| 2 ε 2 - (t -s) 2 η 2 -φ(x, t).
Then there exist a sequence of global maximum points (x ε , y ε , t η , s η ) of function Ψ ε,η with the properties

(x ε , t η ), (y ε , s η ) → (x 0 , t 0 ) as η, ε → 0 |x ε -y ε | 2 ε 2 → ε as ε → 0 (t η -s η ) 2 η 2 → 0 as η → 0 and the test-function ϕ being continuous lim η,ε→0 (u(x ε , t η ) -v(y ε , s η )) = u(x 0 , t 0 ) -v(x 0 , t 0 ). (5.22)
In addition, there exist

X ε , Y ε ∈ S N such that (a η + φ t (x ε , t η ), p ε + Dφ(x ε , t η ), X ε + D 2 φ(x ε , t η )) ∈ D 2,+ u(x ε , t η ) (a η , p ε , Y ε ) ∈ D 2,-v(y ε , s η ) X ε + Dφ(x ε , t η ) 0 0 -Y ε ≤ 4 ε 2
I -I -I I + Dφ(x ε , t η ) 0 0 0 and p ε , a η are defined by

p ε := 2 x ε -y ε ε 2 and a η := 2 t η -s η η 2 . Consider the test function φ 1 ε,η (x, t) = v(y ε , s η ) + |x -y ε | 2 ε 2 + (t -s η ) 2 η 2 + φ(x, t).
Then uφ 1 ε,η has a global maximum at (x ε , t η ). But u is a subsolution of (1.1) and thus for δ > 0 the following holds

φ t (x ε , t η ) + a η + F x ε , t η , Dφ(x ε , t η ) + p ε , ... ..., D 2 φ(x ε , t η ) + X ε , J 1 δ [x ε , t η , φ + |x -y ε | 2 ε 2 ] + J 2 δ [x ε , t η , Dφ(x ε , t η ) + p ε , u] ≤ 0.
Similarly, consider the test function

φ 2 ε,η (y, s) = u(x ε , t η ) - |x ε -y| 2 ε 2 - (t η -s) 2 η 2 -φ(x ε , t η ).
Then vφ 2 ε,η has a global minimum at (y ε , s η ). But v is a supersolution of (1.1) and thus:

a η + F y ε , s η , p ε , Y ε , J 1 δ [y ε , s η , |x ε -y| 2 ε 2 ] + J 2 δ [y ε , s η , p ε , v] ≥ 0.
Subtracting the two inequalities and taking into account (H) we get that for all δ > 0

φ t (x ε , t η ) -ω(|(x ε , t η ) -(y ε , s η )|) -c|Dφ(x ε , t η )| -M -(D 2 φ(x ε , t η ) + X ε -Y ε ) -c(J 1 δ [x ε , t η , φ + |x -y ε | 2 ε 2 ] + J 2 δ [x ε , t η , Dφ(x ε , t η ) + p ε , u]) -c(J 1 δ [y ε , s η , - |x ε -y| 2 ε 2 ] -J 2 δ [y ε , s η , p ε , v]) ≤ 0.
Taking into account the matrix inequality and the sublinearity of Pucci's operator, we deduce that

M -(D 2 φ(x ε , t η ) + X ε -Y ε ) ≤ M -(D 2 φ(x ε , t η )).
On the other hand, we seek to estimate the integral terms. For this purpose denote

l u (z) := u(x ε + j(x ε , z), t η ) -u(x ε , t η ) -(p ε + Dφ(x ε , t η )) • j(x ε , z) l v (z) := v(y ε + j(y ε , z), s η ) -v(y ε , s η ) -p ε • j(y ε , z) l φ (z) := φ(x ε + j(x ε , z), t η ) -φ(x ε , t η ) -Dφ(x ε , t η ) • j(x ε , z).
Fix δ ′ ≫ δ and split the integrals into:

J 2 δ [x ε , t η , p ε + Dφ(x ε , t η ), u] = J 2 δ ′ [x ε , t η , p ε + Dφ(x ε , t η ), u] + δ<|z|<δ ′ l u (z)µ(dz) J 2 δ [y ε , s η , p ε , v] = J 2 δ ′ [y ε , s η , p ε , v] + δ<|z|<δ ′ l v (z)µ(dz). Since (x ε , y ε , t η , s η ) is a maximum of Ψ ε,η we have u(x ε + j(x ε , z), t η ) -v(y ε + j(y ε , z), s η ) - |x ε + j(x ε , z) -y ε -j(y ε , z)| 2 ε 2 - -φ(x ε + j(x ε , z), t η ) ≤ u(x ε , t η ) -v(y ε , s η ) - |x ε -y ε | 2 ε 2 -φ(x ε , t η )
from where we get

l u (z) -l v (z) ≤ l φ (z) + |j(x ε , z) -j(y ε , z)| 2 ε 2 ≤ l φ (z) + C 2 0 |x ε -y ε | 2 ε 2 |z| 2 .
This leads us to

δ<|z|<δ ′ l u (z)µ(dz) - δ<|z|<δ ′ l v (z)µ(dz) ≤ δ<|z|<δ ′ l φ (z)µ(dz) + O( |x ε -y ε | 2 ε 2 ).
Letting first δ go to zero, we get

lim sup δ→0 J 2 δ [x ε , t η , p ε + Dφ(x ε , t η ), u] -J 2 δ [y ε , s η , p ε , v] ≤ ≤ J 2 δ ′ [x ε , t η , p ε + Dφ(x ε , t η ), u] -J 2 δ ′ [y ε , s η , p ε , v] + J 1 δ ′ [x ε , t η , φ] + O( |x ε -y ε | 2 ε 2 )
whereas close to the origin

J 1 δ [x ε , t η , |x -y ε | 2 ε 2 ] -J 1 δ [y ε , s η , - |x ε -y| 2 ε 2 ] = 2 ε 2 |z|≤δ |j(x ε , z)| 2 µ(dz) → 0 J 1 δ [x ε , t η , φ] ≤ |z|≤δ sup |θ|<1 D 2 φ(x ε + θj(x ε , z), t η )j(x ε , z) • j(x ε , z) µ(dz) → 0.
Furthermore, employing (5.22) and the regularity of the test function φ, as well as the upper semicontinuity of uv and the continuity of the jump function j, we have lim sup η,ε→0

J 2 δ ′ [x ε , t η , p ε + Dφ(x ε , t η ), u] -J 2 δ ′ [y ε , s η , p ε , v] ≤ |z|≥δ ′ lim sup η,ε→0 (u(x ε + j(x ε , z), t η ) -v(y ǫ + j(y ε , z), s η )) -(u(x ε , t η ) -v(y ε , s η )) -(Dφ(x ε , t η ) • j(x ε , z) + p ε • (j(x ε , z) -j(y ε , z)))1 B (z) µ(dz) ≤ |z|≥δ ′ lim sup η,ε→0
(u(x ε + j(x ε , z), t η )v(y ε + j(y ε , z), s η ))

lim η,ε→0

(u(x ε , t η )v(y ε , s η ))lim η,ε→0

Dφ(x ε , t η ) • j(x ε , z)1 B (z) µ(dz)

≤ |z|≥δ ′
(u(x 0 + j(x 0 , z), t η )v(x 0 + j(x 0 , z), t 0 )) -(u(x 0 , t 0 )v(x 0 , t 0 ))

-Dφ(x 0 , t 0 ) • j(x 0 , z) µ(dz) = J 2 δ ′ [x 0 , t 0 , Dϕ(x 0 , t 0 ), w]. Passing to the limits in the viscosity inequality we get, for all δ ′ > 0 that φ t (x 0 , t 0 ) -c|Dφ(x 0 , t 0 )| -M -(D 2 φ(x 0 , t 0 ))c(J 1 δ ′ [x 0 , t 0 , φ] + J 2 δ ′ [x 0 , t 0 , Dϕ(x 0 , t 0 ), w]) ≤ 0. Hence, w is a viscosity subsolution of the equation Therefore, SMaxP applies and we conclude that if uv attains a maximum inside the domain Ω × (0, T ) at some point (x 0 , t 0 ) then uv is constant in Ω × [0, t 0 ].

Appendix

We present in the following some useful properties of the nonlocal terms. We straighten the convex inequality to the following: Lemma 6.2. Let v be a smooth function of the form v(x, t) = e ϕ(x,t) . Then for any δ ≥ 0 there exists a constant c = 1 2 e -δ such that v satisfies I[x, t, v] ≥ e ϕ(x,t) • [I[x, t, ϕ] + c D (ϕ(x + z, t)ϕ(x, t)) 2 µ x (dz)], ∀(x, t) ∈ R N × [0, T ],

where the integral is taken over the domain D = {ϕ(x + z)ϕ(x) ≥ -δ}.

Proof. The proof is direct application of the exponential inequality e y -1 ≥ y + cy 2 , ∀y ≥ -δ.

We now insert the previous inequality with y = ϕ(x + z, t)ϕ(x, t) in the nonlocal term and obtain where the integral is taken over the domain D = {ϕ(x + j(x, z))ϕ(x) ≥ -δ}.

Aknowledgments. The author would like to express his warmest thanks to Professor Guy Barles, whose expert guidance on the topics of this work has proved invaluable and whose careful suggestions helped improving the presentation. Many thanks are addressed to Emmanuel Chasseigne and Cyril Imbert for useful discussions and for their interest in this work.

) 4 . 3 .Example 4 . 4 .

 4344 with b a continuous function and µ as in Example 4.3. Strong Maximum Principle holds provided that b(•)(1m) ≥ 0. Strong Maximum Principle coming from local diffusion terms. Theorem 2.4 applies to integro-differential equations uniformly elliptic with respect to the diffusion term and linear in the nonlocal operator. Quasilinear parabolic integro-differential equations of the form

Example 4 . 5 .

 45 Consider the following equation where local and nonlocal diffusions are mixed up

  [START_REF] Espen | Continuous dependence estimates for viscosity solutions of integro-PDEs[END_REF] satisfy Strong Maximum Principle if the corresponding Lévy measure(s) verify (M ) and (M c ), with β > 1 and if a, c ≥ ζ > 0 in R N .

Theorem 5 . 1 (

 51 Strong Comparison Principle). Assume the Lévy measure µ satisfies assumption (M c ) with β > 1. Let u ∈ U SC(R N × [0, T ]) be a viscosity subsolution and v ∈ LSC(R N × [0, T ]) a viscosity supersolution of (1.1), with the Dirichlet boundary condition

  w t -c|Dw| -M -(D 2 w) -cJ [x, t, w] = 0 in Ω × (0, T ).In case the sub and super-solutions are Lipschitz continuous we take R * = max{||Du|| ∞ , ||Dv|| ∞ } and denote by c = c R * and w = w R * .2. The equation satisfies the strong maximum principle since the nonlinearity is positively 1-homogeneous and the nondegeneracy conditions (N ) and (N ′ ) are satisfied.(N ) -c|p| -M -(Iγp ⊗ p)c Cµ + cγ Cη,γ |p • j(x, z)| 2 µ(dz) ≥ -c|p|λ tr(Iγp ⊗ p) -(Λλ) λ j <0 λ j (Iγp ⊗ p)c Cµ + C(η)γ β-1 |p| 2 ≥-c|p| -λN + λγ|p| 2c Cµ + C(η)γ β-1 |p| 2 > 0, for γ large.

Remark 5 . 1 .Example 5 . 1 .

 5151 If Pucci's operator M -appearing in hypothesis (H) is nondegenerate, i.e. λ R > 0, then one can consider any Lévy measure µ, not necessarily satisfying (M c ). The linear PIDE u t -∆u -I[u] = f (x) in Ω satisfies Strong Comparison, as (H) holds for the corresponding nonlinearity. Example 5.2. On the other hand, for the equation u t + |Du| m -I[u] = f (x) in Ω condition (H) holds if the sub and super-solutions are Lipschitz continuous in space.Indeed, for u subsolution and v supersolution(uv) t + |Du| m -|Dv| m -I[uv] ≥ (uv) t + m|Dv| m-2 (Du -Dv) -I[uv] ≥ (uv) t -cD(uv) -I[uv].

  For a given function v defined on R N × [0, T ], consider the integral operatorsI[x, t, v] = D (v(x + z, t)v(x, t) -Dv(x, t) • z1 B (z))µ x (dz), and J [x, t, v] = D (v(x + j(x, z), t)v(x, t) -Dv(x, t) • j(x, z)1 B (z))µ(dz),where the integral is taken over a domain D ⊆ R N . Lemma 6.1. Any smooth function v(x, t) = e ϕ(x,t) , satisfies the integral inequalityI[x, t, v] ≥ v • I[x, t, ϕ], ∀(x, t) ∈ R N × [0, T ]Proof. The inequality is immediate from e y -1 ≥ y, ∀y ∈ R. More preciselyI[x, t, v] = D e ϕ(x+z,t)e ϕ(x,t)e ϕ(x,t) Dϕ(x, t) • z1 B (z) µ x (dz) = e ϕ(x,t) D e ϕ(x+z,t)-ϕ(x,t) -1 -Dϕ(x, t) • z1 B (z) µ x (dz)≥ e ϕ(x,t) D ϕ(x + z, t)ϕ(x, t) -Dϕ(x, t) • z1 B (z) µ x (dz).

ILemma 6 . 3 .Lemma 6 . 4 .

 6364 [x, t, e ϕ ] = e ϕ(x,t) D e ϕ(x+z,t)-ϕ(x,t) -1 -Dϕ(x, t)• z1 B (z) µ x (dz) ≥ e ϕ(x,t) [ D ϕ(x + z, t)ϕ(x, t) -Dϕ(x, t) • z1 B (z) µ x (dz) +c D (ϕ(x + z, t)ϕ(x, t) 2 µ x (dz)].Similar results hold for Lévy-Itô operators. The function v(x, t) = e ϕ(x,t) , satisfies the integral inequalityJ [x, t, v] ≥ v • J [x, t, ϕ], ∀(x, t) ∈ R N × [0, T ]. For any δ ≥ 0 there exists a constant c = 1 2 e -δ such that v = e ϕ satisfies J [x, t, v] ≥ e ϕ(x,t) • [J [x, t, ϕ] + c D (ϕ(x + j(x, z), t)ϕ(x, t)) 2 µ(dz)], ∀(x, t) ∈ R N × [0, T ],

where

(v(x + j(x, z), t)v(x, t) -Dv(x, t) • j(x, z))µ(dz)

Then the nonlocal operator satisfies for all (x, t)

from where we get the global estimation

Vertical propagation of maxima holds under the same conditions. Strong Maximum Principle can thus be formulated for Lévy-Itô operators. Theorem 3.2 (Strong Maximum Principle -Lévy Itô). Assume the measure µ satisfies assumption (M LI ). Let u ∈ U SC(R N × [0, T ]) be a viscosity subsolution of (1.1) that attains a global maximum at P 0 = (x 0 , t 0 ) ∈ Q T . If F satisfies (E), (S) -(S ′ ), and (N LI ) -(N ′ ), then u is constant in S(P 0 ).

Assume the family of measures {µ x } x∈R N satisfies assumption (M LI ) and F satisfies (E 0 ), (S ′ ) and (N ′ ). Then u is constant in n≥0 A n × [0, t 0 ] with {A n } n given by (2.8).


Jean-Daniel Boissonnat

David Cohen-Steiner

Gert Vegter

Isotopic Implicit Surface Meshing

This paper addresses the problem of piecewise linear approximation of implicit surfaces. We first give a criterion ensuring that the zero-set of a smooth function and the one of a piecewise linear approximation of it are isotopic. Then, we deduce from this criterion an implicit surface meshing algorithm certifying that the output mesh is isotopic to the actual implicit surface. This is the first algorithm achieving this goal in a provably correct way.

However, most graphical algorithms, and especially those implemented in hardware, cannot process implicit surfaces directly, and require that a piecewise linear approximation of the considered surface has been computed beforehand. As a consequence, polygonization of implicit surfaces has been widely studied in the literature.

, are grid based, or, more generally, based on a tesselation of the ambient 3D space. They consist of two steps : first build a tesselation of space, and then analyze the intersection of the considered surface with each cell of the tesselation to construct the approximation.

, who uses an adaptive enumeration method. His algorithm combines interval arithmetic with a quadtree tesselation of the domain of interest. It seems hard to generalize this method to implicit surfaces in three-space. Moreover, this algorithm seems to have high complexity due to the large number of

Introduction

Implicit equations are a popular way to encode geometric objects; See, e.g., [START_REF]Introduction to Implicit Surfaces[END_REF] and [START_REF] Velho | Implicit Objects in Computer Graphics[END_REF]. Typical examples are CSG models, where objects are defined as results of boolean operations on simple geometric primitives. Given an implicit surface, associated geometric objects of interest, such as contour generators, are also defined by implicit equations. Another advantage of implicit representations is that they allow for efficient blending of surfaces, with obvious applications in CAD or metamorphosis. Finally, this type of representation is also relevant to other scientific fields, such as level set methods or density estimation [START_REF] Dobkin | Contour Tracing by Piecewise Linear Approximations[END_REF]. calls to the interval version of Newton's method.

When the conference version of the present paper was published (Proceedings of STOC'04), there was only one paper devoted to the problem of homeomorphic polygonization of surfaces [START_REF] Stander | Guaranteeing the Topology of an Implicit Surface Polygonizer for Interactive Modeling[END_REF]. Since then there has been several papers [START_REF] Plantinga | Isotopic Approximation of Implicit Curves and Surfaces[END_REF][START_REF] Cheng | Sampling and Meshing a Surface with guaranteed Topology and Geometry[END_REF][START_REF] Boissonnat | Provably Good Sampling and Meshing of Surfaces[END_REF] that solve the same problem as ours, or a related one. The main theoretical tool used in [START_REF] Stander | Guaranteeing the Topology of an Implicit Surface Polygonizer for Interactive Modeling[END_REF] is Morse theory. The authors first find a level set of the considered function that can be easily polygonized. This initial polygonization is then progressively transformed into the desired one, by computing intermediate level sets. This requires in particular to perform topological changes when critical points are encountered. This algorithm has an intuitive justification and seems to work on simple cases. Unfortunately, the authors do not give any proof of its correctness, and it is not clear to us whether it can deal with complex shapes in a robust way. In particular, the method does not guarantee that the mesh produced are self-intersection free.

In this paper, we give the first certified algorithm for the more difficult problem of isotopic implicit surface polygonization. This means that our output can be continuously deformed into the actual implicit surface without introducing self-intersections [START_REF] Hirsch | Differential Topology[END_REF]. For instance, if the original implicit surface is knotted, then our output is guaranteed to be knotted in the same way, which would not be guaranteed by an algorithm ensuring only homeomorphic polygonization. Moreover, the whole algorithm can be implemented in the setting of interval analysis. We only assume that the considered isosurface is smooth, that is, does not contain any critical point. By Sard's theorem [START_REF] Sard | The measure of the critical values of differentiable maps[END_REF], this is a generic condition. Our polygonization is the zero-set of the linear interpolation of the implicit function on a mesh of R 3 . We first exhibit a set of conditions on the mesh used for interpolation that ensure the topological correctness (section 2).

Then, we describe an algorithm for building a mesh satisfying these conditions, thereby leading to a provably correct isotopic polygonization algorithm (section 3).

We note that since the publication of the conference version of the present paper, another method appeared that solves exactly the same problem as ours [START_REF] Plantinga | Isotopic Approximation of Implicit Curves and Surfaces[END_REF]. One difference between the two methods is that [START_REF] Plantinga | Isotopic Approximation of Implicit Curves and Surfaces[END_REF] uses octrees instead of triangulations. A more important difference is in the refinement stopping criterion: in [START_REF] Plantinga | Isotopic Approximation of Implicit Curves and Surfaces[END_REF], cells are subdivided until the intersection of the implicit surface with each cell is sufficiently flat.

By contrast, we stop refinement as soon as a certain global criterion ensuring topological correctness is met. Hence, we may expect that our method is faster than [START_REF] Plantinga | Isotopic Approximation of Implicit Curves and Surfaces[END_REF]. This remains to be proved though, since we did not implement our method.

A condition for isotopic meshing

Let f be a C 2 function from R 3 to R, and M be its zero-set. We assume that M, the surface we want to polygonize, is compact (condition a1). In what follows, T denotes a triangulation of a domain Ω ⊂ R 3 containing M and f the function that coincides with f at the vertices of T and that is linearly interpolated on the simplices of T . A vertex v will be said to be larger (resp. smaller) than a vertex u if f (v) is larger (resp. smaller) than f (u) ; the sign of f at a vertex will be referred to as the sign of that vertex. We set M = f -1 (0).

Topological Background

Collapses. Loosely speaking, a collapse [START_REF] Rourke | Introduction to Piecewise-Linear Topology[END_REF] is an operation which consists of removing cells from a simplicial complex whithout changing its connectivity. More precisely :

Definition 1 If L is a simplicial complex and K a subcomplex of L, one says that there is an elementary collapse from L to K if there is a p-simplex s of L and a (p -1)-face t of s such that :

-s is not a face of any simplex of L.

-t is not a face of any simplex of L other than s.

-L is the union of K, s, and all the faces of s.

-∂ s \ K is the relative interior of t.

PSfrag replacements

s t K L Figure 1: Elementary collapse.
Definition 2 If L is a simplicial complex and K a subset of L, one says that L collapses to K if there is a subdivision L of L such that a subdivision of K can be obtained from L by a sequence of elementary collapses.

Definition 2 is illustrated in figure 2. In figure 2, the complexes in the middle and on the right do not collapse to the bold curve because they would need to be "torn" in order to do so.

PSfrag replacements

v - + Figure 2:
The grey complex L on the left collapses to the bold curve K (dashed edges represent the subdivision L ). This is not true for the two other complexes.

Smooth Morse theory. The topology of implicit surfaces is usually investigated through Morse theory [START_REF] Milnor | Morse theory[END_REF]. Given a real function f defined on a manifold, Morse theory studies the topological changes in the sets f -1 (] -∞, a]) (lower level-sets) when a varies. In our case, as f is defined on R 3 , this amounts to studying how the topology of the part of the graph of f lying below a horizontal hyperplane changes as this hyperplane sweeps R 4 . Classical Morse theory assumes that f is of class C 2 . In this case, as is well known, these topological changes are related to the critical points of f , that is, the points where the gradient ∇ f of f vanishes. More precisely, the only topological changes occur when f -1 (a) passes through a critical point p. The value a is then called a critical value. Generically, in the 2-dimensional case, the topology of f -1 (] -∞, a]) can change in three possible ways, according to the type of the critical point p (see figure 3). In figure 3, the sets f -1 (] -∞, a]) are displayed as light grey regions. The leftmost column depicts the situation where p is a local maximum, that is, when the Hessian of

PSfrag replacements p

p p p p p + a = f (p) -ε a = f (p) + ε
f at p is positive. In this case, f -1 (] -∞, a + ε]) is obtained from f -1 (] -∞, a -ε])
by gluing a topological disk along its boundary. In the case of a saddle point (i.e. the Hessian has critical values of both signs), passing a critical value amounts to gluing a thickened topological line segment (in grey) along its "thickened" boundary (in bold).

Finally, passing through a local minimum (negative Hessian) just amounts to adding a disk disconnected from f -1 (] -∞, a -ε]). If p does not fall in any of these categories, that is, if the Hessian at p is degenerate, then classical Morse theory cannot be applied.

C 2 functions the critical points of which all have non-degenerate Hessian are called Morse functions. From now on, we will assume that f is a Morse function (condition a2). Also, we require that 0 is not a critical value of f (condition a3), which implies that M is a manifold.

The number n of negative eigenvalues of the Hessian at p is classically called the index of p. However, for consistency reasons that will appear later, we call the index of p the integer (-1) n . The index of f on a region V is the sum of the indices of all critical points of f lying in V . The index satisfies the following important theorem : Theorem 1 (Poincaré-Hopf index theorem) The index of f on one of its lower levelsets is the Euler characteristic of that lower level-set. PL Morse theory. Morse theory has been extended to a broad class of non-smooth functions by Goresky and McPherson [12]. We now outline the special case of PL functions, that is, we consider the case of f . We assume from now on that no two neighboring vertices map to the same value under f , and that no vertex of T maps to 0 under f (conditions b1 and b2), which guarantees that M is a manifold. We refer to these assumptions as genericity assumptions. Let us first recall some well-known definitions [START_REF] Edelsbrunner | Hierarchical Morse complexes for piecewise linear 2-manifolds[END_REF][START_REF] Goresky | Stratified Morse Theory[END_REF] : Definition 1 The star of a vertex is the union of all simplices 1 containing this vertex.

The link of a vertex is the boundary of its star.

Definition 2

The lower star St -(v) of f at a vertex v is the union of all simplices 1 By simplex we mean a closed cell of T of any dimension.

-1 (] -∞, f (v) -ε]) in grey, and sets f -1 ([ f (v) -ε, f (v) + ε]) in light grey.
Figure 4 shows that -for small ε-the topological changes between lower level-

sets f -1 (] -∞, f (v) -ε]) and f -1 (] -∞, f (v) + ε]) are determined by the topology of Lk -(v).
In particular, in 2D, topological changes occur whenever Lk -(v) is not connected or equals the link of v (right and middle cases in figure 4). This is what motivates the next definition in the higher dimensional case :

Definition 3 A critical point of f is a vertex whose lower link is not collapsible 2 . A
vertex that is not a critical point of f will be called regular.

With this definition, topological changes in lower level-sets occur exactly at critical points, which is consistent with smooth Morse theory. The index of a vertex v is defined to be 1 minus the Euler characteristic of Lk -(v) [START_REF] Th | Critical points and curvature for embedded polyhedra[END_REF]. In particular, regular points all have index 0. The converse is not true however in dimension at least 3. Also, checking if a vertex is regular is easy for PL functions defined on three-dimensional meshes : it is sufficient to check that the lower link and the upper link are both non-empty and connected 3 . Define the index of f on a region V to be the sum of the indices of all critical points of f lying in V . Again, this definition is consistent with the smooth case, since the PL index can be shown to also satisfy the Poincaré-Hopf index theorem [START_REF] Th | Critical points and curvature for embedded polyhedra[END_REF].

The following lemma will be used later :

Lemma 2 If the gradients of f on tetrahedra incident to a vertex v all have a positive inner product with some vector, then v is regular.

PROOF. By Proposition 1.2 page 450 in [1], f -1 (] -∞, f (v) + ε]) retracts by deforma- tion on f -1 (] -∞, f (v) -ε]) for sufficiently small ε. Hence Lk -(v)
has the homology groups of a point, implying that it is collapsible since it is a subcomplex of the 2sphere.

Main result

We assume throughout the paper that f and T satisfy conditions a1, a2, a3, b1, b2.

That is, M is compact, f is a Morse function, 0 is not a critical value of f , no vertex of T map to 0 by f , and no two neighboring vertices of T map to the same value by f .

Additionally, we assume that the following condition holds: 0. f does not vanish on any tetrahedron of T containing a critical point of f .

Theorem 3 Let W be a subcomplex of T satisfying the following conditions :

1. f does not vanish on ∂W .

W contains no critical point of f .

2'. W contains no critical point of f .

3.

W collapses to M.

f and f have the same index on each bounded component of Ω \W.

Then M and M are isotopic in W . Moreover, the Hausdorff distance between M and M is smaller than the "width" of W , that is, the maximum over the components V of W of the Hausdorff distance between the subset of ∂V where f is positive and the one where f is negative.

Here, isotopic in W means that M can be continuously deformed into M while remaining a manifold embedded in W , so that M could not be a knotted torus if M is an unknotted one, for instance. We first prove that under the conditions of the theorem, M and M are homeomorphic. Under the assumptions of the theorem, the fact that they actually are isotopic will be a direct consequence of a result obtained in [START_REF] Chazal | A condition for isotopic approximation[END_REF]. Before

Proof of the theorem

Lemma 4 Let S and T be two subsets of a topological space X that meet (ie S ∩T = / 0).

Assume the boundary of S, as well as T and X \ T , are connected.

If X \ S and X \ T meet but their boundaries do not, then S is contained in the interior of T or the other way around.

PROOF. The boundary of S is the disjoint union of ∂ S ∩ int(T ) and ∂ S ∩ int(X \ T )

since ∂ S ∩ ∂ T is empty. So we have a partition of ∂ S in two relatively open sets. As it is connected, one has to be empty.

If ∂ S ∩ int(T ) is empty then ∂ S ⊂ int(X \ T ) that is, T ∩ ∂ S is empty. As a consequence,
T is included in int(S) or in int(X \ S) by connectedness. Since S and T meet, we have that T ⊂ int(S). M ∩V is a connected smooth compact manifold without boundary.

Now if ∂ S ∩ int(X \ T ) is empty then X \ T is contained in int(S)
PROOF. Condition 3 implies easily that V collapses to M ∩ V . Therefore V contains a simplex having positive and negative vertices. As a consequence, f vanishes on V . Since f does not vanish on ∂W (condition 1), M intersects V . Also, M does not meet the boundary of V (condition 1), so M ∩V is a smooth compact manifold without boundary.

Because V , which is connected, collapses to M ∩ V , M ∩ V is a connected closed surface. Therefore, the complement of M ∩ V has exactly two components, one of which is bounded. Because V collapses to M ∩V , R 3 \V also has exactly one bounded component which we denote by A and one unbounded component we denote by B (see figure 8). The complement of A, which is B ∪ V , is connected, because B and V are connected. For the same reason, A ∪ V is also connected. Moreover, the complement of A ∪V , being equal to B, is also connected. In summary, A is connected as well as its complement, and the same is true for A ∪V .

Call now M i , i = 1..n the connected components of M ∩V (see figure 8). For each i,

let N i be the bounded component of R 3 \ M i . M i = ∂ N i does not meet ∂ (A ∪V ) ⊂ ∂W
(1), and A ∪V is connected as is its complement. So N i is included in A ∪V thanks to lemma 4. Now N i contains at least one critical point of f . But as

N i ⊂ A ∪ V , such a point has to lie in A, by 2. So N i meets A, but since ∂ N i = M i does not meet ∂ A ⊂ W , N i
contains A by lemma 4 again. Suppose M ∩V is not connected. Then N 1 and N 2 both contain A so they intersect. Because M is smooth, their boundaries do not intersect. So one has w.l.o.g. The proof of the bound on the Hausdorff distance between M and M is not difficult.

N 2 ⊂ N 1 . Now f vanishes on ∂ (N 1 \ N 2 ) = ∂ N 1 ∪ ∂ N 2 ,
Pick any point p in M and let V be the component of W containing it. Assume w.l.o.g. that f (p) > 0 and let p be the closest point of p on the component of ∂V where f is negative. By the intermediate value theorem, the line segment pp meets M at a point q. The distance between p and q is smaller than the distance between p and p which is smaller than the Hausdorff distance between the two components of ∂V . This shows one part of the bound. The other part can be proved in a similar way.

Now that we know that M and M are homeomorphic, the fact that they are isotopic is a consequence of proposition 7, which is proved in [START_REF] Chazal | A condition for isotopic approximation[END_REF].

Proposition 7 Let M be an orientable compact surface without boundary and let M be a surface such that

• M is homeomorphic to M,
• M separates the sides of a topological thickening4 W of M.

Then M is isotopic to M in W .

Indeed, considering a regular neighborhood of W [START_REF] Rourke | Introduction to Piecewise-Linear Topology[END_REF] yields the desired topological thickening W , as can be seen from the uniqueness theorem for regular neighborhoods from piecewise-linear topology [START_REF] Rourke | Introduction to Piecewise-Linear Topology[END_REF].

Algorithm

In the algorithm, we take as W a set that is related to the notion of watershed from topography. This set satisfies properties 2'. and 3. by construction. In section 3.1, we give its definition, basic properties, and construction algorithms. Section 3.2 describes the meshing algorithm itself, which ensures that W fulfills also conditions 0., 1., 2., and 4., and proves its correctness.

PL watersheds

We first assume that the mesh T conforms to M, i.e. M is contained in a union of triangles of T . We will see later how to remove this assumption, which is in contradiction with the genericity assumptions. Define W + as the result of the following procedure :

Positive Watershed Algorithm set W + = M.
mark all vertices of M.

while there is a positive regular unmarked vertex v of T such that the vertices of Lk -(v) are marked

do set W + = W + ∪ St -(v). mark v.
end while return W + W -is defined as the result of the same algorithm applied tof . We set W = W + ∪W -. Note that W contains no critical point of f . Also, positive marked vertices are exactly the vertices of W + .

PSfrag replacements PROOF. It is sufficient to show the result for W + . Let W + i be the state of W + after i steps of the algorithm, and let v i be the i-th marked vertex. As W + 0 = M, the only thing we have to show is that W + i+1 collapses to

M W + v 1 v 2
W + i for all i. Let us first show that Lk -(v i ) is included in W + i . If it is not the case, let u be the largest vertex of some simplex s of Lk -(v i ) that is not in W + i . Simplex s is in St -(u) which is therefore not included in W + i . This is a contradiction since v i is marked. Therefore Lk -(v i ) ⊂ W + i . Now since v i is regular, Lk -(v i ) is collapsible.
Consider a sequence of elementary collapses allowing to collapse Lk -(v i ) to p and let s j ⊂ Lk -(v i ), j = 1, . . . , n be the sequence of simplices defining these elementary collapses. The simplices conv(s j ∪v i )), j = 1, . . . , n and the edge pv i define a valid sequence of elementary collapses allowing to collapse

W + i+1 = W + i ∪ St -(v i ) to W + i ,
which concludes the proof. One may prefer a more intrinsic definition of W + . In the same spirit as in [START_REF] Edelsbrunner | Surface reconstruction by wrapping finite point sets in space[END_REF], one can define a partial order on the vertices of T by the closure of the acyclic relation ≺ defined by u ≺ v if u ∈ Lk -(v) or u = v. We will denote this order ≺ again and say that v flows into u whenever u ≺ v. The next lemma shows that the vertices of W + do not depend on the order in which the vertices are considered in the construction. Note that W is the union of simplices with all their vertices in W . As a result, we get an intrinsic definition of W , and not only of its vertices. From an algorithmic point of view, it may be efficient to examine the vertices in increasing order in the construction of W + . One can for instance maintain the ordered list of vertices neighboring W , always consider the first element of this list for marking, and discard it if it cannot be marked. Indeed, with this strategy, a vertex that cannot be marked at some point will never be marked.

Another consequence of lemma 9, which will be useful later, goes as follows. Non conforming case. We now drop the assumption that T conforms to M and assume genericity again. From T and M one can build a mesh S that is finer than T , conforms to M, and has all its extra vertices on M. Indeed, it suffices to triangulate the overlay of M and T without adding extra vertices except those of M ∩ T . This can be done as the cells of the overlay are convex. The construction of W described above can then be applied to S. A positive vertex of T has its lower link in S containing only vertices of M if and only if its lower link in T contains only negative vertices. Thus, in order to find the positive vertices of W ∩ T , one can apply the positive watershed algorithm described above to T , if at the initialization step one marks all negative vertices having a positive neighbor instead of those of M. Still, note that if a negative critical point has a positive neighbor, then this neighbor will not be marked by this modified algorithm, whereas it could have been marked by the standard algorithm applied to S. However, if we assume that vertices having a neighbor of opposite sign are regular (condition c), then this does not happen and the result W of the modified algorithm is equal to W . The negative vertices of W ∩ T are determined similarly. In our meshing algorithm, we will not build the mesh S, but rather make sure condition c holds, and apply the modified algorithm.

Updating W . The intrinsic definition of W -or W -given above yields an efficient way of updating W when T undergoes local transformations. It is sufficient to describe the algorithm for updating the vertices of W + . Let T 1 be a mesh obtained from T by removing some set of tetrahedra E and remeshing the void left by E. Call

A the set of positive critical points of the linear interpolation of f on T 1 that lie in E.

Then the vertex set of the positive watershed W + 1 associated with T 1 can be computed from the vertex set of W + by performing the following two operations. To begin with, the set of vertices of T 1 that flow into A must be removed from W + (lemma 9), which amounts to a graph traversal. The remaining vertices of T 1 all belong to W + 1 . Then, mark these vertices and apply the positive watershed algorithm loop to get the other

vertices of W + 1 .
Remark. The watershed we compute is in general strictly included in the 'true watershed'. The 'true watershed' seems hard to compute, though, and can intersect a triangle in a very complicated way. There might be interesting intermediate definitions between ours and the true one, for instance based on the PL analog of the Morse complex introduced in [10].

Main algorithm

Theorem 3 enables us to build a mesh isotopic to M using two simple predicates, vanish and vanish'. The predicate vanish (resp. vanish') takes a triangle or a box and return true if f (resp. ∇ f ) vanishes on that triangle or that box. We actually do not even need predicates, but rather filters. More precisely, vanish (or vanish') may return true even if f does not vanish on the considered element, but not the other way around. Still, we require that vanish returns the correct answer if the input triangle or box is sufficiently small. Such filters can be designed using interval analysis.

Our algorithm also requires to build a refinable triangulation of space such that f (resp. ∇ f ) converges to f (resp. ∇ f ) when the size of the elements tends to 0. As noticed by Shewchuk [START_REF] Shewchuk | What Is a Good Linear Finite Element? Interpolation[END_REF], this is guaranteed provided all tetrahedra have dihedral and planar angles bounded away from π. In [START_REF] Bern | Provably Good Mesh Generation[END_REF], Bern, Eppstein and Gilbert described an octree-based algorithm yielding meshes the angles of which are bounded away from 0.

In our case, which is much easier, the desired triangulation can simply be obtained by adding a vertex at the center of each square and each cube of the octree, triangulating the squares radially from their center, and doing the same with the cubes. Indeed, resulting planar and dihedral angles are all bounded away from π. One can expect that this scheme does not produce too many elements upon refinement, because the size of elements is allowed to change rapidly as we do not require that these have a bounded aspect ratio (see figure 10). The main algorithm uses an octree O, the associated tri- By the result of [START_REF] Agrachev | On Morse Theory for Piecewise Smooth Functions[END_REF] which we mentioned when we stated lemma 2, this implies that the index of p is 0. We thus proved the announced claim.

Suppose that some box b of Critical2 of size smaller than s 1 is split. Let v be a critical point of f included in b. All the boxes containing v are in Critical2 and their

Conclusion

We have given an algorithm that approximates regular level sets of a given function with piecewise linear manifolds having the same topology. Though no implementation has been carried out, we believe that it should be rather efficient due to the simplicity of the involved predicates and the relative coarseness of the required space decomposition.

Figure 3 :

 3 Figure 3: Smooth Morse theory in 2D.

Figure 4 :

 4 Figure 4: Morse theory for PL functions in 2D. Plus and minus signs indicate whether neighbors of v are larger or smaller than v. Lower links are displayed in bold, sets f-1 (] -∞, f (v) -ε]) in grey, and sets f -1 ([ f (v) -ε, f (v) + ε]) in light grey.

Figure 5 :

 5 Figure 5: Condition 0. is necessary.

Figure 5 Figure 6 :

 56 Figure 5 shows that condition 0. cannot be removed even in the 2D case. By allowing for critical points of f inside a triangle of T with positive vertices, one can build an example where M has an extra component with respect to M without violating

Figure 7 Figure 7 :

 77 Figure7shows a 3D example where M is a torus whereas M is a sphere. This is because f has an extra negative minimum inside f -1 (] -∞, 0]) whereas f has an index 1 saddle point outside the bounding box Ω. Depending on whether this extra minimum lies in W or not (see the circle arc with arrows at both ends in figure7), one obtains counterexamples to the theorem if assumptions 2'. or 4. are dropped. One can build similar examples showing that condition 2. is also needed.We now return to the proof of theorem 3.

Lemma 5

 5 or in int(X \ S) by connectedness again. Similarly as above it has to be contained in int(X \ S), which implies that S ⊂ T . Thus int(S) ⊂ int(T ) so ∂ S ⊃ S \ int(T ) = S ∩ ∂ T . If S would meet ∂ T , then ∂ S and ∂ T would meet, which is impossible. Hence, S is included in the interior of T . Let V be a connected component of W .

and therefore has an extremum in N 1 \Figure 8 :

 18 Figure 8: Proof of lemma 5.

Figure 9 :

 9 Figure 9: Construction of W + : lower stars of regular vertices (such as v 1 ) are added one by one. Lower stars of critical vertices (v 2 ) are discarded.

Lemma 9

 9 The vertices of W + are exactly the positive vertices that do not flow into any positive critical point of f . PROOF. The vertices of W + have this property by construction. Let p be a positive vertex not belonging to W + and assume p does not flow into any positive critical point. In particular, p is regular by reflexivity. Hence, as p / ∈ W + , the lower link of p, which is not empty, has to contain an unmarked vertex. It cannot contain a critical point because as T conforms to M, vertices in Lk -(p) are all non-negative, and so p would flow into a positive critical point. There is thus an unmarked vertex in Lk -(p). If we can choose an unmarked positive vertex p 1 in Lk -(p), then p 1 does not belong to W + , and flows into a positive critical point. Repeating this process with p replaced by p 1 , we find a strictly decreasing sequence of positive vertices, that thus has to end. Let p k be its last term. The lower link Lk -(p k ) contains no positive unmarked vertices. But as T conforms to M, vertices in Lk -(p k ) are all non-negative. Since vertices of M are marked, we get a contradiction.

  Let c be the minimum of | f (v)|, and hence the minimum of | f (v)| over all critical points v of f . Lemma 10 W contains all vertices the image of which under | f | is smaller than c. PROOF. Let p be such that | f (p)| < c. Without loss of generality, assume that p is positive. Any critical point v into which p flows satisfies f (v) < f (p). So it cannot be positive by definition of c : by lemma 9, p lies in W + .

Figure 10 :

 10 Figure 10: Octree and triangulation used in the algorithm. In this 2D example, only the edges of the triangulation of the box on the right are shown (dashed).

Figure 11 :

 11 Figure 11: Proof of lemma 11.

  angulation T , and the watershed W . We will say that two (closed) boxes of O are neighbors if they intersect. O is initialized to a bounding box Ω of M. Such a bounding box can be found by computing the critical points of the coordinate functions restricted to M, if possible, or by using interval analysis. Besides, we maintain five sets of boxes ordered by decreasing size. Critical1 is a certain set of boxes obtained by interval analysis (see below). This set has the property that the union of its boxes, which we call the critical set, encloses all critical points of f but does not intersect M. Critical2 contains all boxes containing a critical point of f that is not in a box belonging to Critical1. Index contains all boxes neighboring a box b in Critical1 such that f and f have different indices on the connected component of the critical set that contains b. We defer the description of a method that computes the index of f on a box in a certified way to the appendix. Boundary1 contains all boxes containing two neighboring vertices of opposite signs one of which is critical for f (condition c, see paragraph Non conforming case). Boundary2 contains all boxes that are not included in W , and that contain a triangle t of ∂W such that vanish(t) is true. Finally, for our algorithm to work, we need to introduce a slight modification of the watershed W , which we call W . The modification consists of taking as W + vertices -and the same for W || is smaller than g min /2 on the interior of that tetrahedron. If the tetrahedron is included in C, ||∇ f || > g min , which implies that ∇ f and ∇ f make an angle smaller than π/6.The proof of lemma 11 resorts to stratified Morse theory, which is an extension of both the smooth and PL Morse theory to the case of piecewise smooth functions. We refer to[START_REF] Goresky | Stratified Morse Theory[END_REF] for a complete exposition of this subject. PROOF. For p ∈ ∂ A, let d(p) denote the largest number such that the simplices of T that meet the open ball centered at p of radius d(p) all share a vertex, v(p). The quantity d(p) is the 3-dimensional analog of the local feature size function introduced by Ruppert [22]. We call d min the minimum of d, which is known to be positive, and set k equal to the minimum of d min and e, where e is half the distance from ∂ A to the closest box that does not meet ∂ A.

	while (true) do
	update T , W , and the four sets.
	if Critical2 = / 0 then
	split its first element.
	else if Boundary1 = / 0 then
	split its first element.
	else if Boundary2 = / 0 then
	split its first element.
		e
	PSfrag replacements	v(p)	∂ A
	p
	k
	Main Algorithm
	Initialization Refine O until all boxes b satisfy either vanish(b) is false or vanish'(b)
	is false. Insert all boxes b such that vanish'(b) is true in Critical1.
	compute T and W , and the four sets Critical2, Boundary1, Lemma 11 Let A ⊂ R 3 be such that ∂ A is a manifold included in C and containing no
	Boundary2, and Index. vertex of T . Suppose that all boxes meeting ∂ A are smaller than s 1 . Then f and f have
	the same index on A.

--the positive vertices that do not flow into positive critical points of f nor into vertices lying in a box containing a positive critical point of f . With this modification, lemma 8 still holds and lemma 10 holds if one replaces c by the minimum c of c and the minimum of | f | on the boxes containing a critical point of f . Also, c is positive as f does not vanish on these boxes. else if f and f have different indices on some component of the critical set then split the first element of Index. else return M end if end while

Thanks to theorem 3 applied to W , the correctness of this algorithm amounts to its termination. We now show that the main algorithm terminates. First note that after the initialization step, no box containing a critical point of f is split, because such boxes belong to Critical1. The magnitude of ∇ f is thus larger than a certain constant g min on the complement C of the union of these boxes. Let us show that the size of the boxes of Critical2 that are split at some point is bounded from below. As ∇ f converges to ∇ f , there is a number s 1 such that for each tetrahedron with diameter smaller than s 1 ,

||∇ f -∇ f

A complex is collapsible if it collapses to a point.

This follows from Alexander duality together with the fact that contractible subcomplexes of the 2sphere are collapsible.

This means that there is a homeomorphism Φ : W → M × [0, 1] mapping M to M × {1/2}.

size is smaller than s 1 since we consider boxes in decreasing order. Now the gradients of f on tetrahedra incident on v all have a positive inner product with ∇ f (v) (recall ∇ f and ∇ f make an angle less than π/6), which is a contradicts lemma 2, implying that v is not critical. So the conclusion is that Critical2 becomes -at least temporarily-empty after a finite number of consecutive splittings of boxes in Critical2. To complete the proof of termination, we need to prove that Index does not contain boxes that are too small. This is true by applying lemma 11 to smooth neighborhoods of each connected component of the critical set. Finally :

Theorem 12 The main algorithm returns an isotopic piecewise linear approximation of M.

If one wishes to guarantee in addition that the Hausdorff distance between M and its approximation is less than say ε, by theorem 3 it is sufficient to modify the positive watershed algorithm so as to control that the width of W is smaller than ε.

Appendix

We now briefly explain how to compute the index of a generic smooth function f : R 3 → R on a box B ⊂ R 3 in a certified way. Without loss of generality, we assume that B = [0, 1] 3 . Our approach is based on a recursive definition of the index of a vector field introduced in [START_REF] Gottlieb | The index of discontinuous vector fields[END_REF]. The central formula in this work is the following (see figure 12). If V denotes a vector field (in our case, V = ∇ f ) defined on a compact smooth n-manifold M and not vanishing on ∂ M, then the index of V satisfies:

Here ∂ -V is a vector field defined on ∂ -M, which is the set of boundary points where V points inwards. On ∂ -M, ∂ -V coincides with the projection of V on the tangent space of ∂ M. Now suppose we can find a (n -1)-submanifold M 1 ⊂ ∂ -M that contains all zeroes of ∂ -V . Then, to compute the index of V on M, it is sufficient to compute the index of ∂ -V on M 1 (and the Euler characteristic of M 1 ). By repeated application of this principle, we can express the index of V as a sum of Euler characteristics and indices of vector fields defined over 1-manifolds, which are trivial to compute.

To apply this strategy to our case, in which M = B has edges and corners, we conceptually consider offsets of M, which are smooth, and let the offset parameter go to 0. Almost by definition, in this setting the zeros of ∂ -V are the points where V belongs to the normal cone and points inwards. Using interval analysis, it is not difficult to find a subset B 1 of ∂ -B that contains all such points, and such that ∂ -V does not vanish on ∂ B 1 . To do this, we recursively subdivide the faces of the cube until all cells satisfy one of the two following conditions: either the cell does not contain a zero of ∂ -V , or it is included in ∂ -B. The union of the cells of the latter type will then provide a suitable B 1 . For a square C lying on the face supported by, say, the plane

Here V z (C) > 0 for instance means that the z-coordinate of V is positive on C. The condition under which C is included in ∂ -B is obviously V z (C) < 0. Edges of the cube might also have to be subdivided. Without loss of generality we assume that edge E is supported by the line with equation x = y = 1. Then sufficient conditions under which E cannot contain a zero are as follows:

Also, the condition under which E is included in ∂ -B is (V x (E) < 0) and (V y (E) < 0).

It can be checked that this subdivision process terminates if V has no zeroes on the surface of the cube, which is a generic condition. Upon termination of the subdivision process, we obtain a set B 1 to which the formula can be applied. It thus remains to