Nicolas Forcadel

Cyril Imbert

R Monneau

Uniqueness and existence of spirals moving by forced mean curvature motion

Keywords: AMS Classification: 35K55, 35K65, 35A05, 35D40 spirals, motion of interfaces, comparison principle, quasi-linear parabolic equation, viscosity solutions, mean curvature motion

published or not. The documents may come

Uniqueness and existence of spirals moving by forced mean curvature motion

Introduction

In this paper we are interested in curves (Γ t ) t>0 in R2 which are half lines with an end point attached at the origin. These lines are assumed to move with normal velocity (1.1) V n = c + κ where κ is the curvature of the line and c ∈ R is a given constant. We will see that this problem reduces to the study of the following quasi-linear parabolic equation in non-divergence form (1.2)

rū t = c 1 + r 2 ū2 r + ūr 2 + r 2 ū2 r 1 + r 2 ū2 r + rū rr 1 + r 2 ū2 r , t > 0, r > 0
This paper is devoted to the proof of a comparison principle in the class of sub-linear weak (viscosity) solutions and to the study of the associated Cauchy problem.

Motivations and known results

Continuum mechanics. From the viewpoint of applications, the question of defining the motion of spirals in a two dimensional space is motivated by the seminal paper of Burton, Cabrera and Frank [START_REF] Burton | The growth of crystals and the equilibrium structure of their surfaces[END_REF] where the growth of crystals with the vapor is studied. When a screw dislocation line reaches the boundary of the material, atoms are adsorbed on the surface in such a way that a spiral is generated; moreover, under appropriate physical assumptions, these authors prove that the geometric law governing the dynamics of the growth of the spiral is precisely given by (1.1) where -c denotes a critical value of the curvature. We mention that there is an extensive literature in physics dealing with crystal growth in spiral patterns.

Different mathematical approaches. First and foremost, defining geometric flows by studying nonlinear parabolic equations is an important topic both in analysis and geometry. Giving references in such a general framework is out of the scope of this paper. As far as the motion of spirals is concerned, the study of the dynamics of spirals have been attracting a lot of attention for more than ten years. Different methods have been proposed and developed in order to define solutions of the geometric law (1.1). A brief list is given here. A phase-field approach was first proposed in [START_REF] Karma | Spiral surface growth without desorption[END_REF] and the reader is also referred to [START_REF] Ogiwara | Spiral traveling wave solutions of some parabolic equations on annuli[END_REF][START_REF]Spiral traveling wave solutions of nonlinear diffusion equations related to a model of spiral crystal growth[END_REF].

Other approaches have been used; for instance, "self-similar" spirals are constructed in [START_REF] Ishimura | Shape of spirals[END_REF] by studying an ordinary differential equation. In [START_REF] Giga | Spiral solutions for a weakly anisotropic curvature flow equation[END_REF], spirals moving in (compact) annuli with homogeneous Neumann boundary condition are constructed. From a technical point of view, the classical parabolic theory is used to construct smooth solutions of the associated partial differential equation; in particular, gradient estimates are derived. We point out that in [START_REF] Giga | Spiral solutions for a weakly anisotropic curvature flow equation[END_REF], the geometric law is anisotropic, and is thus more general than (1.1).

In [START_REF] Smereka | Spiral crystal growth[END_REF][START_REF] Ohtsuka | A level set method for spiral crystal growth[END_REF], the geometric flow is studied by using the level-set approach [START_REF] Osher | Fronts propagating with curvature-dependent speed: algorithms based on Hamilton-Jacobi formulations[END_REF][START_REF] Chen | Uniqueness and existence of viscosity solutions of generalized mean curvature flow equations[END_REF][START_REF] Evans | Motion of level sets by mean curvature. I[END_REF]. As in [START_REF] Giga | Spiral solutions for a weakly anisotropic curvature flow equation[END_REF], the author of [START_REF] Ohtsuka | A level set method for spiral crystal growth[END_REF] considers spirals that typically move into a (compact) annulus and reaches the boundary perpendicularly.

The starting point of this paper is the following fact: to the best of our knowledge, no geometric flows were constructed to describe the dynamics of spirals by mean curvature by taking into account both the singularity of the pinned point and the unboundedness of the domain.

The equation of interest. We would like next to explain with more details the main aims of our study. By parametrizing spirals, we will see (cf. Subsection 1.2) that the geometric law (1.1) is translated into the quasi-linear parabolic equation (1.2). We note that the coefficients are unbounded (they explode linearly with respect to r) and that the equation is singular: indeed, as r → 0, either ru t → 0 or first order terms explode. Moreover, initial data are also unbounded. In such a framework, we would like to achieve: uniqueness of weak (viscosity) solutions for the Cauchy problem for a large class of initial data, to construct a unique steady state (i.e. a solution of the form λt + φ(r)), and finally to show the convergence of general solutions of the Cauchy problem to the steady state as time goes to infinity. This paper is mainly concerned with proving a uniqueness result and constructing a weak (viscosity) solution; the study of large time asymptotic will be achieved in [START_REF] Forcadel | Large time asymptotic for spirals moving by mean curvature type motion[END_REF]. Classical parabolic theory. Classical parabolic theory [START_REF] Friedman | Partial differential equations of parabolic type[END_REF][START_REF] Ladyženskaja | Linear and quasilinear equations of parabolic type[END_REF] could help us to construct solutions but there are major difficulties to overcome. For instance, Giga, Ishimura and Kohsaka [START_REF] Giga | Spiral solutions for a weakly anisotropic curvature flow equation[END_REF] studied a generalization of (1.2) in domains of the form R a,b = {a < r < b} with a > 0 and b > 0, with Neumann boundary conditions at r = a, b. Roughly speaking, we can say that our goal is to see what happens when a → 0 and b → ∞. First, we mentioned above that the equation is not (uniformly) parabolic in the whole domain R 0,∞ = {0 < r < +∞}. Second, in such analysis, the key step is to obtain gradient estimates. Unfortunately, the estimates from [START_REF] Giga | Spiral solutions for a weakly anisotropic curvature flow equation[END_REF] in the case of (1.2) explode as a goes to 0. Third, once a solution is constructed, it is natural to study uniqueness but even in the setting of classical solutions there are substantial difficulties. To conclude, classical parabolic theory can be useful in order to get existence results, keeping in mind that getting gradient estimates for (1.2) is not at all easy, but such techniques will not help in proving uniqueness.

Recently, several authors studied uniqueness of quasilinear equations with unbounded coefficients (see for instance [START_REF] Barles | Uniqueness results for quasilinear parabolic equations through viscosity solutions' methods[END_REF][START_REF] Chou | On quasilinear parabolic equations which admit global solutions for initial data with unrestricted growth[END_REF]) by using viscosity solution techniques for instance. But unfortunately, Eq. (1.2) does not satisfy the assumptions of these papers.

Main new ideas. New ideas are thus necessary to handle these difficulties, both for existence and uniqueness. As far as uniqueness is concerned, one has to figure out what is the relevant boundary condition at r = 0. We remark that solutions of (1.2) satisfy at least formally a Neumann boundary condition at the origin

(1.3) 0 = c + 2ū r for r = 0.
In some sense, we thus can say that the boundary condition is embedded into the equation. Second, taking advantage of the fact that the Neumann condition is compatible with the comparison principle, viscosity solution techniques (also used in [START_REF] Barles | Uniqueness results for quasilinear parabolic equations through viscosity solutions' methods[END_REF]) permit us to get uniqueness even if the equation is degenerate and also in a very large class of weak (sub-and super-) solutions.

But there are remaining difficulties to be overcome. First, the Boundary Condition (1.3) is only true asymptotically (as r → 0) and the fact that it is embedded into the equation makes it difficult to use.

We will overcome this difficulty by making a proper change of variables (namely x = ln r, see below for further details) and proving a comparison principle (whose proof is rather involved; in particular many new arguments are needed in compare with the classical case) in this framework. Second, classical viscosity solution techniques for parabolic equations do not apply directly to (1.2) because of polar coordinates. More precisely, the equation do not satisfy the fundamental structure conditions as presented in [START_REF] Crandall | User's guide to viscosity solutions of second order partial differential equations[END_REF]Eq. (3.14)] when polar coordinates are used. But the mean curvature equation has been extensively studied in Cartesian coordinates [START_REF] Evans | Motion of level sets by mean curvature. I[END_REF][START_REF] Chen | Uniqueness and existence of viscosity solutions of generalized mean curvature flow equations[END_REF]. Hence this set of coordinates should be used, at least far from the origin.

Perron's method and smooth solutions. We hope we convinced the reader that it is really useful, if not mandatory, to use viscosity solution techniques to prove uniqueness. It turns out that it can also be used to construct solutions by using Perron's method [START_REF] Ishii | Perron's method for Hamilton-Jacobi equations[END_REF]. This technique requires to construct appropriate barriers and we do so for a large class of initial data. The next step is to prove that these weak solutions are smooth if additional growth assumptions on derivatives of initial data are imposed; we get such a result by deriving non-standard gradient estimates (with viscosity solution techniques too).

We would like also to shed some light on the fact that this notion of solution is also very useful when studying large time asymptotic (and more generally to pass to the limit in such non-linear equations). Indeed, convergence can be proved by using the half-relaxed limit techniques if one can prove a comparison principle. See [START_REF] Forcadel | Large time asymptotic for spirals moving by mean curvature type motion[END_REF] for more details.

The geometric formulation

In this section, we make precise the way spirals are defined. We will first define them as parametrized curves.

Parametrization of spirals. We look for interfaces Γ parametrized as follows: Γ = {re -iū(r) : r ≥ 0} ⊂ C for some function ū : [0, +∞) → R. If now the spiral moves, i.e. evolves with a time variable t > 0, then the function ū also depends on t > 0.

Definition 1.1 (Spirals). A moving spiral is a family of curves (Γ t ) t>0 of the following form

(1.4) Γ t = {re iθ : r > 0, θ ∈ R, θ + ū(t, r) = 0}
for some function ū : [0, +∞) × [0, +∞) → R. This curve is oriented by choosing the normal vector field equal to (-i + r∂ r ū(t, r))e -iū(t,r) . With the previous definition in hand, the geometric law (1.1) implies that ū satisfies (1.2) with the initial condition (1.5) ū(0, r) = ū0 (r) for r ∈ (0, +∞) .

Ū > 0 Ū < 0 V n
Link with the level-set approach. In view of (1.4), we see that our approach is closely related to the level-set one. We recall that the level-set approach was introduced in [START_REF] Osher | Fronts propagating with curvature-dependent speed: algorithms based on Hamilton-Jacobi formulations[END_REF][START_REF] Evans | Motion of level sets by mean curvature. I[END_REF][START_REF] Chen | Uniqueness and existence of viscosity solutions of generalized mean curvature flow equations[END_REF]; in particular, it permits to construct an interface moving by mean curvature type motion, that is to say satisfying the geometric law (1.1). It consists in defining the interface Γ t as the 0-level set of a function Ũ (t, •) and in remarking that the geometric law is verified only if Ũ satisfies a non-linear evolution equation of parabolic type. In an informal way, we can say that the quasi-linear evolution equation (1.2) is a "graph" equation associated with the classical mean curvature equation (MCE), but written in polar coordinates. More precisely, if Ũ (t, X) = θ + ū(t, r) with X= (r cos θ, r sin θ) ∈ R 2 , then ū will satisfy (1.2) as long as Ũ solves the following level-set equation

(1.6) Ũt = c|D X Ũ | + D X Ũ ⊥ • D 2 XX Ũ D X Ũ ⊥ for X = 0
(where p = p/|p| and p ⊥ = (-p 2 , p 1 ) for p = (p 1 , p 2 ) ∈ R 2 ). Notice that the angle θ is multivalued, i.e. only defined modulo 2π. Such an approach is for instance systematically developed in [START_REF] Ohtsuka | A level set method for spiral crystal growth[END_REF].

Main results

Comparison principle. Our first main result is a comparison principle: it says that all sub-solutions lie below all super-solutions, provided they are ordered at initial time.

Theorem 1.2 (Comparison principle for (1.2)). Assume that ū0 : (0, +∞) → R is a globally Lipschitz continuous function. Consider a sub-solution ū and a super-solution v of (1.2),(1.5) (in the sense of Definition 2.1) such that there exist C 1 > 0 and for all t ∈ [0, T ) and r > 0,

(1.7) ū(t, r) -ū0 (r) ≤ C 1 and v(t, r) -ū0 (r) ≥ -C 1 . If ū(0, r) ≤ ū0 (r) ≤ v(0, r) for all r ≥ 0, then ū ≤ v in [0, T ) × (0, +∞).
Remark 1.3. The growth of the sub-solution u and the super-solution v is made precise by assuming Condition (1.7). Such a condition is motivated by the large time asymptotic study carried out in [START_REF] Forcadel | Large time asymptotic for spirals moving by mean curvature type motion[END_REF]; indeed, we construct in [START_REF] Forcadel | Large time asymptotic for spirals moving by mean curvature type motion[END_REF] a global solution of the form λt + ū0 (r).

The proof of Theorem 1.2 is rather involved and we will first state and prove a comparison principle in the set of bounded functions for a larger class of equations (see Theorem 3.1). We do so in order to exhibit the structure of the equation that makes the proof work. We then turn to the proof of Theorem 1.2.

Both proofs are based on the doubling of variable method, which consists in regularizing the sub-and super-solutions. Obviously, this is a difficulty here because one end point of the curve is attached at the origin and the doubling of variables at the origin is not well defined. To overcome this difficulty, we work with logarithmic coordinates x = ln r for r close to 0. But then the equation becomes

u t = ce -x 1 + u 2 x + e -2x u x + e -2x u xx 1 + u 2 x
We then apply the doubling of variables in the x coordinates. There is a persistence of the difficulty, because we have now to bound terms like

A := ce -x 1 + u 2 x -ce -y 1 + v 2 y
that can blow up as x, y → -∞. We are lucky enough to be able to show roughly speaking that A can be controlled by the doubling of variable of the term e -2x u x which appears to be the main term (in a certain sense) as x goes to -∞.

In view of the study from [START_REF] Forcadel | Large time asymptotic for spirals moving by mean curvature type motion[END_REF], ū0 has to be chosen sub-linear in Cartesian coordinates and thus so are the sub-and super-solutions to be compared. The second difficulty arises when passing to logarithmic coordinates for large r's; indeed, the sub-solution and the super-solution then grow exponentially in x = ln r at infinity and we did not manage to adapt the previous reasoning in this setting. There is for instance a similar difficulty when dealing with the mean curvature equatio. Indeed, in this framework, for super-linear initial data, the uniqueness of the solution is not known in full generality (see [START_REF] Barles | Uniqueness results for quasilinear parabolic equations through viscosity solutions' methods[END_REF][START_REF] Chou | On quasilinear parabolic equations which admit global solutions for initial data with unrestricted growth[END_REF]). In other words, the change of variables do not seem to work far from the origin. We thus have to stick to Cartesian coordinates for large r's (using a level-set formulation) and see the equation in different coordinates when r is either small or large (see Section 4).

Existence theorem. In order to get an existence theorem, we have to restrict the growth of derivatives of the initial condition. We make the following assumptions: the initial condition is globally Lipschitz continuous and its mean curvature is bounded. We recall that the mean curvature of a spiral parametrized by ū is defined by

κ ū(r) = u r 2 + (rū r ) 2 (1 + (rū r ) 2 ) 3 2 + rū rr (1 + (rū r ) 2 ) 3 2
.

We can now state our second main result.

Theorem 1.4 (The general Cauchy problem). Consider ū0 ∈ W 2,∞ loc (0, +∞). Assume that ū0 is globally Lipschitz continuous and that κ ū0 ∈ L ∞ (0, +∞). Then there exists a unique solution u of (1.2),(1.5) on [0, +∞) × (0, +∞) (in the sense of Definition 2.1) such that for all T > 0, there exists CT > 0 such that for all t ∈ [0, T ) and r > 0, (1.8) |ū(t, r) -ū0 (r)| ≤ CT .

Moreover, ū is Lipschitz continuous with respect to space and 1 2 -Hölder continuous with respect to time. More precisely, there exists a constant C depending only on

|(ū 0 ) r | ∞ and |κ ū0 | ∞ such that |ū(t, r + ρ) -ū(t, r)| ≤ C|ρ| and (1.9) |ū(t + h, r) -ū(t, r)| ≤ C |h|.
Remark 1.5. Notice that Theorem 1.4 allows us to consider an initial data ū0 which does not satisfy the compatibility condition (1.3), like for instance ū0 ≡ 0 with c = 1. Notice also that we do not know if the solution constructed in Theorem 1.4 is smooth (i.e. belongs to C ∞ ((0, +∞) 2 )).

To get such a result, we first construct smooth solutions requiring that the compatibility condition (1.3) is satisfied by the initial datum, like in the following result.

Theorem 1.6 (Existence and uniqueness of smooth solutions for the Cauchy problem). Assume that ū0 ∈ W 2,∞ loc (0, +∞) with

(ū 0 ) r ∈ W 1,∞ (0, +∞) or κ ū0 ∈ L ∞ (0, +∞)
and that it satisfies the following compatibility condition for some r 0 > 0:

(1.10)

|c + κ ū0 | ≤ Cr for 0 ≤ r ≤ r 0 .
Then there exists a unique continuous function: Open questions.

ū : [0, +∞) × [0, +∞) which is C ∞ in (0, +∞) × (0,
A. Weaker conditions on the initial data It would be interesting to investigate the existence/non-existence and uniqueness/non-uniqueness of solutions when we allow the initial data ū0 to be less than globally Lipschitz. For instance what happens when the initial data describes an infinite spiral close to the origin r = 0, with either ū0 (0 + ) = +∞ or ū0 (0 + ) = -∞? On the other hand, what happens if the growth of ū0 is super-linear as r goes to +∞? B. More general shapes than spiral One of our main limitation to study only the evolution of spirals in this paper is that we were not able to prove a comparison principle in the case of the general level-set equation (1.6). The difficulty is the fact that the gradient of the level-set function Ũ may degenerate exactly at the origin where the curve is attached.

The fact that a spiral-like solution is a graph θ = -ū(t, r) prevents the vanishing of the gradient of Ũ at the origin r = 0. If now we consider more general curves attached at the origin, it would be interesting to study the existence and uniqueness/non-uniqueness of solutions with general initial data, like the curves on Figure 2. Organization of the article. In Section 2, we recall the definition of viscosity solutions for the quasilinear evolution equation of interest in this paper. The change of variables that will be used in the proof of the comparison principle is also introduced. In Section 3, we give the proof of Theorem 1.2 in the case of bounded solutions. The proof in the general case is given in Section 4. In Section 5, a classical solution is constructed under an additional compatibility condition on the initial datum (see Theorem 1.6). First, we construct a viscosity solution by Perron's method (Subsection 5.1); second, we derive gradient estimates (Subsection 5.2); third, we explain how to prove that the viscosity solution is in fact a classical one (Subsection 5.3). The construction of the solution without compatibility assumption (Theorem 1.4) is made in Section 6. Finally, proofs of technical lemmas are gathered in Appendix A.

Notation. If a is a real number, a + denotes max(0, a) and a -denotes max(0, -a) If p = (p 1 , p 2 ) ∈ R 2 , p = 0, then p denotes p/|p| and p ⊥ denotes (-p 2 , p 1 ).

Preliminaries 2.1 Viscosity solutions for the main equation

In view of (1.2), it is convenient to introduce the following notation

(2.12) F (r, q, Y ) = c 1 + r 2 q 2 + q 2 + r 2 q 2 1 + r 2 q 2 + rY 1 + r 2 q 2 .
We first recall the notion of viscosity solution for an equation such as (1.2).

Definition 2.1 (Viscosity solutions for (1.2),(1.5)). Let T ∈ (0, +∞]. A lower semi-continuous (resp. upper semi-continuous) function u : [0, T ) × (0, +∞) → R is a (viscosity) super-solution (resp. sub-solution) of (1.2),(1.5) on [0, T ) × (0, +∞) if for any C 2 test function φ such that u -φ reaches a local minimum (resp. maximum) at (t, r) ∈ [0, T ) × (0, +∞), we have (i) If t > 0: rφ t ≥ F (r, φ r , φ rr ) resp. rφ t ≤ F (r, φ r , φ rr ) . (ii) If t = 0: u(0, r) ≥ ū0 (r) resp. u(0, r) ≤ ū0 (r) . A continuous function u : [0, T ) × (0, +∞) → R is a (viscosity) solution of (1.2),(1.5) on [0, T ) × (0, +∞)
if it is both a super-solution and a sub-solution.

Remark 2.2. We do not impose any condition at r = 0; in other words, it is not necessary to impose a condition on the whole parabolic boundary of the domain. This is due to the "singularity" of our equation at r = 0.

Since we only deal with this weak notion of solution, (sub-/super-)solutions will always refer to (sub-/super-)solutions in the viscosity sense.

When constructing solutions by Perron's method, it is necessary to use the following classical discontinuous stability result. The reader is referred to [START_REF] Chen | Uniqueness and existence of viscosity solutions of generalized mean curvature flow equations[END_REF] for a proof.

Proposition 2.3 (Discontinuous stability). Consider a family (u α ) α∈A of sub-solutions of (1.2),(1.5) which is uniformly bounded from above. Then the upper semi-continuous envelope of sup α∈A u α is a sub-solution of (1.2),(1.5).

A change of unknown function

We will make use of the following change of unknown function: u(t, x) = ū(t, r) with x = ln r satisfies for all t > 0 and x ∈ R (2.13)

u t = ce -x 1 + u 2 x + e -2x u x + e -2x u xx 1 + u 2
x submitted to the initial condition: for all x ∈ R,

(2.14) u(0, x) = u 0 (x)
where u 0 (x) = ū0 (e x ). Eq. (2.13) can be rewritten

u t = F (x, u x , u xx ) with (2.15) F (x, p, X) = ce -x 1 + p 2 + e -2x p + e -2x X 1 + p 2 .
Remark that functions F and F are related by the following formula

(2.16) F (x, u x , u xx ) = 1 r F (r, ūr , ūrr ) .
Since the function ln is increasing and maps (0, +∞) onto R, we have the following elementary lemma which will be used repeatedly throughout the paper.

Lemma 2.4 (Change of variables).

A function ū is a solution of (1.2),(1.5) if and only if the corresponding function u is a solution of (2.13)-(2.14) with u 0 (x) = ū0 (e x ).

The reader is referred to [START_REF] Crandall | User's guide to viscosity solutions of second order partial differential equations[END_REF] (for instance) for a proof of such a result. When proving the comparison principle in the general case, we will also have to use Cartesian coordinates. From a technical point of view, the following lemma is needed. Lemma 2.5 (Coming back to the Cartesian coordinates). We consider a sub-solution u (resp. super-solution v) of (2.13)-(2.14) and we define the function

Ũ (resp. Ṽ ) : (0, +∞) × R 2 → R by Ũ (t, X) = θ(X) + u(t, x(X)) (resp. Ṽ (t, Y ) = θ(Y ) + u(t, x(Y )))
where (θ(Z), x(Z)) is defined such that Z = e x(Z)+iθ(Z) = 0. Then Ũ (resp. Ṽ ) is sub-solution (resp. super-solution) of (2.17)

       w t = c|Dw| + Dw ⊥ |Dw| D 2 w Dw ⊥ |Dw| w(0, x) = θ(X) + ū0 (x(X)).
Remark 2.6. In Lemma 2.5, for Z = 0, the angle θ(Z) is only defined modulo 2π, but is locally uniquely defined by continuity. Then Dθ, D 2 θ are always uniquely defined.

A comparison principle for bounded solutions

As explained in the introduction, we first prove a comparison principle for (1.2) in the class of bounded weak (viscosity) solutions. In comparison with classical comparison results for geometric equations (see for instance [START_REF] Evans | Motion of level sets by mean curvature. I[END_REF][START_REF] Chen | Uniqueness and existence of viscosity solutions of generalized mean curvature flow equations[END_REF][START_REF] Sato | Interface evolution with Neumann boundary condition[END_REF][START_REF] Giga | Generalized interface evolution with the Neumann boundary condition[END_REF]), the difficulty is to handle the singularity at the origin (r = 0). In order to clarify why a comparison principle holds true for such a singular equation, we consider the following generalized case (3.18) ūt = b(ū r , rū r ) r + σ 2 (rū r )ū rr which can be written, with x = ln r,

(3.19) u t = e -x b(e -x u x , u x ) + e -2x σ 2 (u x )u xx where b(q, p) = b(q, p) -σ 2 (p)q.
Assumption on (b, σ).

-σ ∈ W 1,∞ (R); -There exists δ 1 , δ 2 , δ 3 , δ 4 > 0 such that -for all q ∈ R and p 1 , p 2 ∈ R, |b(q, p 1 ) -b(q, p 2 )| ≤ δ 1 |p 1 -p 2 |;
-for all p ∈ R and

q 1 ≤ q 2 , δ 2 (q 2 -q 1 ) ≤ b(q 2 , p) -b(q 1 , p); |b(q 1 , p) -b(q 2 , p)| ≤ δ 3 |q 1 -q 2 |; -for all p ∈ R |b(0, p)| ≤ δ 4 1 + |p| 2 -we have σ 2 ∞ < 2δ 2 .
In our special case, σ(p) = (1 + p 2 ) -1 2 and b(q, p) = c 1 + p 2 + q, and the assumption on (b, σ) is satisfied.

Theorem 3.1 (Comparison principle for (3.18)-(2.14)). Assume that u 0 : (0, +∞) → R is Lipschitz continuous. Consider a bounded sub-solution u and a bounded super-solution v of (3.18), (2.14) in the sense of Definition 2.1 with F given by the right hand side of (3.18). Then u ≤ v in (0, +∞) × R.

Remark 3.2. For radial solutions of the heat equation u t = ∆u on R n \ {0}, we get b(q, p) = (n -1)q and σ(p) = 1. Therefore the assumption on (b, σ) is satisfied if and only if 1 < 2(n -2). Notice that in particular for n = 2 this assumption is not satisfied.

Proof of Theorem 3.1. We classically fix T > 0 and argue by contradiction by assuming that

M = sup 0<t<T,x∈R (u(t, x) -v(t, x)) > 0.
Lemma 3.3 (Penalization). For α, ε, η > 0 small enough, and any K ≥ 0, the supremum

M ε,α = sup 0<t<T,x,y∈R u(t, x) -v(t, y) -e Kt (x -y) 2 2ε - η T -t -α x 2 2 is attained at (t, x, y) with t > 0, M ε,α > M/3 > 0, |x -y| ≤ C 0 √ ε and α|x| ≤ C 0 √ α for some C 0 > 0 only depending on u ∞ and v ∞ .
Proof of Lemma 3.3. The fact that M > 0 means that there exist t * > 0 and x * ∈ R such that

u(t * , x * ) -v(t * , x * ) ≥ M/2 > 0.
Since u and v are bounded functions, M ε,α is attained at a point (t, x, y). By optimality of (t, x, y), we have in particular

u(t, x) -v(t, y) -e Kt (x -y) 2 2ε - η T -t -α x 2 2 ≥ u(t * , x * ) -v(t * , x * ) - η T -t * -α (x * ) 2 2 ≥ M/3
for α and η small enough (only depending on M ). In particular,

(x -y) 2 2ε + α x 2 2 ≤ u ∞ + v ∞ .
Hence, there exists a constant C 0 only depending on u ∞ and v ∞ such that

(3.20) |x -y| ≤ C 0 √ ε and α|x| ≤ C 0 √ α .
Assume that t = 0. In this case, we use the fact that u 0 is Lipschitz continuous and (3.20) in order to get

M 3 ≤ u 0 (x) -u 0 (y) ≤ Du 0 ∞ |x -y| ≤ C 0 Du 0 ∞ √ ε
which is absurd for ε small enough (depending only on M, C 0 and Du 0 ∞ ). Hence t > 0 and the proof of the lemma is complete.

In the remaining of the proof, ε is fixed (even if we will choose it small enough) and α goes to 0 (even if it is not necessary to pass to the limit). In view of the previous discussion, we can assume that, for ε small enough, we have t > 0 for all α > 0 small enough (independent on ε). We thus can write two viscosity inequalities. It is then classical to use Jensen-Ishii's Lemma and combine viscosity inequalities in order to get the following result. where p = e Kt (x-y) ε . Proof of Lemma 3.4. Jensen-Ishii 's Lemma [START_REF] Crandall | User's guide to viscosity solutions of second order partial differential equations[END_REF] implies that for all γ 1 > 0, there exist four real numbers a, b, A, B such that

a ≤ e -x b(e -x (p + αx), p + αx) + e -2x σ 2 (p + αx)(A + α) (3.22)
b ≥ e -y b(e -y p, p) + e -2y σ 2 (p)B (3.23) Moreover a, b satisfy the following inequality

(3.24) a -b ≥ η (T -t) 2 + Ke Kt (x -y) 2 2ε
(it is in fact an equality) and for any γ 1 > 0 small enough, there exist two real numbers A, B satisfying the following matrix inequality

A 0 0 -B ≤ e Kt ε (1 + γ 1 ) 1 -1 -1 1 .
This matrix inequality implies

(3.25) Aξ 2 1 ≤ Bξ 2 2 + e Kt ε (1 + γ 1 )(ξ 1 -ξ 2 ) 2
for all ξ 1 , ξ 2 ∈ R. Use this inequality with ξ 1 = e -x σ(p + αx) and ξ 2 = e -y σ(p) and let γ 1 → 0 in order to get the desired inequality.

We can next make appear which error terms depend on α and which ones depend on ε. For all γ 2 > 0,

(3.26) η T 2 + Ke Kt (x -y) 2 2ε ≤ T α + T ε
where

T α = e -x b(e -x (p + αx), p + αx) -e -x b(e -x p, p) + σ 2 ∞ e -2x α + (1 + γ -1 2 ) e Kt-2x ε σ ′ 2 ∞ (αx) 2
and

T ε = T 1 ε + T 2 ε with T 1 ε = e -x b(e -x p, p) -e -y b(e -y p, p) and T 2 ε = (1 + γ 2 ) σ 2 ∞ e Kt-2x ε (1 -e x-y ) 2 .
It remains to estimate T ε .

Lemma 3.5 (Estimate for T ε ). For all γ 3 > 0,

(3.27) T ε ≤ ((C -2δ 2 )e -2x + γ 3 )e Kt (x -y) 2 ε + γ 3 ε where C = δ 2 4 4γ3 + (1 + γ 2 ) σ 2 ∞ + o ε (1)
. Proof. Through a Taylor expansion, we obtain

T 1 ε = -e -y θ b(e -y θ p, p)(x -y) -e -2y θ ∂ q b(e -y θ p, p)p(x -y) ≤ -εe -Kt b(e -y θ p, p)e -y θ p -δ 2 e Kt-2y θ (x -y) 2 ε
where y θ = θy + (1 -θ)x for some θ ∈ [0, 1], and we have used the fact that for all q ∈ R,

q(b(q, p) -b(0, p)) ≥ δ 2 q 2
We get for any γ 3 > 0

T 1 ε ≤δ 4 e -y θ |x -y| √ ε √ ε 1 + p 2 -2δ 2 e Kt-2y θ (x -y) 2 ε ≤ δ 2 4 4γ 3 (1 + o ε (1))e Kt-2x (x -y) 2 ε + e -Kt γ 3 ε + γ 3 e Kt (x -y) 2 ε -2δ 2 (1 + o ε (1))e Kt-2x (x -y) 2 ε ,
where we have used that y θ = x + o ε (1). Now, since y = x + O( √ ε), we also have

T 2 ε = (1 + γ 2 )(1 + o ε (1)) σ 2 ∞ e Kt-2x ε (x -y) 2
and we can conclude.

Combining (3.26) and (3.27) finally yields

η T 2 + K 2 -γ 3 + (2δ 2 -C)e -2x e Kt (x -y) 2 ε ≤ T α + γ 3 ε.
It suffices now to choose γ i , i = 1, 2, 3, such that C ≤ 2δ 2 and then choose K = 2γ 3 and ε small enough to get: η 2T 2 ≤ T α . The following lemma permits to estimate T α . Lemma 3.6 (Estimate for T α ). For D > 0 large enough, we have

(3.28) T α D ≤ e -2x (-αx -+ αx + ) + e -x |αx| + e -2x α + e Kt-2x √ α ε |αx|.
Proof. Using assumptions on b immediately yields

T α ≤ e -2x (-δ 2 αx -+ δ 3 αx + ) + δ 1 e -x |αx| + σ 2 ∞ e -2x α + (1 + γ -1 2 ) e Kt-2x √ α ε σ ′ 2 ∞ C 0 |αx|
where we used that |αx| ≤ C 0 √ α.

We next consider a > 0 such that for all x ≤ -a, we have

-|x|e -2x + 2|x|e -x + e -2x ≤ 0.
We now distinguish cases.

Case 1: x n ≤ -a for some α n → 0. We choose n large enough so that e Kt √ αn ε ≤ 1 and we get η 2T 2 ≤ Dα(-|x|e -2x + 2|x|e -x + e -2x ) ≤ 0 which implies η ≤ 0. Contradiction.

Case 2: x ≥ -a for all α small enough. We use (3.20) and get

η 2T 2 ≤ De 2a (2α|x| + α + e Kt √ α ε |αx|) ≤ D(2C 0 √ α + α + e Kt C 0 α ε )
and we let α → 0 to get η ≤ 0 in this case too. The proof is now complete.

Comparison principle for sub-linear solutions

Proof of Theorem 1.2. Thanks to the change of unknown function described in Subsection 2.2, we can consider the functions u and v defined on (0, +∞) × R which are sub-and super-solutions of (2.13). We can either prove that ū ≤ v in (0, +∞) × (0, +∞) or that u ≤ v in (0, +∞) × R.

For θ ∈ R, we define

U (t, x, θ) = θ + u(t, x) and V (t, x, θ) = θ + v(t, x).
Note that U and V are respectively sub and super-solution of (4.29)

W t (t, x, θ) = ce -x |DW | + e -2x DW • e 1 + e -2x DW ⊥ |DW | D 2 W DW ⊥ |DW | .
We fix T > 0 and we argue by contradiction by assuming that

M = sup t∈[0,T ],x,θ∈R {U (t, x, θ) -V (t, x, θ)} > 0.
In order to use the doubling variable technique, we need a smooth interpolation function Ψ between polar coordinates for small r's and Cartesian coordinates for large r's. Precisely, we choose Ψ as follows.

Lemma 4.1 (Interpolation between logarithmic and Cartesian coordinates).

There exists a smooth (C ∞ ) function ψ : R 2 → R 3 such that (4.30)

   ψ(x, θ + 2π) = ψ(x, θ) ψ(x, θ) = (x, e iθ ) if x ≤ 0 ψ(x, θ) = (0, e x e iθ ) if x ≥ 1
and such that there exists two constants δ 0 > 0 and m ψ > 0 such that for x ≤ 1 and θ ∈ R,

(4.31) if ψ(x, θ) = (a, b) then |b| ≤ e
and such that for all x, y, σ, θ,

if |ψ(x, θ) -ψ(y, σ)| ≤ δ 0 and |θ -σ| ≤ π 2 , then |ψ(x, θ) -ψ(y, σ)| ≥ m ψ |(x, θ) -(y, σ)|, (4.32) Dψ(x, θ) T ⊙ (ψ(x, θ) -ψ(y, σ)) ≥ m ψ |(x, θ) -(y, σ)| (4.33)
where ⊙ is the tensor contraction defined for a p-tensor A = (A i1,...,ip ) and a q-tensor B = (B j1,...,jq ) by

(A ⊙ B) i1,...,ip-1,j2,...,jq = k A i1,...,ip-1,k B k,j2,...,jq .
The proof of this lemma is given in Appendix A.

Penalization. We consider the following approximation of M (4.34) M ε,α = sup t∈[0,T ],x,θ,y,σ∈R

U (t, x, θ) -V (t, y, σ) -e Kt |ψ(x, θ) -ψ(y, σ)| 2 2ε - 1 ε |θ -σ| - π 3 2 + - α 2 |ψ(x, θ)| 2 - η T -t
where ε, α, η are small parameters and K ≥ 0 is a large constant to be fixed later. For α and η small enough we remark that M ε,α ≥ M 2 > 0. In order to prove that the maximum M ε,α is attained, we need the following lemma whose proof is postponed until Appendix A.

Lemma 4.2 (A priori estimates).

There exists a constant C 2 > 0 such that the following estimate holds true for any x, y, θ, σ ∈ R

|u 0 (x) -u 0 (y)| ≤ C 2 + e Kt |ψ(x, θ) -ψ(y, σ)| 2 4ε |θ -σ| ≤ C 2 + 1 2ε |θ -σ| - π 3 2 + .
Using this lemma, we then deduce that

(4.35) U (t, x, θ) -V (t, y, σ) -e Kt |ψ(x, θ) -ψ(y, σ)| 2 2ε - 1 ε |θ -σ| - π 3 2 + ≤ u(t, x) -u 0 (x) -v(t, y) + u 0 (y) + |θ -σ| + |u 0 (x) -u 0 (y)| -e Kt |ψ(x, θ) -ψ(y, σ)| 2 2ε - 1 ε |θ -σ| - π 3 2 + ≤ 2C 1 + 2C 2 -e Kt |ψ(x, θ) -ψ(y, σ)| 2 4ε - 1 2ε |θ -σ| - π 3 2 + .
Using the 2π-periodicity of ψ, the maximum is achieved for θ ∈ [0, 2π]. Then, using the previous estimate and the fact that -α(ψ(x, θ)) 2 → -∞ as |x| → ∞, we deduce that the maximum is reached at some point that we still denote (t, x, θ, y, σ).

Penalization estimates. Using Estimate (4.35) and the fact that M ε,α ≥ 0, we deduce that there exists a constant

C 0 = 4(C 1 + C 2 ) such that (4.36) α(ψ(x, θ)) 2 + 1 ε |θ -σ| - π 3 2 + + e Kt |ψ(x, θ) -ψ(y, σ)| 2 2ε ≤ C 0 .
On the one hand, an immediate consequence of this estimate is that

|θ -σ| ≤ π 2
for ε small enough. On the other hand, we deduce from (4.36) and (4.32)

m ψ |θ -σ| 2 + |x -y| 2 2ε ≤ C 0 .
Hence, we have |θ -σ| ≤ π 4 for ε small enough so that the constraint |θ -σ| ≤ π 3 is not saturated. We can also choose ε small enough so that |x -y| ≤ 1 2 .

In the sequel of the proof, we will also need a better estimate on the term α(ψ(x)) 2 ; precisely, we need to know that α(ψ(x)) 2 → 0 as α → 0. Even if such a result is classical (see [START_REF] Crandall | User's guide to viscosity solutions of second order partial differential equations[END_REF]), we give details for the reader's convenience. To prove this, we introduce

M ε,0 = sup t∈[0,T ],x,θ,y,σ∈R U (t, x, θ) -V (t, y, σ) -e Kt |ψ(x, θ) -ψ(y, σ)| 2 2ε - 1 ε |θ -σ| - π 3 2 + - η T -t
which is finite thanks to (4.35).

We remark that M ε,α ≤ M ε,0 and that M ε,α is non-decreasing when α decreases to zero. We then deduce that there exists L such that M ε,α → L as α → 0. A simple computation then gives that

α 4 (ψ(x, θ)) 2 ≤ M ε, α 2 -M ε,α → 0 as α → 0
and then (4.37) α 2 (ψ(x, θ)) 2 → 0 as α → 0.

Initial condition. We now prove the following lemma.

Lemma 4.3 (Avoiding t = 0). For ε small enough, we have t > 0 for all α > 0 small enough.

Proof. We argue by contradiction. Assume that t = 0. We then distinguish two cases.

If the corresponding x and y are small (x ≤ 2 and y ≤ 2) then, since u 0 is Lipschitz continuous and (4.32) holds true, there exists a constant L 0 > 0 such that

0 < M 2 ≤ M ε,α ≤U (0, x, θ) -V (0, y, σ) - |ψ(x, θ) -ψ(y, σ)| 2 2ε ≤L 0 |(x, θ) -(y, σ)| -m ψ |(x, θ) -(y, σ)| 2 2ε ≤ L 2 0 2m ψ ε
which is absurd for ε small enough. The other case corresponds to large x and y (x ≥ 1 and y ≥ 1). In this case, since ū0 is Lipschitz continuous, we know that there exists a constant

L 1 > 0 such that 0 ≤ M 2 ≤ M ε,α ≤ |U (0, x, θ) -V (0, y, σ)| ≤ |θ -σ| + L 1 |e x -e y |.
Using the fact

|θ -σ| + L 1 |e x -e y | ≤ 1 m ψ + L 1 |ψ(x, θ) -ψ(y, σ)| ≤ 1 m ψ + L 1 2C 0 √ ε
we get a contradiction for ε small enough.

Thanks to Lemma 4.3, we will now write two viscosity inequalities, combine them and exhibit a contradiction. We recall that we have to distinguish cases in order to determine properly in which coordinates viscosity inequalities must be written (see the Introduction).

Case 1: There exists α n → 0 such that x ≥ 3 2 and y ≥ 3 2 . We set X = e x+iθ and Y = e y+iσ . Consider Ũ and Ṽ defined in Lemma 2.5. Remark that, even if θ(X) is defined modulo 2π, the quantity θ(X) -θ(Y ) is well defined (for |X|, |Y | ≥ e and |X -Y | ≤ 1 2 ) and thus so is Ũ (t, X) -Ṽ (t, Y ). Recall also that Ũ , Ṽ are respectively sub and super-solutions of the following equation

w t = c|Dw| + Dw ⊥ • D 2 w • Dw ⊥
Moreover, using the explicit form of ψ, we get that

M ε,α = sup t∈[0,T ],X,Y ∈R 2 \B1(0) Ũ (t, X) -Ṽ (t, Y ) - e Kt 2ε |X -Y | 2 - α 2 |X| 2 - η T -t . Moreover, -|D X Ũ | ≤ -1
|X| (in the viscosity sense). We set

p = X -Y ε e Kt .
We now use the Jensen-Ishii Lemma [START_REF] Crandall | User's guide to viscosity solutions of second order partial differential equations[END_REF] in order to get four real numbers a, b, A, B such that

a ≤ c|p + αX| + (p + αX) ⊥ |p + αX| (A + αI) (p + αX) ⊥ |p + αX| , b ≥ c|p| + p ⊥ |p| B p ⊥ |p| .
Moreover, p satisfies the following estimate

(4.38) |p + αX| ≥ 1 |X| , |p| ≥ 1 |Y | ,
a, b satisfy the following equality

a -b = η (T -t) 2 + Ke Kt |X -Y | 2 2ε
and A, B satisfy the following matrix inequality

A 0 0 -B ≤ 2e Kt ε I -I -I I .
This matrix inequality implies

(4.39) Aξ 2 1 ≤ Bξ 2 2 + 2e Kt ε |ξ 1 -ξ 2 | 2 for all ξ 1 , ξ 2 ∈ R 2 .
Subtracting the two viscosity inequalities, we then get

η T 2 ≤c|p + αX| -c|p| + α + (p + αX) ⊥ |p + αX| A (p + αX) ⊥ |p + αX| - p ⊥ |p| B p ⊥ |p| ≤α|c||X| + α + 2e Kt ε p + αX |p + αX| - p |p| 2 ≤|c| C 0 √ α + α + 2e Kt ε   2 αX 1 |X| 2 + 2 p |p| |αX| |p + |αX|| 2   ≤|c| C 0 √ α + α + 8e Kt ε α|X| 2 2
where we have used successively (4.39), (4.36) and (4.38). Recalling, by (4.37) that α|X| 2 = o α (1), we get a contradiction for α small enough.

Case 2: There exists α n → 0 such that x ≤ -1 2 and y ≤ -1 2 . Using the explicit form of ψ and the fact that U (t, x, θ) = θ + u(t, x) and V (t, y, σ) = σ + v(t, y) with u and v respectively sub and super-solution of (2.13), we remark that

M ε,α = sup t ′ ,x ′ ,y ′ {u(t ′ , x ′ ) -v(t ′ , y ′ ) -e Kt ′ |ψ(x ′ , θ) -ψ(y ′ , σ)| 2 2ε - α 2 |x ′ | 2 - η T -t ′ + θ -σ - α 2 }.
Moreover, the maximum is reached at (t, x, y), where we recall that (t, x, θ, y, σ) is the point of maximum in (4.34). Using the Jensen-Ishii Lemma [START_REF] Crandall | User's guide to viscosity solutions of second order partial differential equations[END_REF], we then deduce the existence, for all γ 1 > 0, of four real numbers a, b, A, B such that

a ≤ ce -x 1 + (p + αx) 2 + e -2x (p + αx) + e -2x A + α 1 + (p + αx) 2 b ≥ ce -y 1 + p 2 + e -
a -b = η (T -t) 2 + Ke Kt |ψ(x, θ) -ψ(y, σ)| 2 2ε ≥ η (T -t) 2 + Ke Kt |x -y| 2 2ε
and we obtain (3.24). Moreover, A, B satisfy the following matrix inequality

A 0 0 -B ≤ e Kt ε (1 + γ 1 ) 1 -1 -1 1
which implies (3.25). On one hand, from (3.22), (3.23), (3.24) and (3.25), we can derive (3.21). On the other hand, (4.36), the fact that x ≤ 0, y ≤ 0 and Lemma 4.1 imply (3.20) (with a different constant). We thus can apply Lemmas 3.5, 3.6 and deduce the desired contradiction.

Case 3: There exists α n → 0 such that -1 ≤ x, y ≤ 2. Since ψ ∈ C ∞ , there then exists M ψ > 0 (only depending on the function ψ) such that for all x ∈ [-1, 2] and θ ∈ [-π, 3π],

(4.40) |ψ(x, θ)| + |Dψ(x, θ)| + |D 2 ψ(x, θ)| + |D 3 ψ(x, θ)| ≤ M ψ .
For simplicity of notation, we denote (x, θ) by x and (y, σ) by ȳ. We next define

p x = e Kt ε Dψ(x) T ⊙ (ψ(x) -ψ(ȳ)) and p ȳ = e Kt ε Dψ(ȳ) T ⊙ (ψ(x) -ψ(ȳ)).
We have p x, p ȳ ∈ R 2 and we set (e 1 , e 2 ) a basis of R 2 .

Lemma 4.4 (Combining viscosity inequalities for α = 0). We have for α = 0

(4.41) η T 2 + Km 2 ψ e Kt |x -ȳ| 2 2ε ≤ ce -x |p x| -ce -y |p ȳ | + e -2x p x • e 1 -e -2y p ȳ • e 1 + 2e Kt ε (I 1 + I 2 )
where

I 1 = (ψ(x) -ψ(ȳ)) ⊙ D 2 ψ(x)e -x p ⊥ x • e -x p ⊥ x -D 2 ψ(ȳ)e -y p ⊥ ȳ • e -y p ⊥ y I 2 = Dψ(x)e -x p ⊥ x -Dψ(ȳ)e -y p ⊥ ȳ 2 .
Proof. Recall that U and V are respectively sub and super-solution of (4.29) and use the Jensen-Ishii Lemma [START_REF] Crandall | User's guide to viscosity solutions of second order partial differential equations[END_REF] in order to deduce that there exist two real numbers a, b and two 2 × 2 real matrices A, B such that

a ≤ ce -x |p x| + e -2x px • e 1 +e -2x p⊥ x |p x| A + α(ψ(x) ⊙ D 2 ψ(x) + Dψ(x) T ⊙ Dψ(x)) p⊥ x |p x| b ≥ ce -y |p ȳ | + e -2y p ȳ • e 1 + e -2y p ⊥ ȳ |p ȳ| B p ⊥ ȳ |p ȳ| where px = p x + αDψ(x) T ⊙ ψ(x).
Remark that , since D θ U = D θ V = 1, there exists δ 0 > 0 such that px ≥ δ 0 > 0 and p ȳ ≥ δ 0 > 0.

Moreover a, b satisfy the following equality

a -b = η (T -t) 2 + Ke Kt |ψ(x) -ψ(ȳ)| 2 2ε
and A, B satisfy the following matrix inequality

A 0 0 -B ≤ 2e Kt ε (ψ(x) -ψ(ȳ)) ⊙ D 2 ψ(x) 0 0 -(ψ(x) -ψ(ȳ)) ⊙ D 2 ψ(ȳ) + Dψ(x) T ⊙ Dψ(x) -Dψ(ȳ) T ⊙ Dψ(x) -Dψ(ȳ) T ⊙ Dψ(x) Dψ(ȳ) T ⊙ Dψ(ȳ) .
This implies

Aξ • ξ ≤ Bζ • ζ + 2e Kt ε (ψ(x) -ψ(ȳ)) ⊙ D 2 ψ(x)ξ • ξ -(ψ(x) -ψ(ȳ)) ⊙ D 2 ψ(ȳ)ζ • ζ + |Dψ(x)ξ -Dψ(ȳ)ζ| 2 for all ξ, ζ ∈ R 2 .
Combining the two viscosity inequalities and using the fact that |ψ(x) -

ψ(ȳ)| ≥ m ψ |x -ȳ|, we obtain η T 2 + Km 2 ψ e Kt |x -ȳ| 2 2ε ≤ce -x |p x| -ce -y |p ȳ| + e -2x px • e 1 -e -2y p ȳ • e 1 +αe -2x . p⊥ x ψ(x) ⊙ D 2 ψ(x) + Dψ(x) T Dψ(x) p⊥ x + 2e Kt ε ( Ĩ1 + Ĩ2 )
where Ĩ1 and Ĩ2 are defined respectively as I 1 and I 2 with p x replaced by px . Remarking that there exists a constant C > 0 such that

ce -x |p x| + e -2x px • e 1 + αe -2x p⊥ x |p x| ψ(x) ⊙ D 2 ψ(x) + Dψ(x) T Dψ(x) p⊥ x |p x| ≤ ce -x |p x| + e -2x p x • e 1 + Cα |D 2 ψ(x)| 2 + |Dψ(x)| 2 + |ψ(x)| 2 ≤ ce -x |p x| + e -2x p x • e 1 + 3M 2 ψ Cα and | Ĩ1 -I 1 | + | Ĩ2 -I 2 | ≤C p⊥ x -p ⊥ x ≤C px -p x |p x| + |p x| 1 |p x| - 1 |p x| ≤C px -p x δ 0 + |p x| -|p x| δ 0 ≤2C px -p x δ 0 ≤ 2C 2 α δ 0
and sending α → 0 (recall that x, ȳ lie in a compact domain), we get (4.41).

Lemma 4.5 (Estimate on I 1

). There exists a constant C 1 such that

(4.42) |I 1 | ≤ C 1 |x -y| 2
Proof. In order to prove (4.42), we write

|I 1 | |ψ(x) -ψ(ȳ))| ≤|(D 2 ψ(x) -D 2 ψ(ȳ))e -x p ⊥ x • e -x p ⊥ x | +|D 2 ψ(ȳ)(e -x -e -y ) p ⊥ x • e -x p ⊥ x | +|D 2 ψ(ȳ)e -y p ⊥ x -p ⊥ y • e -x p ⊥ x | +|D 2 ψ(ȳ)e -y p ⊥ y • (e -x -e -y ) p ⊥ x +|D 2 ψ(ȳ)e -y p ⊥ ȳ • e -y p ⊥ x -p ⊥ y |.
Thanks to (4.40) and max(|x|, |y|) ≤ 2, we have

|D 2 ψ(x) -D 2 ψ(ȳ)| ≤ M ψ |x -ȳ|, |e -x -e -y | ≤ e 2 |x -ȳ|.
We also have the following important estimate

p ⊥ x -p ⊥ ȳ ≤ p x -p ȳ |p x| + |p ȳ | 1 |p x| - 1 |p ȳ | ≤ p x -p ȳ |p x| + |p ȳ| -|p x| |p x| ≤2 p x -p ȳ |p x| ≤2 e Kt ε |Dψ(x) -Dψ(ȳ)||ψ(x) -ψ(ȳ)| e Kt ε m ψ |x -ȳ| ≤ 2M 2 ψ m ψ |x -ȳ|
where we have used the fact that |p x| ≥ e Kt ε m ψ |x -ȳ| (see (4.33)). This finally gives that there exists a constant C 1 (depending on m ψ and M ψ ) such that (4.42) holds true.

Using the fact that |p x|, |p ȳ | ≤ C e Kt ε |x -ȳ|, we can prove in a similar way the following lemma. Lemma 4.6 (Remaining estimates). There exist three positive constants C 2 , C 3 and C 4 such that

|I 2 | ≤ C 2 |x -ȳ| 2 , ce -x |p x| -ce -y |p ȳ | ≤ C 3 e Kt ε |x -ȳ| 2 , e -2x p x • e 1 -e -2y p ȳ • e 1 ≤ C 4 e Kt ε |x -ȳ| 2 .
Use now Lemmas 4.5 and 4.6 in order to derive from (4.41) the following inequality

η T 2 + Km ψ e Kt |x -ȳ| 2 2ε ≤ C e Kt ε |x -ȳ| 2 with C = C 1 + C 2 + C 3 + C 4 . Choosing K ≥ 2C
m ψ , we get a contradiction.

Construction of a classical solution

In this section, our main goal is to prove Theorem 1.6 which claims the existence and uniqueness of classical solutions under suitable assumptions on the initial data ū0 . Notice that assumptions (1.10) on the initial data imply in particular that (5.43) c + 2(ū 0 ) r (0) = 0.

To prove Theorem 1.6, we first construct a unique weak (viscosity) solution. We then prove gradient estimates from which it is not difficult to derive that the weak (viscosity) solution is in fact smooth; in particular, it thus satisfies the equation in a classical sense.

Barriers and Perron's method

Before constructing solutions of (1.2) submitted to the initial condition (1.5), we first construct appropriate barrier functions. Proposition 5.1 (Barriers for the Cauchy problem). Assume that ū0 ∈ W 2,∞ loc (0, +∞) and

(ū 0 ) r ∈ W 1,∞ (0, +∞) or κ ū0 ∈ L ∞ (0, +∞)
with ū0 such that (1.10) holds true. Then there exists a constant C > 0 such that ū± (t, r) = ū0 (r) ± Ct are respectively a super-and a sub-solution of (1.2),(1.5).

Proof. It is enough to prove that the following quantity is finite

C = sup r≥0 1 r F (r, (ū 0 ) r (r), (ū 0 ) rr (r)) = max( C1 , C2 ) with C1 = sup r∈[0,r0] | F (r, (ū 0 ) r (r), (ū 0 ) rr (r))| r , C2 = sup r∈[r0,+∞) | F (r, (ū 0 ) r (r)(x), (ū 0 ) rr (r))| r .
On one hand, thanks to (1.10) and the Lipschitz regularity of ū0 , we have C1 is finite. On the other hand, thanks to Lipschitz regularity and (ū 0 ) r ∈ W 1,∞ or κ ū0 ∈ L ∞ , C2 is also finite. The proof is now complete.

We now construct a viscosity solution for (1.2),(1.5); this is very classical with the results we have in hand, namely the strong comparison principle and the existence of barriers. However, we give a precise statement and a sketch of proof for the sake of completeness. Proposition 5.2 (Existence by Perron's method). Assume that ū0 ∈ C(0, +∞) and that there exists

u + (t, r) := ū0 (r) + f (t) resp. u -(t, r) := ū0 (r) -f (t)
for some continuous function f satisfying f (0) = 0, which are respectively a super-and a sub-solution of (

. Then, there exists a (continuous) viscosity solution ū of (1.2),(1.5) such that (1.8) holds true for some constant CT depending on f . Moreover ū is the unique viscosity solution of (

Proof. In view of Lemma 2.4, it is enough to construct a solution u of (2.13) satisfying (2.14) with u 0 (x) = ū0 (e x ). Consider the set

S = {v : (0, +∞) × R → R, sub-solution of (2.13) s.t. v ≤ u + } .
Remark that it is not empty since u -∈ S (where u ± (t, x) = ū± (t, r) with x = ln r). We now consider the upper envelope u of (t, r) → sup v∈S v(t, r). By Proposition 2.3, it is a sub-solution of (2.13). The following lemma derives from the general theory of viscosity solutions as presented in [START_REF] Crandall | User's guide to viscosity solutions of second order partial differential equations[END_REF] for instance.

Lemma 5.3. The lower envelope u * of u is a super-solution of (2.13).

We recall that the proof of this lemma proceeds by contradiction and consists in constructing a so-called bump function around the point the function u * is not a super-solution of the equation. The contradiction comes from the maximality of u in S.

Since for all v ∈ S,

u 0 (x) -f (t) ≤ v ≤ u 0 (x) + f (t),
with f (0) = 0 we conclude that u 0 (x) = u * (0, x) = u(0, x) .

If ū satisfies (1.8), we use the comparison principle and get u ≤ u * in (0, T ) × R for all T > 0. Since u * ≤ u by construction, we deduce that u = u * is a solution of (2.13). The comparison principle also ensures that the solution we constructed is unique. The proof of Proposition 5.2 is now complete.

Gradient estimates

In this subsection, we derive gradient estimates for a viscosity solution ū of (1.2) satisfying (1.8).

Proposition 5.4 (Lipschitz estimates). Consider a globally Lipschitz continuous function ū0 . We denote by L 0 > 0 and L 1 > 0 such that for all r > 0,

-L 0 ≤ (ū 0 ) r (r) ≤ L 1 .
Let ū be a viscosity solution ū of (1.2),(1.5) satisfying (1.8). Then ū is also Lipschitz continuous in space: ∀t > 0, ∀r ≥ 0, (5.44)

   -max(1, L 0 ) ≤ ūr (t, r) ≤ L 1 if c ≥ 0 -L 0 ≤ ūr (t, r) ≤ max(1, L 1 ) if c ≤ 0 Moreover, if ū0 ∈ W 2,∞ loc (0, +∞) with (ū 0 ) r ∈ W 1,∞ (0, +∞) and κ ū0 ∈ L ∞ (0, +∞)
and (1.10) holds true, then ū is C-Lipschitz continuous with respect to t for all r > 0 where C denotes the constant appearing in Proposition 5.1.

Proof.

Step 1: gradient estimates Proving (5.44) for c ≥ 0 is equivalent to prove that the solution u of (2.13) satisfies the following gradient estimate: ∀t > 0, ∀x ∈ R,

(5.45) -L0 e x ≤ u x (t, x) ≤ L 1 e x
where L0 = max(1, L 0 ). We will prove each inequality separately. Since ū is sublinear, there exists

C u > 0 such that for all x ∈ R |u(t, x)| ≤ C u (1 + e x ).
Eq. ( 5.44) is equivalent to prove M 0 = sup t∈(0,T ),x≤y∈R u(t, x) + L0 e x -u(t, y) -L0 e y ≤ 0

M 1 = sup t∈(0,T ),x≥y∈R {u(t, x) -L 1 e x -u(t, y) + L 1 e y } ≤ 0.
We first prove that M 0 ≤ 0. We argue by contradiction by assuming that M 0 > 0 and we exhibit a contradiction. The following supremum

M 0 α = sup t∈(0,T ),x≤y∈R u(t, x) -u(t, y) + L0 e x -L0 e y - α 2 x 2 - α 2 y 2 - η T -t
is also positive for α and η small enough.

Using the fact that, by assumption on ū0 ,

(5.46) u(t, x) -u(t, y) + L0 e x -L0 e y ≤ u(t, x) -u 0 (x) + u 0 (x) -u 0 (y) + u 0 (y) -u(t, y) + L0 e x -L0 e y ≤ 2C 1
and the fact that -α 2 x 2 -α 2 y 2 → -∞ as x → ±∞ or y → ±∞, we deduce that the supremum is achieved at a point (t, x, y) such that t ∈ (0, T ) and x > y.

Moreover, we deduce using (5.46) and the fact that M α > 0, that there exists a constant C 0 := 4C 1 such that x and y satisfy the following inequality

αx 2 + αy 2 ≤ C 0 .
Thanks to Jensen-Ishii's Lemma (see e.g. [START_REF] Crandall | User's guide to viscosity solutions of second order partial differential equations[END_REF]), we conclude that there exist a, b, X, Y ∈ R such that

a ≤ ce -x 1 + (-L0 e x + αx) 2 + e -2x (-L0 e x + αx) + e -2x X -L0 e x + α 1 + (-L0 e x + αx) 2 , b ≥ ce -y 1 + ( L0 e y + αy) 2 -e -2y ( L0 e y + αy) + e -2y Y -L0 e y -α 1 + ( L0 e x + αy) 2 , a -b = η (T -t) 2 , X 0 0 -Y ≤ 0.
Subtracting the viscosity inequalities and using the last line yield η T 2 ≤ce -x 1 + ( L0 e x -αx) 2 -ce -y 1 + ( L0 e y + αy) 2 + αe -2x (x + 1) + αe -2y (y + 1)

-L0 e -x + L0 e -y -L0 e -x 1 + ( L0 e x -αx) 2 + L0 e y 1 + ( L0 e x + αy) 2 Using the fact that the functions z → √ 1 + z 2 and z → 1 1+z 2 are 1-Lipschitz, we deduce that η T 2 ≤ce -x 1 + L2 0 e 2x -ce -y 1 + L2 0 e 2y + e Remarking that the function z → e -z ((|c| + L0 )|z| + ze -z + e -z ) is bounded from above by a constant C 3 , we have

(5.47) η T 2 ≤ 2C 3 α + g(x) -g(y)
where

g(x) = e -x c 1 + L2 0 e 2x -L0 e -x - L0 e -x
1 + L2 0 e 2x . Case A: c ≥ 0 We now rewrite g in the following way

g(x) =c e -2x + L2 0 -L0 e -x - L0 e x + L2 0 e 3x = c 2 e -2x (1 -L2 0 ) -L2 0 e -2x c e -2x + L2 0 + L0 e -x - L0 e x + L2 0 e 3x = c 2 (1 -L2 0 ) c e 2x + L2 0 e 4x + L0 e x - L2 0 e 2x + L2 0 e 4x + L0 e x - L0 e x + L2 0 e 3x
and use the fact that L0 ≥ 1 to deduce that g is non-decreasing. Hence, we finally get

η T 2 ≤ 2C 3 α
which is absurd for α small enough.

In order to prove that M 1 ≤ 0, we proceed as before and we obtain (5.47) where

g(x) = c e -2x + L 2 1 + L 1 e -x +
L 1 e x + L 2 1 e 3x . Remarking that g is decreasing permits us to conclude in this case. Case B: c ≤ 0 We simply notice that the equation is not changed if we change (w, c) in (-w, -c).

Step 2: Lipschitz in time estimates It remains to prove that ū is C-Lipschitz continuous with respect to t under the additional compatibility condition (1.10). To do so, we fix h > 0 and we consider the following functions: ūh (t, r) = ū(t + h, r) -Ch and ūh (t, r) = ū(t + h, r) + Ch.

Remark that ūh and ūh satisfy (1.2). Moreover, Proposition 5.1 implies that ūh (0, r) ≤ ū0 (r) ≤ ūh (0, r).

Thanks to the comparison principle, we conclude that ūh ≤ ū ≤ ūh in [0, +∞)× (0, +∞); since h is arbitrary, we thus conclude that ū is C-Lipschitz continuous with respect to t. The proof of Proposition 5.4 is now complete.

Proof of Theorem 1.6

It is now easy to derive Theorem 1.6 from Propositions 5.2 and 5.4.

Proof of Theorem 1.6. Consider the viscosity solution ū given by Proposition 5.2 with f (t) = Ct where the constant C is given in the barrier presented in Proposition 5.1.

This function is continuous. Moreover, thanks to Proposition 5.4, ūt and ūr are bounded in the viscosity sense; hence u is Lipschitz continuous. In particular, there exists a set Ñ ⊂ (0, +∞) × (0, +∞) of null measure such that for all (t, r) / ∈ Ñ , ū is differentiable at (t, r). Thanks to the equation (5.48) ūt -a(r, ūr )ū rr = f (r, ūr ) for (t, r) ∈ (0, +∞) × (0, +∞) with

a(r, ūr ) = 1 1 + r 2 ū2 r , f (r, ūr ) = 1 r c 1 + r 2 ū2 r + ūr 2 + r 2 ū2 r 1 + r 2 ū2
r we also have that ūrr is locally bounded in the viscosity sense. This implies that ū is locally C 1,1 with respect to r, and in particular, we derive from Alexandrov's theorem [6, p. 242] that for all t > 0 there exists a set N t ⊂ [0, +∞) of null measure such that for all r / ∈ N t , ū(t, •) is twice differentiable with respect to r, i.e. there exist p, A ∈ R such that for ρ in a neighborhood of r, we have

(5.49) ū(t, ρ) = ū(t, r) + p(ρ -r) + 1 2 A(ρ -r) 2 + o((ρ -r) 2 ).
From Ñ and {N t } t>0 , we can construct a set N ⊂ (0; +∞) × (0; +∞) of null measure such that for all (t, r) / ∈ N , ū is differentiable with respect to time and space at (t, r) and there exists A ∈ R such that (5.49) holds true. We conclude that ū(s, ρ) = ū(t, r)

+ ∂ t ū(t, r)(s -t) + ∂ r ū(t, r)(ρ -r) + 1 2 A(ρ -r) 2 + o((ρ -r) 2 ) + o(s -t).
In particular, (5.48) holds true for (t, r) / ∈ N . We deduce from the previous discussion that ūt -ūrr = f ∈ L ∞ loc holds true almost everywhere, and thus in the sense of distributions. From the standard interior estimates for parabolic equations, we get that ū ∈ W 2,1;p loc for any 1 < p < +∞. Then from the Sobolev embedding (see Lemma 3.3 in [15]), we get that for p > 3, and α = 1 -3/p, we have ūr ∈ C α,α/2 loc . We now use that (5.48) holds almost everywhere. Therefore we can apply the standard interior Schauder theory (in Hölder spaces) for parabolic equations. This shows that ū ∈ C 2+α,1+α/2 loc . Bootstrapping, we finally get that ū ∈ C ∞ loc , which ends the proof of the theorem.

Construction of a general weak (viscosity) solution

The main goal of this section is to prove Theorem 1.4. We start with general barriers, Hölder estimates in time and finally an approximation argument.

Proposition 6.1 (Barriers for the Cauchy problem without the Compatibility Condition). Let ū0 ∈ W 2,∞ loc (0, +∞) be such that there exists C 0 such that (6.50)

|(ū 0 ) r | ≤ C 0 and |κ ū0 | ≤ C 0 .
Then, there exists a constant C > 0 (depending only on C 0 ) such that for any function B : [0, T ] → R with B(0) = 0 and B ′ ≥ C(1 + Ct), ū± (t, r) = ū0 (r) ± Ct r ± B(t) are respectively a super-and a sub-solution of (1.2),(1.5).

Proof. We only do the proof for the super-solution since it is similar (and even simpler) for the sub-solution. We also do the proof only in the case c ≥ 0, noticing that the equation is unchanged if we replace (w, c) with (-w, -c).

It is convenient to write A for Ct and do the computations with this function. Since |κ ū0 | ≤ C 0 , we have

r(ū 0 ) rr (1 + (r(ū 0 ) r ) 2 ) 3 2 + (ū 0 ) r 2 + (r(ū 0 ) r ) 2 (1 + (r(ū 0 ) r ) 2 ) 3 2 ≤ C 0 . Subcase
) ≤(c + 2C 0 + 4c 1 ) + A( c r - 1 2r 2 ) + cC 0 r + 16c 1 C 0 r ≤(c + 2C 0 + 4c 1 ) + (dA + cC 0 + 16c 1 C 0 )r
where for the last line we have used the fact that we can find d > 0 (only depending on c) such that c r -1 2r 2 ≤ dr for all r > 0. We finally get the desired result taking C ≥ max(c + 2C 0 + 4c 1 , cC 0 + 16c 1 C 0 , d). The proof is now complete. Proposition 6.2 (Time Hölder estimate -(I)). Let ū0 ∈ W 2,∞ loc (0, +∞) satisfying (6.50). Let ū be a solution of (1.2),(1.5) satisfying (1.8). If ū is L 0 -Lipschitz continuous with respect to the variable r, then there exists a constant C, depending only on C 0 and L 0 such that

|ū(t, r) -ū0 (r)| ≤ C √ t + B(t)
where B is defined in Proposition 6.1.

Remark 6.3. Let us note that in Proposition 6.1, we can choose B(t) = Ct(1 + C 2 t). Hence, we deduce from Proposition 6.2 that there exists C > 0 such that for all t ∈ [0, 1], (6.51)

|ū(t, r) -ū0 (r)| ≤ C √ t.
Proof. Let r 0 > 0. Using Proposition 6.1 and the comparison principle, we deduce that there exists a constant C and a function B such that

|ū(t, r 0 ) -ū0 (r 0 )| ≤ C t r 0 + B(t).
Since ū is L 0 -Lipschitz continuous in r, we also have

|ū(t, 0) -ū(t, r 0 )| ≤ L 0 r 0 and |ū 0 (0) -ū0 (r 0 )| ≤ C 0 r 0 .
Combining the previous inequalities, we get that

|ū(t, 0) -ū0 (0)| ≤ (L 0 + C 0 )r 0 + C t r 0 + B(t).
Taking the minimum over r 0 in the right hand side, we get that

|ū(t, 0) -ū0 (0)| ≤ C 1 √ t + B(t) with C 1 := 2 (C 0 + L 0 ) C. We finally deduce that |ū(t, r) -ū0 (r)| ≤ min C t r + B(t), C 1 √ t + B(t) + (L 0 + C 0 )r .
The desired result is obtained by remarking that, if r ≤

√ t, then C 1 √ t + B(t) + (L 0 + C 0 )r ≤ (C 1 + L 0 + C 0 ) √ t + B(t), while if r ≥ √ t, then C t r + B(t) ≤ C√ t + B(t).
The next proposition asserts that the previous proposition is still true if we do not assume that ū is Lipschitz continuous with respect to r. Proposition 6.4 (Existence and time Hölder estimate -(II)). Let ū0 ∈ W 2,∞ loc (0, +∞) satisfying (6.50). Then there exists a solution ū of (1.2),(1.5) satisfying (1.8). Moreover there exists a constant C, depending only on C 0 such that

|ū(t, r) -ū0 (r)| ≤ C √ t + B(t)
where B is defined in Proposition 6.1, and there exists a constant L 0 (only depending on C 0 ) such that

|ū(t, r + ρ) -ū(t, r)| ≤ L 0 |ρ|.
Proof. The initial datum is approximated with a sequence of initial data satisfying (6.50) and the compatibility condition (1.10); passing to the limit will give the desired result. We can assume without loss of generality that C 0 ≥ c 2 . Then we consider

ūε 0 = Ψ ε U 0 + (1 -Ψ ε )ū 0 where U 0 ∈ C ∞ is such that (6.52) U 0 (0) = ū0 (0), (U 0 ) r (0) = - c 2 , |(U 0 ) r | ≤ C 0 , r|(U 0 ) rr | ≤ C 0 for r ≤ 2 and Ψ ε (r) = Ψ 1 r ε where the non-increasing function Ψ 1 ∈ C ∞ satisfies Ψ 1 = 1 if r ≤ 1, 0 if r ≥ 2.
Claim 6.5. The initial condition ūε 0 satisfies the compatibility condition (1.10) and (6.50) for some constant C 0 which does not depend on ε.

Let u ε denote the unique solution of (1.2) with initial condition ūε 0 given by Proposition 5.2, using the barrier (Proposition 6.1) provided by the Claim 6.5. In particular, u ε satisfies (1.8) for some constant Cε depending on ε. Using Proposition 5.4, we deduce that ūε is L 0 -Lipschitz continuous with L 0 := max(1, C 0 ). Then Proposition 6.2 can be applied to obtain the existence of a constant C (depending only on C 0 , because L 0 now depends on C 0 ) such that for all ε

|ū ε (t, r) -ūε 0 (r)| ≤ C √ t + B(t).
Taking ε → 0 and using the stability of the solution and the uniqueness of (1.2),(1.5), we finally deduce the desired result.

We now prove the claim.

Proof of Claim 6.5. We have

(ū ε 0 ) r = (Ψ ε ) r (U 0 -ū0 ) + Ψ ε (U 0 ) r + (1 -Ψ ε )(u 0 ) r .
Hence, since (Ψ ε ) r (0) = 0 and Ψ ε (0) = 1, we get

(ū ε 0 ) r (0) = (U 0 ) r (0) = - c 2
which means that ūε 0 satisfies (5.43). Using the fact that ūε 0 ∈ W 2,∞ loc and (6.52), we get (1.10). Since U 0 (0) = ū0 (0) and U 0 and ū0 are C 0 -Lipschitz continuous, we have

|U 0 (r) -ū0 (r)| ≤ 2C 0 r. Let c 1 denote sup ρ≥0 ρ|(Ψ 1 ) r (ρ)| < +∞. We then have |(Ψ ε ) r (U 0 -ū0 )| ≤ 2C 0 r ε (Ψ 1 ) r r ε ≤ 2C 0 c 1 . Hence |(ū ε 0 ) r | ≤ 2C 0 (c 1 + 1
) rr (1 + (r(ū ε 0 ) r ) 2 ) 3 2
.

If r > 2, then ūε 0 = ū0 and the estimate follows from (6.50). If r ≤ 2, it is enough to estimate r(ū ε 0 ) rr . We have The reverse inequality is obtained in the same way. This implies (1.9). The proof is now complete.

r(ū ε 0 ) rr = r(Ψ ε ) rr (U 0 -ū0 ) + 2r(Ψ ε ) r ((U 0 ) r -(ū 0 ) r ) + rΨ ε (U 0 ) rr + r(1 -Ψ ε )(ū 0 )
A Appendix: proofs of technical lemmas Study of (4.32). It is convenient to use the following notation: ψ(x, θ) = (φ 1 (x), φ 2 (x)e iθ ). We first write (4.32) in terms of φ i : We choose ε ≤ 1 and we remark that such an inequality is clear if x ≤ -1 or x ≥ 2. Through a Taylor expansion and using the fact that φ 2 (y) ≥ 1, this reduces to check that min( inf For x far from 0, a simple computation shows that φ ′ 2 (x) ≥ ι(x)e x (for x ≥ 0) and this permits us to conclude. For x in a neighborhood of 0, φ ′ 1 (x) = 1 + o(1) and φ ′ 2 (x) = O(x) and we can conclude in this case too. In [-1, 2]\[0, 1], the conclusion is straightforward.

Study of (4.33). We next write (4.33) in terms of φ i {(φ ′ 1 (x)) 2 + (φ ′ 2 (x)) 2 } ≥ 2m ψ .

The same reasoning as above applies here too.

Reduction to the case: |(x, θ) -(y, σ)| ≤ ε. It remains to prove that for ε > 0 given, we can find δ 0 > 0 such that, as soon as |ψ(x, θ) -ψ(y, σ)| ≤ δ 0 and |θ -σ| ≤ π 2 , then |(x, θ) -(y, σ)| ≤ ε. We argue by contradiction by assuming that there exists ε 0 > 0 and two sequences (x n , θ n ) and (y n , σ n ) such that

|θ n -σ n | ≤ π 2 |x n -y n | + |θ n -σ n | ≥ ε 0 φ 1 (x n ) -φ 1 (y n ) → 0 cos(θ n -σ n )φ 2 (x n ) -φ 2 (y n ) → 0 φ 2 (x n ) sin(θ n -σ n ) → 0
as n → ∞. Since φ 2 is bounded from below by 1, we deduce that sin(θ n -σ n ) → 0. Up to a subsequence, we can assume that θ n -σ n → δ and we thus deduce that δ = 0. Hence, |x n -y n | ≥ ε0 2 for large n's. Thanks to a Taylor expansion in θ n -σ n , we can also get that φ 2 (x n ) -φ 2 (y n ) → 0. Because |x n -y n | ≥ ε0 2 , we then get that x n and y n remain in a bounded interval. We can thus assume that x n → x * and y n → y * . Finally, we have φ i (x * ) = φ i (y * ) for i = 1, 2 and |x * -y * | ≥ ε0 2 which is impossible. The proof of the lemma is now complete.

Proof of Lemma 4.2. The second estimate is satisfied if C 2 is chosen such that

C 2 ≥ sup r>0 r -r - π 3 2 +
.

We now prove the first estimate. We distinguish three cases: where L u0 is the Lipschitz constant of ū0 . Hence, C 2 is chosen such that

C 2 ≥ sup r>0 L u0 r - 1 4ε r 2 .
The proof is now complete.

Figure 1 :

 1 Figure 1: Motion of the spiral

Figure 2 :

 2 Figure 2: Examples of non spiral initial data

Lemma 3 . 4 (

 34 Consequence of viscosity inequalities).(3.21) η (T -t) 2 + Ke Kt (x -y) 2 2ε ≤ e -x b(e -x (p + αx), p + αx) -e -y b(e -y p, p) + e -2x σ 2 ∞ α + e Kt ε (e -x σ(p + αx) -e -y σ(p)) 2

  -x α((|c| + L0 )|x| + xe -x + e -x ) + αe -y ((|c| + L0 )|y| + ye -y + e -y ) -L0 e -x + L0 e -y -L0 e -x 1 + ( L0 e x ) 2 + L0 e y 1 + ( L0 e x ) 2

4 . 2 -

 42 rr . Moreover there exists a constant c 2 (depending only on C 0 ) such that for all r ≤ 2, r|(ū0 ) rr | ≤ c 2 . Let c 3 denote sup ρ≥0 ρ 2 |(Ψ 1 ) rr (ρ)| < +∞. We then have r|(Ψ ε ) rr (U 0 -ū0 )| ≤ 2C 0 r 2 ε 2 (Ψ 1 ) rr r ε ≤ 2C 0 c 3 .We finally deduce that for r ≤ 2,|r(ū ε 0 ) rr | ≤ 2C 0 c 3 + 4C 0 c 1 + C 0 + c 2which proves that ūε 0 satisfies (6.50) with a constant C0 = 2C 0 c 3 + 4C 0 c 1 + C 0 + c 2 depending only on C 0 .We now turn to the proof of Theorem 1.Proof of Theorem 1.4. The existence of ū and its Lipschitz continuity with respect to r follows from Proposition 6.4. The uniqueness (and continuity) of ū follows from the comparison principle (Theorem 1.2). Let us now prove that ū is 1 Hölder continuous with respect to time. By Remark 6.3, there exists a constant C such that for h ≤ 1 |ū(h, r) -ū0 (r)| ≤ C √ h. with C given in (6.51). Proceeding as in Step 2 of the proof of Proposition 5.4, we get for 0 ≤ h ≤ 1: ū(t + h, r) -ū(t, r) ≤ C √ h.

Proof of Lemma 4 . 1 .

 41 We look for ψ under the following form: for x, θ ∈ R,ψ(x, θ) = (1 -ι(x))(x, e iθ ) + ι(x)(0, e x+iθ ) where ι : R → R is non-decreasing, smooth (C ∞ ) and such that ι(x) = 0 if x ≤ 0 and ι(x) = 1 if x ≥ 1.Remark that (4.30) and (4.31) are readily satisfied.It remains to prove (4.32) and (4.33). Let us first find ε > 0 and m ψ > 0 such that for all x, y, θ, σ such that |(x, θ) -(y, σ)| ≤ ε, we have (4.32) and (4.33).

|φ 1

 1 (x) -φ 1 (y)| + |φ 2 (x) -φ 2 (y) cos(θ -σ)| + φ 2 (y)| sin(θ -σ)| ≥ m ψ (|x -y| + |θ -σ|)(we used a different norm in R 3 and m ψ is changed accordingly). It is enough to prove|φ 1 (x) -φ 1 (y)| + |φ 2 (x) -φ 2 (y)| + φ 2 (y)(| sin | -1 + cos)(θ -σ)≥ m ψ (|x -y| + |θ -σ|).

x∈(- 1 , 2 )

 12 (|φ ′ 1 (x)| + |φ ′ 2 (x)|), 1) ≥ 2m ψ which reduces to inf x∈(-1,2) {|φ ′ 1 (x)| + |φ ′ 2 (x)|} > 0.

(A. 1 )

 1 |Φ(x, y) + φ ′ 2 (x)φ 2 (y)(1 -cos(θ -σ))| + |φ 2 (x)φ 2 (y)|| sin(θ -σ)| ≥ m ψ (|x -y| + |θ -σ|) where Φ(x, y) = φ ′ 1 (x)(φ 1 (x) -φ 1 (y)) + φ ′ 2 (x)(φ 2 (x) -φ 2 (y)). Once again, the previous inequality is true for x / ∈ (-1, 2) and for x ∈ (-1, 2), we choose m ψ such that inf x∈(0,1)

Case 1 : 2 ≤

 12 x ≤ 1 and y ≤ 1. In this case, e x and e y are bounded and the definition of u 0 in terms of the Lipschitz continuous function ū0 implies|u 0 (x) -u 0 (y)| ≤ C for some constant C > 0.Case 2: (x ≤ 1 and y ≥ 1) or (x ≥ 1 and y ≤ 1). The two cases can be treated similarly and we assume here that x ≤ 1 and y ≥ 1. In that case ψ(x, θ) = (a, b) with a ∈ R and b ∈ C with |b| ≤ e (see (4.31)) and ψ(y, σ) = (0, e y+iσ ). Moreover, there exists a constant C such that|u 0 (x) -u 0 (y)| ≤ C(1 + e y ).We also have|ψ(x, θ) -ψ(y, σ)| = a 2 + |e y+iσ -b| 2 ≥|e y+iσ -b| ≥e y -|b| ≥e y -e.Hence,|u 0 (x) -u 0 (y)| ≤ C(1 + e) + C(e y -e) ≤ C(1 + e) + C 2 εe -Kt + e Kt 4ε (e y -e) C(1 + e + C) + e Kt 4ε |ψ(x, θ) -ψ(y, σ)| 2which gives the desired estimate. Case 3: x ≥ 1 and y ≥ 1. In this case, |ψ(x, θ) -ψ(y, σ)| = |e x+iθ -e y+iσ | ≥ |e x -e y | and |u 0 (x) -u 0 (y)| ≤ L u0 |e x -e y |,

  These inequalities are exactly(3.22) and (3.23). Moreover a, b satisfy the following inequality

		2y p + e -2y B 1 + p 2
	where	p =	x -y ε	e Kt .

  2.1: A r ≤ 2. In this sub-case, we get F (r, ū+ r , ū+ rr) ≤ (3c + 2C 0 + 4c 1 ) + r(cC 0 + 16c 1 C 0 )and we obtain the desired result taking C ≥ max(3c + 2C 0 + 4c 1 , cC 0 + 16c 1 C 0 ).

	Subcase 2.2: A r ≥ 2. In this subcase, |ρ -1| A r ≥ 1 and
	(ρ -1) 2 A r 1 + (ρ -1) 2 A 2 r	2 ≥	1 2
	and thus
	F (r, ū+ r , ū+ rr

  ). Let us now obtain an estimate on κ ūε 0 . Using the previous bound, we only have to estimate r(ū ε 0

Université Paris-Dauphine, CEREMADE, UMR CNRS 7534, place de Lattre de Tassigny, 75775 Paris cedex 16

Université Paris-Est, CERMICS, Ecole des Ponts ParisTech, 6-8 avenue Blaise Pascal, 77455 Marne-la-Vallée Cedex 2, France

Acknowledgements. The authors would like to thank Guy Barles for fruitful discussions during the preparation of this article.

Since |u r | ≤ C 0 , there exists c 1 > 0 such that |r(ū 0 ) rr | ≤ c 1 (1 + (r(ū 0 ) r ) 2 ) 3 2 .

We then have F (r, ū+ r , ū+ rr ) =c 1 + (rū + r ) 2 + ūr

Using (6.50), we can write

We now set ρ such that r(ū 0 ) r = ρ A r and distinguish two cases: Case 1: 1 2 < ρ < 2. In this case, F (r, ū+ r , ū+ rr ) ≤c(1

where for the second line, we have used the fact that for a, b ≥ 0, (a + b) 3 ≤ 4(a 3 + b 3 ). On the other hand, we have rū

) we get the desired result in this case.

Case 2: ρ ≤ 1 2 or ρ ≥ 2. In this case We distinguish two sub-cases:


Guillaume Moroz

Boris Aronov
email: aronov@poly.edu.

Computing the Distance between Piecewise-Linear Bivariate Functions *

We consider the problem of computing the distance between two piecewise-linear bivariate functions f and g defined over a common domain M . We focus on the distance induced by

If f is defined by linear interpolation over a triangulation of M with n triangles, while g is defined over another such triangulation, the obvious naïve algorithm requires Θ(n 2 ) arithmetic operations to compute this distance. We show that it is possible to compute it in O(n log 4 n) arithmetic operations, by reducing the problem to multi-point evaluation of a certain type of polynomials.

We also present an application to terrain matching.

Introduction and problem statement

In this paper we use a novel combination of tools from computational geometry and computer algebra to speed up a computation of • 2 -norm distance between two bivariate piecewise-linear functions. Algebraic tools have already been used in other recent work in computational geometry, to seemingly defy "obvious" lower bounds: for example, Ajwani, Ray, Seidel, and Tiwary [START_REF] Ajwani | On computing the centroid of the vertices of an arrangement and related problems[END_REF] use algebraic tools to compute the centroid of all vertices in an arrangement of n lines in the plane, without explicitly computing the vertices.

We feel that working on computational geometry problems using a combination of traditional and algebraic tools expands the repertoire of questions that can be approached and answered satisfactorily. Employing such combinations of methods expands the horizon of solvable problems. Indeed, in a significant recent development, several breakthrough results have been obtained by applying algebraic methods to problems of combinatorial geometry: Guth and Katz's recent work on the joints problem [START_REF] Guth | Algebraic methods in discrete analogs of the Kakeya problem[END_REF] and on the Erdős distinct distance problem [START_REF] Guth | On the Erdős distinct distance problem in the plane[END_REF] has triggered an avalanche of activity; see, for example, [START_REF] Gy | On lines, joints, and incidences in three dimensions[END_REF][START_REF] Gy | Incidences in three dimensions and distinct distances in the plane[END_REF][START_REF] Kaplan | Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique[END_REF][START_REF] Matoušek | The dawn of an algebraic era in discrete geometry?[END_REF][START_REF] Quilodrán | The joints problem in R n[END_REF][START_REF] Solymosi | An incidence theorem in higher dimensions[END_REF][START_REF] Haim | On lines and joints[END_REF]. It appears that the use of algebraic tools in geometry (both combinatorial and computational) allows one to approach problems inaccessible by more traditional methods. The present work is just one step in that direction.

Background and previous work

In [START_REF] Agarwal | Computing similarity between piecewise-linear functions[END_REF], Aronov et al. considered a quite common object in computational geometry and geographical information systems (GIS): that of a "terrain." A terrain is (the graph of) a bivariate function over some planar domain, say, a rectangle or a square. It is often used to model geographic terrains, e.g., elevation in a mountainous locale, but can also be applied to storing any two-dimensional data sets, such as precipitation or snow cover data. A common (though by no means the only) way of interpolating and representing discrete twodimensional data is a triangulated irregular network (TIN ): the values of a bivariate function are given at discrete points in, say, the unit square. The square is triangulated, using data points as vertices. The function is then linearly interpolated over each triangle. This produces a piecewiselinear approximation of the "real" (and unknown) function.

The problem raised in [START_REF] Agarwal | Computing similarity between piecewise-linear functions[END_REF] was that of comparing two terrains over the same domain, say, the unit square, but given over two unrelated triangulations. One could imagine comparing the outcome of two different ways of measuring the same data, or finding correlation between, say, the elevation and the snow cover over the same geographic region. The focus of that work was on identifying linear dependence between the two functions or terrains. Three natural distance measures between the two functions were considered and several algorithms presented for computing such a distance and optimizing it, subject to vertical translation and scaling. The only observation made for the • 2 norm (see the definitions below) in [START_REF] Agarwal | Computing similarity between piecewise-linear functions[END_REF] is that, if the two terrains share a triangulation, both the distance computation and the optimization problem can be solved easily in linear time, while it appears that in general quadratic time seems to be needed to deal with the case of arbitrarily overlapping triangulations. The substance of the current work is disproving this assertion and describing a near-linear-time algorithm for both problems.

Problem statement and results Given bivariate functions f, g : M → R, one can naturally define a distance between them as

f -g 2 = M (f (x, y) -g(x, y)) 2 dxdy 1/2 .
Expanding the expression under the integral, we obtain (f -g) 2 = f 2 -2 f g + g 2 . If the two functions are piecewise linear, defined over different triangulations of M , only the middle term presents a problem for efficient computation. Thus, in the bulk of the paper we will focus on the computation of f g, showing the following:

Theorem 1.1. Given piecewise-linear functions f and g defined over different triangulations of the same domain M , with n triangles each, M f (x, y)g(x, y)dxdy can be computed using O(n log 4 n) arithmetic operations.

Armed with this result, as already mentioned, we can quickly compute f -g 2 :

Theorem 1.2. Given piecewise-linear functions f and g defined over different triangulations of the same domain M , with n triangles each, f -g 2 can be computed using O(n log 4 n) arithmetic operations.

Naïvely, the integral in Theorem 1.1 can be expressed as a sum of integrals over each cell appearing in the overlay of the two triangulations of f and g. Unfortunately, this overlay has a quadratic number of cells, in the worst case. The main idea of our algorithm is to reduce the computation of the integral to double sums of algebraic functions over grids, which allows us tu use fast multi-point evaluation algorithms.

The paper is organized as follows. In section 2, we will show how the integral of a function over a convex polygon can be expressed as a sum of elementary algebraic functions over its vertices. Applying the process to a convex decomposition of a region M expresses the value of M f g as a summation over the vertices of the decomposition. Then, in section 3, we show how the integral over the overlay of the two triangulations can be reduced to a sum of elementary functions over pairs of edges, plus some additional terms computable in linear time. In section 4, we use the bipartite clique decomposition to arrange the pairs of edges in complete grids of fairly rigid form. Finally, in section 5, we use a fast multi-point evaluation algorithm to compute the sums over each grid, completing the description of our method.

How to integrate over a convex subdivision

Consider a bivariate function h defined over a convex polygon C in the plane. To simplify our presentation and without loss of generality, we assume that all vertices of C lie to the right of the y-axis. For a vertex p of C we refer to the lines supporting the edges of C incident to p as L(p, C) (the one with higher slope) and U (p, C) (the one with lower slope); to the left of p, L(p, C) is below

U (p, C). Let L(p, C) : y = y l (p, C) + s l (p, C)x, and
U (p, C) : y = y u (p, C) + s u (p, C)x.
We omit the explicit dependence on C and/or p whenever it causes no confusion. Define

δ(p, C) = -1 if C is above both L(p, C) and U (p, C), or below both of them, +1 if C is below U (p, C) and above U (p, C), or vice versa.
Finally, put

T (p, C, h) := δ(p, C) xp j x=0 yu(p,C)+su(p,C)x y=y l (p,C)+s l (p,C)x h(x, y)dxdy.
In words, T is the signed integral of h over the triangle T p delimited by the y-axis, L(p, C), and

U (p, C). p R t 1 t 2 p L b 1 b 2 C T R T L Figure 1: An illustration of the proof of Lemma 2.1. T R is dotted; T L is dashed; A T is lightly shaded.
With the above notation, we express the integral of h over C in a convenient way as a sum of terms associated with its vertices: Lemma 2.1. Let C be a convex polygon with vertices p 1 , ..., p k , and h a bivariate function. Then

C h(x, y)dxdy = k j=1 T (p j , C, h). (1)
Proof. Partition the vertices of C into four subsets V L , V R , V T , and V B as follows. To each vertex p, we associate the triangle T p as defined above. Put T L := T p L and T R := T p R . Since C is convex, so for all i, line t i t i+1 (resp., b i b i+1 ) is below the line t i-1 t i (resp., above the line b i-1 b i ) left of C. Thus, the triangles T t , t ∈ V T , (resp., T b , for b ∈ V B ) do not overlap. Let A T = t∈V T T p and A B = b∈V B T b . By construction we have

V L := {p L } (resp., V R := {p R })
A T ∪ A B = (T L ∪ T R ) \ C and A T ∩ A B = T L ∩ T R .
Since C ⊂ T L ∪ T R , the first equality, written in terms of characteristic functions, gives

1 A T + 1 A B -1 A T ∩A B = 1 T L + 1 T R -1 T L ∩T R -1 C ,
which can be simplified, using the second equality, to yield, as promised

1 A T + 1 A B = 1 T L + 1 T R -1 C .
We now consider a convex subdivision C of some bounded region M in the plane, with each cell C associated with its own bivariate function h C , thereby defining a function h over all of M (as it does not affect the value of the integral, the functions h C need not agree along the common boundaries of adjacent cells). By summing eq. ( 1) over the cells C of C, we can compute M h(x, y)dxdy:

Corollary 2.2. M h(x, y)dxdy = cell C ∈ C C h C (x, y)dxdy = cell C ∈ C C adjacent to p T (p, C, h C ).
(2)

One of the advantages of the formulation in eq. ( 2) for our application is that an individual integral under the sum can be expressed as a rational function when h C is a bivariate polynomial. x i y j dxdy = P i,j (y l , y u , s l , s u ) (s u -s l ) i+j+1 , where P i,j is a polynomial of total degree i + 2j + 2.

Proof. Let Q i,j (u, v, x) be the only polynomial such that ∂Q i,j ∂x = x i (u + vx) j and Q i,j (u, v, 0) = 0 for all u, v ∈ R. In particular, Q i,j has total degree i + 2j + 1, its degree in x is i + j + 1, and the coefficient of

x i+j+1 in Q i,j is 1 i+j+1 v j . Now xp x=0 yu+sux y=y l +s l x x i y j dxdy = xp x=0 1 j + 1 (x i (y u + s u x) j+1 -x i (y l + s l x) j+1 )dx = 1 j + 1 (Q i,j+1 (y u , s u , x p ) -Q i,j+1 (y l , s l , x p )).
Therefore the value of the integral can be expressed as a polynomial in y l , y u , s l , s u , x p of total degree i + 2j + 3 of the form

1 j + 1 (s j+1 u -s j+1 l )x i+j+2 p + i+j+1 k=0
q k (y u , s u , y l , s l )x k p .

After substituting -yu-y l su-s l for x p and bringing to a common denominator, we conclude that the expression can be rewritten in the form (s u -s l )P (y l , y u , s l , s u ) (s u -s l ) i+j+2 , as claimed.

How to integrate over an overlay

In our problem, we are interested in computing the integral f (x, y)g(x, y)dxdy, where f is defined over a triangulation T f of M ⊂ R 2 , with a separate linear function f ∆ (x, y) determining f over each triangle ∆ ∈ T f ; g is defined similarly over a different triangulation T g of M . The product h(x, y) := f (x, y)g(x, y) is thus naturally defined over the convex decomposition C of M that is the overlay of T f and T g . By Corollary 2.2, it is sufficient to evaluate a sum over all vertices of C. The vertices of C come in two flavors: the original vertices of T f and of T g , and the intersections of edges of T f and T g . Therefore,

M f (x, y)g(x, y)dxdy = p vertex of C C adjacent to p T (p, C, h C ) = p vertex of T f ∪ Tg C adjacent to p T (p, C, h C ) Σv + p=e 1 ∩e 2 , (e 1 ,e 2 )∈T f ×Tg C adjacent to p T (p, C, h C ). Σe Σ v involves O(n) integrals.
We preprocess each of T f and T g for logarithmic-time point location queries, in O(n log n) time (see, for example, [START_REF] Berg | Computational Geometry: Algorithms and Applications[END_REF]). For each vertex p of T f , we locate the triangle ∆ g ∈ T g containing it. Then, for each triangle ∆ f ∈ T f incident to p, we can compute T (p, ∆ g ∩ ∆ h , f ∆ f g ∆g ) in constant time. The treatment of vertices of T g is symmetric. We spend O(n log n) total for point location. The remaining work is proportional to the sum of vertex degrees in both triangulations, which is O(n). Hence Σ v can be computed in O(n log n) arithmetic operations. We devote the rest of the discussion to computing Σ e efficiently.

Bipartite clique decomposition

Let E f be the set of edges of T f and E g the set of edges of T g . In [START_REF] Chazelle | Algorithms for bichromatic line segment problems and polyhedral terrains[END_REF], it is shown that it is possible to compute a family

F = {(R 1 , B 1 ), . . . , (R u , B u )} where R k ⊂ E f and B k ⊂ E g ,
) ∈ E f × E g ; (iv) k (|R k | + |B k |) = O(n log 2 n).
This family can be computed in O(n log 2 n) time.

Multi-point evaluation

In this section, we explain how to efficiently compute

p=e 1 ∩e 2 , (e 1 ,e 2 )∈R×B C adjacent to p T (p, C, h C ) = e 1 ∈R e 2 ∈B C adjacent to p = e 1 ∩ e 2 T (p, C, h C ), (3)
where (R, B) := (R k , B k ) is a pair of sets of triangulation edges produced by the bipartite clique decomposition. In particular, all segments of R intersect all segments of B and, moreover, without loss of generality, the slopes of segments of R are greater than those of segments of B.

Reduction to sums of rational functions

Each triangle of T f and T g is associated with a bivariate linear function. If e is an edge of T f ∪ T g , let f u (e) be the linear function associated to the upper triangle (in the triangulation to which e belongs) adjacent to e; f l (e) is the corresponding function for the lower triangle; we can define the function to be identically zero for regions outside M , but it will never be used by the algorithm.

A vertex p = e 1 ∩ e 2 , with e 1 ∈ R and e 2 ∈ B, lies on the boundary of four cells of C. We focus on the cell C lef t = C lef t (p) lying above e 1 and below e 2 , for which p is the rightmost point. Thus h C lef t = f u (e 1 )f l (e 2 ) and δ(p, C lef t ) = +1. Suppose f u (e 1 ) : (x, y) → a(e 1 ) + b(e 1 )x + c(e 1 )y and f l (e 2 ) : (x, y) → a(e 2 ) + b(e 2 )x + c(e 2 )y. We compute the contribution to the sum (3) of such cells, over all choices of p. (The remaining three types of cells adjacent to p are treated by an entirely symmetric argument.) Given an edge e of T f ∪ T g , let y = y(e) + s(e)x be the equation of the line supporting it, so we can write The above integral can be expressed as the sum of nine integrals of a function of the form v(e 1 )w(e 2 )x i y j , where v and w are some functions that assign a real number to each edge. Gathering all the terms and recalling that p = e 1 ∩ e 2 , eq. ( 3) can be rewritten as the sum of 36 expressions of the form v(e 1 )w(e 2 )P i,j (y(e 1 ), y(e 2 ), s(e 1 ), s(e 2 )) (s(e 2 ) -s(e 1 )) i+j+1 ,

T (p, C lef t , f u (e 1 )f u (e 2 )) =

Fast multi-point evaluation

Now we will use multi-point evaluation to speed up the computation of eq. ( 4). To accomplish this, we will replace the values associated to the edges of R by symbolic variables, while using the actual numerical values for those for the edges of B. Then we will compute the corresponding symbolic rational function using a divide-and-conquer strategy (Lemma 5.1). Finally, we will use multi-point evaluation on the resulting polynomials (Lemma 5.2).

Lemma 5.1. Let u and v be two functions from the edges of B to R and suppose |B| ≤ n.

Then e∈B u(e) (X -v(e)) d (5)
can be expressed in the form N (X) D(X) ,

where N (X) and D(X) are polynomials of degree at most (n -1)d and nd respectively; their coefficients can be computed explicitly in O(M(nd) log n) arithmetic operations, where M(q) = O(q log q) is the cost of multiplication of two univariate polynomials of degree at most q.

Proof. For simplicity of presentation and without loss of generality, assume that |B| is a power of two. We bring eq. ( 5) to a common denominator by combining the fractions in pairs, reducing their number to |B|/2, and repeating the process log |B| = O(log n) times. The bounds on the degree of the final numerator and denominator are immediate from examining the original fractions. We now explain how to bring

N 1 (X) D 1 (X) + N 2 (X) D 2 (X) ,
with N 1 , N 2 , D 1 , D 2 of degree at most kd, to a common denominator in time 3M(kd) + O(kd). Indeed, the above fraction is equal to

N 1 (X)D 2 (X) + N 2 (X)D 1 (X) D 1 (X)D 2 (X) ,
so it can be computed by three calls to fast polynomial multiplication plus a linear number of additional operations, as claimed. This completes the proof of the lemma, as the cost of one round of combining fractions with denominators and numerators of degree at most kd is n/k • (3M(kd) + O(kd)) = O(M(nd)), since M is superlinear.

The second lemma handles summing the values of a special kind of polynomials. Lemma 5.2. Let P (X 0 , X 1 , . . . , X r ) be a polynomial of degree n in X 0 and d in X 1 , . . . , X r . Let E be a set of at most n points of R r+1 . The values of P at the points of E can be simultaneously computed in O( d+r r M(n) log n) time.

Proof. P can be expanded with respect to the variables X 1 , . . . , X r , and has at most d+r r monomials. Each coefficient is a univariate polynomial in X 0 of degree at most n. Then, using standard multi-point evaluation algorithm for univariate polynomials [7, ch. 10], we can compute simultaneously the values of these univariate coefficients of P in O( d+r r M(n) log n) at every point of E. Finally, we compute the values of each of the monomials of P in time O( d+r r n). Combining all these values also costs O( d+r r n) arithmetic operations, concluding the proof. Now we are ready to efficiently evaluate eq. ( 4). Let F (X, Y, V ) be the polynomial

F (X, Y, V ) := e 2 ∈B
V w(e 2 )P i,j (Y, y(e 2 ), X, s(e 2 )) (s(e 2 ) -X) i+j+1 .

After expanding the numerator of this fraction, we note that F has the form

F (X, Y, V ) = 0≤d X ≤i+2j+2 0≤d Y ≤i+2j+2   e 2 ∈B c d X ,d Y ,d V (w(e 2 ), y(e 2 ), s(e 2 )) (s(e 2 ) -X) i+j+1   X d X Y d Y V.
In our case, i + j + 1 ≤ 3, and, using Lemma 5.1, we can compute each coefficient of X d X Y d Y V and express F in the following form, in O(n log 2 n) time:

F (X, Y, V ) = N (X, Y )V D(X) ,
with N a polynomial of degree n(i + j + 1) + 1 in X, i + j + 2 in Y , and D a univariate polynomial of degree n(i + j + 1).

Finally, eq. ( 4) can be rewritten as

e 1 ∈R e 2 ∈B
v(e 1 )w(e 2 )P i,j (y(e 1 ), y(e 2 ), s(e 1 ), s(e 2 )) (s(e 2 ) -s(e 1 )) i+j+1 = e 1 ∈R N (s(e 1 ), y(e 1 ))v(e 1 ) D(s(e 1 )) .

As |R| < n, using Lemma 5.2, we can compute simultaneously all the terms under the sum, and add them together in O(n log 2 n) arithmetic operations.

Putting it together

To summarize, we can evaluate eq. ( 4

Discussion

In [START_REF] Agarwal | Computing similarity between piecewise-linear functions[END_REF], the following optimization problem was considered: given two functions f and g and a distance measure f -g between them (the paper discusses • 1 , • 2 , and • ∞ , but we only consider • 2 here), find the values of real parameters s and t that minimize f -(sg+t) . If f and g are interpreted as geometric "terrains," we are looking for the scaling and translation of the vertical coordinate of the terrain g to best match terrain f [START_REF] Agarwal | Computing similarity between piecewise-linear functions[END_REF]. Since f -(sg + t) 2 2 = (f -(sg + t)) 2 is a degree-two polynomial in s and t with coefficients easily expressible in terms of f , g, f 2 , g 2 , f g, and 1, being able to compute f g efficiently immediately yields Theorem 6.1. Given piecewise-linear functions f and g defined over different triangulations of the same domain M , with n triangles each, the values s and t minimizing f -(sg + t) 2 can be computed using O(n log 4 n) arithmetic operations.

Theorems 1.1, 1.2, and 6.1 extend to piecewise-polynomial functions of constant maximum degree with essentially no modifications. What other classes of functions can be handles using similar methods?

  consists of the unique leftmost (resp., rightmost) vertex of C. V T := {t 1 , . . .} (resp., V B := {b 1 , . . .}) is the sequence of vertices of C from p R to p L in the counterclockwise (resp., clockwise) direction; refer to Fig. 1.

Lemma 2 . 3 .

 23 Let p be an intersection point of y = y l + s l x and y = y u + s u x as above. Thenx p = -y u -y l s u -s land xp x=0 yu+sux y=y l +s l x

  2 )+s(e 2 )x y=y(e 1 )+s(e 1 )x    a(e 1 )a(e 2 ) + (a(e 1 )b(e 2 ) + a(e 2 )b(e 1 ))x + (a(e 1 )c(e 2 ) + a(e 2 )c(e 1 ))y + b(e 1 )b(e 2 )x 2 + (b(e 1 )c(e 2 ) + b(e 2 )c(e 1 ))xy + c(e 1 )c(e 2 )y 2

e 1

 1 ∈R e 2 ∈B xe 1 ∩e 2 x=0 y(e 2 )+s(e 2 )x y=y(e 1 )+s(e 1 )x v(e 1 )w(e 2 )x i y j = e 1 ∈R e 2 ∈B

  ) in O((|B k | + |R k |) log 2 (|B k | + |R k |)) operations, for each pair (R k , B k ). We also saw in section 4 that k (|R k | + |B k |) = O(n log 2 n),where n is the number of triangles appearing in our triangulations. Thereforek (|R k | + |B k |) log 2 (|R k | + |B k |) ≤ k (|R k | + |B k |) log 2 n = O(n log 4 n),which allows us to conclude that we can compute Σ e in O(n log 4 n) time. This completes the proof of Theorem 1.1.

Acknowledgments

The authors would like to thank Raimund Seidel, Christian Knauer and Sylvain Lazard for helpful discussions. The authors were also inspired to work on this problem at the Workshop on Discrete and Algebraic Geometry in September 2010, at Val d'Ajol, France.

Work by B.A. on this paper has been supported by grant No. 2006/194 from the U.S.-Israel Binational Science Foundation, by NSF Grant CCF-08-30691, and by NSA MSP Grant H98230-10-1-0210.