S Viret

LASER Monitoring system for the ATLAS Tile Calorimeter

Keywords: LHC, ATLAS, Tile Calorimeter, LASER, Calibration PACS: 29.40.Vj

Laser monitoring system for the ATLAS tile calorimeter

S.

1. Introduction LASER monitoring system [1] is an important part of the ATLAS TileCal [START_REF] Abdallah | Design, Construction and Installation of the ATLAS Hadronic Barrel Scintillator-Tile Calorimeter[END_REF] calibration scheme. Its main role is to measure the stability and the linearity of the 9852 PMTs used in the detector. This will be of particular importance during physics analysis, as energy resolution will strongly depend on our understanding of the PMT response. The LASER system setup is presented in Section 2, and some first results and achievements obtained during TileCal commissioning are presented in Section 3. Conclusions are given in Section 4.

LASER System Description

2.1. Hardware setup LASER monitoring system was initially proposed in Ref. [START_REF] Ajaltouni | The Tilecal laser monitoring[END_REF]. The idea is to send short LASER pulses to the TileCal PMTs. Light pulses give a similar PMT response than a signal produced by a particle. The major difference is that the initial energy, in the case of the LASER pulse, is known precisely. This thus allows to monitor accurately PMTs gains and linearity.

However, illuminating simultaneously 9852 PMTs requires a powerful light source. Pulse shape requirements (∼10ns pulse width) has driven our choice toward a commercial Q-switched DPSS (Diode-Pumped Solid State) LASER manufactured by SPECTRA-PHYSICS [4]. This is a frequency-doubled infrared LASER emitting a 532nm green light beam1 . This LASER is the first part of a setup described on Fig. 1. It is divided into two distinct parts: the LASER box and the light dispatching system.

LASER box is the main component of the system, as it provides its absolute calibration and triggering tools. A part of the light emitted by the LASER head is indeed collected there and sent to one photodiode and two PMTs (identical to the TileCal PMTs). The photodiode is used for the absolute calibration of the system, and the PMTs for the triggering of the LASER events. In order to monitor light budget at different levels, three other diodes are collecting light emitted after the first beam splitter. The four photodiodes, which are contained into the same thermally-regulated box, are then inter-calibrated using an 241 Am radioactive source. The LASER box also contains a rotating filter wheel, which is used to attenuate the outgoing light in order to cover the whole TileCal dynamic (from 100 MeV/PMT to 1.5 TeV/PMT).

Then, the light outgoing the LASER box is brought via a 1m long liquid fiber towards a first beam-splitter. This splitter dispatches the primary beam toward a bunch of ∼400 clear fibres. In order to improve the splitting uniformity, the amount of light going out of the secondary fibres is tunable via dedicated connectors. Long clear fibers then bring the light from the counting rooms (where the main system stands) to TileCal modules. The light finally enters the modules where it is split a last time before reaching the PMTs.

Electronics and software aspects

The system is monitored, controlled, and if necessary interlocked, by a set of 6 electronic cards located in a VME crate situated right below the LASER box. This is also where the timing of the LASER pulses is handled. Indeed, LASER event are taken within ATLAS normal physics run, during the 3 µs gap occurring at the end of each LHC cycle. The timeline of a LASER calibration pulse is sketched on Fig. 2. The interface between ATLAS and LASER hardware is made via a dedicated low-level software called Lutin. This program, which runs in the VME crate on a special CPU, is a generic interface. It thus enables not only the LASER system control from ATLAS, but also allows an independent access to the system (via a special program named LasCo), an interface to the ATLAS DCS (Detector Control System),...

Preliminary results

As previously stated, the LASER system main goal is to control and monitor the PMTs linearity and stability. The chosen solution, which is sketched on Fig. 3 is to compare the PMT signal to the diodes signals, as this one is precisely known and calibrated for every pulse. The first results on stability, obtained with calibration runs taken during late 2008 (ATLAS was working in stable mode It has also been clearly demonstrated (see Fig. 4) that the timing of the LASER pulses is well within requirements, and that the system is able to send light into the TileCal with a ±25 ns precision (to be compared with the gap width of 3 µs).

Conclusions

A system to monitor the linearity and stability of the ATLAS TileCal 9852 PMTs has been described. This calibration setup is based on high intensity LASER pulses sent via an optic fibers network trough the PMTs within ATLAS physics run. The light intensity is precisely measured using calibrated photodiodes, and the monitoring procedure is based on the comparison of the diodes signals with the PMTs ones. The system is now fully integrated into ATLAS calibration scheme, and first encouraging results have been obtained.

Figure 1 :

 1 Figure 1: Light path: from the LASER to the TileCal channels

Figure 2 :

 2 Figure 2: The timeline of a LASER calibration pulse

Figure 3 :

 3 Figure 3: How linearity and stability are tested with the LASER system ?

Figure 4 :

 4 Figure 4: Difference between the LASER pulse peak time in one of the TileCal PMT and the time requested

This wavelength is close to the one of the light produced in the scintillating tiles (480nm) Preprint submitted to Elsevier June 4,


Ovono Andami

Armel

Asymptotic behaviour for a diffusion equation governed by nonlocal interactions

In this paper we study the asymptotic behaviour of a nonlocal nonlinear parabolic equation governed by a parameter. After giving the existence of unique branch of solutions composed by stable solutions in stationary case, we gives for the parabolic problem L ∞ estimates of solution based on using the Moser iterations and existence of global attractor. We finish our study by the issue of asymptotic behaviour in some cases when t → ∞.

Introduction

The non-local issues are important in studying the behavior of certain physical phenomena and population dynamics. A major difficulty in studying these problems often lie in the absence of well-known properties as maximum principle, regularity and properties of Lyapunov (see [START_REF] Caffarelli | Regularity theory for fully nonlinear integro-differential equations[END_REF], [START_REF] Chang | On some mixed boundary value problems with nonlocal diffusion[END_REF]) and also the difficulty to characterize and determine the stationary solutions associated thus making study the asymptotic behavior of these solutions very difficult. In this paper we study the solution u(t, x) to the nonlocal equation      u t -div(a(l r (u(t)))∇u) = f dans R + × Ω u(x, t) = 0 sur R + × ∂Ω u(., 0) = u 0 dans Ω. [START_REF] Ambrosetti | A primer of nonlinear analysis[END_REF] In the above problem u 0 and f are such that

u 0 ∈ L 2 (Ω), f ∈ L 2 (0, T, L 2 (Ω)), (2)
with T a arbitrary positive number, a is a continuous function such that ∃m, M such that 0 < m ≤ a(ǫ) ≤ M ∀ǫ ∈ R.

The nonlocal functional l r is defined such that l r (.)(x) : L 2 (Ω) → R, u → l r (u(t))(x) = Ω∩B(x,r) g(y)u(t, y)dy.

Here B(x, r) is the closed ball of R n with radius r and g ∈ L 2 (Ω).. It is sometimes possible to consider g more generally, especially when one is interested in the study of stationary solutions of (see [START_REF] Ovono | Elliptic equations with diffusion parameterized by the range of nonlocal interactions[END_REF]).

1

In physical point of view problem [START_REF] Ambrosetti | A primer of nonlinear analysis[END_REF] gives many applications especially where g = 1 in population dynamics. Indeed, in this situation u may represent a population density and l r (u) the total mass of the subdomain Ω ∩ B(x, r) of Ω. Hence [START_REF] Ambrosetti | A primer of nonlinear analysis[END_REF] can describe the evolution of a population whose diffusion velocity depends on the total mass of a subdomain of Ω. For more details of modelisation we refer the reader to [START_REF] Chipot | Elements of nonlinear analysis[END_REF]. This type of equation can be applied more generally to other models including the study of propagation of mutant gene (see [START_REF] Genieys | Pattern and waves for a model in population dynamics with nonlocal consumption of resources[END_REF], [START_REF] Gourley | Travelling front solutions of a nonlocal Fisher equation[END_REF], [START_REF] Perthame | Concentration in the nonlocal Fisher equation: the Hamilton-Jacobi limit[END_REF]). A very recent study of this propagation was made by Bendahmane and Sepúlveda [START_REF] Bendahmane | Convergence of a finite volume scheme for nonlocal reaction-diffusion systems modelling an epidemic disease[END_REF] in which they analyze using a finite volume scheme adapted, the transmission of this gene through 3 types of people: susceptible, infected and recovered.

In mathematical point of view, when r = d where d is the diameter of Ω problem [START_REF] Ambrosetti | A primer of nonlinear analysis[END_REF] has been studied in various forms (see [START_REF] Chang | On some mixed boundary value problems with nonlocal diffusion[END_REF], [START_REF] Chipot | Existence and uniqueness results for a class of nonlocal elliptic and parabolic problems[END_REF], [START_REF] Chipot | On a class of nonlocal nonlinear elliptic problems[END_REF], [START_REF] Siegwart | Asymptotic behavior of some nonlocal parabolic problems[END_REF]).

However when 0 < r < d, several questions from the theory of bifurcations have arisen concerning the structure of stationary solutions including the existence of a principle of comparison of different solutions depending on the parameter r and the existence of branches (local and global) of solutions. A large majority of these issues has been resolved in [START_REF] Ovono | Elliptic equations with diffusion parameterized by the range of nonlocal interactions[END_REF]. It shows that when a is decreasing the existence of a unique global branch of solutions and existence of branch of solutions that are purely local. Some questions may then arise:

(i) The unique branch described in [START_REF] Ovono | Elliptic equations with diffusion parameterized by the range of nonlocal interactions[END_REF] it is composed of stable solutions? (ii) What about stability properties of the corresponding parabolic problem?

The plan for this work is the following. In section 2 we give some existence and uniqueness results. Section 3 is devoted to stationary problem corresponding to [START_REF] Ambrosetti | A primer of nonlinear analysis[END_REF]. In particular, we study in a radial case, a generalisation of Chipot-Lovat results about determination of the number of solutions. We also establish that the unique global branch of solutions described in [START_REF] Ovono | Elliptic equations with diffusion parameterized by the range of nonlocal interactions[END_REF] is composed by stable solutions (theorem 3.8). In section 4 firstly we address a L ∞ estimate taking to account L p estimate based on Moser iterations. Secondly we prove existence of absorbing set in H 1 0 , which allows us to prove the existence of a global attractor associated to (1) (see remark 5). Finally we obtain a result of stability properties of the corresponding parabolic problem.

Existence and uniqueness results

In this section we show a result of existence . We set V = H 1 0 (Ω) and V ′ its dual, we take the norm in V , . V such that

u 2 V = Ω |∇u| 2 dx
< ., . > means the duality bracket of V ′ and V.

Then we have

Theorem 2.1. Let T > 0, f ∈ L 2 (0, T, V ′ ) and u 0 ∈ L 2 (Ω), we assume that a is a continuous function and the assumption (3) checked then for every r fixed, r ∈ [0, diam(Ω)], there exists a function u such that

     u ∈ L 2 (0, T, V ), u t ∈ L 2 (0, T, V ′ ) u(0, .) = u 0 in Ω d dt (u, φ) + Ω a(l r (u(t)))∇u∇φdx =< f, φ > in D ′ (0, T ) ∀φ ∈ H 1 0 (Ω). (5) Moreover if a is locally Lipschitz i.e ∀c ∃γ c such that |a(ǫ) -a(ǫ ′ )| ≤ γ c |ǫ -ǫ ′ | ∀ǫ, ǫ ′ ∈ [-c, c], (6)
then the solution of ( 5) is unique.

Remark 1. Before to do the proof, it is necessary to see that for r = 0 problem ( 5) is linear and the proof follows a well-known result (see [START_REF] Dautray | Analyse mathématique et calcul numérique pour les sciences et les techniques[END_REF]), it is even when r = diam(Ω) (see [START_REF] Chipot | Elements of nonlinear analysis[END_REF]). We will focus therefore in the following where r ∈]0, diam(Ω)[.

Proof.

For the existence proof we will use the Schauder fixed point theorem. Let w ∈ L 2 (0, T, L 2 (Ω)) we get

t -→ l r (w(t)),
is measurable as a is continuous then

t -→ a(l r (w(t))), is too. The problem of finding u = u(t, x) solution of      u ∈ L 2 (0, T, V ) ∩ C([0, T ], L 2 (Ω)) u t ∈ L 2 (0, T, V ′ ) u(0, .) = u 0 d dt (u, φ) + Ω a(l r (w(t)))∇u∇φdx =< f, φ > in D ′ (0, T ) ∀φ ∈ H 1 0 (Ω), (7)
is linear, besides (7) admits a unique solution u = F r (w) (see [START_REF] Dautray | Analyse mathématique et calcul numérique pour les sciences et les techniques[END_REF], [START_REF] Chipot | Elements of nonlinear analysis[END_REF]). Thus we show that the application

w -→ F r (w) = u, (8)
admits a fixed point. Taking w = u in (7) we get using (3) and the Cauchy-Schwarz inequality 1 2

d dt |u| 2 2 + m u 2 V ≤ |f | ⋆ u V , (9)
. V is the usual norm in V and |f | ⋆ is the dual norm of f. We take

|u| L 2 (0,T,V ) = T 0 u 2 V dt 1 2
.

Using Young's inequality to the right-hand side of (9), it follows that 1 2

d dt |u| 2 2 + m 2 u 2 V ≤ 1 2m |f | 2 ⋆ . (10)
By integrating [START_REF] Dautray | Analyse mathématique et calcul numérique pour les sciences et les techniques[END_REF] on (0, t) for t ≤ T we obtain

1 2 |u(t)| 2 2 + m 2 t 0 u 2 V dt ≤ 1 2 |u 0 | 2 2 + 1 2m t 0 |f | 2 ⋆ . (11)
We deduce that there exists a constant C = C(m, u 0 , f ) such that

|u| L 2 (0,T,V ) ≤ C (12)
Moreover

< u t , v > + < -div(a(l r (u(t)))∇u), v >=< f, v > ∀v ∈ V,
This gives us

|u t | ⋆ ≤ M u V + |f | ⋆ . (13)
By raising (13) squared and using the Young inequality we have that

|u t | 2 ⋆ ≤ 2M 2 u 2 V + 2|f | 2 ⋆ . (14)
By integrating ( 14) on (0, t) and assuming [START_REF] Gourley | Travelling front solutions of a nonlocal Fisher equation[END_REF] we obtain

|u t | L 2 (0,T,V ′ ) ≤ C ′ , (15)
with C ′ = C ′ (m, M, f, u 0 ) and C ′ is independent to w. It follows from ( 12) and ( 15)

|u t | 2 L 2 (0,T,V ′ ) + |u| 2 L 2 (0,T,V ) ≤ R, (16)
with R = C 2 + C ′2 . From ( 12) and the Poincaré inequality it follows that

|u| L 2 (0,T,L 2 (Ω)) ≤ R ′ , (17)
By setting

R 1 = max(R ′ , R), (18)
and associating (17) and ( 18), it follows that the application F maps the ball B(0, R 1 ) of L 2 (0, T, L 2 (Ω)) into itself. Moreover the balls of H 1 (0, T, V, V ′ ) are relatively compact in L 2 (0, T, L 2 (Ω)) (see [START_REF] Dautray | Analyse mathématique et calcul numérique pour les sciences et les techniques[END_REF] for more details), ( 16) clearly shows us that F (B(0, R 1 ) is relatively compact in B(0, R 1 ) with

B(0, R 1 ) = {u ∈ L 2 (0, T, L 2 (Ω)); |u| L 2 (0,T,L 2 (Ω)) ≤ R 1 }.
In order to apply the Schauder fixed point theorem, as announced, we just need to show that F is continuous from B(0, R 1 ) to itself. This is actually the case and completes the proof of existence. We will now discuss the uniqueness assuming of course that assumption (6) be verified. Consider u 1 and u 2 two solutions [START_REF] Caffarelli | Regularity theory for fully nonlinear integro-differential equations[END_REF], by subtracting one obtains in

D ′ (0, T ) d dt (u 1 -u 2 , v)+ Ω (a(l r (u 1 (t))∇u 1 (t)-a(l r (u 2 (t)))∇u 2 (t))∇φdx = 0 ∀φ ∈ H 1 0 (Ω). (19) Since a(l r (u 1 (t)))∇u 1 -a(l r (u 2 (t)))∇u 2 (t) = (a(l r (u 1 (t))) -a(l r (u 2 (t)))∇u 1 (t) + a(l r (u 2 (t)))∇(u 1 (t) -u 2 (t)), (20)
we get

d dt (u 1 -u 2 , v)+ Ω a(l r (u 2 (t)))∇(u 1 (t) -u 2 (t))∇φdx = - Ω (a(l r (u 1 (t))) -a(l r (u 2 (t)))∇u 1 ∇φdx ∀φ ∈ H 1 0 (Ω). ( 21
) Moreover u 1 , u 2 ∈ C([0, T ], L 2 (Ω)) there exist z > 0 such that l r (u 1 (t)), l r (u 2 (t)) ∈ [-z, z]. (22)
Taking v = u 1 -u 2 in (21), it comes easily by Cauchy-Schwartz inequality and ( 6)

1 2 d dt |u 1 -u 2 | 2 2 + m u 1 -u 2 2 V ≤ γ|l r (u 1 (t)) -l r (u 2 (t))| u 1 V u 1 -u 2 V . (23) We get in [3] |l r (u(t)) ≤ C|B(x, r) ∩ Ω| 1 n∨3 |g| 2 |u(t)| 2 ≤ |Ω| 1 n∨3 |g| 2 |u(t)| 2 , (24)
where C a constant, |Ω| represents the measure of Ω and n ∨ 3 the maximum between the dimension n of Ω and 3. By using ( 24), ( 23) and the Young inequality

ab ≤ 1 2m b 2 + m 2 a 2 .
We deduce

d dt |u 1 -u 2 | 2 2 + m u 1 -u 2 2 V ≤ p(t)|u 1 -u 2 | 2 2 , (25)
with

p(t) = 1 m (γC |Ω| 1 n∨3 |g| 2 u 1 V ) 2 ∈ L 1 (0, T ), which leads to d dt |u 1 -u 2 | 2 2 ≤ p(t)|u 1 -u 2 | 2 2 . (26)
Multiplying ( 26) by e -t 0 p(s)ds it follows that

e -t 0 p(s)ds d dt |u 1 -u 2 | 2 2 -p(t)e -t 0 p(s)ds |u 1 -u 2 | 2 2 ≤ 0. ( 27
) Hence d dt {e -t 0 p(s)ds |u 1 -u 2 | 2 2 } ≤ 0. ( 28
)
This shows that t -→ e

- t 0 p(s)ds |u 1 -u 2 | 2 2 is nonincreasing. Since for t = 0, u 1 (0, .) = u 2 (0, .) = u 0 .
This function vanishes at 0 and nonnegative, we conclude that it is identically zero. This concludes the proof.

Stationary solutions

Consider the weak formulation to the stationary problem associated to (1)

(P r ) -div(a(l r (u))∇u) = f dans Ω u ∈ H 1 0 (Ω).
(29)

The case r = d

By taking φ the weak solution of the problem

-∆φ = f dans Ω φ ∈ H 1 0 (Ω), (30)
we get due to a Chipot-Lovat [START_REF] Chipot | Existence and uniqueness results for a class of nonlocal elliptic and parabolic problems[END_REF] results that Theorem 3.1. Let a be a mapping from R into (0, ∞). The problem (P d ) has many solutions as the problem in R

µ a(µ) = l d (φ), ( 31
)
with µ = l d (u d ).
Remark 2. Theorem 3.1 allows us to see where a is increasing that the problem P d admits a unique solution and determine for a given a the exact number of solutions (P d ). However it is difficult or impossible to adapt the proof of the theorem 3.1 in case 0 < r < d.

The case 0 < r < d

As announced in the introduction we focus our study to the case of radial solutions of (P d ). We will assume Ω is the open ball of R n with radius d/2 centered at zero. We set

L 2 r (Ω) = {u ∈ L 2 (Ω) ∃ũ ∈ L 2 (]0, d/2[) such that u(x) = ũ( x )
}, and we also assume that

f ∈ L 2 r (Ω) g ∈ L 2 r (Ω) a ∈ W 1,∞ (R), inf R a > 0 f ≥ 0 a.e in Ω g ≥ 0 a.e in Ω. (32)
We start by giving in some sense in a linear case a result that will be used later to explain the asymptotic behavior.

Proposition 3.2. Let A, B ∈ C(Ω) be positive radial functions such that A ≤ B in Ω and also f, h ∈ L 2 (Ω) two positive radial functions. Let u ∈ H 1 0 (Ω) the radial solution to -div(A(x)∇u) = f in Ω, ( 33
)
and -div(B(x)∇u) = h in Ω. ( 34
)
Then f ≤ h a.e in Ω.

Proof. We proved in [START_REF] Ovono | Elliptic equations with diffusion parameterized by the range of nonlocal interactions[END_REF] that if u is a the radial solution of (33) then for a.e t in [0, d/2],

ũ′ (t) = - 1 Ã(t) t 0 ( s t ) n-1 f (s) ds. (35)
From ( 33), ( 34) and ( 35) we obtain

B(t) Ã(t) t 0 ( s t ) n-1 f (s) ds = t 0 ( s t ) n-1 h(s) ds. Since A ≤ B in Ω and f, h ≥ 0 with f ≡ 0, h ≡ 0 hence f ≤ g.
In a nonlocal case, some results of existence of radial solutions and comparison principle between u r , u d and u 0 has been demonstrated in [START_REF] Ovono | Elliptic equations with diffusion parameterized by the range of nonlocal interactions[END_REF]. It is also proved that if we set for all r ∈ [0, d]

I r := [inf Ω l r (φ), sup Ω l r (φ)]. ( 36
)
Here φ denotes the solution of

-∆φ = f dans Ω φ ∈ H 1 0 (Ω). (37)
By the inclusion or not of I r at an interval of R we somehow generalize the theorem 3.1.

I r ⊂ [m 1 a(m 1 ), m 2 a(m 2 )]. ( 39
)
Then (P r ) admits a radial solution u and

m 1 ≤ l r (u) ≤ m 2 a.e in Ω. (40)
For the proof, we refer the reader to [START_REF] Ovono | Elliptic equations with diffusion parameterized by the range of nonlocal interactions[END_REF]. Generalizing this construction type of the diffusion coefficient a we obtain

Proposition 3.4. Let r ∈ [0, d].
Assume that (32) holds true and there exist an odd integer n 1 and n 1 + 1 positive real numbers {m i } i=0...n1 , with m 0 = 0 and for all i ∈ {0, . . . , n 1 -1} we have m i < m i+1 . Moreover

a(m i ) = max [mi,mi+1] a; a(m i+1 ) = min [mi,mi+1] a ∀i ∈ {0, 2, . . . , n 1 -3, n 1 -1} I r ⊂ i=0,2,...,n1-3,n1-1 [m i a(m i ), m i+1 a(m i+1 )] (41)
Then (P r ) admits at least n1+1 2 radial solutions {u i } i∈{0,2,...,n1-1} such that

m i ≤ l r (u i ) ≤ m i+1 ∀i ∈ {0, 2, . . . , n 1 -3, n 1 -1}.
Proof. The proof here is by induction. Indeed we set 41) is satisfied then(P r ) admits at least n 1 + 1 2 solutions.} By using lemma 3.3 with m 1 = 0 and m 2 = m 1 , it is easy to prove for n 1 = 1 that P n1 is true. For n 1 > 1, This procedure can be repeated to prove that if P n1-2 holds true then P n1 holds too. In the representation of a we have deliberately left, on solid line parts of the curve satisfying the conditions of proposition 3.4 and dotted line one without constraints. This situation are explain in the figure 1. Remark 3. As previously announced, the proposition 3.4 generalizes a certain point of view Theorem 3.1. However it does not accurately determine the exact number of solutions of (P r ) and the bifurcation points of branch of solutions. We have shown in [START_REF] Ovono | About the counting stationary solutions of a nonlocal problem by revisiting the Krein-Rutman theorem[END_REF] way to solve this problem by using the linearized problem, the principle of comparisons obtained in [START_REF] Ovono | Elliptic equations with diffusion parameterized by the range of nonlocal interactions[END_REF] and the Krein-Rutman theorem.

P n1 = { If condition (

Stable solutions of (

P r ) Definition 3.5. Given a domain Ω ⊂ R n , a solution u r ∈ H 1 0 (Ω) of (P r ) is stable if: ∀φ ∈ H 1 0 (Ω) G ur (φ) := Ω a(l r (u r ))|∇φ| 2 - Ω a ′ (l r (u r ))l r (φ)∇u r ∇φ ≥ 0. ( 42
) Definition 3.6. Given u : [0, d] → H 1 0 (Ω), the graph of u is called a (global) branch of solutions if (i) u ∈ C([0, d], H 1 0 (Ω)), (ii) u(r) is solution to (P r ) for all r in [0, d].
u is called a local branch if it's defined only on a subinterval of [0, d] with positive measure.

Before concluding this section, we will focus into the case a nonincreasing to prove the stability of the global branch of solutions. Assume for all r ∈ [0, d], u r is a solution to (P r ) and 0 ≤ l r (u r )(x) ≤ µ d for a.e x ∈ Ω.

(43)

Assume that there exists a solution µ d to (31) such that

a(µ d ) = min [0,µ d ]
a and a(0

) = max [0,µ d ] a. (44)
We prove in [START_REF] Ovono | Elliptic equations with diffusion parameterized by the range of nonlocal interactions[END_REF] Theorem 3.7. Assume (32), ( 43), ( 44) and (31) holds. Assume in addition that a ∈ W 1,∞ (R) and for some positive constant ǫ, it holds that

C 1 |g| 2 |f | 2 |a ′ | ∞,[-ǫ,µ d +ǫ] 1 a(µ d ) 2 < 1, ( 45
)
where C 1 is a constant dependent to Ω. Then (i) For all r in [0, d], (P r ) possesses a unique radial solution u r in [u 0 , u d ];

(ii) {(r, u r ) : r ∈ [0, d]} is a branch of solutions without bifurcation point;

(iii) it is only global branch of solutions;

(iv) if in addition, a is nonincreasing on [0, µ d ] then r → u r is nondecreasing.

Remark 4. It is very difficult to obtain property (iv) for any a. However when a is nonincreasing provide us important information for studying the stability of this branch of solutions.

Corollary 3.8. Let u 1 d the smallest solution to (P d ). Assume ( 32) and ( 31) holds true and there exists a solution µ d to (31) satisfied (44). Assume in addition that a ∈ W 1,∞ (R), u 1 d satisfied ( 43) and for some positive constant ǫ, it holds that

C 1 |g| 2 |f | 2 |a ′ | ∞,[-ǫ,µ d +ǫ] 1 a(µ d ) 2 < 1, ( 46
)
where

C 1 is a constant dependent to Ω. Then {(r, u r ) : r ∈ [0, d]}
|f | 2 |a ′ | ∞,[-ǫ,µ2+ǫ] 1 a(µ2) 2 < 1.
In this case, using theorem 3.7 we get (P r ) possesses a unique radial solution u r in [u 0 , u 2 d ] and the mapping r → u r is nondecreasing. By continuity of this mapping, we can find a r 0 ∈]0, d[ such that u r0 = u 1 d for a.e x ∈ Ω. This means that u 1 d is a solution of (P r0 ). This gives us an absurdity and concludes the proof.

We are now able to prove: Proposition 3.9. Under assumptions and notation of corollary 3.8, the global branch of solutions described in theorem 3.7 is composed by stable solutions.

Proof. For all r ∈ [0, d], let u r be a solution belonging to the global branch of solutions described in theorem 3.7. By using the linearized problem of (P r ), we get ∀φ ∈ H 1 0 (Ω)

Ω a(l r (u r ))|∇φ| 2 - Ω a ′ (l r (u r ))l r (φ)∇u r ∇φ ≥ inf Ω a(l r (u r ))|∇φ| 2 2 -C |g| 2 |a ′ | ∞,[-ǫ,µ1+ǫ] |∇u r | 2 |∇φ| 2 2 . (47)
Taking into account that

|∇u r | 2 ≤ C(Ω) |f |2 inf Ω a(l r (u r ))
where C(Ω) designed the Poincaré Sobolev constant. We obtain

Ω a(l r (u r ))|∇φ| 2 - Ω a ′ (l r (u r ))l r (φ)∇u r ∇φ ≥ |∇φ| 2 2 inf Ω a(l r (u r )) -C 1 |g| 2 |a ′ | ∞,[-ǫ,µ1+ǫ] |f | 2 inf Ω a(l r (u r )) . (48)
Moreover by assumptions ( 43) and (44) we get a(µ 1 ) ≤ inf Ω a(l r (u r )).

Thus (46) becomes

C 1 |g| 2 |f | 2 |a ′ | ∞,[-ǫ,µ d +ǫ] 1 inf Ω a(l r (u r )) 2 < 1. (49)
We deduces

Ω a(l r (u r ))|∇φ| 2 - Ω a ′ (l r (u r ))l r (φ)∇u r ∇φ ≥ 0. ( 50
)
This concluded the proof. In what follows we obtain L ∞ estimate of the solution (1) from L q estimate. The method we use is based on iterations Moser type, for more details on the method see [START_REF] Quittner | Superlinear parabolic problems[END_REF]. We get Theorem 4.1. Let n ≥ 3 and u a classical solution of ( 1) defined on [0, T ).

Assume that p > 1 and q > 1 such that 1 p + 1 q = 1. Suppose further that

U q = sup t<T |u(t)| q < ∞, f ∈ L ∞ (0, ∞, L q (Ω)). If p < n n-2 then U ∞ < ∞.
To prove this theorem we need the following proposition: Lemma 4.2. Consider u a classical solution of ( 1) on [0, T ), r ≥ 1 and p > 1 such that 1 p + 1 q = 1 with p < n n-2 . We take

Ũr = max{1, |u 0 | ∞ , U r = sup t<T |u(t)| r } and let σ(r) = p(n + 2) 2[r(2p -pn + n) + np] .
Then there exists a constant

C 2 = C 2 (Ω, m) such that Ũ2r ≤ [C 2 f L ∞ (0,∞,L q (Ω)) ] σ(r) r σ(r)
Ũr .

Proof. Multiplying (1) by u 2r-1 and then using the Hölder inequality yields 1 2r

d dt Ω u 2r dx + m 2r -1 r 2 Ω |∇(u r )| 2 dx ≤ |f | q |u 2r-1 | p . (51)
As

|u 2r-1 | p = |u r | 2r-1 r p 2r-1 r , (52)
by taking w = u r in (51) and (52), we get easily 1 2r

d dt |w| 2 2 + m 2r -1 r 2 |∇w| 2 2 ≤ |f | q |w| α αp , (53)
with α = 2r-1 r . Let β such that

1 αp = β + 1 -β 2 ⋆ , (54)
with 2 ⋆ = 2n n-2 . We claim that β ∈ (0, 1). In fact β = 2nr -(n -2)(2r -1)p (n + 2)(2r -1)p .

Since p < 2r

2r-1 n n-2 then β > 0. As well as (n+2)(2r-1)p > 2nr-(n-2)(2r-1)p implies that β < 1 this prove that β ∈ (0, 1).

Using an interpolation inequality (see [START_REF] Quittner | Superlinear parabolic problems[END_REF]) in ( 53) and (54), we get 1 2r

d dt |w| 2 2 + m 2r -1 r 2 |∇w| 2 2 ≤ |f | q |w| β 1 |w| 1-β 2 ⋆ α . (55)
Applying Sobolev injections in (55), we have 1 2r

d dt |w| 2 2 +m 2r -1 r 2 |∇w| 2 2 ≤ |f | q 2r m α(1-β) 2 |w| βα 1 C (1-β)α m 2r α(1-β) 2 |∇w| (1-β)α 2 ,
(56) and also 1 2r

d dt |w| 2 2 +m 2r -1 r 2 |∇w| 2 2 ≤ |f | q 2r m α(1-β) 2 |w| βα 1 C (1-β)α m 2r |∇w| 2 2 α(1-β) 2
.

(57) Since β ∈ (0, 1) and α 2 ∈ (0, 1) it is clear that α(1-β) 2 ∈ (0, 1). Applying Young's inequality to (57) with α(1-β)

2 + 1 -α(1-β) 2 = 1. We obtain 1 2r d dt |w| 2 2 +m 2r -1 r 2 |∇w| 2 2 ≤ δ |f | 1 δ q 2r m α(1-β) 2δ |w| βα δ 1 C 2 δ + α(1 -β) 2 m 2r |∇w| 2 2 , (58) with δ = 1 -α(1-β) 2 .
Joining the fact that α(1-β) 2 ∈ (0, 1) and δ < 1 to (58), we deduce 1 2r

d dt |w| 2 2 + m 3r -2 2r 2 |∇w| 2 2 ≤ |f | 1 δ q 2r m α(1-β) 2δ |w| βα δ 1 C 2 δ . (59)
We set

2rσ(r) -1 = α(1 -β) 2δ and 2ρ(r) = βα δ , (59)
becomes 1 2r

d dt |w| 2 2 + m 3r -2 2r 2 |∇w| 2 2 ≤ |f | 1 δ q 2r m 2rσ(r)-1 |w| 2ρ(r) 1 C 2 δ . ( 60
)
This gives us taking into account that 3r-2 r > 1

d dt |w| 2 2 + m|∇w| 2 2 ≤ |f | 1 δ q 2r m 2rσ(r) |w| 2ρ(r) 1 m C 2 δ . (61)
By a calculation we can verify that

ρ(r) = 2nr -(n -2)(2r -1)p 2r(p(n + 2) + n) -2n(2r -1)p ,
and also that ρ(r) ∈ (0, 1). Using the Poincaré Sobolev inequality and that ρ(r) < 1 in (61), yields

d dt |w| 2 2 + m C 1 (Ω) |w| 2 2 ≤ |f | 1 δ q 2r m 2rσ(r) |w| 2 1 m C 2 δ , (62)
where C 1 (Ω) designed the Poincaré Sobolev constant. Noticing that

e -m C 1 (Ω) t d dt e m C 1 (Ω) t |w| 2 2 = d dt |w| 2 2 + m C 1 (Ω) |w| 2 2 ≤ |f | 1 δ q 2r m 2rσ(r) |w| 2 1 m C 2 δ . (63)
and integrating (63) on [0, t) we get

|w(t)| 2 2 ≤ |w(0)| 2 2 + f 1 δ L ∞ (0,∞,L q (Ω)) 2r m 2rσ(r) m C 2 δ |w| 2 1 . ( 64
) Since |w(0)| 2 2 = Ω w(0) 2 dx = Ω u(0) 2r dx ≤ |Ω||u(0)| 2r ∞ ≤ |Ω| Ũ 2r r , (65)
(64) and (65) gives us

Ũ 2r 2r ≤ |Ω| Ũ 2r r + f 1 δ L ∞ (0,∞,L q (Ω)) 2r m 2rσ(r) m C 2 δ Ũ 2r r . ( 66
) Whereas 1 δ > 1, 2rσ(r) > 0 and σ(r) = 1 2rδ it follows that Ũ2r ≤ C σ(r) 2 f σ(r) L ∞ (0,∞,L q (Ω)) r σ(r) Ũr , (67)
with C 2 = C 2 (Ω, m). This completes the proof of Lemma.

We have also Ũ2r ≤ [C 2 f L ∞ (0,∞,L q (Ω)) ] σ(r) r σ(r) Ũr .

By iterating this equation by taking r = h, r = 2h, r = 2 2 h, etc, we obtain

Ũ2 k+1 h ≤ [C 2 f L ∞ (0,∞,L q (Ω)) ] λ1 2 λ2 h λ1 Ũh , with λ 1 := σ(h) + σ(2h) + σ(2 2 h) + .. + σ(2 k-1 h) + σ(2 k r) et λ 2 := σ(2h) + 2σ(2 2 h) + 3σ(2 3 h) + ... + (k -1)σ(2 k-1 h) + kσ(2 k r).
To complete the proof we just need to show that λ 1 , λ 2 < +∞. Indeed by lemma 4.3 Hence u ∈ L ∞ (t 0 , +∞, H 1 0 (Ω)). By using (73) and the classical Gronwall lemma it is easy to see that u ∈ L ∞ (0, t 0 , H 1 0 (Ω)). This completes the proof of the theorem.

λ 1 ≤ k µ=0 α µ σ(h) ≤ ∞ µ=0 α µ σ(h) = σ(h) (1 -α) < ∞. Noting also that σ(2 k h) ≤ θ k-1 σ(2h) ∀k ∈ N ⋆ ,
Remark 5. This theorem show us the existence of absorbing set in H 1 0 (Ω). By considering S(t) the semigroup associated to the equation ( 1) defined by

S(t) : L 2 (Ω) → L 2 (Ω) u 0 → u(t),
with u(t) a solution of [START_REF] Ambrosetti | A primer of nonlinear analysis[END_REF]. As a result of the theorem 4.4 and the compact embedding of H 1 0 (Ω) into L 2 (Ω) we deduce that the semigroup S(t) possesses a global attractor. Indeed it is easy to show the existence of absorbing set in L 2 (Ω), the main difficulty here is to show that S(t) is such that ∀B ⊂ L 2 (Ω) bounded, ∃t 0 = t 0 (B) such that t≥t0 S(t)B is relatively compact in L 2 (Ω).

(78)

This property known as S(t) is uniformly compact for t large can be proved by using theorem 4.4 and the compact embedding of H 1 0 (Ω) into L 2 (Ω).

Asymptotic behaviour

In this part we are interested in asymptotic behaviour of a weak solution of (1).

Our main interest here is the radial solutions. By radial solutions we means ũ(t, |x|) = u(t, x). As in the stationary case Ω is a open ball of R n . Remember that L 2 r (Ω) = {v ∈ L 2 (Ω) ∃ṽ ∈ L 2 (]0, d/2[) such that v(x) = ṽ( x )}.

In order to not make confusion between u 0 the solution to (P 0 ) and the initial value of (1), we will take u 0 the initial value of (1).

Theorem 4.5. Assume that f, g ∈ L 2 r (Ω), a is a continuous function and the assumption (3) checked then (1) admits a radial solution.

Proof. Let w ∈ L 2 (0, t, L 2 r (Ω)) it is clear that l r (w) is radial and also a(l r (w)). Thus by (8) F r maps L 2 (0, t, L 2 r (Ω)) into itself. The proof now follows by using arguments similar to those used in theorem 2.1.

Lemma 3 . 3 .

 33 Let r ∈ [0, d]. Assume that (32) holds true and there exist 0 ≤ m 1 ≤ m 2 such that a(m 1 ) = max [m1,m2]

Example 1 .

 1 Let us see a function a satisfying proposition 3.4. For this, we consider the case n 1 = 3 and r ∈ (0, d]. Considering (32) and the strong maximum principle we get min I r > 0. Taking m 1 := 2 max I r a(0) , a(m 1 ) := a(0) 2 with a(0) > 0 and also a decreasing on [0, m 1 ] then we prove lemma 3.3 conditions. By repeating this process with m 2 > m 1 and setting a(m 2 ) := min I r m 2 , m 3 := 2 max I r a(m 2 ) with a(m 3 ) := a(m2) 2 and also a is decreasing on [m 2 , m 3 ]. This shows the existence of such a.

Figure 1 :

 1 Figure 1: The case n 1 = 3

  Figure 2: case of 2 solutions

Figure 3 :

 3 Figure 3: Branch of solutions

Lemma 4 . 3 . 2 , c 2 =

 4322 Let r > 1, n ≥ 3, p < n n-2 and σ(r) = p(n+2) 2[r(2p-pn+n)+np] then we get σ(2 k r) ≤ θ k σ(r) ∀k ∈ N,with θ ∈ (0, 1).Proof. By askingc 1 = p(n+2) (2p -pn + n) and c 3 = np yields σ(r) = c1 rc2+c3 with c 1 , c 2 , c 3 ∈ R ⋆ + .By taking θ = 1 -c2 2c2+c3 the proof of this lemma is deduced by reasoning by induction. Returning now to the proof of the theorem, by lemma 4.2 we get Proof.

  is the only global branch of solutions starting to u 1 d . Proof. The fact that {(r, u r ) : r ∈ [0, d]} is the only global branch of solutions results from theorem 3.7. We will now show that this unique branch of solutions is stable and start at r = d by u 1 d . For this we consider without loss of generality (P d ) admits two solutions u 1 d and u 2 d such that u 1 d ≤ u 2 d . We denote by µ 1 and µ 2 respectively solutions of (31) corresponding to u 1 d and u 2 d (see figure2). It is easy to see that µ 1 and µ 2 satisfied (44).

Assume {(r, u r ) : r ∈ [0, d]} is the only global branch of solutions starting to u 2 d . Then we get C 1 |g| 2

it follows

This completes the proof of the theorem.

Uniform estimate in time

We prove in what follows an estimate of u in L ∞ (R + , H 1 0 (Ω)). We get

Taking a spectral basis related to the Laplace operator in the Galerkin approximation (see [START_REF] Temam | Infinite-dimensional dynamical systems in mechanics and physics[END_REF]) we find that -∆u can be regarded as test function in L 2 (0, T, L 2 (Ω)) for all T > 0. By multiplying (1) by -∆u(t) and integrating over Ω (u t , -∆u)

and also 1 2

(69) Here (., .) is the usual scalar product on L 2 (Ω). Taking to account

where K is a constant depending of Ω. It comes

Now from ( 71) and (69) we have 1 2

By using Young's inequality ab

In order to apply the uniform Gronwall lemma to (73) we start with a small estimate. Remember that

where λ is the principal eigenvalue of the Laplacian operator with Dirichlet boundary conditions. By integrating on [t, t 0 ) we get

Assume now

with u 0 the initial value to (1) and u 0 and u d respectively the solution of (P 0 ) and (P d ).

We can now give a stability result assuming that (1) admits a unique solution.

Theorem 4.6. Assume (79) and f, g ∈ L 2 r (Ω). Let u, u d and u 0 respectively the solution of ( 1), (P d ) and (P d ). If

It is easy to prove that S contains 0 (see 80). By setting

By continuity of the mapping t → l d (u(t)), we get

By using (1) and (P d ) we get in D(0, t ⋆ )

Applying Poincarr Sobolev inequality we get 1 2

this prove

In the same way we can also prove u 0 ≤ u ∀t ∈ [0, t ⋆ ]. It follows

To finish we just need to prove that t ⋆ is very large, this is typically the case.

From ( 79) and (90) we deduce

Due to the uniqueness of (1), we deduce that t = ∞. This shows that

and achieve the proof.

Remark 6. The fact that |u(t)| 2 2 is not a Lyapunov function that is to say decreases in time, makes very complex the study of certain asymptotic properties of our problem. Indeed under our study it is tempting to show that for r fixed

where u is the solution of ( 1) and u 1 r the solution belonging to the stable global branch described previously. A numerical study would be a great contribution to try to carry out some of our theoretical intuitions.


Mathew Dilip
email: dilip@csa.iisc.ernet.in

Vijay Thomas

Member, IEEE Georges-Pierre Natarajan

Bonneau

Dilip Mathew Thomas

Vijay Natarajan
email: vijayn@csa.iisc.ernet.in

Georges-Pierre Bonneau
email: georges-pierre.bonneau@inria.fr

Link Conditions for Simplifying Meshes with Embedded Structures

Keywords: Embedded structures, extended complex, link conditions, mesh simplification, topology preservation, quadric error metric

Interactive visualization applications benefit from simplification techniques that generate good quality coarse meshes from high resolution meshes that represent the domain. These meshes often contain interesting substructures, called embedded structures, and it is desirable to preserve the topology of the embedded structures during simplification, in addition to preserving the topology of the domain. This paper describes a proof that link conditions, proposed earlier, are sufficient to ensure that edge contractions preserve topology of the embedded structures and the domain. Excluding two specific configurations, the link conditions are also shown to be necessary for topology preservation. Repeated application of edge contraction on an extended complex produces a coarser representation of the domain and the embedded structures. An extension of the quadric error metric is used to schedule edge contractions, resulting in a good quality coarse mesh that closely approximates the input domain and the embedded structures.

INTRODUCTION

S EVERAL modeling and simulation applications pro- duce complex meshes at a very high level of detail. In order to speed up the subsequent processing, the meshes are simplified to generate a lower resolution approximation of the original mesh. A popular method used to simplify meshes is the iterative contraction of mesh edges. Many applications require that the topology of the mesh remain unchanged after simplification. In the context of edge contractions, topology preservation can be ensured by evaluating, for each edge, a set of conditions called link conditions [START_REF] Dey | Topology preserving edge contraction[END_REF] and allowing only those edges that satisfy the link conditions to be contracted.

Many meshes contain interesting substructures of lower dimensions embedded within the mesh. The topology of such embedded structures is often important. For instance, in a mesh that contains two distinct regions, the boundary separating the two regions could be an embedded structure whose topology needs to be preserved while simplifying the mesh.

Vivodtzev et al. [START_REF] Vivodtzev | Substructure Topology Preserving Simplification of Tetrahedral Meshes[END_REF], [START_REF] Vivodtzev | Topology Preserving Simplification of 2D Non-Manifold Meshes with Embedded Structures[END_REF] have proposed a simplification technique that preserves the topology of the mesh and the embedded structures. They transform the original mesh to an extended complex by attaching simplices from a dummy vertex to simplices of the embedded structure. Link conditions are evaluated on the extended complex and only those edges that satisfy the link conditions are contracted to simplify the mesh. They use this technique to simplify meshes with embedded structures and demonstrate, using multiple datasets, that the simplification process preserves the topology of the mesh and the embedded structures. However, the theoretical correctness of this technique is yet to be established for volumetric meshes.

The main contributions of this paper are:

• We give a mathematical proof to show that edge contractions that satisfy link conditions evaluated in the extended complex of a 3D mesh preserve the topology of the mesh and the embedded structures.

• Our proof for 3D meshes is generic. We use the same arguments to prove the analogous result for 2D meshes also.

• We extend the simplification algorithm to handle embedded structures that lie on the boundary. This was a limitation of the previous algorithm.

• We demonstrate the usefulness of the simplification technique in geophysics, isosurface topology preservation, and molecular surface topology preservation.

• We show that evaluation of link conditions on the extended complex is necessary for topology preservation of a restricted class of 2D meshes with 1D embedded structures.

Our implementation of the simplification algorithm for tetrahedral meshes uses ideas based on the Quadric Error Metric (QEM) to improve the quality of mesh elements and to approximate the scalar field defined on the mesh. Further, the algorithm also preserves the geometry of the embedded structure. Evaluation of link conditions requires computation of the order of a simplex. This computation is non-trivial in the context of embedded structures. We describe an explicit characterization of simplices that leads to an algorithm for computing their order.

The rest of the paper is organized as follows. Section 2 describes related work. Section 3 defines all terms used in this paper. Section 4 describes the proofs in detail. Section 5 discusses implementation of the simplification algorithm. Section 6 lists applications of the algorithm. Section 7 discusses our experimental results. Section 8 concludes the paper.

RELATED WORK 2.1 Mesh Simplification

Mesh simplification is an area of active research within the scientific visualization community. Edge contractions are extensively used for mesh simplification and several algorithms exist that differ in the manner in which edges are chosen for contraction. A notable algorithm is the quadric error based algorithm of Garland et al. [START_REF] Garland | Surface simplification using quadric error metrics[END_REF], which produces high quality approximations and is computationally very efficient. A multitude of techniques for mesh simplification are compared in several survey articles [START_REF] Cignoni | A comparison of mesh simplification algorithms[END_REF], [START_REF] Garland | Multiresolution modeling: survey and future opportunities[END_REF], [START_REF] Luebke | A developer's survey of polygonal simplification algorithms[END_REF].

Topology Preservation and Controlled Simplification

Dey et al. [START_REF] Dey | Topology preserving edge contraction[END_REF] showed that an edge that satisfies a set of conditions, called link conditions, can be contracted without causing topology violation. These are local conditions evaluated in the neighbourhood of the edge. However, link conditions do not distinguish embedded structures from the rest of the mesh and hence may not ensure topology preservation of embedded structures.

Early work on minimum and minimal triangulations studied the smallest possible mesh that can be reached without violating the topology [START_REF] Barnette | All 2-manifolds have finitely many minimal triangulations[END_REF], [START_REF] Lavrenchenko | Irreducible triangulations of a torus[END_REF]. Different from topology preserving simplification, controlled topology simplification helps to remove topological noises like small holes, while retaining important topological characteristics of the mesh. Reeb graphs and Morse-Smale complexes are extensively used for controlled topological simplification [START_REF] Guskov | Topological noise removal[END_REF], [START_REF] Gyulassy | Topology-based simplification for feature extraction from 3d scalar fields[END_REF], [START_REF] Gyulassy | A topological approach to simplification of three-dimensional scalar fields[END_REF].

Attribute Preservation

Various attributes like material colour, scalar field, etc. are often available as attributes at each vertex of the mesh. These attributes also need to be preserved during simplification. Quadric error metric based simplification methods can be extended to enable attribute preservation [START_REF] Garland | Simplifying Surfaces with Color and Texture using Quadric Error Metrics[END_REF], [START_REF] Natarajan | Simplification of three-dimensional density maps[END_REF]. Cignoni et al. compared various simplification techniques to approximate the scalar field of a tetrahedral mesh [START_REF] Cignoni | A comparison of mesh simplification algorithms[END_REF].

Substructure Preservation

Mesh simplification algorithms should preserve important substructures of the mesh. We assume that the substructure is specified by the user or is available as the output of prior analysis of the mesh. By transforming the input mesh to an extended complex, Vivodtzev et al. [START_REF] Vivodtzev | Substructure Topology Preserving Simplification of Tetrahedral Meshes[END_REF], [START_REF] Vivodtzev | Topology Preserving Simplification of 2D Non-Manifold Meshes with Embedded Structures[END_REF] capture the topology of the substructures in a new mesh and ensure that the topology of both the input mesh and the embedded structures is preserved during simplification.

They sketch a proof for topology preservation in the case of 2D meshes. However, this proof is not complete because their analysis overlooks the presence of new simplices in the extended complex, which are added from the dummy vertex. Moreover, the proof does not extend to the case of 3D meshes because it relies on specific properties of edges within a 2D mesh.

Scalability

When the size of the mesh becomes huge, out-of-core algorithms are required to process the mesh. These methods design a mesh representation scheme and a simplification algorithm that accesses the mesh in a spatially coherent manner [START_REF] Lindstrom | A memory insensitive technique large model simplification[END_REF], [START_REF] Vo | Streaming Simplification of Tetrahedral Meshes[END_REF]. Since link conditions are evaluated in the neighbourhood of an edge, they can also be implemented out-of-core for large meshes.

DEFINITIONS

A k-simplex η is the convex hull of k + 1 ≥ 1 affinely independent points. Its dimension is dim(η) = k. A face τ
of η is the simplex defined by a non-empty subset of the k +1 points and τ is proper if the subset is proper. We say τ ≤ η and call η a coface of τ . The interior of a simplex, int τ is the set of points contained in τ but not in any proper face of τ . A simplicial complex K is a collection of simplices such that:

i. If η ∈ K then all faces of η are also in K ii. If η, τ ∈ K then η ∩ τ is empty or a face of η, τ . The dimension of K, dim(K), is the largest dimension of simplices in K. The underlying space of K, |K| is the union of simplex interiors in K. A simplex in K is principal if it has no coface in K other than itself. Two simplicial complexes K and L are said to be combinatorially equivalent, K ≃ L, if they have isomorphic subdivisions.

For L ⊆ K, the closure of L, denoted by L is the smallest subcomplex that contains L. The star of L in K, denoted by St(L; K), is the set of cofaces of simplices in L. The link of L in K, denoted by Lk(L; K), is the set of all faces of cofaces of simplices in L that are disjoint from simplices in L.

L = {τ ∈ K|τ ≤ η ∈ L} St(L; K) = {η ∈ K|η ≥ τ ∈ L} Lk(L; K) = St(L; K) -St(L; K)
The order of a simplex τ in K, denoted by Ord(τ ; K), measures the topological complexity of τ in K. Let k = dim(St(τ ; K)). Ord(τ ; K) is the smallest integer i such that there is a (ki) simplex η, in a suitable simplicial complex F , such that St(τ ; K) and St(η; F ) are combinatorially equivalent. Fig. 3. The order of a simplex is an indicator of the topological complexity of its star. Grey simplices are of order 1 and the two red vertices have order 2. Other simplices have order 0.

To illustrate order of a simplex, consider the 2D simplicial complex in Figure 3. The order of all triangles in the mesh is 0 because the star of a triangle in the mesh is the triangle itself. Hence k = 2. Now, we can choose a triangle with its faces as a simplicial complex so that the star of the triangle is combinatorially equivalent to a triangle in the mesh. Hence ki = 2 and therefore i = 0. So all triangles of the mesh have order 0. The black edges are shared by two triangles. So k = 2. The star of a black edge is isomorphic to a triangle subdivided into two. Thus order of black edges is also 0. The star of the black vertex is isomorphic to subdivisions of a triangle and hence has order 0. Following a similar reasoning, all grey edges and vertices have order 1 and the two red vertices have order 2.

The j-th boundary of a simplicial complex K, denoted by Bd j K is the set of simplices with order greater than or equal to j. In Figure 3, the 0 th boundary is the entire mesh, the 1 st boundary is the set of grey edges, grey vertices and red vertices. The 2 nd boundary consists of the two red vertices.

For a k-simplex η and a vertex x that is affinely independent of the vertices v 1 , v 2 , . . . , v k+1 of η, the cone from x to η is defined as a simplex with vertices x, v 1 , v 2 , . . . , v k+1 and is denoted by x • η.

For each i, define Bd ω i K to be the simplicial complex formed from Bd i K by adding a dummy vertex ω and adding cones from ω to all simplices in Bd i+1 K. So,

Bd ω i K = Bd i K ∪ (ω • Bd i+1 K).
For a simplex η ∈ Bd ω i K, we denote the link within Bd ω i K as Lk ω i (η; K). We use edge contraction as the basic operation for mesh simplification. While doing edge contractions in a simplicial complex K, topology of K would be preserved if a set of conditions, called link conditions, are satisfied. For an edge ab, the link conditions are: For a simplicial complex K, an embedded structure is a user defined subcomplex of K where dim(E) < dim(K). An extended complex, K, as defined by Vivodtzev et al. [START_REF] Vivodtzev | Substructure Topology Preserving Simplification of Tetrahedral Meshes[END_REF], [START_REF] Vivodtzev | Topology Preserving Simplification of 2D Non-Manifold Meshes with Embedded Structures[END_REF], is obtained from K by introducing a dummy vertex σ and adding cones from σ to simplices in E so that K = K ∪ σ • E.

Lk ω i (a; K) ∩ Lk ω i (b; K) = Lk ω i (ab; K) ∀i ≥ 0.
To illustrate this, consider the simplicial complex K in Figure 5(a), where the edges in blue form the embedded structure. Then the extended complex is constructed by inserting cones from σ to the blue edges as shown in Figure 5(b).

TOPOLOGY PRESERVATION

Let K be a tetrahedral mesh with embedded structure E of dimension 2 or lower. K is the extended complex formed from K by adding cones to E from a dummy vertex σ. Vivodtzev et al. [START_REF] Vivodtzev | Substructure Topology Preserving Simplification of Tetrahedral Meshes[END_REF], [START_REF] Vivodtzev | Topology Preserving Simplification of 2D Non-Manifold Meshes with Embedded Structures[END_REF] assume that K can be simplified without violating topology of K or E by contracting edges that satisfy link conditions of K. They sketch a proof for the case dim(K) = 2. However, as indicated earlier, this proof has a major gap since it does not consider the cones added from σ while analysing order of simplices in K. Moreover, the proof does not extend to the case of dim(K) = 3. In this section, we present a proof for the case when dim(K) = 3. Analogous arguments prove the result for dim(K) = 2. Initially we assume that E is disjoint from Bd 1 K and prove that link conditions are sufficient for topology preservation of E and K. Later, we show that this assumption can be relaxed.

Consider edge contractions of K where the edges are not incident on the dummy vertex σ. The link conditions for a 3-complex K are:

Lk ω 0 (a; K) ∩ Lk ω 0 (b; K) = Lk ω 0 (ab; K), (III.0) Lk ω 1 (a; K) ∩ Lk ω 1 (b; K) = Lk ω 1 (ab; K), (III.1) Lk ω 2 (a; K) ∩ Lk ω 2 (b; K) = ∅. (III.2)
We want to prove that edge contractions that satisfy the above link conditions of K preserve topology of K and E.

We adopt a two-step approach to prove this result. First, we show that topology of K is preserved by proving that if an edge is selected for contraction then it will satisfy link conditions of K. This is done by proving the contrapositive statement -if an edge violates link conditions of K, then it will also violate link conditions of K and hence will not be selected for edge contraction.

Next, we show that topology of E is preserved. For this, we classify edges into different categories based on whether they are part of E or not. It is easy to show that edges outside E that satisfy link conditions of K will not cause topology violation of E. For edges that belong to E, we use an approach similar to the one used for K and show that link conditions of K are violated whenever link conditions of E are violated.

Order of a simplex in E and K

To argue about violation of link conditions in E and K, it is important to understand the relationship between the order of a simplex in E and its order in K. The lemmas below state this relationship. For better readability, we postpone the discussion on the proof of these lemmas to Appendix A.

Lemma 1. For an edge ab

∈ E, if Ord(ab; E) = 1, then i. Ord(σab; K) = 1 ii. Ord(ab; K) ≥ 1.

Lemma 2. For an edge ab

∈ E, if Ord(ab; E) = 0, then Ord(σab; K) = 0. Lemma 3. For a vertex a ∈ E, if Ord(a; E) ≥ 1, then Ord(σa; K) ≥ 1. Lemma 4. For an edge ab ∈ E, if Ord(ab; E) = 1 and Ord(a; E) = 2, then Ord(σa; K) = 2. Lemma 5. Bd ω i K ⊆ Bd ω i K, ∀i ≥ 0.

Preserving topology of K

We now show that whenever link conditions are violated for an edge ab of K, they are violated for K as well. Let i th link condition (where i = 0, 1, 2) in K be violated by a simplex s ∈ Bd ω i K. Note that link of an edge is contained in the link of its vertices, hence it is not possible that s ∈ Lk ω i (ab; K) and

s ∈ Lk ω i (a; K) ∩ Lk ω i (b; K). Hence, s ∈ Lk ω i (a; K) ∩ Lk ω i (b; K) and s ∈ Lk ω i (ab; K). By Lemma 5, s ∈ Lk ω i (a; K) and s ∈ Lk ω i (b; K). We show that s ∈ Lk ω i (ab; K). For a simplex s ∈ E, since E ∩ Bd 1 K = ∅, Ord(s; K) = 0.
When K is extended to K, cones are added from σ to simplices in E. The cones thus added to s may increase the order of s in K i.e., Ord(s; K) may be greater than Ord(s; K). Thus a new simplex that appears in Lk ω i (ab; K) is a simplex belonging to one of the following types: I. a cone from σ II. a cone from ω to simplices incident on σ III. a cone from ω to simplices in E IV. the subcomplex E (if i > 0).

If any of these new simplices in Lk ω i (ab; K) is s, link conditions in K would be satisfied. However, we show that none of the new simplices lie in Bd ω i K and hence cannot be s since s ∈ Bd ω i K. Type I or type II is not in

Bd ω i K since the dummy vertex σ ∈ Bd ω i K. Type III is not in Bd ω i K because in Bd ω i K
, cones from ω are added only to simplices whose order is higher than 0. However, all simplices in E have order 0 in K. Type IV is not in Bd ω i K because all simplices in E have order 0 and hence do not belong to Bd ω i K, i > 0. Hence, none of the new simplices in Lk ω i (ab; K) can be s. Thus the simplex s lies in both Lk ω i (a; K) and Lk ω i (b; K) but does not lie in Lk ω i (ab; K). So i th link condition of K is violated.

Preserving topology of E

An edge ab either belongs to the subcomplex E or lies outside E. In either case we show that if contracting ab does not violate link conditions in K then the topology of E is preserved.

Contracting edges not in E

Let ab denote an edge in K that is not contained in E. Let c be the new vertex obtained after contracting ab. Let F denote the embedded structure after contracting ab. A simplex <v 1 , . . . , v n , c> lies in F if and only if either <v 1 , . . . , v n , a> or <v 1 , . . . , v n , b> lies in E. This edge contraction is rejected because link condition (III.0) is violated. Cones are added from σ to a and b but not to ab. So,

σ ∈ Lk ω 0 (a; K)∩Lk ω 0 (b; K) but σ ∈ Lk ω 0 (ab; K).

Contracting edges in E

The embedded structure E is a 2-complex. The two link conditions corresponding to Bd ω 0 E and Bd ω 1 E are:

Lk ω 0 (a; E) ∩ Lk ω 0 (b; E) = Lk ω 0 (ab; E), (II.0) Lk ω 1 (a; E) ∩ Lk ω 1 (b; E) = ∅. (II.1)
We show that if the i th link condition, (i = 0, 1), is violated in E, then i th link condition in K is also violated. First, we show that if ab ∈ Bd i E, then ab ∈ Bd i K, so that it is meaningful to talk about contracting ab in i th boundary of K.

It is clear that ab ∈ Bd 0 K since ab ∈ E ⊂ K ⊂ K. Now, suppose ab ∈ Bd 1 E. The order of an edge in a 2-complex cannot be two or higher. So, Ord(ab; E) = 1. Using Lemma 1, ab ∈ Bd 1 K. Thus, if ab ∈ Bd i E, then ab ∈ Bd i K. Now, suppose i th link condition is violated in E while contracting edge ab. Then there is a simplex Case 1. Link condition (II.0) is violated: Since Bd ω 0 E is a 2-complex, s is either an edge or a vertex. Case 1a. s is an edge, say v 1 v 2 :

s ∈ Bd ω i E such that s ∈ Lk ω i (a; E), s ∈ Lk ω i (b; E) and s ∈ Lk ω i (ab; E). (a) (b) (c) (d)
If

v 1 = ω and v 2 = ω, then av 1 v 2 ∈ E and hence σav 1 v 2 ∈ K, see Fig- ure 6(a). So, σv 1 v 2 ∈ Lk ω 0 (a; K). Similarly, σv 1 v 2 ∈ Lk ω 0 (b; K). Therefore, Lk ω 0 (a; K) ∩ Lk ω
0 (b; K) contains a triangle. Now, assume that either v 1 or v 2 is the dummy vertex ω. Without loss of generality, let v 1 be the dummy vertex. Since cones from ω are added only to simplices in Bd 1 E, Ord(av 2 ; E) = 1. Using Lemma 1, Ord(σav 2 ; K) = 1 and so ωσav 2 ∈ Bd ω 0 K, see Figure 6

Since Bd ω 1 E is a 1-complex, s is a vertex, say v. Case 2a. v ∈ E: Ord(av; E) = 1 since Bd ω 1 E is a 1-complex. Using Lemma 1, Ord(σav; K) = 1, which implies σv ∈ Lk ω 1 (a; K), see Fig- ure 6(c). Similarly, σv ∈ Lk ω 1 (b; K). There- fore, Lk ω 1 (a; K) ∩ Lk ω 1 (b; K) contains an edge. Case 2b. v is ω:
Since in Bd ω 1 E, cones from ω are added only to vertices of order 2, Ord(a; E) = 2. Using Lemma 4, Ord(σa; K) = 2. Hence, ωσa ∈ Bd ω 1 K and ωσ ∈ Lk ω 1 (a; K), see Figure 6

(d). Similarly, ωσ ∈ Lk ω 1 (b; K). Therefore, Lk ω 1 (a; K) ∩ Lk ω 1 (b; K) contains an edge.
In both cases the link condition (III.1) is violated because Lk ω 1 (ab; K) cannot contain an edge.

2-complexes

We now consider the analogous problem in 2D, where K is a 2-complex and E is a 1-complex disjoint from Bd 1 K. Vivodtzev et al. [START_REF] Vivodtzev | Topology Preserving Simplification of 2D Non-Manifold Meshes with Embedded Structures[END_REF] describe a proof of topology preservation by claiming that Bd 1 K = E ∪ Bd 1 K. However, this is not true because Bd 1 K contains edges incident on σ in addition to edges in E ∪ Bd 1 K. For example, in Figure 5(b), the edges σa, σb, σc and σd are all order-1 edges. Moreover, the arguments used in their proof infers order of an edge by considering the number of triangles shared by the edge. These arguments do not extend to the case of 3-complexes. For instance, the star of an edge in 3-complexes contains several tetrahedra but the number of tetrahedra do not directly indicate the order of the edge. Our arguments look at relationship between star of simplices in E and K to infer the order of a simplex. This approach is more general than the earlier arguments [START_REF] Vivodtzev | Topology Preserving Simplification of 2D Non-Manifold Meshes with Embedded Structures[END_REF] and we prove the result in the case of 2D meshes using arguments analogous to the 3D case.

Topology preservation of K and topology preservation of E while contracting edges that do not lie in E, can be shown using the same arguments as in the 3D case. For the sake of completeness, we describe topology preservation of E when an edge from E is contracted, although this is analogous to the 3D case.

Since E is a 1-complex, E has one link condition given by:

Lk ω 0 (a; E) ∩ Lk ω 0 (b; E) = ∅. (I.0)
We show that if contracting an edge ab ∈ E violates link condition (I.0), then link conditions are violated in K as well. Since E is a 1-complex, only vertices can be present in Lk ω 0 (a; E) ∩ Lk ω 0 (b; E). The vertex, v, that violates link condition (I.0) can either be a vertex in E or the dummy vertex ω. and ωσ ∈ Lk ω 0 (a; K), see Figure 7(b). Similarly, ωσ ∈ Lk ω 0 (b; K). Therefore, Lk ω 0 (a; K) ∩ Lk ω 0 (b; K) contains an edge. Since K is a 2-complex, Lk ω 0 (ab; K) cannot contain an edge. Hence, in both the cases 0 th link condition is violated in K.

Embedded structure on boundary

We now extend our result to include embedded structures that intersect the boundary of K. This assumption is a serious shortcoming of the previous result [START_REF] Vivodtzev | Substructure Topology Preserving Simplification of Tetrahedral Meshes[END_REF], [START_REF] Vivodtzev | Topology Preserving Simplification of 2D Non-Manifold Meshes with Embedded Structures[END_REF] because embedded structures often lies on the boundary, as shown in our applications.

Lemmas 1-4 clearly show that the relation between order of a simplex in E and K does not change whether embedded structure intersects the boundary of K or not. However, Lemma 5 is not necessarily true when we remove the assumption on E. For example, if E contains a triangle, say abc, which is part of a single tetrahedron in K, then Ord(abc; K) = 1. However, the triangle abc ∈ K is incident on two tetrahedra due to the cone from σ and hence Ord(abc; K) = 0. Thus Bd ω 1 K ⊆ Bd ω 1 K. However, note that Lemma 5 is not necessary to show that topology of E is preserved while contracting an edge. A simple solution that ensures that topology of K is also preserved is to verify that link conditions of K are satisfied in addition to the link conditions for K. Although this additional validation seems to require evaluation of three new link conditions, in practice, the link conditions for K and K can be verified in a single procedure.

Necessity of Link Conditions

For a manifold M , the link condition for an edge ab is Lk(a; M ) ∩ Lk(b; M ) = Lk(ab; M ). For 2-manifolds and 3-manifolds, link conditions are necessary for ensuring topology preservation [START_REF] Dey | Topology preserving edge contraction[END_REF]. The assumption of the domain being a manifold is very restrictive and does not hold in many practical situations. However, in a more general setting of non-manifolds, link conditions are not necessary for ensuring topology preservation. In this section, we show that under practically reasonable assumptions, link conditions are almost always necessary. In particular, when K is a 2-manifold with or without boundary, E is a 1-manifold with or without boundary, and E ∩ Bd 1 K = ∅, we show that except for two special cases, the link conditions of K are necessary for preserving the topology of K and E.

Since necessity of link conditions for topology preserving simplification of meshes with embedded structures were not studied earlier, it was not clear if such simplifications were too conservative and disallowed edge contractions that preserved the topology but violated link conditions. Our result shows that 2D mesh simplification with embedded structures is nearly optimal using link conditions, in the sense that most of the edge contractions that we disallow do in fact modify topology. Section 7.2 describes an example of link condition violation that results in modification of the topology of the embedded structure. We describe the proof of necessity of link conditions in Appendix B.

IMPLEMENTATION

Our implementation of simplification of 3D meshes with embedded structures essentially contracts edges that satisfy link conditions. The input mesh represents a 3-manifold with or without boundary. The simplification proceeds until the number of vertices in the mesh reaches a user-specified threshold, v, or until no edge can be contracted without violating topology, whichever happens earlier.

Data structure and algorithm

We represent the input mesh using the triangle-edge data structure [START_REF] Mucke | Shapes and Implementations in Three Dimensional Geometry[END_REF]. Each triangle has a flag to identify if the triangle belongs to E. We use quadric error metric [START_REF] Garland | Surface simplification using quadric error metrics[END_REF] to handle 3D meshes with a scalar field and improve the quality of the mesh [START_REF] Natarajan | Simplification of three-dimensional density maps[END_REF]. In order to ensure that the geometry of the embedded structure is minimally affected, triangles in the embedded structure are treated similar to boundary triangles i.e. edges that are incident on the embedded structure are penalized with a higher weight. Edges are selected from a priority queue in the order of increasing cost. Function SIMPLIFY describes the high level algorithm. Implementation details, except for the evaluation of order of simplices in K, can be found in earlier work [START_REF] Garland | Surface simplification using quadric error metrics[END_REF], [START_REF] Natarajan | Simplification of three-dimensional density maps[END_REF].

SIMPLIFY(K)

Initialise priority queue Q with edges in K while(# of vertices > v and Q.notempty()) do ab = Q.pop() if(Link Conditions for K and K are satisfied) Contract ab and update K and Q endif endwhile

Computing the order of simplices in K

Simplices that are not part of E have the same order in K and K. Hence we consider only simplices whose order is different in K and K in this section. We describe in detail the computation of order when the embedded structure is a 2-manifold with or without boundary. For non-manifold embedded structures, the order is evaluated on a case by case basis.

Tetrahedra: All tetrahedra incident on σ have order 0.

Triangles: A triangle abc ∈ E ∩ Bd 1 K is incident on exactly two tetrahedra, one in K and the other a cone from σ, and hence Ord(abc; K) is 0. If abc lies in the interior of K then abc is incident on three tetrahedra and hence has order 1. The triangle could also be a cone Edges: For an edge σa, Ord(σa; K) = Ord(a; E). For edges in E, we consider the following two cases.

Case 1. Edge ab ∈ E lies on Bd 1 K: If ab is incident on exactly two triangles abc and abd in E and if both abc and abd are on Bd 1 K as shown in Figure 8(a), then Ord(ab; K) is 0. This is because the half sphere St(ab; K) grows to become a sphere in K after adding the cones from σ. If, at least one triangle, say abc is in the interior of K, as shown in Figure 8 Vertices: For a vertex a ∈ Bd 1 K, Ord(a; K) = Ord(a; E)+1, using isomorphic subdivisions of St(ab; E) described in Figure 9(a) and Figure 9(c). For a vertex a ∈ Bd 1 K, if St(a; E) ⊂ Bd 1 K, then Ord(a; K) = Ord(a; E), using the subdivision of St(ab; K), described in Figure 8(a) and Figure 8(c). If St(a; E) is a disk such that a half disk lies on Bd 1 K and the remaining half disk lies in the interior of K, then Ord(a; K) is 2, using the subdivision of St(ab; K), described in Figure 8(b). If St(a; E) is a half disk that lies in the interior of K, then Ord(a; K) is 2, using the subdivision of St(ab; K), described in Figure 8(d).

Although it is possible to analyse the remaining cases when a lies on Bd 1 K and its star lies partially in the interior of K, for ease of computation and bookkeeping involved during implementation, we consider such a vertex to have order 3. Overestimating the order of the vertex assures that the topology is preserved at the cost of preventing a few legal edge contractions.

APPLICATIONS

Study of Seismic Activity

Geophysicists model the earth at different scales in space and time in order to study different phenomena including the convection in the terrestrial crust that influences tectonic plates dynamics, the convection in the outer core region for the generation of earth's magnetic field [START_REF] Glatzmaier | A three-dimensional selfconsistent computer simulation of a geomagnetic field reversal[END_REF], or at a smaller scale, the propagation of seismic waves in a particular site of earth's surface [START_REF] De La Puente | Discontinuous Galerkin Methods for Wave Propagation in Poroelastic Media[END_REF].

All these phenomena share in common the fact that one or more regions of homogeneous behaviour are separated by strong discontinuities that play a crucial role in the physical process. For example, in the generation of earth's magnetic field, the Gutenberg and the Lehmann discontinuities respectively separating the outer core region from the mantel above and from the inner core below are the key to the simulation of thermal convection. In the simulation of seismic waves for a specific site of earth's surface, the clear separation between different geological formation and soil types, as well as the precise modeling of faults are crucial. For example, solid rocks tend to transmit seismic waves without transformation while sandy and clay soils will amplify them.

Figure 10 shows a tetrahedral mesh modeling the different soil types and faults in a local site. Embedded structures in the mesh can be used to represent the faults and the interfaces between soil types. These embedded structures, shown in yellow, form a non-manifold surface with non-manifold edges at the intersection between interfaces. Vertices of order 3 are obtained whenever these non-manifold edges reach the boundary of the mesh. Our simplification process preserves the complex non-manifold topology of the embedded structures even at a very coarse scale. of isosurfaces may be important in medical applications like cortex labeling, organ template fitting, etc. In CAD modeling, features like tunnels and holes are used in identifying important characteristics of the model.

Isosurface Topology Preservation

Our simplification technique can be applied to preserve topology of specific isosurfaces in the case of tetrahedral meshes. Triangles that constitute the isosurface need not be part of the input mesh. So, we consider an outer and inner envelope of the isosurface such that triangles in the envelope are faces of tetrahedra in the input mesh, see Figure 11. The envelope thus identifies an isovolume that contains the isosurface. We treat the inner and outer envelopes as embedded structures while simplifying the volume. Since the topology of the envelope is preserved, the topology of the isovolume enclosed by the two envelopes is also preserved. Hence the topology of the original isosurface is preserved. It may happen that the simplified envelopes are not the envelopes of the isosurfaces computed on the simplified meshes. However, we can prevent this artifact by choosing the simplified scalar field values to lie outside that of the envelope surfaces.

Figure 12 shows isosurface extracted from the original and simplified Bucky Ball dataset. The isosurface in Figure 12(b) is very similar to the original isosurface, however changes can be noticed in Figure 12(c). This happens because the edges incident on the envelopes have a higher cost and hence the volume between the envelopes change only after 70% simplification is done.

Molecular Surface Topology Preservation

Modeling of molecular surfaces of proteins is useful in applications like biomolecular recognition, study of drug binding cavities, etc. Preserving the topology of the molecular surface is important in studying the properties of the molecule. For example, the stability of a protein depends on the number and size of voids [START_REF] Chakravarty | A procedure for detection and quantitation of cavity volumes in proteins: application to measure the strength of the hydrophobic driving force in protein folding[END_REF]. A molecule in solution is represented by a volume mesh. We simplify the mesh while preserving the topology of the molecular skin surface [START_REF] Cheng | Quality mesh generation for molecular skin surfaces using restricted union of balls[END_REF] , which is specified as an embedded structure. Figure 13 shows a molecular surface embedded within a tetrahedral mesh having a spherical boundary. The molecular surface is very dense in the sense that many of the vertices of the mesh lie on the molecular surface. So, most of the edges selected for contraction lie on the molecular surface. This results in the spherical boundary remaining unchanged even after removing 90% of the vertices. Our technique preserves the topology of the molecular surface even though the simplification is essentially restricted to the molecular surface.

EXPERIMENTS

We simplify four datasets and measure the root mean square error, the time taken, and the standard deviation of dihedral, solid, and face angles during simplification. Three datasets from the AIM@SHAPE repository, (BUCKY BALL, PLASMA64, and LIQUID OXYGEN POST) have a scalar field associated with them. In each case, we are interested in preserving the topology of one or more isosurfaces extracted from the data. For each vertex of the original mesh, the corresponding location in the simplified mesh is determined by interpolating inside tetrahedra of the simplified mesh. The difference between the scalar field value at these two locations determine the root mean square error. The fourth dataset represents a molecule in solution (PDB ID: 193L), where the surface of the molecule is stored as the embedded structure, see Section 6.3. Error introduced by the simplification is measured as the rms distance between the two surfaces. The datasets are normalised so that the spatial coordinates and function values lie between 0 and 1.

Results

Table 1 lists the average root mean square error introduced and the time taken during simplification of the four datasets. The average values of dihedral, solid, and face angles remain nearly constant, close to 1.22, 0.53, and 1.05 radians respectively. The standard deviation increases with simplification as shown in Figure 15.

Topology violation without using Link Conditions

The quadric error metric as described in Section 5.1 aims to preserve the geometry of the mesh and the embedded structure. We now illustrate, using an example, the importance of link conditions to ensure topology preservation.

Figure 14 shows a thin ring-like section in the embedded structure of the LIQUID OXYGEN POST dataset. The magnified view shows that the ring-like section is a 2-manifold with boundary. A simplification without checking link conditions of K creates a principal edge (i.e. no cofaces). This shows violation of the topology of the embedded surface since the original embedded surface did not contain a principal edge. This example shows that a naïve simplification approach will not be suitable for applications that require guarantee about topology preservation.

CONCLUSION

We prove theoretically the correctness of the link conditions proposed earlier [START_REF] Vivodtzev | Substructure Topology Preserving Simplification of Tetrahedral Meshes[END_REF], [START_REF] Vivodtzev | Topology Preserving Simplification of 2D Non-Manifold Meshes with Embedded Structures[END_REF] for topology preserving simplification of meshes with embedded structures. Our approach results in a unified proof for 2D and 3D meshes. We also demonstrate usefulness of this technique in three novel applications: soil interface preservation in geophysics, isosurface topology preservation, and molecular surface topology preservation. Besides preserving the scalar field and creating good quality mesh elements, our implementation also ensures that the geometry of the embedded structure is preserved.

In this paper, we have analysed the necessity of the mesh simplification technique for 2D meshes with 1D embedded structures. The necessity of the technique in the case of 3D meshes needs to be analysed. Currently, we require a detailed case analysis for computing the order of simplices. We plan to explore other approaches to compute the order of a simplex. Since such techniques would measure the topological complexity of simplices, they may provide better insights in identifying important features of a mesh. Lemma 2. For an edge ab ∈ E, if Ord(ab; E) = 0, then Ord(σab; K) = 0.

APPENDIX A PROOF OF LEMMAS

Proof: Since Ord(ab; E) = 0, ab is either principal or incident on exactly two triangles (Figure 16(c)). Hence in K, σab is principal or incident on exactly two tetrahedra (Figure 16(d)) and therefore Ord(σab; K) = 0. tetrahedron σay i y i+1 and corresponding to each principal edge av, St(σa; K) contains the principle triangle σav. It is not possible to have isomorphic subdivisions of St(σa; K) and star of a triangle in any arbitrary complex because of the principal triangles in St(σa; K). So, Ord(σa; K) = 2. Case 2b. ax is incident on more than two triangles:

In this case, ab is incident on one triangle and ax is incident on more than two triangles, as shown in Figure 18(b). Hence, St(σa; K) will contain the triangle σab, which is incident on only one tetrahedron, and σax which is incident on more than two tetrahedra. No subdivision of star of a triangle in any arbitrary complex can contain triangles incident on one and more than two tetrahedra at the same time. Thus Ord(σa; K) = 2. The above arguments extend to the case when ab is incident on more than two triangles and ab and ax are incident on different number of triangles.

The only case remaining is when ab and ax do not form half disks but are incident on the same number of triangles. At least two of the triangles incident on ab remain connected even when edge ab is removed. This implies, at least two of the tetrahedra incident on σab remain connected even when the triangle σab is removed. Note that the above mentioned tetrahedra lie in St(σa; K). Now, consider a triangle in an arbitrary complex whose star contains at least three tetrahedra. One of the triangles in the subdivision of this star satisfies the property that its removal disconnects the incident tetrahedra. The existence of such a triangle implies that St(σa; K) and the star of a triangle cannot have isomorphic subdivisions. So, Ord(σa; K) = 2. Lemma 5. Bd ω i K ⊆ Bd ω i K, ∀i ≥ 0. Proof: Except for the simplices in E, all other simplices have the same star in K and K. Hence the only simplices whose order may differ between K and K are those in E. For a simplex s ∈ E, Ord(s; K) = 0 since E ∩ Bd 1 K = ∅. Since order of a simplex is a non-negative number, Ord(s; K) ≥ 0. Hence Bd ω i K ⊆ Bd ω i K. Note that the assumption, E ∩Bd 1 K = ∅, is essentially required only for the proof of Lemma 5.

APPENDIX B PROOF OF NECESSITY CONDITIONS

The link conditions for K,

Lk ω 0 (a; K) ∩ Lk ω 0 (b; K) = Lk ω 0 (ab; K), (1)
Lk

ω 1 (a; K) ∩ Lk ω 1 (b; K) = ∅. (2)
are not necessary in the following special cases. 19(a). In this case, there is no topology violation since the complex before and after contraction is topologically equivalent. However, link condition (1) is violated as an edge is present in Lk ω 0 (a; K) ∩ Lk ω 0 (b; K). Exception 2. Lk ω 0 (a; K) ∩ Lk ω 0 (b; K) contains an edge xy such that either ya or yb lies on the boundary of K (Figure 19(b)). If ya and yb were not on the boundary of K, then after contraction of ab, the edge yc would have been incident on three triangles and hence caused a topology violation. However, without loss of generality, say ya is on the boundary. After contraction, yc is incident on two triangles and hence there is no topology violation. We now show that, in all other cases, whenever link conditions of K are violated, the topology of K or E changes. The link conditions of K could be violated in three ways: The only edges in Bd ω 0 K that are not part of K are the edges incident on either σ or ω. Since all the edges in E are part of three triangles in K, the order of any edge in E is 1 in K. Hence for any simplex s ∈ Bd ω 0 K, if cone from σ is added to s, then cone from ω is also added to s. So we can assume without loss of generality that x is ω.

Fig. 1 .Fig. 2 .

 12 Fig. 1. (a) Original and (b) simplified volume containing embedded structure shown in grey.

Figure 1 (

 1 a), 2(a) show the surface of a grey spherical ball embedded inside a cube. The mesh and the embedded structure, after simplification, is shown in Figure 1(b), 2(b).

Fig. 4 .

 4 Fig. 4. (a) Simplicial complex K before contracting edge ab. (b) After contraction, yc is incident on three triangles and hence topology of K is not preserved.

Figure 4

 4 illustrates topology violation when an edge is contracted without checking link conditions. Edge ab of a 2-complex K, shown in Figure4(a), is contracted to c as shown in Figure4(b). Topology is violated since edge yc after contraction is incident on three triangles, vyc, xyc, and uyc. However, checking link conditions prevents this situation since xy ∈ Lk ω 0 (a; K) ∩ Lk ω 0 (b; K) but xy ∈ Lk ω 0 (ab; K).

Fig. 5 .

 5 Fig. 5. (a) Simplicial complex K with embedded structure in blue and (b) K obtained by inserting cones from σ.

Case 1 .

 1 a, b ∈ E: None of the vertices of E are affected by the contraction. So F = E and topology of E is preserved. Case 2. a ∈ E; b ∈ E: After contracting ab, all simplices <v 1 , . . . , v n , a>∈ E become <v 1 , . . . , v n , c>∈ F . This renaming of a vertex does not change the topology of E. Case 3. a, b ∈ E; ab ∈ E:

Fig. 6 .

 6 Fig. 6. Different cases in which link conditions are violated. Link of a contains (a) σv 1 v 2 (b) ωσv 2 (c) σv (d) ωσ.

Fig. 7 .

 7 Fig. 7. (a) K contains σav and σbv since cones from σ are added to av and bv. (b) Cone from ω added to σa since Ord(σa; K) = 1.

Fig. 8 .Fig. 9 .

 89 Fig. 8. (a) St(ab; E) contains triangles abc and abd, both lying in Bd 1 K. (b) St(ab; E) contains triangle abd on Bd 1 K and abc in the interior of K. (c) St(ab; E) contains exactly one triangle abc lying in Bd 1 K. (d) St(ab; E) contains exactly one triangle abc lying in the interior of K.

Fig. 10 .

 10 Fig.10. Tetrahedral mesh modeling different soil types at 100%, 30%, and 10% (from left to right) of original data. First row shows the boundary of the mesh. Second row shows a cutaway view of the mesh interior with tetrahedra on the left and the embedded surface in yellow. Third row shows the embedded surface.

Fig. 11 .Fig. 12 .

 1112 Fig. 11. (a) A cube along with an extracted isosurface shown in brown. (b) A cut section of the isosurface sandwiched between inner and outer envelopes shown in pink. (c) The simplified mesh and the extracted isosurface. (d) The cut section after simplification. Topology of isosurfaces gives insights about important features of the underlying volumetric data. The topology

Fig. 13 .

 13 Fig. 13. Molecular surface simplification. The mesh representing the volume occupied by the protein molecule (PDB ID: 193L) is simplified while preserving the topology of the molecular surface. (a), (b), and (c) show molecular surface at 100%, 30%, and 10% respectively of original data.

Fig. 14 .

 14 Fig. 14. Topology violation of embedded structure. (a) Embedded structure with a ring like portion. (b) Magnified view of the ring like portion which is a 2-manifold with boundary. (c) A principal edge appears (shown in red) after simplification. This indicates topology violation since the original embedded structure did not contain a principal edge.

Fig. 15 .

 15 Fig. 15. Graph showing increase in standard deviation of dihedral, solid, and face angles for Liquid Oxygen Post dataset.

Lemma 1 .Fig. 16 .

 116 Fig. 16. (a) An order-1 edge ab in E and (b) the corresponding order-1 triangle σab in K. (c) An order-0 edge ab in E and (d) the corresponding order-0 triangle σab in K. Proof: Ord(ab; E) = 1. So, St(ab; E) has either exactly one triangle (as shown in Figure 16(a)) or more than two triangles and hence St(σab; K) has either exactly one tetrahedron (Figure 16(b)) or more than two tetrahedra. Thus Ord(σab; K) = 1. Since order of a face cannot be less than its coface, Ord(ab; K) ≥ 1.

Lemma 3 .Lemma 4 .Fig. 17 .Fig. 18 .

 341718 Fig. 17. (a) A 1-complex with a vertex a on its 1-boundary. Note that all vertices with degree not equal to two, lie on the 1-boundary. (b) Add cones from σ to the 1-complex. The edge σa is incident on three triangles and therefore lies on the 1-boundary of the 2-complex. Proof: Case 1. a ∈ Bd 1 Bd 1 E:Since all the edges in Bd 1 E are order-1 edges in E, in particular, the edges incident on a in Bd 1 E are order-1 edges in E. By Lemma 1, the triangles in K formed by adding cones from σ to these edges have order 1. Since Bd 1 E is a 1-complex, a is incident on one or more than two edges (see Figure17(a)). Hence, the edge σa is incident on one or more than two triangles in K(see Figure 17(b)). Hence σa ∈ Bd 1 Bd 1 K. We know from [9] that Bd 1 Bd 1 K ⊆ Bd 2 K. Therefore σa ∈ Bd 2 K. Thus Ord(σa; K) = 2. Case 2. a ∈ Bd 1 Bd 1 E:Degree of a in Bd 1 E is exactly 2. Besides the edge ab, assume that the vertex a is incident on edge ax. Since Ord(ab; E) = 1, ab is incident on either exactly one or more than two triangles in E. Let ab be incident on exactly one triangle. Since all edges incident on a, besides ax and ab, have order 0, the star of a contains a half disk as shown in Figure18. We now consider two cases based on the number of triangles incident on ax. Case 2a. ax is incident on one triangle:In this case the sequence of triangles aby 1 , ay 1 y 2 , . . . , ay n x form a half disk of triangles. If St(a; E) is exactly a half disk, then Ord(a; E) = 1. However, we know Ord(a; E) = 2, hence St(a; E) must contain at least one principal edge in addition to the half disk, as shown in Figure18(a).Corresponding to each triangle, ay i y i+1 in the half disk, St(σa; K) contains the

Fig. 19 .Exception 1 .

 191 Fig. 19. Two exceptions where the edge ab can be contracted without violating topology, but violates the link conditions. (a) Exception 1 : a, x, and b are the first 3 vertices in E. (b) Exception 2 : ya is on the boundary of K. Exception 1. Lk ω 0 (a; K) ∩ Lk ω 0 (b; K) contains an edge σx where a, x, and b are three vertices of E as shown in Figure19(a). In this case, there is no topology violation since the complex before and after contraction is topologically equivalent. However, link condition (1) is violated as an edge is present in Lk ω 0 (a; K) ∩ Lk ω 0 (b; K). Exception 2. Lk ω 0 (a; K) ∩ Lk ω 0 (b; K) contains an edge xy such that either ya or yb lies on the boundary of K (Figure19(b)). If ya and yb were not on the boundary of K, then after contraction of ab, the edge yc would have been incident on three triangles and hence caused a topology violation. However, without loss of generality, say ya is on the boundary. After contraction, yc is incident on two triangles and hence there is no topology violation. We now show that, in all other cases, whenever link conditions of K are violated, the topology of K or E changes. The link conditions of K could be violated in three ways:

Case 1 .

 1 An edge xy violates link condition (1): Case 1a. xy ∈ K: Since Exception 2 is excluded, the edge ya is part of two triangles in Kyax and yau. Similarly, yb is part of two triangles in Kybx and ybv (Figure 20(a)). If u = v, after contracting ab to c, the edge yc is part of three triangles, ycx, ycu, and ycv.

Fig. 20 .

 20 Fig. 20. (a) After contracting ab to c, yc becomes part of three triangles. (b) If ab contracts to c, the edge xc would be incident on three triangles.

Fig. 21 .Case 2 . 3 .

 2123 Fig. 21. (a) Bd 1 K or E becomes a non-manifold after contracting ab. (b) Contracting edge ab creates a new cycle in Bd 1 K or E. Case 2. Link condition (1) is violated only by vertices, say vertex x: If x is not σ or ω, then edge ax, bx, and ab exist, but the triangle axb does not exist. Since K cannot have principal edges, there exists triangles axu and bxv. We can assume that u = v, since Lk ω 0 (a; K) ∩ Lk ω 0 (b; K) does not contain any edges. If both ax and bx were part of exactly one triangle, then Lk ω 0 (a; K) ∩ Lk ω 0 (b; K) would have contained the edge ωx. Hence we can assume that ax is shared by a second triangle, axz (Figure 20(b)). After contracting ab to c, the edge xc becomes part of three triangles, xzc, xcu, and xcv and thus topology of K changes. If x is either σ or ω, then a and b are vertices in E or Bd 1 K. We can assume without loss of generality that x is ω since all the cones added from σ are also added from ω. If there is no path from a to b in link of ω then contracting ab would violate topology as it would connect two components which are disconnected in Bd 1 K. If there is a path from a to b in link of ω, then since Lk ω 0 (a; K) ∩ Lk ω 0 (b; K) contains no edges, the path contains at least 3 edges (Figure 21(b)). Otherwise if ay, yb are the only two edges, then edge ωy ∈ Lk ω 0 (a; K) ∩ Lk ω 0 (b; K). Hence contracting ab introduces a new cycle and changes topology of E or Bd 1 K. Case 3. Link condition (2) is violated by a vertex x: If x ∈ K, then the cycle ax, bx, and ab exists in E ∪ Bd 1 K and the cycle would be destroyed by contracting ab thus changing the topology of E or Bd 1 K. If x is ω or σ, a and b are degree-1 vertices in E. We have already considered this case earlier in Case 1b.

  (b). Hence ωσv 2 ∈ Lk ω 0 (a; K).

	Similarly, ωσv 2 ∈ Lk ω 0 (b; K). Therefore,
	Lk ω 0 (a; K) ∩ Lk ω 0 (b; K) contains a triangle.
	In both cases the link condition (III.0) is vi-
	olated because Lk ω 0 (ab; K) cannot contain
	a triangle.
	Case 1b. s is a vertex, say v:
	If v = ω, then av, bv ∈ E and abv ∈ E
	which implies σav, σbv ∈ Bd ω 0 K and
	σabv ∈ Bd ω 0 K. Hence σv ∈ Lk ω 0 (a; K) ∩
	Lk ω 0 (b; K) and not in Lk ω 0 (ab; K), see Fig-
	ure 6(c). Thus link condition (III.0) is vio-
	lated.
	If v is ω, then since link condition
	(II.0) is violated, ω ∈ Lk ω
	However, since Ord(ab; E) = 0, it follows
	from Lemma 2, that Ord(σab; K) = 0 and
	hence ωσ ∈ Lk ω 0 (ab; K). Therefore link
	condition (III.0) is violated.
	Case 2. Link condition (II.1) is violated:

0 (ab; E). This implies ωab ∈ Bd ω 0 E, and therefore Ord(ab; E) = 0. Since ω ∈ Lk ω 0 (a; E), it follows that Ord(a; E) ≥ 1, because cones from ω are added only to simplices in Bd 1 E. Using Lemma 3, Ord(σa; K) ≥ 1. Hence ωσa ∈ Bd ω 0 K and ωσ ∈ Lk ω 0 (a; K), see Figure

6(d)

. Similarly, ωσ ∈ Lk ω 0 (b; K).

TABLE 1

 1 Results of simplification of three isosurface and a molecular surface dataset. The time taken is measured on a 2 GHz Intel Xeon CPU.

	Dataset	%	#vert	rms time (sec)
		100 262144	0	0
		50 131072	0.024	34
	Bucky Ball	20	52428	0.035	60
		10	26214	0.037	71
		5	13107	0.041	78
		100 274625	0	0
		50 137312	0.032	35
	Plasma64	20	54925	0.035	62
		10	27462	0.036	72
		5	13731	0.037	78
		100 108300	0	0
		50	54150	0.051	17
	Liquid Oxygen Post	20	21660	0.084	27
		10	10830	0.095	30
		5	5415	0.105	33
		100	34920	0	0
		50	17460	0.008	6
	Molecule	20	6984	0.021	11
		10	3492	0.047	13
		5	1746	0.127	14

ACKNOWLEDGMENTS

We thank Dr. Fabien Vivodtzev for his valuable inputs and contributions to this paper. We thank Dr. Basudeb Datta for discussions on the correctness of proof of topology preservation, and Dr. Philippe Gueguen for discussions on applications in geophysics. We also thank Dr. Xinwei Shi for skin meshing software and AIM@SHAPE repository for providing interesting datasets.