Sébastien Fourey
email: sebastien.fourey@greyc.ensicaen.fr

Luc Brun
email: luc.brun@greyc.ensicaen.fr

A first step toward combinatorial pyramids in nD spaces

Combinatorial maps define a general framework which allows to encode any subdivision of an nD orientable quasi-manifold with or without boundaries. Combinatorial pyramids are defined as stacks of successively reduced combinatorial maps. Such pyramids provide a rich framework which allows to encode fine properties of the objects (either shapes or partitions). Combinatorial pyramids have first been defined in 2D. This first work has latter been extended to pyramids of nD generalized combinatorial maps. Such pyramids allow to encode stacks of non orientable partitions but at the price of a twice bigger pyramid. These pyramids are also not designed to capture efficiently the properties connected with orientation. The present work presents our first result on the design of an nD pyramid of combinatorial maps.

Note also that an index of the definitions, propositions, lemmas and theorems is provided at the end of this report.

Introduction

Pyramids of combinatorial maps have first been defined in 2D [START_REF] Brun | Combinatorial pyramids[END_REF], and latter extended to pyramids of n-dimensional generalized maps by Grasset et al. [START_REF] Grasset-Simon | nD generalized map pyramids: Definition, representations and basic operations[END_REF]. Generalized maps model subdivisions of orientable but also non-orientable quasi-manifolds [START_REF] Lienhardt | Topological models for boundary representation: a comparison with n-dimensional generalized maps[END_REF] at the expense of twice the data size of the one required for combinatorial maps. For practical use (for example in image segmentation), this may have an impact on the efficiency of the associated algorithms or may even prevent their use. Furthermore, properties and constrains linked to the notion of orientation may be expressed in a more natural way with the formalism of combinatorial maps. For these reasons, we are interested here in the definition of pyramids of n-dimensional combinatorial maps. This paper is a first step toward the definition of such pyramids, and the link between our definitions and the ones that consider G-maps is maintained throughout the paper. In fact, the link between n-G-maps and n-maps was first established by Lienhardt [START_REF] Lienhardt | Topological models for boundary representation: a comparison with n-dimensional generalized maps[END_REF] so that it was claimed in [START_REF] Damiand | Removal and contraction for n-dimensional generalized maps[END_REF], but not explicitly stated, that pyramids of n-maps could be defined.

The key notion for the definition of pyramids of maps is the operation of simultaneous removal or contraction of cells that satisfy some criterions. Thus, we define the operation of simultaneous removal and the one of simultaneous contraction of cells in an n-map, the latter being introduced here as a removal operation in the dual map.

We first raise in Section 3.1 a minor problem with the definition of "cells with local degree 2 in a G-map" used in [START_REF] Grasset-Simon | Définition et étude des pyramides généralisées nD : application pour la segmentation multi-echelle d'images 3d[END_REF][START_REF] Damiand | Removal and contraction for n-dimensional generalized maps[END_REF] and more precisely with the criterion for determining if a cell is a valid candidate for removal. We provide a formal definition of the local degree, which is consistent with the results established in the previous papers, using the notion of a regular cell that we introduce.

An essential result of this paper, presented in Section 3.1, is that the removal operation we introduce here is well defined since it indeed transforms a map into another map. Instead of checking that the resulting map satisfies from its very definition the properties of a map, we use an indirect proof by using the removal operation in G-maps defined by Damiand in [START_REF] Damiand | Removal and contraction for n-dimensional generalized maps[END_REF][START_REF] Damiand | Removal and contraction for n-dimensional generalized maps[END_REF]. If needed, this way again illustrates the link between the two structures.

Eventually, in Section 3.2 we will state a definition of simultaneous contraction of cells in a G-map in terms of removals in the dual map, definition which we prove to be equivalent to the one given by Damiand and Lienhardt in [START_REF] Damiand | Removal and contraction for n-dimensional generalized maps[END_REF]. We finally define in the same way the simultaneous contraction operation in maps and provide a first result (Proposition 20) that justifies this definition using the latter equivalence.

Combinatorial maps

Basic definitions

Definition 1 (n-G-map [START_REF] Lienhardt | Topological models for boundary representation: a comparison with n-dimensional generalized maps[END_REF]) Let n ≥ 0, an n-G-map is defined as an n + 2tuple G = (D, α 0 , . . . , α n ) where:

• D is a finite non-empty set of darts; • α 0 , . . . , α n are involutions on D (i.e. ∀i ∈ {0, . . . , n}, α 2 i (b) = b) such that: • ∀i ∈ {0, . . . , n -1}, α i is an involution without fixed point (i.e. ∀b ∈ D, α i (b) = b); • ∀i ∈ {0, . . . , n -2}, ∀j ∈ {i + 2, . . . , n}, α i α j is an involution.

If α n is an involution without fixed point, G is said to be without boundaries or closed. In the following we only consider closed n-G-maps with n ≥ 2.

Remark 1 For any i, j ∈ {0, . . . , n} such that j ≥ i + 2, the permutation α i α j is an involution. Therefore, in any n-G-map we have: ∀i ∈ {0, . . . , n -2}, ∀j ∈ {i + 2, . . . , n}, α i α j = α j α i Indeed, if α i α j α i α j = 1 D , then α i α j α i = α -1 j = α j and α i α j = α j α -1 i = α j α i .

Definition 2 (n-map [START_REF] Lienhardt | Topological models for boundary representation: a comparison with n-dimensional generalized maps[END_REF]) An n-map (n ≥ 1) is defined as an (n + 1)-tuple M = (D, γ 0 , . . . , γ n-1 ) such that:

• D is a finite non-empty set of darts;

• γ 0 , . . . γ n-2 are involutions on D and γ n-1 is a permutation on D such that ∀i ∈ {0, . . . , n -2}, ∀j ∈ {i + 2, . . . , n}, γ i γ j is an involution.

Definition 3 (Orbit) Let Φ = {φ 1 , . . . , φ k } be a set of permutations on D (a set of darts). We denote by < Φ > the permutation group generated by Φ, i.e. the set of permutations obtained by any composition and inversion of permutations contained in Φ. The orbit of a dart d ∈ D relatively to Φ is defined by

< Φ > (d) = { φ(d) φ ∈< Φ > }
. Furthermore, we extend this notation to the empty set by defining < ∅> as the identity map. Definition 4 (Connected component) Let M = (D, γ 0 , . . . , γ n-1 ) be an n-map (resp. G = (D, α 0 , . . . , α n ) be an n-G-map). A subset D of D is called a connected component of M (resp. G) if D =< γ 0 , . . . , γ n-1 > (d) (resp. D =< α 0 , . . . , α n-1 >(d)) for some dart d ∈ D .

An n-map may be associated to an n-G-map, as stated by the next definition. In this paper, we use this direct link between the two structures to show that the removal operation we introduce for maps is properly defined (Section 3.1).

For that purpose, we notably use the fact that a removal operation (as defined by Damiand and Lienhardt) in a G-map has a counterpart (according to our definition) in its associated map and vice versa.

Definition 5 (Map of the hypervolumes) Let G = (D, α 0 , . . . , α n ) be an n-G-map (n ≥ 1). The n-map HV = (D, δ 0 = α n α 0 , . . . , δ n-1 = α n α n-1 ) is called the map of the hypervolumes of G.

Lienhardt [START_REF] Lienhardt | N-dimensional generalized combinatorial maps and cellular quasimanifolds[END_REF] proved that if the n-G-map G is orientable, HV has two connected components. In the following we only consider orientable n-G-maps and assume that an arbitrary component of the map HV is chosen.

Definition 6 (Dual and inverse)

Let G = (D, α 0 , . . . , α n ) be an n-G-map and let M = (D, γ 0 , . . . , γ n-1 ) be an n-map.

• The dual of G, denoted by G, is defined by: G = (D, α n , α n-1 , . . . , α 0 )

• The dual and the inverse of M are respectively defined by: M = (D, γ -1 0 , γ -1 0 γ n-1 , . . . , γ -1 0 γ 1 ) = (D, γ 0 , γ 0 γ n-1 , . . . , γ 0 γ 1 ) M -1 = (D, γ 0 , . . . , γ n-2 , γ -1 n-1 )

Note that we also have M -1 = (D, γ -1 0 , . . . , γ -1 n-2 , γ -1 n-1 ) since (γ i ) i∈{0,...,n-2} is an involution.

Proposition 1 If we consider the function HV which maps each n-G-map G to an n-map of the hypervolumes HV (G). We have if n > 1:

HV (G) = HV (G).

In other words the following diagram commutes:

G dual ---→ G HV       HV M dual ---→ M Proof: G = (D, α 0 , . . . , α n )
HV (G) = (D, α n α 0 , . . . , α n α n-1 ) G = (D, α n , . . . , α 0 )

HV (G) = (D, α 0 α n , . . . , α 0 α 1 ) HV (G) = (D, α 0 α n , . . . , α 0 α 1 ) Indeed, since n > 1, α n α 0 = α 0 α n and ∀i ∈ {1, . . . , n -1}, α n α 0 α n α i = α 0 α n α n α i = α 0 α i . 2

Proposition 2 (Associated maps of an n-G-map [8])

The two n-maps associated to an n-G-map G = (D, α 0 , . . . , α n ) are defined as:

M 1 = HV (G) = (D, α n α 0 , α n α 1 , . . . , α n α n-1 )
not.

= (D, γ 0 , . . . , γ n-1 )

M 2 = M 1 = HV (G) = (D, α 0 α n , α 0 α n-1 , . . . , α 0 α 1 ) not. = (D, γ 0 , . . . , γ n-1 )
Since there is a one-to-one correspondence between i-cells 1 of M 1 and (n -i)cells of M 2 = M 1 , and since there is a direct link between the subscripts of the permutations of a map and the way cells are defined, it is convenient to denote 2 (D, γ 0 , . . . , γ n-1 )

not.

= (D, β n , . . . , β 1 ).

Moreover the permutations (β i ) i∈{1,...,n} and (γ i ) i ∈{0,...,n-1} are related by the following relationships (n ≥ 2):

γ 0 = β n and ∀i ∈ {1, . . . , n -1}      γ i = β n β i β i = γ 0 γ i Proof: From Definition 6 M 2 = (D, β n , β n β 1 , . . . , β n β n-1 ). Since M 2 = M 1 = M 1 , we have γ 0 = β n and ∀i ∈ {1, . . . , n -1}, γ i = β n β i .
In the same way, we have M 1 = (γ 0 , γ 0 γ n-1 , . . . , γ 0 γ 1 ). We also have by Proposition 1, M 1 = HV (G) = HV (G) = M 2 . Therefore:

β n = γ 0 and ∀i ∈ {1, . . . , n -1} β i = γ 0 γ i 2
The two maps M 1 and M 2 associated to an n-G-map G are respectively defined as the maps of the hypervolumes of G and G. However, whenever the reference 1 Cells are formally defined in subsection 2.3.

2 These notation are also used for example in [START_REF] Damiand | Définition et étude d'un modèle topologique minimal de représentation d'images 2D et 3D[END_REF].

to the n-G-map will not be required we will simply consider that we have two dual maps describing a same partition of the space. The equivalence between these two representations is illustrated in Fig. 1 where the 2-G-map G is the triple (D = D 1 ∪ D 2 , γ 0 , γ 1 ) with: -6)

D 1 = {1, 2, 3, 4, 5, 6}, D 2 = {-1, -2, -3, -4, -5, -6} α 0 = (1, -1)(2, -2)(3, -3)(4, -4)(5, -5)(6,
α 1 = (-1, -2)(2, -1)(3, -4)(4, -3)(5, -6)(6, -5) α 2 = (1, -6)(2, -3)(3, -2)(4, -5)(5, -4)(6, -1)
The 2-map HV (G) is (D 1 , γ 0 , γ 1 ) where -5)

γ 0 = (1, 6)(2, 3)(4, 5)(-1, -6)(-2, -3)(-4,
γ 1 = (1, 5, 3)(2, 4, 6)(-2, -4, -6)(-1, -5, -3) The 2-map HV (G) is (D 2 , β 2 , β 1 )
where

β 2 = γ 0 β 1 = (1, 2)(3, 4)(5, 6)(-1, -2)(-3, -4)(-5, -6) G = (D, α 0 , α 2 , α 2 ) M 1 = HV (G) = (D 1 , γ 0 , γ 1 ) M 2 = HV (G) = (D 2 , β 2 , β 1 ) 2 3 -4 -2 -6 -3 -5

From maps to G-maps and vice versa

We first define the notion of an n-G-map associated to a given n-map. We need a precise construction scheme of the associated G-map, since Lienhard's Theorem 4 [START_REF] Lienhardt | Topological models for boundary representation: a comparison with n-dimensional generalized maps[END_REF] only stated the existence of such a G-map. • α i is defined for i ∈ {0, . . . , n -2} by:

α i : D -→ D d -→      dγ i σ if d ∈ D dσ -1 γ i if d ∈ D • α n-1 is defined by: α n-1 : D -→ D d -→      dγ -1 n-1 σ if d ∈ D dσ -1 γ n-1 if d ∈ D
• α n is defined by:

α n : D -→ D d -→      dσ if d ∈ D dσ -1 if d ∈ D Remark 2
Any map α i of Definition 7 satisfies:

α i|D : D -→ D α i|D : D -→ D (1)
Furthermore, α i|D and α i|D are both one-to-one correspondances, as the composition of bijective maps for i < n, and from the very definition of α n .

Lemma 1 If M = (D, γ 0 , . . . , γ n-1 ) is an n-map and AG(M ) = ( D, α 0 , . . . , α n ).
For all i ∈ {0, . . . , n -1} we have (α n α i ) |D = γ i . We also have (α 0 α n ) |D = γ 0 and for all i ∈ {1, . . . , n -1} and (α

0 α i ) |D = γ 0 γ i .
Proof: This comes from the very definition of the involutions α i , i ∈ {0, . . . , n} (Definition 7). Indeed, let d be a dart of D, we have dα j ∈ D for all j ∈ {0, . . . , n}.

If i ∈ {0, . . . , n -1}, by Definition 7 we obtain that dα n α i = dσσ -1 γ i = dγ i . We also have dα 0 α n = dγ 0 σσ -1 = dγ 0 . In the last case, if i ∈ {1, . . . , n -1} we have dα 0 α i = dγ 0 σσ -1 γ i = dγ 0 γ i . 2

Proposition 3 For any n-map M , AG(M ) is an n-G-map.

Proof: We show that AG(M ) satisfies the properties of G-maps (Definition 1). The set D is indeed finite and non-empty, so we need to check that the applications α i from D to D are involutions that satisfy the conditions given by the definition.

For i ∈ {0, . . . , n}, following Remark 2 and the fact that:

• D ∩ D = ∅, and
• the maps α i|D and α i|D are one-to-one we conclude that α i is one-to-one. Indeed, if Let us additionally remark that the preimage of b may be explicited. Indeed,

d 1 α i = d 2 α i for d 1 , d 2 ∈ D, it follows from (1) that either {d 1 , d 2 } ⊂ D or {d 1 , d 2 } ⊂ D . In both cases, it implies that d 1 = d 2 since α i|D (resp. α i|D )
if i < n -1 we have b = dγ i σ if d ∈ D and b = dσγ i if d ∈ D . For i = n -1 we have b = dγ n-1 σ if d ∈ D and b = dσγ -1 n-1 if d ∈ D . For i = n, b = dσ -1 if d ∈ D and b = dσ if d ∈ D .
Eventually, the maps α i are both one-to-one and onto, so they are permutations of D. Let us check that they are involutions.

The map α n is an involution since dα 2 n is either equal to dσσ

-1 = d (if d ∈ D) or to dσ -1 σ = d (if d ∈ D ). For i = n -1, we have dα 2 i = dγ -1 n-1 σσ -1 γ n-1 or dα i = dσ -1 γ n-1 γ -1 n-1 σ, which in both cases is equal to d, so α n-1 is an involution. If i < n -1, from the definition of α i we have dα i α i = dγ i σσ -1 γ i if d ∈ D since in this case dγ i σ ∈ D . Since γ i , i < n -1 is an involution we obtain dα i α i = d, so α i is an involution. (The case when d ∈ D is similar.)
We conclude that all the maps α i are involutions on D. It is also readily seen from ( 1) and the fact that D ∩ D = ∅ that these maps have no fixed points. Now, we need to check that for all i ∈ {0, . . . , n -2} and all j ∈ {i + 2, . . . , n}, α i α j is an involution. For that purpose, we simply follow Definition 7 to build the following table. The two last columns show that the equality holds for any possible value of i and j.

i j d ∈ dα i α j dα j α j < n -1 n D dγ i σσ -1 = γ i dσσ -1 γ i = γ i < n -1 n D dσ -1 γ i σ dσ -1 γ i σ < n -2 n -1 D dγ i σσ -1 γ n-1 = γ i γ n-1 dγ -1 n-1 σσ -1 γ i = γ -1 n-1 γ i < n -2 n -1 D dσ -1 γ i γ -1 n-1 σ dσ -1 γ -1 n-1 γ i σ < n -3 < n -1 D dγ i σσ -1 γ j = γ i γ j dγ j σσ -1 γ i = γ j γ i < n -3 < n -1 D dσ -1 γ i γ j σ dσ -1 γ j γ i σ
In the last four rows of the table, we simply use the fact that

γ i γ j = γ j γ i (since M is an n-map) to conclude that dα i α j = dα j α i .
The overall conclusion is that AG(M ) is indeed an n-G-map. In the same way, the notion of a sub-map of an n-G-map is used in the sequel. Its definition is similar.

Proposition 4 If M = (D, γ 0 , . . . , γ n-1 ), then we have M = HV (AG(M )) |D .

Proof: Let us consider the following (G-)maps:

• M = (D, γ 0 , . . . , γ n-1 ) • G = AG(M ) = ( D = D ∪ D , α 0 , . . . , α n ) • HV (G) = ( D, γ 0 , . . . , γ n-1 )
following Definitions 7 and 5.

We first prove that for all d ∈ D and all i ∈ {0, . . . , n -1}, dγ i = dγ i . In other word, we prove that γ i |D = γ i . Indeed, by Definition 5 and Definition 7, we have for all d ∈ D:

If i = n -1, dγ n-1 = dα n α n-1 (Definition 5) = dσσ -1 γ n-1 = dγ n-1 (Definition 7) if i < n -1, dγ i = dα n α i (Definition 5) = dσσ -1 γ i = dγ i ( Definition
For i = n C n (d) = < γ 0 γ 1 , . . . , γ 0 γ n-1 >(d)
In both an n-map and an n-G-map, two cells C and C with different dimensions will be called

incident if C ∩ C = ∅.
Proposition 5 The cells of the map M = (D, γ 0 , . . . , γ n-1 ) may be equivalently expressed according to the permutations of M = (D, β n , . . . , β 1 ) using the following equations:

For i = 0 C 0 (d) = < β -1 1 β 2 , . . . , β -1 1 β n >(d) ∀i ∈ {1, . . . , n} C i (d) = < β 0 , . . . , βi , . . . , β n >(d)
Proof: Using Proposition 2, we have for any i ∈ {2, . . . , n -1}, β -1

1 β i = γ -1 1 γ 0 γ 0 γ i = γ -1 1 γ i . Moreover, β -1 1 β n = γ -1 1 γ 0 γ 0 = γ -1 1 .
We have thus:

• For i = 0, C 0 (d) = < γ 1 , γ 2 , . . . , γ n-1 >(d) = < β n β 1 , β n β 2 , . . . , β n β n-1 >(d) = < β -1 1 β n , β n β 2 , . . . , β n β n-1 >(d) = < β -1 1 β n , β -1 1 β 2 , . . . , β -1 1 β n-1 >(d) = < β -1 1 β 2 , . . . , β -1 1 β n-1 , β -1 1 β n >(d) • For i ∈ {1, . . . , n -1}, C i (d) = < γ 0 , γ 1 , . . . , γ i-1 , γ i+1 , . . . , γ n-1 >(d) = < γ 0 , γ 0 γ 1 , . . . , γ 0 γ i-1 , γ 0 γ i+1 , . . . , γ 0 γ n-1 >(d) = < β n , β 1 , . . . , β i-1 , β i+1 , . . . , β n-1 >(d) = < β 1 , . . . , β i-1 , β i+1 , . . . , β n-1 , β n >(d) • For i = n, C n (d) = < γ 0 γ 1 , . . . , γ 0 γ n-2 , γ 0 γ n-1 >(d) = < β 1 , . . . , β n-2 , β n-1 >(d) 2
Definition 11 (Degree and dual degree of a cell) Let C be an i-cell in an n-(G-)map, 0 ≤ i ≤ n.

• The degree of C is the number of (i + 1)-cells incident to C.

• The dual degree of C is the number of (i -1)-cells incident to C. Notation 1 Let (D, α 0 , . . . , α n ) be an n-G-map. For d ∈ D, we denote by < αk 1 , αk 2 , . . . , αkp >(d), where all the involutions are excluded, the orbit < Φ> (d) where Φ = {α 0 , . . . , α n } \ {α k 1 , α k 2 , . . . , α kp }. More intuitively, the local degree of an i-cell C is the number of i + 1-cells that locally appear to be incident to C. It is called local because it may be different from the degree since an i + 1-cell may be incident more than once to an i-cell, as illustrated in Figure 3 where the 1-cell e 2 is multi-incident to the 0-cell v 2 .

e 1 v 1 v 2 e 2 4 -1 -2 2 1 -3 -4 3 v 1 = {1, 2} v 2 = {-1, 3, 4, -4, -3, -2} e 1 = {1, -1, 2, -2} e 2 = {3, 4, -3, -4}
On the other hand, the dual local degree of an i-cell C is the number of (i -1)cells that appear to be incident to C. As in the example given in Figure 3 where the egde e 2 locally appears to be bounded by two vertices, as it is always the case for a 1-cell, whereas the darts involved by the orbits considered in Definition 12 all belong to a unique vertex (v 2 ).

Property 2

The degree of a cell in an n-G-map is greater than zero and less than or equal to its local degree.

Proof: Let C be an i-cell, i ≤ n -1, in an n-G-map and d ∈ C. Following Definition 9, C i+1 (d) is not empty and d ∈ C ∩ C i+1 (d). Thus, C is incident to at least one (i + 1)-cell.
The degree of C is the number |∆| where ∆ =

/ ∈< αi+1 >(b ). Since b ∈< αi , αi+1 >(b) we deduce that < αi , αi+1 >(b) ⊂< αi+1 >(b ). As < αi , αi+1 >(b) ⊂< αi+1 >(b)
it follows that this inclusion relation allows to associate each orbit of Λ with exactly one orbit of ∆, thus to define a map from Λ to ∆. Furthermore, the inclusion < αi , αi+1 > (b) ⊂< αi+1 > (b) also implies that this map is onto. From the existence of such a map we deduce that |∆| ≤ |Λ|. 2

Property 3 (Cell with local degree 1) An i-cell C in an n-G-map is of local degree 1 if and only if for all

d ∈ C, dα i+1 ∈< αi , αi+1 >(d). Proof: If C is of local degree 1, we have { < αi , αi+1 > (d) d ∈ C } = 1. It follows that < αi , αi+1 >(d) = C for all d ∈ C. From the definition of an i-cell, dα i+1 ∈ C so that dα i+1 ∈< αi , αi+1 >(d), hence the "only if" part. If dα i+1 ∈< αi , αi+1 >(d) for all d ∈ C, it is readily seen that ∀b ∈ C, < αi , αi+1 >(b) =< αi >(b) Indeed, in b = bα k 1 . . . α kp ∈< αi > (b) any involution α k j = α i+1 may be replaced by a composition of involutions in < αi , αi+1 > since bα k 1 . . . α k j-1 ∈ C. Thus we have < αi > (b) ⊂< αi , αi+1 > (b), and obviously < αi , αi+1 > (b) ⊂< αi >(b). Hence the "if" part. 2
The following definition for a cell C with a local degree 2 is given in [START_REF] Grasset-Simon | Définition et étude des pyramides généralisées nD : application pour la segmentation multi-echelle d'images 3d[END_REF].

Definition 13 (Cell with local degree 2 [6])

• For all i ∈ {0, . . . , n -2}, an i-cell C is of local degree two if ∀b ∈ C, bα i+1 α i+2 = bα i+2 α i+1 • For all i ∈ {2, . . . , n}, an i-cell C is of dual local degree two if ∀b ∈ C, bα i-1 α i-2 = bα i-2 α i-1
In fact, according to the above definition, the 0-cell v 1 in Figure 3 would have a local degree of 2, although this is obviously not what was meant by the authors in their definition. Beside the fact that this definition does not distinguish cells with local degree 1 from cells with local degree 2, it is also far more restrictive then our definition for a cell with local degree 2 (Definition 12).

However, Grasset's definition was intended to characterize cells that could be removed from a G-map, producing a valid new G-map. To that extend, and except for the case of cells with a local degree 1, it is a good criterion but again not a proper definition for cells with local degree 2. (The removal operation in maps is the purpose of Section 3.)

For clarity, we introduce here a criterion for a cell to be removable. This criterion may be expressed as a modified version of Grasset's definition for the local degree 2 that actually excludes cells with a local degree 1. But we also provide an equivalent characterization, in terms of several conditions among which appears clearly the exact notion of local degree 2 (Theorem 1).

Lemma 3 For any i ∈ {0, . . . , n -2}, and any

i-cell C if: i) ∃b ∈ C, bα i+1 / ∈< αi , αi+1 >(b), and ii) ∀b ∈ C, bα i+1 α i+2 = bα i+2 α i+1 then C is of local degree 2.
Proof: Let C be an i-cell that satisfies conditions i) and ii). Let b ∈ C be a dart such that bα i+1 / ∈< αi , αi+1 >(b), following condition i). Eventually, let d be any other dart of C.

From the definition of a cell, we have

d = bα k 1 α k 2 . . . α kp with k h = i for all h ∈ {1, . . . , p}. For all h > 1 such that k h = i + 1, let us consider d = bα k 1 . . . α k h-2 . If k h-1 = i + 2 then from condition ii) we know that d α k h-1 α k h = d α k h α k h-1 . In the remaining cases (k h-1 / ∈ {i, i + 2}) we have either |k h -k h-1 | > 1 or k h = k h-1 , so that in both cases d α k h-1 α k h = d α k h α k h-1 (see Definition 1 when |k h -k h-1 | > 1)
. In other words, α i+1 always commutes with its predecessor in the sequence of compositions α k 1 α k 2 . . . α kp . At this point, we introduce the notion of a regular cell that will help us to clarify (with Theorem 1) the link between the proper notion of a local degree 2 and the one of cells that may indeed be removed while preserving the properties of a G-map.

It follows that we way write

d = bα r i+1 α k 1 α k 2 . . . α k q with k h / ∈ {i, i + 1} for all h ∈ {0, . . . , q } and r ∈ N. Eventually, if r is even we have d = (b)α k 1 α k 2 . . . α k q and if r is odd, d = (bα i+1 )α k 1 α k 2 . . . α k q . In other words, d ∈< αi , αi+1 >(b) or d ∈< αi , αi+1 >(bα i+1 ).

Definition 14 (Regular cell)

An i-cell (i ≤ n -2) in an n-G-map is said to be regular if it satisfies the two following conditions: a) ∀d ∈ C, dα i+1 α i+2 = dα i+2 α i+1 or dα i+1 α i+2 ∈< αi , αi+1 > (dα i+2 α i+1 ), and b) ∀b ∈ C, bα i+1 / ∈< αi , αi+1 >(b)
Note that condition a) of the above definition may be read as an implication, in other words:

∀d ∈ C, if dα i+1 α i+2 = dα i+2 α i+1 then dα i+1 α i+2 ∈< αi , αi+1 >(dα i+2 α i+1 )
As an illustration, Figure 4 depicts a vertex with local degree 2 in a 3-Gmap, vertex which is not regular according to the above definition. Following Grasset et al.'s criterion, such a vertex is not considered as removable because it does not have a local degree two (according to their definition of the local degree). In our case, this vertex actually has a local degree two but is still excluded because it is not regular.

Lemma 4 Let G be an n-G-map and C be an

i-cell of G for i ∈ {0, . . . , n-2}. If both conditions i) and ii) below are satisfied, i) ∃b ∈ C, bα i+1 / ∈< αi , αi+1 >(b), and ii) ∀b ∈ C, bα i+1 α i+2 = bα i+2 α i+1 then C is regular. Proof: The proposition a) of Definition 14 is trivial from ii).
Let us consider a dart b which satisfies i) and an arbitrary dart

d ∈ C. Using Lemma 3, d ∈< αi , αi+1 >(b) or d ∈< αi , αi+1 >(bα i+1 ) with: < αi , αi+1 >(b) =< αi , αi+1 >(bα i+1 ). Let us suppose that d ∈< αi , αi+1 > (b). We have thus d = bα j 1 . . . α jp with j k ∈ {0, . . . , n} -{i, i + 1} for all k. • If j k = i + 2, for any k ∈ {1, . . . , p} then α i+1 commutes with any α j k , k ∈ {1, .
. . , p} and we have:

dα i+1 = bα i+1 α j 1 . . . α jp .
• Otherwise, let us consider the greatest index h such that j h = i + 2. By definition of h we have:

dα i+1 = bα j 1 . . . α jp α i+1 = bα j 1 . . . α j h-1 α i+2 α i+1 α j h+1 . . . α jp
with both sequences α j 1 . . . α j h-1 and α j h+1 . . . α jp being possibly empty. Since bα j 1 . . . α j h-1 belongs to C we have by ii):

bα j 1 . . . α j h-1 α i+2 α i+1 α j h+1 . . . α jp = bα j 1 . . . α j h-1 α i+1 α i+2 α j h+1 . . .

α jp

This process may be iterated on the sequence dα j 1 . . . α j h-1 α i+1 until α i+1 reaches the dart b. We obtain thus finally:

dα i+1 = bα i+1 α j 1 . . . α jp
We have thus in both cases dα i+1 ∈< αi , αi+1 > (bα i+1 ). Since < αi , αi+1 > (bα i+1 ) =< αi , αi+1 >(b) and d ∈< αi , αi+1 >(b) by hypothesis we obtain:

dα i+1 ∈< αi , αi+1 >(d)
The same demonstration may be conducted if d ∈< αi , αi+1 >(bα i+1 ). 2

Theorem 1 For any i ∈ {0, . . . , n -2}, an i-cell C is a regular cell with local degree 2 if and only if

i) ∃d ∈ C, dα i+1 / ∈< αi , αi+1 >(d), and ii) ∀d ∈ C, dα i+1 α i+2 = dα i+2 α i+1
Proof: The reverse implication is provided by Lemma 3 (local degree 2) and 4 (regular). Let us show the implication. First, if C is of local degree 2 it is not of local degree 1 and the property i) is provided by Property 3.

Secondly, let us consider a dart d ∈ C. We have by condition b) of Definition 14 (and the fact that dα i+2 ∈ C):

dα i+1 ∈< αi , αi+1 >(d) and dα i+2 α i+1 ∈< αi , αi+1 >(d)
Therefore if dα i+1 ∈< αi , αi+1 >(dα i+2 α i+1 ), the three orbits < αi , αi+1 >(d), < αi , αi+1 >(dα i+1 ) and < αi , αi+1 >(dα i+2 α i+1 ) are distinct. However, in this case C would be of local degree at least 3, which contradicts the hypothesis about the local degree 2 of C. We have thus:

dα i+1 ∈< αi , αi+1 >(dα i+2 α i+1 ) which implies that dα i+1 α i+2 ∈< αi , αi+1 >(dα i+2 α i+1 )
Using property a) given by Definition 14, this last point implies that dα i+1 α i+2 = dα i+2 α i+1 which corresponds to ii). 2 Definition 15 (Local degree in maps) Let C be an i-cell in an n-map.

• The local degree of C is the number

{ < γi , γi+1 >(b) b ∈ C } if i ∈ {0, . . . , n -2} {< γ 0 γ 1 , . . . , γ 0 γ n-2 >(b) b ∈ C } if i = n -1 • The dual local degree of C is the number { < γi , γi-1 >(b) b ∈ C } for i ∈ {1, . . . , n -1} {< γ 0 γ 1 , . . . , γ 0 γ n-2 >(b) b ∈ C } for i = n
The local degree (resp. dual local degree) of an n-cell (resp. a 0-cell) is 0.

Let us justify the orbits considered in the definition of the local degree when i ∈ {0, . . . , n -2}. As for G-maps, we consider the darts that may be reached from d while allowing no change of i-cell (hence γi ) and no change of (i+1)-cell (hence γi+1 ). In the case when i = n -1, preventing any change of (n -1)-cell means that the allowed involutions are in {γ 0 , . . . , γ n-2 }, and preventing any change of n-cell means, according to Definition 10, that the set of allowed involutions is {γ 0 γ 1 , . . . , γ 0 γ n-1 }. Overall, only the involution γ 0 γ n-1 of the latter set is not allowed by the first one, therefore we obtain the orbit that must be considered, i.e. < γ 0 γ 1 , . . . , γ 0 γ n-2 >. Proposition 6 Let G = (D, γ 0 , . . . , γ n-1 ) be an n-map and let us consider

d ∈ D. The i-cell C i (d) is of local degree at most 2 if: • For i ∈ {0, . . . , n -3}, bγ -1 i+1 γ i+2 = bγ -1 i+2 γ i+1 for all b ∈ C i (d). • For i = n -2, bγ -1 n-1 = bγ n-1 for all b ∈ C i (d).
Such a characterization may be equivalently performed in terms of the dual map G = (D, β n , . . . , β 1 ):

∀i ∈ {0, . . . , n -2} ∀b ∈ C i (d), bβ -1 i+1 β i+2 = bβ -1 i+2 β i+1
Proof: Let us first show the equivalence between both characterizations:

• If i ∈ {0, . . . , n -3} dγ -1 i+1 γ i+2 = dβ -1 i+1 β -1 n β n β i+2 = dβ -1 i+1 β i+2 dγ -1 i+2 γ i+1 = dβ -1 i+2 β -1 n β n β i+1 = dβ -1 i+2 β i+1 So that dγ -1 i+1 γ i+2 = dγ -1 i+2 γ i+1 if and only if dβ -1 i+1 β i+2 = dβ -1 i+2 β i+1 . • If i = n -2: dγ n-1 = dβ n β n-1 and dγ -1 n-1 = dβ -1 n-1 β -1 n
Since β n is an involution we obtain:

dγ n-1 = dβ -1 n β n-1 and dγ -1 n-1 = dβ -1 n-1 β n So that dγ -1 n-1 = dγ n-1 if and only if dβ -1 n-1 β n = dβ -1 n β n-1 .
Let us now show that the above equations characterize i-cells with local degree 2.

• If i ∈ {0, . . . , n -3} let us consider a dart d such that:

dγ -1 i+1 γ i+2 = dγ -1 i+2 γ i+1
Since i ≤ n -3, γ i+1 is an involution and we have:

dγ -1 i+1 γ i+2 = dγ i+1 γ i+2 = dγ -1 i+2 γ i+1
Since the above equation is valid for any dart d ∈ C i (d), we may apply it to (dγ i+2 ) and we obtain:

(dγ i+2 )γ -1 i+2 γ i+1 = dγ i+2 γ i+1 γ i+2 = dγ i+1
We have thus:

dγ i+2 γ i+1 = dγ i+2 γ i+1 γ i+2 γ -1 i+2 = dγ i+1 γ -1 i+2
Let us now consider one dart b ∈ C i (d) =< γ 0 , . . . , γi , . . . , γ n-1 >(d). The dart b is equal to dϕ with ϕ ∈< γ 0 , . . . , γi , . . . , γ n-1 >. Let us consider ϕ as a word built on the alphabet {γ 0 , . . . , γi , . . . , γ n-1 } ∪ {γ -1 0 , . . . , γ -1 i , . . . , γ -1 n-1 }. Within the general case, the symbol γ i+1 commutes with all the symbols of this alphabet except γ i+2 and γ -1 i+2 . But as we have shown, the relationship

dγ -1 i+1 γ i+2 = dγ -1 i+2 γ i+1 induces for all d ∈ C:      dγ i+2 γ i+1 = dγ i+1 γ -1 i+2 dγ -1 i+2 γ i+1 = dγ i+1 γ i+2
We may thus consider the natural p and the function

ψ ∈< γ 0 , . . . , γi , γ i+1 , . . . , γ n-1 >(d) such that b = dγ p i+1 ψ. Since i ≤ n -3, γ i+1 is an involution and: -If p is even dγ p i+1 = d and: b = dψ ∈< γ 0 , . . . , γ i+1 , . . . , γ n-1 >(d) = C i+1 (d) -If p is odd dγ p i+1 = dγ i+1 and: b = dγ i+1 ψ ∈< γ 0 , . . . , γ i+1 , . . . , γ n-1 >(d) = C i+1 (dγ i+1 ) Therefore any dart of C i (d) belongs either to C i+1 (d) or to C i+1 (dγ i+1 ), C i (d)
is thus incident to at most two i + 1 cells and its degree is at most 2.

• If i = n -2, C n-2 (d) =< γ 0 , . . . , γ n-3 , γ n-1 > (d). The permutation γ n-1
commutes with all γ i , i ≤ n -3 and we have thus as previously, for each

b ∈ C 0 (d) a function ϕ ∈< γ 0 , . . . , γ n-3 > such that b = dγ p n-1 ϕ. We have thus b ∈ C n-1 (d) if p is even and b ∈ C n-1 (dγ n-1 ) if p is odd. The n -2 cell C n-2 (d) is thus incident to at most two n -1 cells: Its degree is at most 2.
dγ i+1 γ i+2 = dγ i+2 γ i+1 or dγ i+1 γ i+2 / ∈< γi , γi+1 >(dγ i+2 γ i+1 ) If i = n -3, for all d ∈ C we have: dγ n-2 γ n-1 = dγ -1 n-1 γ n-2 and dγ n-2 γ -1 n-1 = dγ n-1 γ n-2 , or dγ n-2 / ∈ ( < γn-3 , γn-2 >(dγ -1 n-1 γ n-2 )γ -1 n-1 ∪ < γn-3 , γn-2 >(dγ n-1 γ n-2 )γ n-1
)

If i = n -2, for all d ∈ C we have:

dγ -1 n-1 = dγ n-1 , or dγ -1 n-1 / ∈< γ 1 , . . . , γ n-3 >(dγ n-1 ) b) If i < n -2, for all b ∈ C we have: bγ i+1 / ∈< γi , γi+1 >(b) If i = n -2,
for all b ∈ C we have:

{bγ n-1 , bγ -1 n-1 }∩ < γ 0 , . . . , γ n-3 >(b) = ∅ Remark 4 If γ is a permutation of a set S, then for all s ∈ S there exists p ∈ N such that sγ = s p γ -1 . . . γ -1 = sγ -p
Conversly, for all s ∈ S there exists q ∈ N such that sγ -1 = sγ q .

= AG(M ). If C is an i-cell of M , then the set C = C ∪ Cσ is an i-cell of G if i < n, and C = C ∪ Cγ 0 σ is an n-cell of G if i = n.
Corollary 2 With the notations of Proposition 7 we have:

∀d ∈ C, < αi >(d) = C
Proof of Proposition 7:

• If i < n. We prove that for all b ∈ C ∪ Cσ, < αi >(b) = C ∪ Cσ = C ∪ Cα n . Let us show first that < αi > (b) ⊂ C ∪ Cσ. Let d ∈< αi > (b), we have d = bα k 1 α k 2 . . . α kp where p ∈ N and k h ∈ {0, . . . , n} \ {i}, 0 ≤ h ≤ p. (Note that α i = α -1 i
for all i ∈ {0, . . . , n}, hence there is no need to consider inverse involutions in the sequence α k 1 . . . α kp .)

We prove by recurence on p, the length of the sequence

α k 1 α k 2 . . . α kp , that d ∈ C ∪ Cσ.
α k p+1 =        b γ k p+1 σ if k p+1 < n -1 b γ -1 n-1 σ if k p+1 = n -1 b σ if k p+1 = n so that in all cases b α k p+1 ∈< γi >(d)σ = Cσ.
d = b α k p+1 = b σα k p+1 =    b σσ -1 γ k p+1 = b γ k p+1 if k p+1 < n b σσ -1 = b if k p+1 = n so that b α k p+1 ∈ C since b ∈ C and k p+1 = i.
From the two latter cases, we obtain that bα k 1 . . . α kp α k p+1 ∈ C ∪ Cσ; hence the property is valid for all p ∈ N * . We conclude that < αi >(b) ⊂ C ∪ Cσ.

We prove now that < αi >(b) ⊃ C ∪ Cσ. Since C =< γi >(b), we deduce from Lemma 1 that the orbit

< γ 1 , . . . , γi , . . . , γ n-1 >(b) in M is precisely < α n α 0 , . . . , αn α i , . . . , α n α n-1 >(b) in AG(M ).
Since i < n we have

< α n α 0 , . . . , αn α i , . . . , α n α n-1 >(b) ⊂< α 0 , . . . , αi , . . . , α n >(b) Eventually, C ⊂< αi > (b). Since i = n, we immediatly obtain that Cσ = Cα n ⊂< αi >(b).
We conclude that < αi >(b) = C ∪ Cσ.

• If i = n. Let b ∈ C, we prove that < αn >(b) = C ∪ Cγ 0 σ where C =< γ 0 γ 1 , . . . , γ 0 γ n-1 >(b) -(< αn > (b) ⊂ C ∪ Cγ 0 σ) Let d ∈< αn > (b). We have d = bα k 1 . . . α kp for p ∈ N, with k h ∈ {0, . . . , n -1} for 1 ≤ h ≤ p.
We prove by recurence on p, the length of the sequence α k 1 . . . α kp , that d ∈ C ∪ Cγ 0 σ. If p = 0, we have d = b ∈ C and there is nothing left to prove.

Thus, we suppose that the property holds for some p ∈ N and we consider a dart d = bα k 1 . . . α kp α k p+1 . We denote d = bα k 1 . . . α kp , so from the recurence hypothesis we have d ∈ C ∪ Cγ 0 σ.

If d ∈ C, from Definition 7 we obtain that:

• If k p+1 = 0, d α k p+1 = d α 0 α n α n = d α n α 0 α n = d (γ 0 σ) ∈ Cγ 0 σ. • If 0 < k p+1 ≤ n -1, d α k p+1 = d α k p+1 σ -1 γ 0 γ 0 σ = d α k p+1 α n γ 0 γ 0 σ = d (α n α k p+1 ) -1 γ 0 γ 0 σ = d γ -1 k p+1 γ 0 γ 0 σ (By Lemma 1) = d (γ 0 γ k p+1 ) -1 γ 0 σ Since d ∈ C we have d (γ 0 γ k p+1 ) -1 ∈ C, hence d α k p+1 ∈ Cγ 0 σ.
If d ∈ Cγ 0 σ then d = d γ 0 σ for some dart d ∈ C and we have

d α k p+1 = d γ 0 σα k p+1 = d γ 0 σσ -1 γ k p+1 (since d γ 0 σ ∈ D and k p+1 < n) = d γ 0 γ k p+1 Since d ∈ C, we obtain that d α k p+1 ∈ C =< γ 0 γ 1 , . . . , γ 0 γ n-1 >(b).
Eventually, either d ∈ Cγ 0 σ or d ∈ C, i.e. d ∈ C ∪ Cγ 0 σ, and the property holds for p + 1.

-

(C ∪ Cγ 0 σ ⊂< αn >(b)) We have C =< γ 0 γ 1 , . . . , γ 0 γ n-1 >(b). From Lemma 1 we deduce that the orbit < γ 0 γ 1 , . . . , γ 0 γ n-1 >(b) in M is precisely < α n α 0 α n α 1 , . . . , α n α 0 α n α n-1 >(b) in AG(M )
and since n ≥ 2 we have

< α n α 0 α n α 1 , . . . , α n α 0 α n α n-1 >(b) = < α 0 α n α n α 1 , . . . , α 0 α n α n α n-1 >(b) = < α 0 α 1 , . . . , α 0 α n-1 >(b)
We observe that < α 0 α 1 , . . . , α 0 α Now, we will prove that if a cell of a map M has a local degree of 2, then its associated cell in AG(M ) also has a local degree of 2. This result will be stated by Proposition 8.

Lemma 5 Let M = (D, γ 0 , . . . , γ n-1 ) be an n-map and AG(M ) = ( D = D ∪ D , α 0 , . . . , α n ) be the associated n-G-map of M . Let C be an i-cell with local degree 2 in M , for 0 ≤ i < n, and C 1 , C 2 be the two sets of darts defined (following Definition 15) by

• {C 1 , C 2 } = { < γi , γ i+1 >(b) b ∈ C } if i < n, and • {C 1 , C 2 } = { < γ 0 γ 1 , . . . , γ 0 γ n-2 >(b) b ∈ C } if i = n -1.
Then we have

(C 1 ∪ C 1 γ 0 α n ) ∩ (C 2 ∪ C 2 γ 0 α n ) = ∅ Proof: -If i < n -1, we first rewrite (C 1 ∪ C 1 α n ) ∩ (C 2 ∪ C 2 α n ) = ((C 1 ∪ C 1 α n ) ∩ C 2 ) ∪ ((C 1 ∪ C 1 α n ) ∩ C 2 α n ) = ((C 1 ∩ C 2 ) ∪ (C 1 α n ∩ C 2 )) ∪ ((C 1 ∩ C 2 α n ) ∪ (C 1 α n ∩ C 2 α n ))
From C 1 ∩ C 2 = ∅ and the fact that α n is a one-to-one map from D to D we deduce that

C 1 α n ∩ C 2 α n = ∅. Since D ∩ D = ∅ and α n is a map from D to D we also have C 1 ∩C 1 α n = ∅, C 1 ∩C 2 α n = ∅, C 2 ∩C 2 α n = ∅, and C 1 ∩C 2 α n = ∅.
Thus, all the intersections of the above union of sets are empty.

-

If i = n -1, we rewrite (C 1 ∪ C 1 γ 0 α n ) ∩ (C 2 ∪ C 2 γ 0 α n ) = ((C 1 ∪ C 1 γ 0 α n ) ∩ C 2 ) ∪ ((C 1 ∪ C 1 γ 0 α n ) ∩ C 2 γ 0 α n ) = (C 1 ∩ C 2 ) ∪ (C 1 γ 0 α n ∩ C 2 ) ∪(C 1 ∩ C 2 γ 0 α n ) ∪ (C 1 γ 0 α n ∩ C 2 γ 0 α n ) From C 1 ∩ C 2 = ∅ and the fact that γ 0 α n is a one-to-one map from D to D we deduce that C 1 γ 0 α n ∩ C 2 γ 0 α n = ∅. Since D ∩ D = ∅ and γ 0 α n is a map from D to D we also have C 1 ∩ C 1 γ 0 α n = ∅, C 1 ∩ C 2 γ 0 α n = ∅, C 2 ∩ C 2 γ 0 σ = ∅,
and If C has local degree 2 in M we have:

C 1 ∩ C 2 γ 0 α n = ∅.
{ < γ 0 γ 1 , . . . , γ 0 γ n-2 >(b) b ∈ C } = {C 1 , C 2 }
where C 1 and C 2 are non-empty and disjoint sets. Thus, there exist b 1 , b 2 ∈ C such that

• C 1 =< γ 0 γ 1 , . . . , γ 0 γ n-2 >(b 1 ), • C 2 =< γ 0 γ 1 , . . . , γ 0 γ n-2 >(b 2 ), • ∀d ∈ C, < γ 0 γ 1 , . . . , γ 0 γ n-2 >(d) ∈ {C 1 , C 2 }. Now, with C = C ∪ Cγ 0 σ, we prove that {< αn-1 , αn >(d) d ∈ C} = {C 1 ∪ C 1 γ 0 σ, C 2 ∪ C 2 γ 0 σ} Let d ∈ C. We may suppose without loss of generality that d ∈ C 1 if d ∈ C and that dσγ 0 ∈ C 1 if d ∈ Cγ 0 σ. In all cases, we prove that < αn-1 , αn >(d) = C 1 ∪ C 1 γ 0 σ.
Thus, let d ∈ C ∪ Cγ 0 σ, we consider the set < αn-1 , αn >(d). If d is a dart of the latter orbit, we have

d = dα k 1 . . . α kp , p ∈ N
where k j ∈ {0, . . . , n -2}, 1 ≤ j ≤ p.

We prove by recurence on p, the length of the sequence

α k 1 . . . α kp , that d ∈ C 1 ∪ C 1 γ 0 σ with C 1 =< γ 0 γ 1 , . . . , γ 0 γ n-2 >(d) (2)
The case p = 0 comes from the assumption we made on d or dσγ 0 . Therefore, we suppose that the property holds for some p ∈ N.

We have

d = dα k 1 . . . α kp α k p+1 with k j ∈ {0, . . . , n -2}, 1 ≤ j ≤ p + 1. Let us denote b = dα k 1 . . . α kp . From the recurence hypothesis we know that b ∈ C 1 ∪ C 1 γ 0 σ.
If b ∈ C 1 , from Definition 7 and the fact that k p+1 ≤ n -2 we have

d = bα k p+1 = dγ k p+1 σ
We may rewrite

d =    bγ 0 σ if k p+1 = 0 bγ k p+1 σ(σ -1 γ 0 γ 0 σ) = d(γ k p+1 γ 0 )γ 0 σ if 0 < k p+1 < n -1 In the second case, γ k p+1 is an involution since k p+1 < n-1 therefore d(γ k p+1 γ 0 ) = d(γ 0 γ k p+1 ) -1 . Thus, in both cases b ∈ C 1 implies that d ∈ C 1 γ 0 σ (see 2). If b ∈ C 1 γ 0 σ, then b = b γ 0 σ for some dart b ∈ C 1 . Then again from Defini- tion 7 we have d = bσ -1 γ k p+1 = b γ 0 σσ -1 γ k p+1 = b γ 0 γ k p+1 . If k p+1 = 0 we obtain that d = b γ 0 γ 0 = b ∈ C 1 , otherwise d = b γ 0 γ k p+1 ∈ C 1 by (2).
We conclude that bα k p+1 ∈ C 1 ∪ C 1 γ 0 σ, so that the property holds for p + 1, hence for all p ∈ N.

Eventually, < αn-1 , αn >(d) ⊂ C 1 ∪ C 1 γ 0 σ. Now, from the definition of C 1 (2) it is straightforward that C 1 ⊂< α 0 , . . . , α n-2 > (d). On the other hand, we have C 1 γ 0 σ = C 1 α n α 0 α n . Since n ≥ 2 we obtain C 1 γ 0 σ = C 1 α 0 . Therefore, C 1 ⊂< α 0 , . . . , α n-2 > (d) implies that C 1 γ 0 σ ⊂< α 0 , . . . , α n-2 >(d). Thus we have C 1 ∪ C 1 γ 0 σ ⊂< α 0 , . . . , α n-2 >(d).
Finally, for all dart d ∈ C, we have proved that < α 0 , . . . , Since i < n -1 and C has local degree 2 in M we have:

α n-2 > (d) = C 1 ∪ C 1 γ 0 σ or < α 0 , . . . , α n-2 >(d) = C 2 ∪ C 2 γ 0 σ. Since C 1 ∪ C 1 γ 0 σ and C 2 ∪ C 2 γ 0 σ are distinct
{ < γi , γ i+1 >(b) b ∈ C } = {C 1 , C 2 }
where C 1 and C 2 are non-empty disjoint sets. Thus, there exists b

1 , b 2 ∈ C such that -C 1 =< γi , γ i+1 >(b 1 ), -C 2 =< γi , γ i+1 >(b 2 ), -∀d ∈ D, < γi , γ i+1 >(d) ∈ {C 1 , C 2 }. With C = C ∪ Cσ, we prove that {< αi , α i+1 >(d) d ∈ C} = {C 1 ∪ C 1 σ, C 2 ∪ C 2 σ}
Let d ∈ C. We may suppose without loss of generality that

d ∈ C 1 if d ∈ C and that dσ -1 ∈ C 1 if d ∈ Cσ. In all cases, we prove that < αi , α i+1 >(d) = C 1 ∪C 1 σ.
Thus, let d ∈ C, we consider the set < αi , αi+1 > (d). Let d be a dart of the latter orbit. We have:

d = dα k 1 α k 2 . . . α kq , q ∈ N
where k j ∈ {0, . . . , n} \ {i, i + 1} for j ∈ {1, . . . , q}.

We prove by recurence on p, the length of the sequence

α k 1 α k 2 . . . α kp , that d ∈ C 1 ∪ C 1 σ with C 1 =< γi , γi+1 > (b 1 ). If p = 0, since we supposed that d ∈ C 1 or dσ -1 ∈ C 1 (i.e. d ∈ C 1 σ
) the property holds and there is nothing left to prove. Now, we suppose that the property is verified for some p ∈ N.

Let d = dα k 1 α k 2 . . . α kp α k p+1 with d = dα k 1 α k 2 . . . α kp . From the recurence hypothesis we have d ∈ C 1 ∪C 1 σ. If d ∈ C 1 , by Definition 7 we obtain that d = d γ k p+1 σ (if k p+1 < n -1), d = d γ -1 n-1 σ (if k p+1 = n -1), or d = d σ (if k p+1 = n) ; therefore in all cases d ∈ C 1 σ. If d ∈ C 1 σ, we have d = d σ -1 γ k p+1 (if k p+1 < n) or d = d σ -1 (if k p+1 = n); so that in both cases d ∈ C 1 . We conclude that d = dα k 1 ∈ C 1 ∪ C 1 σ
and the property holds for p + 1, hence for any p ∈ N.

Eventually, we obtained that

< αi , α i+1 >(d) ⊂ C 1 ∪ C 1 σ Now, we show that C 1 ∪ C 1 σ ⊂< αi , α i+1 > (d). We have C 1 =< γi , γ i+1 > (b 1 ) =< γi , γ i+1 >(d)
and by Lemma 1:

< γi , γ i+1 >(d) =< α n α 0 , . . . , αn α i , αn α i+1 , . . . , α n α n-1 >(d) Since i < n -1, we have α n ∈ {α 0 , . . . , α n } \ {α i , α i+1 }, therefore < α n α 0 , . . . , αn α i , αn α i+1 , . . . , α n α n-1 >(d) ⊂< αi , α i+1 >(d) Finally, C 1 ⊂< αi , α i+1 > (d). Since i + 1 < n, this also implies that C 1 α n = C 1 σ ⊂< αi , α i+1 >(d).
We conclude that < αi ,

α i+1 >(d) = C 1 ∪ C 1 σ.
The overall result is that for all d ∈ C, either

i) < αi , α i+1 >(d) = C 1 ∪ C 1 σ, or ii) < αi , α i+1 >(d) = C 2 ∪ C 2 σ.
where C 1 ∪ C 1 σ and C 2 ∪ C 2 σ are disjoint sets (by Lemma 5). In other words:

{ < αi , α i+1 >(d) d ∈ C} =
d = bα h 1 . . . α hq , q ∈ N
where h j ∈ {k 1 , . . . , k p } for all j ∈ {1, . . . , q}.

We prove by recurence on q, the length of the sequence of involutions α h 1 . . . α hq , that either d ∈< Ψ>(b) or d ∈< Ψ>(b)α n . The property is immediately verified for q = 0. Thus we assume that the property is valid for some integer p and we consider the dart d with

d = bα h 1 . . . α hq α h q+1 , q ∈ N and h j ∈ {k 1 , . . . , k p } for 1 ≤ j ≤ q + 1
By the recurence hypothesis, we have Later on, we use the fact that a regular cell in M is associated with a regular cell in AG(M ). This will be stated by Theorem 4, whose proof is based on the next Lemmas.

d = b α h q+1 where b ∈< Ψ>(b)∪ < Ψ> (b)α n . If b ∈< Ψ>(b) we write d = b α h q+1 α n α n = b (α n α h q+1 ) -1 α n = b (γ h q+1 ) -1 α n , if h q+1 = n,
Lemma 9 If C is an i-cell, 0 ≤ i ≤ n -2,
dγ i+1 γ i+2 = dγ i+2 γ i+1 or dγ i+1 γ i+2 / ∈< γi , γi+1 >(dγ i+2 γ i+1 ). By Lemma 1 we may write dα n α i+1 α n α i+2 = dα n α i+2 α n α i+1 or dα n α i+1 α n α i+2 / ∈< γi , γi+1 >(dα n α i+2 α n α i+1 ). Since i + 1 ≤ n -3 and AG(M ) is an n-G-map, we have bα n α i+1 = bα i+1 α n and bα n α i+2 = bα i+2 α n for all b ∈ D. Hence, either dα i+1 α i+2 = dα i+2 α i+1 or dα i+1 α i+2 / ∈< γi , γi+1 >(dα i+2 α i+1 ). Now, if dα i+1 α i+2 = dα i+2 α i+1 we have dα i+1 α i+2 / ∈< γi , γi+1 >(dα i+2 α i+1
). In this case, let us suppose that dα i+1 α i+2 ∈< αi , αi+1 >(dα i+2 α i+1 ). By Lemma 8, we know that

< αi , αi+1 >(dα i+2 α i+1 ) ⊂< γi , γi+1 >(dα i+2 α i+1 )∪ < γi , γi+1 >(dα i+2 α i+1 )α n Thus, either dα i+1 α i+2 ∈< γi , γi+1 > (dα i+2 α i+1 ) or dα i+1 α i+2 ∈< γi , γi+1 > (dα i+2 α i+1 )α n . Since dα i+1 α i+2 = dγ i+1 γ i+2 ∈ D and < γi , γi+1 >(dα i+2 α i+1 )α n ⊂ D we necessarily have dα i+1 α i+2 ∈< γi , γi+1 > (dα i+2 α i+1 ), a contradiction. Therefore, dα i+1 α i+2 / ∈< αi , αi+1 >(dα i+2 α i+1 ).
Eventually, we have proved that either

dα i+1 α i+2 = dα i+2 α i+1 or dα i+1 α i+2 / ∈< αi , αi+1 >(dα i+2 α i+1 ) which is property a) of Definition 14. b) If d ∈ D , then d = d α n for some dart d ∈ C (Definition 17). From Defi- nition 16 we know that either dα n γ i+1 γ i+2 = dα n γ i+2 γ i+1 or dα n γ i+1 γ i+2 / ∈< γi , γi+1 >(dα n γ i+2 γ i+1 ).
If dα n γ i+1 γ i+2 = dα n γ i+2 γ i+1 , we have:

dα n α n α i+1 α n α i+2 = dα n α n α i+2 α n α i+1 (Lemma 1)
dα i+1 α n α i+2 = dα i+2 α n α i+1 dα i+1 α i+2 α n = dα i+2 α i+1 α n (i < n -3)
dα i+1 α i+2 = dα i+2 α i+1 If dα n γ i+1 γ i+2 = dα n γ i+2 γ i+1 , then dα n γ i+1 γ i+2 / ∈< γi , γi+1 > (dα n γ i+2 γ i+1 ). Since dα n ∈ D, we have proved that dα n α i+1 α i+2 / ∈< αi , αi+1 >(dα n α i+2 α i+1 ). Since i < n -3, dα n α i+2 α i+1 = dα i+2 α i+1 α n and dα n α i+1 α i+2 = dα i+1 α i+2 α n . Futhermore, since n / ∈ {i, i + 1}, < αi , αi+1 > (dα i+2 α i+1 α n ) =< αi , αi+1 > (dα i+2 α i+1 ). It follows that dα i+1 α i+2 α n / ∈< αi , αi+1 > (dα i+2 α i+1 ), which in turn implies that dα i+1 α i+2 / ∈< αi , αi+1 > (dα i+2 α i+1 ). Eventually, either dα i+1 α i+2 = dα i+2 α i+1 or dα i+1 α i+2 / ∈< αi , αi+1 >(dα i+2 α i+1
), which is property a) of Definition 14.

• If i = n -3. a) If d ∈ D. Following Definition 16, either dγ n-2 γ n-1 = dγ -1 n-1 γ n-2 , or dγ n-2 / ∈ ( < γn-3 , γn-2 >(dγ -1 n-1 γ n-2 )γ -1 n-1 ∪ < γn-3 , γn-2 >(dγ n-1 γ n-2 )γ n-1
)

.

If dγ n-2 γ n-1 = dγ -1 n-1 γ n-2 , by Lemma 1 we deduce that dα n α n-2 α n α n-1 = dα n-1 α n α n α n-2 . Since dα n α n-2 = dα n-2 α n , we obtain that dα n-2 α n-1 = dα n-1 α n-2 . Now, if dγ n-2 γ n-1 = dγ -1
n-1 γ n-1 we necessarily have by Definition 16:

dγ n-2 / ∈ ( < γn-3 , γn-2 >(dγ -1 n-1 γ n-2 )γ -1 n-1 ∪ < γn-3 , γn-2 >(dγ n-1 γ n-2 )γ n-1 ) (3)
Suppose that dα n-2 α n-1 ∈< αn-3 , αn-2 >(dα n-1 α n-2 ), which we may rewrite

dα n-2 α n α n α n-1 ∈< αn-3 , αn-2 > (dα n-1 α n α n α n-2 ), or dα n α n-2 α n α n-1 ∈< αn-3 , αn-2 > (dα n-1 α n α n α n-2 ). Since d ∈ D we obtain that dγ n-2 γ n-1 ∈< αn-3 , αn-2 >(dγ -1 n-1 γ n-2 ).
By Lemma 8, we deduce that

dγ n-2 γ n-1 ∈< γn-3 , γn-2 > (dγ -1 n-1 γ n-2 )∪ < γn-3 , γn-2 > (dγ -1 n-1 γ n-2 )α n . Finally, the fact that dγ n-2 γ n-1 ∈ D and < γn-3 , γn-2 > (dγ -1 n-1 γ n-2 )α n ⊂ D implies that dγ n-2 γ n-1 ∈< γn-3 , γn-2 > (dγ -1 n-1 γ n-2 ), i.e. dγ n-2 ∈< γn-3 , γn-2 >(dγ -1 n-1 γ n-2 )γ -1 n-1 ; which is a contradic- tion with (3). Therefore, dα n-2 α n-1 / ∈< αn-3 , αn-2 >(dα n-1 α n-2 ). b) If d ∈ D , we have d = bα n for some b ∈ C. If C is regular, since dα n = b ∈ C, following Definition 16 either dα n γ n-2 γ -1 n-1 = dα n γ n-1 γ n-2 , or dα n γ n-2 / ∈ ( < γn-3 , γn-2 >(dγ -1 n-1 γ n-2 )γ -1 n-1 ∪ < γn-3 , γn-2 >(dα n γ n-1 γ n-2 )γ n-1
)

.

If

dα n γ n-2 γ -1 n-1 = dα n γ n-1 γ n-2 , by Lemma 1 we deduce that dα n α n α n-2 α n-1 α n = dα n α n α n-1 α n α n-2 . Since dα n α n-2 = dα n-2 α n , we obtain that dα n-2 α n-1 α n = dα n-1 α n-2 α n , hence dα n-2 α n-1 = dα n-1 α n-2 . Now, if dα n γ n-2 γ -1 n-1 = dα n γ n-1 γ n-2
. it follows (Definition 16) that

dα n γ n-2 / ∈< γn-3 , γn-2 >(dα n γ n-1 γ n-2 )γ n-1 (4) Let us suppose that dα n-2 α n-1 ∈< αn-3 , αn-2 >(dα n-1 α n-2 ). Since n / ∈ {n - 2, n -3} we have < αn-3 , αn-2 >(dα n-1 α n-2 ) =< αn-3 , αn-2 >(dα n-1 α n-2 α n ).

It follows that

dα n α n α n-2 α n-1 α n ∈ < αn-3 , αn-2 >(dα n α n α n-1 α n-2 α n )
Since dα n ∈ D, by Lemma 1 and from the fact that bα n α n-2 = bα n-2 α n for all b ∈ D, we obtain

dα n γ n-2 γ -1 n-1 ∈ < αn-3 , αn-2 >(dα n γ n-1 γ n-2 )
By Lemma 8 and the fact that dα n γ n-2 γ -1 n-1 ∈ D we deduce that

dα n γ n-2 γ -1 n-1 ∈< γn-3 , γn-2 >(dα n γ n-1 γ n-2 )
in other words,

dα n γ n-2 ∈< γn-3 , γn-2 >(dα n γ n-1 γ n-2 )γ n-1
which is a contradiction with (4). Therefore,

dα n-2 α n-1 / ∈< αn-3 , αn-2 > (dα n-1 α n-2 ).
Enventually, we have proved that condition a) of Definition 14 is satisfied for all d ∈ C.

• If i = n -2. a) If d ∈ D. Following Definition 16, we know that either dγ -1 n-1 = dγ n-1 or dγ -1 n-1 / ∈< γ 1 , . . . , γ n-3 >(dγ n-1 ). If dγ -1 n-1 = dγ n-1 , by Lemma 1 we have dα n-1 α n = dα n α n-1 .
Now, let us consider the case when dγ -1 n-1 = dγ n-1 . Necessarily, we have

dγ -1 n-1 / ∈< γ 1 , . . . , γ n-3 >(dγ n-1 ). Suppose that dα n-1 α n ∈< αn-2 , αn-1 > (dα n α n-1 ). Since d ∈ D, we can write dγ -1 n-1 ∈< αn-2 , αn-1 > (dγ n-1
), and using Lemma 8 we obtain that

dγ -1 n-1 ∈< γn-2 , γn-1 >(dγ n-1 )∪ < γn-2 , γn-1 >(dγ n-1 )α n . Since dγ -1 n-1 ∈ D and < γn-2 , γn-1 >(dγ n-1 )α n ⊂ D it follows that dγ -1 n-1 ∈< γn-2 , γn-1 >(dγ n-1
), a contradiction. Finally, we obtain that dα n-1 α n / ∈< αn-2 , αn-1 >(dα n α n-1 ).

We conclude that either dα n-1 α n = dα n α n-1 or dα n-1 α n / ∈< αn-2 , αn-1 > (dα n α n-1 ), which is property a) of Definition 14. Following Definition 16, we again know that either d γ

-1 n-1 = d γ n-1 or d γ -1 n-1 / ∈< γ 1 , . . . , γ n-3 >(d γ n-1 ), i.e. d γ n-1 / ∈< γ 1 , . . . , γ n-3 >(d γ -1 n-1 ). If d γ -1 n-1 = d γ n-1 we obtain that dα n α n-1 α n = dα n α n α n-1 , thus dα n α n-1 α n = dα n-1 or again dα n α n-1 = dα n-1 α n . If d γ -1 n-1 = d γ n-1 we have necessarily d γ n-1 / ∈< γ 1 , . . . , γ n-3 > (d γ -1 n-1 ). In- deed, let us suppose that dα n-1 α n ∈< αn-2 , αn-1 > (dα n α n-1 ). Since n / ∈ {n -2, n -1} we deduce that dα n-1 ∈< αn-2 , αn-1 > (dα n α n-1 ) and then also that dα n-1 ∈< αn-2 , αn-1 > (dα n α n-1 α n ). Substituting with d = d α n we obtain d α n α n-1 ∈< αn-2 , αn-1 > (d α n α n α n-1 α n ), and finally d γ n-1 ∈< αn-2 , αn-1 >(d γ -1 n-1 ).
However, by Corollary 3, we have

< αn-2 , αn-1 >(d γ -1 n-1 ) ⊂< γ 1 , . . . , γ n-3 >(d γ -1 n-1 )∪ < γ 1 , . . . , γ n-3 >(d γ -1 n-1 )α n As d ∈ D, < γ 1 , . . . , γ n-3 > (d γ -1 n-1 ) ⊂ D and therefore < γ 1 , . . . , γ n-3 > (d γ -1 n-1 )α n ⊂ D . Since d γ n-1 ∈ D and d γ n-1 ∈< αn-2 , αn-1 > (d γ -1 n-1
), we deduce from the above inclusion that d γ n-1 ∈< γ 1 , . . . , γ n-3 > (d γ -1 n-1 ), a contradiction. Finally, dα n-1 α n / ∈< αn-2 , αn-1 >(dα n α n-1 ).

We obtain that property a) of Definition 14 is satisfied by C.

• If i < n -2. a) If d ∈ D. Suppose that dα i+1 ∈< αi , αi+1 >(d). By Lemma 8, < αi , αi+1 > (d) ⊂< γi , γi+1 > (d)∪ < γi , γi+1 > (d)α n so that either dα i+1 ∈< γi , γi+1 > (d) or dα i+1 ∈< γi , γi+1 > (d)α n . Necessarily, we have dα i+1 ∈< γi , γi+1 > (d)α n since dα i+1 ∈ D . We deduce that dα i+1 α n ∈< γi , γi+1 > (d), i.e. dα n α i+1 ∈< γi , γi+1 >(d), since i + 1 < n -1. Thus, we have dγ i+1 ∈< γi , γi+1 >(d).
< αi , αi+1 >(b) ⊂< γi , γi+1 >(b)∪ < γi , γi+1 >(b)α n so either bα n α i+1 ∈< γi , γi+1 >(b) or bα n α i+1 ∈< γi , γi+1 >(b)α n . Since bα n α i+1 ∈ D, necessarily bα n α i+1 ∈< γi , γi+1 > (b). In other words, bγ i+1 ∈< γi , γi+1 > (d)
, which is a contradiction with the fact that b belongs to a regular i-cell of M (property b) of Definition 16). Therefore, dα i+1 / ∈< αi , αi+1 >(d) so that property b) of Definition 14 is verified. Property 4 An (n -1)-cell in an n-map is of degree either 1 or 2. If the n-map is closed, then all (n -1)-cells are of degree 2.

• If i = n -2. a) If d ∈ D, following Definition 14 we have bγ n-1 / ∈< γ 0 , . . . , γ n-3 >(b). Now, let us suppose that dα n-1 ∈< αn-2 , αn-1 >(d). Since n / ∈ {n-2, n-1} we deduce that dα n-1 α n ∈< αn-2 , αn-1 > (d) and by Corollary 3 that dγ -1 n-1 ∈< γn-2 , γn-1 >(d), which is a contradiction. Thus, dα n-1 / ∈< αn-2 , αn-1 >(d). b) If d ∈ D , we have d = d α n for some dart d ∈ D. Let us suppose that dα n-1 ∈< αn-2 , αn-1 > (d). We obtain that d α n α n-1 ∈< αn-2 , αn-1 > (d α n ). Again, since n / ∈ {n -2, n -1} we have d α n α n-1 ∈< αn-2 , αn-1 >(d ),

Cells removal and contraction in G-maps and maps

Cells removal

Notation 3 If S = {E i } 0≤i≤N is a set of sets for N ∈ N, we denote by S * the union of sets in S, i.e.

S * = ∪ 0≤i≤N E i Definition 18 (Removal set) Let G = (D, α 0 , . . . , α n ) be an n-G-map (resp. M = (D, γ 0 , . . . , γ n-1 ) be an n-map) and S r = {R i } 0≤i≤n be sets of i-cells with R n = ∅. The family of sets S r is called a removal set in G (resp. in M ).
Furthermore, for such a familly we will denote R = ∪ n i=0 R i , the set of all cells of S r , so that R * is the set of all darts in S r .

Definition 19 (Removal kernel) Let G be an n-G-map. A removal kernel

K r = {R i } 0≤i≤n in G is a removal set such that all cells of R are disjoint (i.e. ∀C, C ∈ R, C ∩ C = ∅)
and all of them are regular cells with local degree 2 (Definitions 14 and 12). A removal kernel is defined the same way for an n-map M using Definitions 16 and 15 for the notions of regularity and local degree, respectively.

Lemma 11 Let G = (D, α 0 , . . . , α n ) be an n-G-map and K r = {R i } 0≤i≤n be a removal kernel in G. We have R * i α i ∩ R * ⊂ R * i for all i, 0 ≤ i ≤ n.
Proof of Lemma 11:

Let d = dα i for d ∈ R * i (i.e., d ∈ R * i α i ) and such that d ∈ R * . We prove that d ∈ R * i .
Since d ∈ R * , it is sufficient to prove that d / ∈ R * j for all j = i. Let us suppose that d ∈ R * j with i = j, which means that d belongs to a j-cell C j ∈ R j :

d ∈< α 0 , . . . , αj , . . . , α n >(d ), d ∈ R * j
Since i = j, d α i also belongs to the above j-cell. However,

d α i = dα i α i = d ∈ R * i .
We have exhibited a dart which belongs to both a removed j-cell and a removed i-cell. This is a contradiction with the fact that cells of R do not intersect (Definition 19). 2 Corollary 5 Let G = (D, α 0 , . . . , α n ) be an n-G-map and K r = {R i } 0≤i≤n be a removal kernel in G. With D = D \ R * we have for all all i ∈ {0, . . . , n}:

R * i α i \ R * i ⊂ D and R * i α i ∩ D = R * i α i \ R * i ( 5
)
Proof: From Lemma 11, we know that

R * i α i ∩ R * ⊂ R * i . We deduce that R * i α i \ R * i ⊂ R * i α i \ R * . On the other hand, R * i ⊂ R * implies that R * i α i \ R * ⊂ R * i α i \ R * i . It follows that R * i α i \ R * = R * i α i \ R * i . Furthermore, since R * i α i \ R * is a subset of D = D \ R * we also have R * i α i \ R * i ⊂ D .
On the other hand, let us write:

R * i α i ∩ D = R * i α i ∩ (D \ R * ) = (R * i α i ∩ D) \ R * = R * i α i \ R * As shown above, we have R * i α i \ R * = R * i α i \ R * i . Finally, we obtain that R * i α i ∩ D = R * i α i \ R * i . 2
The following definition for cells removal is adapted from [START_REF] Grasset-Simon | Définition et étude des pyramides généralisées nD : application pour la segmentation multi-echelle d'images 3d[END_REF] where a definition combining removals and contractions is given. The definition below is obtained by considering that no cell is to be contracted.

In her definition, Grasset required that cells of the removal kernel should have a local degree two according to her definition (Definition 13). We have seen that this definition is both too restrictive to be a valid definition for the local degree 2, but also that it does not exclude cells with local degree 1.

We know that excluding cells with local degree 1 from Grasset's definition yields the notion of regular cells with local degree 2 (Definition 14). Both notions being equivalent, as shown by Theorem 1. Therefore, the definition we present below as a note, although not exactly the one given by Grasset, is just more restrictive in the sense that no cell with a local degree one should be in the removal kernel.

Note 1

The operation of cells removal in n-G-maps is defined as follows in [START_REF] Grasset-Simon | Définition et étude des pyramides généralisées nD : application pour la segmentation multi-echelle d'images 3d[END_REF]: Let G = (D, α 0 , . . . , α n ) be an n-G-map and

K r = {R i } 0≤i≤n-1 a removal kernel in G. Let BV i = R * i α i \ R * i , ∀i, 0 ≤ i ≤ n.
The set BV i is called the set of surviving darts which are neighbors of an i-cell to be removed. The n-G-map resulting of the removal of the cells of R is G = (D , α 0 , . . . , α n ) defined by:

(1) D = D \ R * ; (2) ∀i, 0 ≤ i ≤ n, ∀b ∈ D \ BV i , bα i = bα i ; (3) ∀i, 0 ≤ i < n, ∀b ∈ BV i , bα i = b = b(α i α i+1 ) k α i where k is the smallest integer such that b ∈ BV i .
In this report, we use the following definition for the removal of cells, definition which is proved to be equivalent to the one used in [START_REF] Grasset-Simon | Définition et étude des pyramides généralisées nD : application pour la segmentation multi-echelle d'images 3d[END_REF].

Definition 20 (Cells removal in n-G-maps) Let G = (D, α 0 , . . . , α n ) be an n-G-map and K r = {R i } 0≤i≤n-1 be a removal kernel in G. The n-G-map resulting of the removal of the cells of R is G = (D , α 0 , . . . , α n ) where: (1) D = D \ R * ; (2) ∀d ∈ D , dα n = dα n ; (3) ∀i, 0 ≤ i < n, ∀d ∈ D , dα i = d = d(α i α i+1 ) k α i
where k is the smallest integer such that d ∈ D .

Notation 4

The n-G-map obtained after removal of a kernel K r = {R i } 0≤i≤n from an n-G-map G will be denoted either by G \ K r , or by G \ R * .

As stated by the next proposition, the involution α n remains unchanged after the removal operation.

Proposition 9

Let G, G be n-G-maps and K r = {R i } 0≤i≤n be a removal kernel as in Definition 20. Since R n = ∅, then dα n ∈ D for all d ∈ D .

Proof: It is readily seen that dα n ∈ D for all d ∈ D . Indeed, suppose that dα n ∈ C i ∈ R i for some i ∈ {0, . . . , n -1}. In other words, dα n belongs to an i-cell which is to be removed for i < n:

C i =< α 0 , . . . , αi , . . . , α n >(dα n ) ∈ R i , 0 ≤ i < n
Since i < n, we deduce that dα n α n = d also belongs to the above orbit, thus d belongs to the same i-cell of R i . This is a contradiction with the fact that d ∈ D . 2

Remark 5 Let G, G be n-G-maps and K r = {R i } 0≤i≤n be a removal kernel as in Definition 20. If a dart d belongs to an i-cell C of R i , then dα n ∈ C. Indeed, since there are no n-cell in K r , i < n so that dα n ∈< αi >(d) = C.

The equivalence between Definition 10 of [START_REF] Grasset-Simon | Définition et étude des pyramides généralisées nD : application pour la segmentation multi-echelle d'images 3d[END_REF] (see Note 1) and Definition 20 is stated by Proposition 10. The next two lemmas will be used in the proof of the proposition.

Lemma 12 Let G = (D, α 0 , . . . , α n ) be an n-G-map and

K r = {R i } 0≤i≤n-1 be a removal kernel in G. Let i ∈ {0, . . . , n -1} and d ∈ R * i α i \ R * i . If k is the smallest integer such that d = d(α i α i+1 ) k α i ∈ D \ R * , then k > 0 and for all 0 ≤ h < k we have d(α i α i+1 ) h α i ∈ R * i . Proof: Let D = D \ R * . We first show that k > 0. Indeed, d ∈ R * i α i \ R * i means that d = bα i for some dart b ∈ R * i so that dα i = bα i α i = b ∈ R * i . Therefore, dα i /
∈ D so k cannot be equal to 0.

Then, we prove by recurrence on h, 0 ≤ h < k that d(α i α i+1 ) h α i ∈ R i , assuming that it does not belong to D since h < k. The property has already been shown to be true for h = 0.

Let us suppose that

d = d(α i α i+1 ) h α i belongs to R * i . Therefore, d belongs to a removed i-cell, say C i =< α 0 , . . . , αi , . . . , α n > (d ). Because i + 1 = i we deduce that d α i+1 = d(α i α i+1 ) h α i α i+1 = d(α i α i+1 ) h+1 ∈ C i ∈ R i . Now, consider d = d(α i α i+1 ) h+1 α i

and suppose it does not belong to D (h + 1 < k).

There are two cases: either it belongs to R * i or it belongs to R * j , j = i. In the latter case we observe that d(α i α i+1 ) h+1 α i and d(α i α i+1 ) h+1 belong to the same j-cell. Therefore, d(α i α i+1 ) h+1 α i ∈ C ∈ R j implies that d(α i α i+1 ) h+1 ∈ C which contradicts the fact that d(α i α i+1 ) h+1 ∈ C i ∈ R i since cells to be removed are disjoint (Definition 19). Hence, d(α i α i+1 ) h+1 α i ∈ R i and the property is true for h + 1. 2 Lemma 13 Let G = (D, α 0 , . . . , α n ) be an n-G-map and K r = {R i } 0≤i≤n-1 be a removal kernel in G. Let D = D\R * , i ∈ {0, . . . , n-1} and We also prove that dα i / ∈ R * j for all j, j = i. Indeed, if dα i ∈ C j =< α 0 , . . . , αj , . . . , α n >(b) for b ∈ R * j then since i = j, dα i α i = d also belongs to C j . This is a contradiction with the fact that d ∈ D . Finally, we have dα i / ∈ R *

BV i = R * i α i \R * i . If d ∈ D \ BV i then dα i ∈ D . Proof: We need to prove that dα i / ∈ R * when d / ∈ R * and d / ∈ BV i . We first show that dα i / ∈ R * i . Indeed, if we suppose that dα i ∈ R * i , then dα i α i = d ∈ R * i α i . Since d / ∈ R * , in particular d ∈ R * i α i \ R * = R * i α i \ R * i ( Corollary
In the same way, we have for all h < k, d(

γ i γ -1 i+1 ) h γ i = dα n (α i α i+1 ) h α i ∈ R * . It follows that k is also the smallest exponent such that dα n (α i α i+1 ) k α i ∈ R * .
On the other hand γ i = α n α i . According to Definition 20 we have for any dart b ∈ D , bα n = bα n and bα i = b = b(α i α i+1 ) r α i where r is the smallest integer such that b ∈ D . Eventually, we have dγ i = dγ i .

-

If i = n -1 then dγ n-1 = dγ k+1 n-1
where k is the smallest integer such that dγ k+1 n-1 ∈ D . Since γ n-1 = α n α n-1 we have

dγ n-1 = d(α n α n-1 ) k+1 = dα n (α n-1 α n ) k α n-1
In the same way, we have for all h < k+1, dγ

h n-1 = dα n (α n-1 α n ) h α n-1 ∈ R * . It follows that k is also the smallest exponent such that dα n (α n-1 α n ) h α n-1 ∈ R * .
On the other hand We show that for all i ∈ {0, . . . , n -1}, γ i = γ i |D .

γ n-1 = α n α n-1 where α n-1 is defined for all b ∈ D by bα n-1 = b = b(α n-1 α n ) r α n-
Let K r = {R j } 0≤j≤n-1 and K r|D = {R j } 0≤j≤n-1 . Furthermore, let i ∈ {0, . . . , n-1} and d ∈ D .

In the definition of dγ

i (Definition 21), d(γ i |D γ i+1 -1 |D ) k γ i |D (dγ k+1 n-1 |D when i = n -1) belongs to D \ R * iff it belongs to D \ R * . Indeed, let us denote d = d(γ i |D γ i+1 -1 |D ) k γ i |D (resp. dγ k+1 n-1 |D ). -(d ∈ D \ R * ⇒ d ∈ D \ R * ) If d ∈ D \ R * , in particular d ∈ D so we have to show that d / ∈ R * . Now, if b is a dart of a cell of R (i.e. d ∈ R * ) such that d ∈ D , the fact that D is a connected component implies that the cell that contains b is itself included in R (Remark 6
), thus it also belongs to R from the very definition of K r|D . Therefore, we have Proof: With G = AG(M ), we have the following diagram: Eventually, if we follow the path [START_REF] Damiand | Removal and contraction for n-dimensional generalized maps[END_REF][START_REF] Damiand | Removal and contraction for n-dimensional generalized maps[END_REF], hence HV ( G \ Kr ) is an n-map [START_REF] Lienhardt | N-dimensional generalized combinatorial maps and cellular quasimanifolds[END_REF], and finally HV ( G \ Kr ) |D , that is M \ K r , is an n-map following Remark 3 and Definition 8. 2

R * ∩ D ⊂ R * ∩ D . It follows that d / ∈ R * implies d / ∈ R * . -(d ∈ D \ R * ⇒ d ∈ D \ R * ) Since d ∈ D , d ∈ D \ R * iff d ∈ D \ R * and the implication is straightforward since R * ⊂ R * . It follows that dγ i = dγ i when d ∈ D , thus γ i |D = γ i . Eventually, we obtain that (M \ K r ) |D = M \ K r|D . 2 Proposition 14 If K r is a removal kernel in M and G = AG(M ) is an associated G-map of M ,
M ---→ M removal of Kr --------→ M \ K r    |D    |D    AG    HV ( G) removal of HV ( Kr) -----------→ HV ( G) \ HV ( Kr )    HV    HV    G ---→ G removal of Kr --------→ G \
M AG -→ G \Kr -→ G \ Kr HV -→ HV ( G \ Kr ) |D -→ M \ K r we deduce that M \ K r is a valid n-map since G = AG(M ) is an n-G-map (by Proposition 3), therefore G \ Kr is an n-G-map
Proposition 15 Let M = (D, β n , . . . , β 1 ) be an n-map and K r = {R i } 0≤i≤n-1 a removal set in M . The (n -1)-tuple obtained after removal of the cells of R is M = (D , β n , . . . , β 1 ) defined by:

• D = D \ R * ; • ∀i ∈ {1, . . . , n -1}, ∀d ∈ D , dβ i = dβ k 1 (β i β -1 i+1 ) k β i ,
where k is the smallest integer such that dβ k 1 β n ∈ D and k is the smallest integer such that

dβ k 1 (β i β -1 i+1 ) k β i ∈ D . • For i = n, ∀d ∈ D , dβ n = dβ k 1 β n where k is the smallest integer such that dβ n = dβ k 1 β n ∈ D .
Proof:

• For i ∈ {1, . . . , n -2} and for all d ∈ D we have dβ i = dγ 0 γ i by Proposition 2. Following Definition 21 we obtain that

dβ i = d(γ 0 γ 1 ) k γ 0 (γ i γ i+1 ) h γ i
where k is the smallest integer such that d(γ 0 γ 1 ) k γ 0 ∈ D (i.e. such that

dβ k 1 β n ∈ D since γ 0 γ 1 = β 1 and γ 0 = β n ), and h is the smallest integer such that d(γ 0 γ 1 ) k γ 0 (γ i γ i+1 ) h γ i ∈ D .
We may thus rewrite,

dβ i = d(γ 0 γ 1 ) k γ 0 (γ i γ i+1 γ 0 γ 0 ) h γ i = d(γ 0 γ 1 ) k (γ 0 γ i γ i+1 γ 0 ) h γ 0 γ i = dβ k 1 (β i β -1 i+1 ) h β i (γ 0 γ 1 = β 1 and for all i ∈ {1, . . . , n -2}, γ 0 γ i = β i and γ i+1 γ 0 = β -1 i+1 )
• For i = n -1, we have

dβ n-1 = dγ 0 γ n-1 (Proposition 2) = d(γ 0 γ 1 ) k γ 0 γ h+1 n-1 (Definition 21) = dβ k 1 β n (β n β n-1 ) h+1 (Proposition 2) = dβ k 1 (β n-1 β n ) h β n-1 ((β n β n-1 ) h+1 = β n (β n-1 β n ) h β n-1 ) = dβ k 1 (β n-1 β -1 n ) h β n-1 (β n = β -1 n )
where k is the smallest integer such that d(γ We also denote:

0 γ 1 ) k γ 0 = dβ k 1 β n ∈ D and h is the smallest integer such that dβ k 1 (β n-1 β -1 n ) h β n-1 ∈ D . • For i = n, from Proposition 2 we have β n = γ 0 . By Definition 21 we know that for all d ∈ D , dβ n = d(γ 0 γ -1 1 ) k γ 0 where k is the smallest integer such that d(γ 0 γ -1 1 ) k γ 0 ∈ D . We may rewrite dβ n = dγ 0 (γ -1 1 γ 0 ) k . From Proposition 2, γ 0 = β n and γ -1 1 γ 0 = β -1 1 , therefore dβ n = dβ n β -k 1 . Since β n is an involution, dβ n = dβ -1 n = dβ k 1 β -1 n . Again, β n = β -1 n so that dβ n = dβ k 1 β n . 2
C * i = ∪ c∈C i c and C * = ∪ i∈{0,...,n} C * i
A contraction kernel is defined in a similar way for an n-map M . It follows that the set of n-cells of K c in G, which is empty, is precisely a set of 0-cells in G.

Remark 7 If G is an n-G-map, then from the very definition of cells (Definition 9) an

i-cell in G is an (n -i)-cell in G. Proposition 16 If G is an n-G-map, a contraction kernel K c in G is a re- moval kernel in G. Proof: If G = (D, α 0 , . . . , α n ) we may write G = (D, α 0 , . . . , α n ) with α i = α n-i for all i ∈ {0, . . . ,
From Definitions 9, 12, and 6 it is also readily seen that an i-cell of degree 2 in G is an (n -i)-cell of dual degree 2 in G. Eventually, from Definition 26 a cell of K c is a regular cell of G. 2

The following definition is adapted from [START_REF] Grasset-Simon | Définition et étude des pyramides généralisées nD : application pour la segmentation multi-echelle d'images 3d[END_REF] where a definition combining removals and contractions was given. The definition below is obtained by considering that no cell is to be removed.

The operation of cells contraction in n-G-maps is defined as follows in [START_REF] Grasset-Simon | Définition et étude des pyramides généralisées nD : application pour la segmentation multi-echelle d'images 3d[END_REF] Note 2 (Definition of cells contraction by [START_REF] Grasset-Simon | Définition et étude des pyramides généralisées nD : application pour la segmentation multi-echelle d'images 3d[END_REF]) Let G = (D, α 0 , . . . , α n ) be an n-G-map and K c = {C i } 1≤i≤n a contraction kernel in G.

Let BV i = C * i α i \ C * i , ∀i, 0 ≤ i ≤ n.
The set BV i is called the set of surviving darts which are neighbors of an i-cell to be contracted. The n-G-map resulting of the contraction of the cells of C is G = (D , α 0 , . . . , α n ) defined by:

(1) D = D \ C * ;

(2) ∀i, 0 ≤ i ≤ n, ∀b ∈ D \ BV i , bα i = bα i ;

(3) ∀i, 0 < i ≤ n, ∀b ∈ BV i , bα i = b = b(α i α i-1 ) k α i where k is the smallest integer such that b ∈ BV i .

In this paper, we choose to define the contraction operation in G-maps as a removal operation in the dual map (Definition 27 below). The equivalence between this definition and the one (Note 2) given by Grasset in [START_REF] Grasset-Simon | Définition et étude des pyramides généralisées nD : application pour la segmentation multi-echelle d'images 3d[END_REF] or by Damiand and Lienhardt in [3] will be stated by Proposition 19. = γ 0 , . . . , β 1 not.

= γ n-1 )

From Definition 28, M = M/K c = M \ K c . Let M 1 = M \K c = (D, γ 0 , . . . , γ n-1 ). From Definition 21, the involutions γ i are defined by

• dγ i = d(γ i γ -1 i+1
) k γ i for i ∈ {0, . . . , n -2}, and

• dγ n-1 = dγ k+1 n-1 if i = n -1.
With the notations of Proposition 2 we obtain:

• dβ (n-i) = d(β (n-i) β -1 (n-i)-1 ) k β (n-i) for i ∈ {0, . . . , n -2}, and

• dβ 1 = dβ k+1 1 if i = 1.
where (n -i) ∈ {2, . . . , n} when i ∈ {0, . . . , n -2}. 2

Conclusion and perspectives

We have defined cells removal and contraction in combinatorial maps, based on the previous work by Damiand and Lienhardt for generalized maps.

A logical sequel of this paper will be the definition of n-dimensional combinatorial pyramids and the related notions, the way Brun and Kropatch [START_REF] Brun | Combinatorial pyramids[END_REF] did in the two-dimensional case and following the works of Grasset [START_REF] Grasset-Simon | Définition et étude des pyramides généralisées nD : application pour la segmentation multi-echelle d'images 3d[END_REF] about pyramids of generalized maps.

Index of theorem-like environments

Fig. 1 .

 1 Fig. 1. A closed 2-G-map G (left). The 2-maps HV (G) and HV (G) (right).

2 α 0 α 1 α 2 α 0 = α 0 α 2 Fig. 2 .

 2122 Fig. 2. A part of a closed 2-G-map G (left) and a part of a connected component of the associated n-map M 2 = HV (G) (right).

Definition 7

 7 Let M = (D, γ 0 , . . . , γ n-1 ) be an n-map. We denote by AG(M ) the (n + 1)-tuple ( D, α 0 , α 1 , . . . , α n ) where • D = D ∪ D , where D is a finite set with the same cardinal as D, • σ is a onte-to-one correspondance between D and D .

  is a one-to-one map. Now, let d ∈ D = D ∪ D . Either d ∈ D or d ∈ D . In either case, by (1) and the fact that α i|D and α i|D are onto, there exists b ∈ D such that d = bα i . The map α i is therefore onto.

Fig. 3 .Property 1 •

 31 Fig. 3. Degree and local degree: The cell v 2 has a degree 2 and a local degree 3. Dual degree and dual local degree: The cell e 1 has a dual degree and a dual local degree 2, whereas e 2 has a dual degree 1 and a dual local degree 2. Property 1 Following Definition 11, the degree of a cell C in an n-G-map G = (D, α 0 , . . . , α n ) is precisely the number of sets in the set ∆ = {

{<

  αi+1 > (d) d ∈ C } (Property 1). By Definition 12, the local degree of C is the number of sets in the set Λ = { < αi , αi+1 >(d) d ∈ C } . Now, for any dart b of C we have < αi , αi+1 >(b) ⊂< αi+1 >(b) (by the definition of an orbit). Let b and b be darts of C such that < αi+1 >(b ) and < αi+1 >(b) are distinct orbits. Necessarily, we have b

Fig. 4 .

 4 Fig. 4. A solid representation of a part of a 3-G-map where a vertex has a local degree 2 but is not regular. (The vertex is made of all the depicted darts.) Since bα i+1 / ∈< αi , αi+1 >(b), it follows that the two above orbits are distinct. As any dart d ∈ C belongs to one of them, they form a partition of C and the local degree of C is 2 according to Definition 12. 2

2

  Definition 16 (Regular cell in n-maps) A cell in an n-map is said to be regular if it satisfies the two conditions a) and b) below: a) If i < n -3, for all d ∈ C we have:

Notation 2 Proposition 7

 27 If D and D are sets, σ : D -→ D , and S ⊂ D, we denote by Sσ the image of S by σ, i.e. Sσ = { sσ s ∈ S } Let M be an n-map and G

  First, if p = 0 we have d = b ∈ C ∪ Cσ and there is nothing left to prove. Thus, the property holds for p = 0. Now we suppose that the property is satisfied for p ∈ N * and we consider a dart d = bα k 1 . . . α kp α k p+1 . We denote b = bα k 1 . . . α kp . Since the property is valid for p, we have b ∈ C or b ∈ Cσ. If b ∈ C, we deduce from Definition 7 that b

  If b ∈ Cσ we have b = b σ with b ∈ C. Again, following Definition 7 and the fact that Cσ ⊂ D , we have

- 1 > 2 Definition 17 (

 1217 (b) ⊂< αn > (b), hence C ⊂< αn > (b). On the other hand, for all dart d ∈ C, dγ 0 σ = dα n α 0 α n . Since n ≥ 2 we obtain dγ 0 σ = dα 0 α n α n = dα 0 . From C ⊂< αn > (b) and d ∈ C we deduce that d ∈< αn >(b), thus dα 0 ∈< αn >(b). Eventually, dγ 0 σ ∈< αn >(b) so that Cγ 0 σ ⊂< αn >(b). We conclude that < αn >(b) = C ∪ Cγ 0 σ. Associated cell) The cell C as defined in Proposition 7 will be called the associated cell of C in AG(M).

2 Lemma 6

 26 Thus, all the intersections of the above union of sets are empty. If C is an (n -1)-cell with local degree 2 in an n-map M , then the associated cell of C in AG(M ) has a local degree 2.Proof: Let M = (D, γ 0 , . . . , γ n-1 ), AG(M ) = ( D = D ∪ D , α 0 , . . . , α n ) following Definition 7.

2 Lemma 7

 27 sets (Lemma 5), we obtain that C has a local degree 2 according to Definition 12. If C is an i-cell with local degree 2 in an n-map M for i < n -1, then the associated cell of C in AG(M ) has local degree 2. Proof: Let M = (D, γ 0 , . . . , γ n-1 ) and AG(M ) = ( D = D ∪ D , α 0 , . . . , α n ) following Definition 7.

2 or 2 Proposition 8 . 2 Lemma 8 )Corollary 3

 228283 again, C has a local degree 2 according to Definition 12. If M is an n-map and C is an i-cell with local degree 2 in M (Definition 15) for 0 ≤ i ≤ n -1, then the associated cell of C in AG(M ) has a local degree of 2 (Definition 12). Proof: The case i = n -1 is proved by Lemma 6, and the case i < n -1 by Lemma 7Let M = (D, γ 0 , . . . , γ n-1 ) be an n-map and AG(M ) = ( D = D ∪ D , α 0 , . . . , α n ) be an associated n-G-map of M following Definition 7. Let Ψ = {γ k 1 , . . . , γ kp } ⊂ {γ 0 , . . . , γ n-1 } for p ≤ n, and Φ = {α k 1 , . . . , α kp }. For all b ∈ D we have < Φ>(b) ⊂ ( < Ψ>(b)∪ < Ψ>(b)α n With the notations of Lemma 8, for all i ≤ n -2 and all b ∈ D we have: < αi , αi+1 >(b) ⊂< γi , γi+1 >(b)∪ < γi , γi+1 >(b)α n Proof of Lemma 8: Let d ∈< Φ>(b). We may write

  and we obtain that d ∈< Ψ>(b)α n . The same result is immediately obtained when h q+1 = n since in this case d = b α n . If b ∈< Ψ > (b)α n , we have b = b α n for some dart b ∈< Ψ > (b) and we obtain, when h q+1 = n, that d = b α n α h q+1 = b γ h q+1 ∈< Ψ > (b). Again, if h q+1 = n we immediately conclude since in this case d = b α n α n = b . Eventually, we have proved that d ∈< Ψ > (b) or d ∈< Ψ > (b)α n when the sequence of involutions has a length p + 1. The property is thus true for any sequence. 2

  in a map that satisfies property a) of Definition 16, than C in AG(M ) satisfies property a) of Definition 14. Proof: Let M = (D, γ 0 , . . . , γ n-1 ) and G = AG(M ) = ( D = D∪D , α 0 , . . . , α n ). • If i < n -3. We may write C =< γi >(b) for some b ∈ D. Following Definition 17 we have C = C ∪ Cα n . Let d ∈ C. a) If d ∈ D, by Definition 16 we know that either

  b) If d ∈ D , we have d = d α n for some dart d ∈ D.

2 Lemma 10

 210 If C is an i-cell in an n-map for i ≤ n -2 and such that it satisfies property b) of Definition 16, then C in AG(M ) satisfies property b) of Definition 14. Proof: Let us denote M = (D, γ 0 , . . . , γ n-1 ) and G = AG(M ) = ( D = D ∪D , α 0 , . . . , α n ). Furthermore, let C be an i-cell of M that satisfies property b), and let d be a dart of C.

  But this is a contradiction with the fact that C is regular in M (point b of Definition 16). Hence, dα i+1 / ∈< αi , αi+1 >(d) which is property b) of Definition 14. b) If d ∈ D , we have d = bα n for some dart b ∈ C. Suppose that dα i+1 = bα n α i+1 ∈< αi , αi+1 >(bα n ). Since n / ∈ {i, i + 1} we have bα n α i+1 ∈< αi , αi+1 > (b). By Lemma 8,

2 Theorem 4

 24 and by Corollary 3 (since d ∈ D ) d γ n-1 ∈< γn-2 , γn-1 >(d ). A contradiction with the fact that C is regular (Definition 16). Thus, again dα n-1 / ∈< αn-2 , αn-1 >(d). Enventually, condition b) of Definition 14 is satisfied by C. Let M = (D, γ 0 , . . . , γ n-1 ) be an n-map and AG(M ) = ( D = D ∪ D , α 0 , . . . , α n ) be an associated n-G-map of M following Definition 7. If C is a regular i-cell in M for 0 ≤ i ≤ n -2 (Definition 16), then the associated cell of C in AG(M ) is regular (Definition 14). Proof: If C satifies properties a) and b) of Definition 16 then by Lemma 9 C satisifies property a) Definition 14 and by Lemma 10 it satisifies property b) of Definition 14. Hence C is regular in G. 2

2 Proposition 12 2 Definition 24 (Remark 6 M

 2122246 1 where r is the smallest integer such that b ∈ D . Again, since dα n = dα n (Definition 20) we have dγ n-1 = dα n (α n-1 α n ) r α n-1 . Eventually, dγ n-1 = dγ n-1 . 2 Definition 23 (Associated removal set) If M = (D, γ 0 , . . . , γ n-1 ) is an n-map and K r = {R i } i=0,...,n is a removal kernel in M . Let G = AG(M ) = ( D, α 0 , . . . , α n ) be an associated n-G-map of M . We define the removal set Kr = { Ri } i=0,...,n in G as follows: ∀i ∈ {0, . . . , n -1}, Ri = { C C ∈ R i } where C, for any cell C of M , is the associated cell of C in AG(M ) (Definition 17). As stated by Proposition 12, the removal set introduced in the previous definition is in fact a removal kernel. Lemma 16 If C 1 and C 2 are disjoint cells in M , then C1 and C2 are disjoint cells of AG(M ).Proof: Following Definition 17 and the notations of Definition 7:• If C 1 and C 2 are both i-cells with i < n we have C1 = C 1 ∪ C 1 σ and C2 = C 2 ∪C 2 σ. Since C 1 ∩C 2 = ∅ and σ is one-to-one, it follows that C 1 σ ∩C 2 σ = ∅. Now, for any cell C ⊂ D and Cσ ⊂ D with D ∩ D = ∅. It follows that C 1 ∩ C 2 σ = C 2 ∩ C 1 σ = ∅. Eventually, we obtain C1 ∩ C2 = ∅. • If C 1 is an i-cell with i < n and C 2 is an n-cell we have C1 = C 1 ∪ C 1 σ and C2 = C 2 ∪ C 2 γ 0 σ,the same arguments apply since γ 0 σ is one-to-one and Cγ 0 σ ⊂ D for all cells C of M . • Same considerations apply if C 1 and C 2 are both n-cell. The removal set Kr in Definition 23 is a removal kernel in AG(M ). Proof: Since K r is a removal kernel, by Proposition 8 all cells of Kr have a local degree 2 and by Theorem 4 they are regular. By Lemma 16, if two cells of K r are disjoint then their associated cells (in Kr ) are disjoint too. Thus, Kr is a removal kernel in AG(M ) according to Definition 19. Associated removal kernel) Let M be an n-map and AG(M ) be an associated G-map of M . If K r is a removal kernel in M , the set Kr (Definition 23) is called the removal kernel associated with K r in AG(M ) (following Proposition 12). Definition 25 (Removal set restriction) If S r = {R i } 0≤i≤n is a removal set in an n-map M and D is a connected component of M , we denote by S r|D the removal set that contains all the cells of S r included in D . In Definition 25, since D is a connected component, a cell of S r is included in D as soon as one of its darts belongs to D . Indeed, any cell of < γ 0 , . . . , γ n-1 >(d) belongs to the same connected component of M as d. Proposition 13 If M is an n-map, K r is a removal set in M , and D is a connected component of M , we have the following diagram: M removal of Kr --------→ M \ K r removal of Kr |D ----------→ M \ K r|D Proof: Following Remark 3 and Definition 8, M = M |D and the sub-map of M \ K r induced by D are both n-maps. We now have to prove that the diagram commutes. Let us denote: M = (D, γ 0 , . . . , γ n-1 ), M = (D , γ 0 |D , . . . , γ n-1 |D ); M \ K r = (D , γ 0 , . . . , γ n-1 ); and M \ K r|D = (D , γ 0 , . . . , γ n-1 ).

Proof: 2 Theorem 6

 26 Let us denote G = AG(M ) = ( D = D ∪ D , α 0 , . . . , α n ) following Definition 7, and Sr = { Ri } 0≤i≤n the associated removal set of S r in AG(M ). (⊂) Let C be an i-cell in R and b ∈ C. From the very definition of the i-cell C associated to C in AG(M ) and from the definition of Sr , we have b ∈ C ∈ Ri . Since b ∈ R * , from Definition 22 there is a cell C in HV ( Sr ) that contains b, being a particular orbit of b. As a cell of HV (AG(M )), since b ∈ D, the cell C belongs to HV ( Sr ) |D . Since M = HV (AG(M )) |D (Proposition 4) the i-cell C is an i-cell of M . From b ∈ C ∩ C we then deduce that C = C so that C is an i-cell of HV ( Sr ) |D . d ∈ C (⊃) Let d ∈ C ∈ HV ( Sr ) |D . From Definition 22 there exists an i-cell C ∈ R such that C ⊂ C ∈ R. The orbit C ∈ R is a particular orbit of d in AG(M ); in particular d ∈ C ∈ R. Following the definition of Sr , the cell C is associated to an i-cell C ∈ R. Note that, from Definition 17, C ∩ D = C. As d ∈ C ⊂ D and d ∈ C we obtain that d ∈ C. Finally, we have d ∈ C ∩ C . Since M = HV (AG(M )) |D (Proposition 4) the i-cell C of HV ( Sr ) |D is an i-cell of M . It follows that C is an i-cell of R. If M is an n-map and K r is a removal kernel in M , the (n + 1)tuple M \ K r as defined by Definition 21 is a valid n-map.

•

  We have HV ( G) |D = M by Proposition 4. Hence the left part of the diagram. • If K r is a removal kernel in M , then Kr as defined in Definition 24 is a removal kernel in G by Proposition 12. Thus the bottom-right part of the diagram holds by Proposition 11. • We have K r = HV ( Kr ) |D by Lemma 17. Thus, the upper-right part of the diagram is valid by Proposition 13.

3. 2

 2 Cells contraction Definition 26 (Contraction kernel) Let G = (D, α 0 , . . . , α n ) be an n-Gmap and K c = {C i } 0≤i≤n be sets of i-cells with C 0 = ∅. Let C = ∪ n i=0 C i . Furthermore, we suppose that the cells of C are disjoint (i.e. ∀c, c ∈ C, c∩c = ∅), have a dual local degree 2, and are regular cells in G. The family of sets K c is then called a contraction kernel in G.

Definition 27 (Notation 5 2 Proposition 18 2 Definition 28 (M

 275218228 Cells contraction in n-G-maps) Let G = (D, α 0 , . . . , α n ) be an n-G-map and K c = {C i } 1≤i≤n be a contraction kernel. The n-G-map resulting of the contraction of the cells of K c is G = G \ K c . The n-G-map obtained after the contraction of a kernel K c = {C i } 0≤i≤n from an n-G-map G will be denoted either by G/K c , or by G/C * . Proposition 17 Let G, G be n-G-maps and K c = {C i } 0≤i≤n be a contraction kernel as in Definition 27. Since C 0 = ∅, then dα 0 ∈ D for all d ∈ D .Proof: It is readily seen that dα 0 ∈ D for all d ∈ D . Indeed, suppose that dα 0 ∈ C i ∈ C i for some i ∈ {1, . . . , n}. In other words, dα 0 belongs to an i-cell which is to be removed for i > 0. Since i > 0, the orbit that defines C i obviously contains bα 0 for all b ∈ C i (Definition 9). Therefore, dα 0 α 0 = d also belongs to C i . This is a contradiction with the fact that d ∈ D . Let G = (D, α 0 , . . . , α n ) be an n-G-map and K c = {C i } 1≤i≤n be a contraction kernel. The n-G-map resulting of the contraction of the cells of C according to Definition 27 is G = (D , α 0 , . . . , α n ) defined by:(1) D = D \ C; (2) ∀d ∈ D , dα 0 = dα 0 ; (3) ∀i, 0 < i ≤ n, ∀d ∈ D , dα i = d = d(α i α i-1 ) k α i where k is the smallest integer such that d ∈ D . Proof: Let G = (D, α 0 , . . . , α n ) with α i = α n-i for 0 ≤ i ≤ n. From Proposition 16, K c is a removal kernel in G and we denote G = G \ K c . Thus, fromDefinition 20 G = (D , α 0 , . . . , α n ) where:• D = D \ C; • ∀d ∈ D , dα n = dα n ; • ∀i, 0 ≤ i < n, ∀d ∈ D , dα i = d = (α i α i+1 ) k α i where k is the smallest integer such that d ∈ D . Now, let us denote G/K c = G = (D , α 0 , . . . , α n ) following Definition 27. Since G = G we have α i = α n-i for 0 ≤ i ≤ n.Therefore, we obtain:• ∀d ∈ D , dα 0 = dα n = dα n ;This definition of α i for 0 ≤ i ≤ n is precisely the one given by Note 2 for the n-G-map obtained after contraction of K c from G. Cells contraction in n-maps) Let M = (D, γ 0 , . . . , γ n-1 ) be an n-map and let K c = {C i } 1≤i≤n be a contraction kernel. The n-map resulting of the contraction of the cells of K c , which we denote M/K c is the n-map M \ K c .The following proposition provides the justification for the definition of cells contraction in n-maps. Proposition 20 We have the following commutative diagram: contraction of HV (Kc) -------------→ M = M/K c Proof: The diagram is a consequence of the one below, which comes from Proposition 1, Proposition 11 and Definition 27.

2 Proposition 21 1 ,

 2211 → G \ K c = G/K c = G/K c HV M \ K c = M /K c = M/K cIndeed, parts[START_REF] Brun | Combinatorial pyramids[END_REF] and (3) of the above diagram were stated by Proposition 1. Part (2) is precisely the diagram of Proposition 11. Eventually, the equalitiesG \ K c = G/K c and M \ K c = M /K c follow Definition 27. Let M = (D, γ 0 , . . . , γ n-1 ) be an n-map. Let K c = {C i } 1≤i≤n be a contraction kernel. The n-map obtained after contraction of the cells of K c , M = (D , γ 0 , . . . , γ n-1) is defined by:• D = D \ C; • ∀d ∈ D , dγ 0 = dγ k n-1 γ 0 where k is the smallest integer such that dγ k n-1 γ 0 ∈ D ; • ∀i ∈ {1, . . . , n -1}, ∀d ∈ D , dγ i = dγ k n-1 (γ i γ -1 i-1 ) k γ i ,where k is the smallest integer such that dγ k n-1 ∈ D and k is the smallest integer such thatdγ k n-1 (γ i γ -1 i-1 ) k γ i ∈ D . • D = D \ C; • For i = 1, ∀d ∈ D , dβ 1 = dβ k+1where k is the smallest integer such thatdβ k+1 1 ∈ D . • ∀i ∈ {2, . . . , n}, ∀d ∈ D , dβ i = d(β i β -1 i-1 ) k β i , where k is the smallest integer such that d(β i β -1 i-1 ) k β i ∈ D .Proof: We use the definition of the contraction in M as a removal of K c in the dual map M . Following Proposition 2, we will denoteM 1 = M = (D, β n not.

  Former definitions, lemmas and propositions numbers and the current ones.

		Definition 24	Definition 23	42
		Lemma 17	Lemma 15	40
		Lemma 19	Lemma 17	44
		Proposition 7	Proposition 7	22
		Proposition 12	Proposition 10	39
	1	Introduction Proposition 13	Proposition 15	46	3
	2	Combinatorial maps Proposition 14	Proposition 11	41	4
	2.1 Basic definitions Proposition 15	Proposition 12	43	4
		Proposition 16	Proposition 13	43
	2.2 From maps to G-maps and vice versa Proposition 21 Proposition 18	48	8
	2.3 Cells in maps Proposition 22	Proposition 19	49	12
	3 Table 1	Cells removal and contraction in G-maps and maps Proposition 24 Proposition 21 50	35
	3.1 Cells removal			35

Email addresses: Sebastien.Fourey@greyc.ensicaen.fr (Sébastien Fourey), Luc.Brun@greyc.ensicaen.fr (Luc Brun).

  |D , . . . , γ n-1 |D ) satisfies all the conditions of Definition 2.Using the next lemma, it follows from the latter remark that M is a valid n-map if and only if D is the union of connected components of M , which leads to the notion of induced sub-map (Definition 8).

	GREYC Technical Report -TR-2009-01
	(D , γ 0 Lemma 2 Let M = (D, γ 0 , . . . , γ n-1 ) be an n-map and D be a subset of D.
	The two following properties are equivalent:
	i) D is a union of connected components of M ;
	ii) ∀d ∈ D , ∀i ∈ {0, . . . , n -1}, dγ i ∈ D .
	Proof: (i ⇒ ii) since dγ i belongs to the same connected component of M as
	d, thus it belongs to D if d ∈ D .
	(ii ⇒ i) Let R be the relation on D defined by
	dRd ⇔ ∃i, dγ i = d
	It is readily seen that the reflexive and transitive closure of R is an equivalence
	relation whose equivalence classes are orbits in M that use all the permuta-
	tions γ's, i.e. they are connected components of M . Using ii), D is such an
	equivalent class. 2
	Definition 8 Let M = (D, γ 0 , . . . , γ n-1 ) be an n-map and D be a union
	of connected components of D. The n-map (D , γ 0 |D , . . . , γ n-1 |D ), following
	Remark 3, is called the sub-map of M induced by D , which we denote by
	M |D .
	2
	Remark 3 If M = (D, γ 0 , . . . , γ n-1 ) is an n-map and D is a subset of D
	such that for all d ∈ D and all i ∈ {0, . . . , n -1}, dγ i ∈ D ; then the map
	γ j |D is well defined for all j ∈ {0, . . . , n -1} and the (n -1)-tuple M =

Definition 9 (n-G-maps and cells [8]) Let

  7)Let b be a dart of D. Since M is connected, we haveD =< γ 0 , . . . , γ n-1 >(b). If d isa dart of D we may thus write d = bγ h 1 . . . γ hp , with p ∈ N and h k ∈ {0, . . . , n -1} for k ∈ {1, . . . , p}. Since γ i = γ i|D , we may prove by a simple recurence on p that bγ h 1 . . . γ hp = bγ h 1 . . . γ hp and we deduce that D ⊂< γ 0 , . . . , γ n-1 >(b) in G. On the other hand, if d ∈< γ 0 , . . . , γ n-1 >(b), we have d = bγ h 1 γ h 2 . . . γ hq with q ∈ N and h k ∈ {0, . . . , n -1} for k ∈ {1, . . . , q}, and it is again readily seen by a recurence on q that d = bγ h 1 γ h 2 . . . γ hq , thus d ∈ D. Eventually, we have D =< γ 0 , . . . , γ n-1 >(b) (in G).

	The orbit D =< γ 0 , . . . , γ n-1 >(b), which uses all the permutations of HV (G),
	is then a connected component of D in G. Therefore, since γ i|D = γ i , we obtain
	that M = (D, γ 0|D , . . . , γ n-1 |D ) is one of the n-maps induced by the connected
	component < γ 0 , . . . , γ n-1 >(b) of HV (G). In other words, M = HV (G) |D . 2
	2.3 Cells in maps
	G = (D, α 0 , . . . , α n ) be an n-
	G-map (n ≥ 1). Let us consider d ∈ D. The i-cell, or cell of dimension i,
	which contains d is denoted by C i (d) and defined by the orbit:
	C i (d) =< α 0 , . . . , αi , . . . , α n >(d)
	where αi denotes the absence of the involution α i .

Definition 10 (n-maps and cells [8]) Let

	M = (D, γ 0 , . . . , γ n-1 ) be an n-
	map. The i-cell or cell of dimension i (vertex, edges,. . . ) of M which owns a
	given dart d ∈ D is denoted by C i (d) and defined by the orbits:
	∀i ∈ {0, . . . , n -1} C i (d) = < γ 0 , . . . , γi , . . . , γ n-1 >(d)

Note 2

Remark 6 43

Proposition 10 Definition 20 and the one given in Note 1 are equivalent.

Proof: We need to check that the involutions α i coincide in both definitions for all i, 0 ≤ i ≤ n .

For i = n, only case [START_REF] Damiand | Définition et étude d'un modèle topologique minimal de représentation d'images 2D et 3D[END_REF] in Note 1 applies and D \ BV n = D since BV n = ∅. This point thus defines bα n = bα n for all b ∈ D which is precisely point [START_REF] Damiand | Définition et étude d'un modèle topologique minimal de représentation d'images 2D et 3D[END_REF] of Definition 20.

It remains the case when 0 ≤ i < n. Let d ∈ D , we distinguish two cases:

∈ BV i then from Lemma 13 we have dα i ∈ D . Thus, k = 0 is the smallest integer such that d ∈ D in point [START_REF] Damiand | Removal and contraction for n-dimensional generalized maps[END_REF] of Definition 20 so that dα i = d = dα i is defined as in point (2) of Note 1.

2) Next, we consider the case when d ∈ BV i . We define

From Lemma 12, we know that for all 0 ≤ h < k 2 we have d(

Because applying α i+1 cannot send a dart from an i-cell to another i-cell we deduce that d(

Definition 21 (Cells removal in n-maps) Let M = (D, γ 0 , . . . , γ n-1 ) be an n-map and S r = {R i } 0≤i≤n-1 a removal set in M . We define the (n -1)tuple M \ S r = (D , γ 0 , . . . , γ n-1 ) obtained after removal of the cells of S r by:

where k is the smallest integer such that dγ k+1 n-1 ∈ D .

We will prove in the sequel (Theorem 6) that the such defined (n -1)-tuple M \ S r is actually an n-map if S r is a removal kernel (Definition 19), this by establishing the link between removal in n-maps and removal in n-G-maps. Note that until this result has been proved, in the notation M = M \ K r , the prime indicates that M is linked to a map but is not necessarily itself a map.

Definition 22

Let G be an n-G-map, S r = {R i } 0≤i≤n be a removal set in G and M = HV (G). We define the set HV (S r ) = {R i } 0≤i≤n as follows:

On the other hand, for all d ∈ D and all i ∈ {0, . . . , n -1} we have

Lemma 15 If G is an n-G-map and S r is a removal set in G, then the set HV (S r ) is a removal set in HV (G).

From the definition of

The next proposition is a first step to show that our definition of cells removal in n-maps is consistent with the one of removal in n-G-maps.

It remains to be proved that the removal operation, when applied to an n-map, produces a valid n-map as soon as the cells to be removed constitute a removal kernel according to Definition 19. A consequence of Propostion 11 is that this is true when the map is the map of the hypervolumes of an n-G-map, not for any map. The extension of Proposition 11 to any map will be the purpose of Theorem 6.

Proposition 11 If G is an n-G-map and K r is a removal kernel in G, we have the following commutative diagram:

In particular, M \ HV (K r ) is an n-map. We need to prove that for all i ∈ {0, . . . , n -1} and for all d ∈ D , dγ i = dγ i which will eventually show that

Proof of

Since α 2 n = 1 D the latter equality becomes:

where k is the smallest integer such that d ∈ D .

or again, since

Which is precisely the definition of α i for 0 ≤ i ≤ n in Proposition 18. 2

Proposition 19 Definition 27 and the one given by Grasset (Note 2, see also [START_REF] Grasset-Simon | Définition et étude des pyramides généralisées nD : application pour la segmentation multi-echelle d'images 3d[END_REF]) are equivalent.

Proof: Let G = (D, α 0 , . . . , α n ) be an n-G-map and K c = {C i } 1≤i≤n a contraction kernel in G.

We first express G/K c = G \ K c , following Definition 27. Thus, let us write G = (D, α 0 , . . . , α n ) where

From [6, Definition 10] (see also Note 1) and by Proposition 10, G is defined by:

(1)

We denote G = (D , α 0 , . . . , α n ) with α i = α n-i for all i ∈ {0, . . . , n}. From the above definition of α i , 0 ≤ i ≤ n we obtain:

(1)

where k is the smallest integer such that b ∈ BV i .

Using the relation α n-i = α i for 0 ≤ i ≤ n, we deduce:

where k is the smallest integer such that b ∈ BV i .

Proof:

The n-map obtained after the contraction of the cells in

) and let M = M \K c , if we denote M = (D , γ 0 , . . . , γ n-1 ), according to Definition 21 and the above notations we have:

where k is the smallest integer such that dγ k+1 n-1 ∈ D .

Since M = M , by Definition 6 we have

Thus,

• For i = 1,

• For i ∈ {2, . . . , n -1},

Proposition 22 Let M = (D, β 1 , . . . , β n ) be an n-map. Let K c = {C i } 1≤i≤n be a contraction kernel. The n-map obtained after contraction of the cells of K c , M = (D , β 1 , . . . , β n ) is equivalently defined by: