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

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

Connecing walks and connecting dart sequences for n-D combinatorial pyramids

Combinatorial maps define a general framework which allows to encode any subdivision of an n-D 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 objects (either shapes or partitions). Combinatorial pyramids have first been defined in 2D. This first work has later been extended to pyramids of n-D 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. This work presents the design of pyramids of n-D combinatorial maps and important notions for their encoding and processing.

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

Introduction

Pyramids of combinatorial maps have first been defined in 2D [START_REF] Brun | Combinatorial pyramids[END_REF], and later 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.

The key notion for the definition of pyramids of maps is the operation of simultaneous removal or contraction of cells. These two notions have been defined in [START_REF] Fourey | A first step toward combinatorial pyramids in nD spaces[END_REF] (see also [START_REF] Fourey | A second step toward combinatorial pyramids in nd spaces[END_REF]) where the definitions have been related to the ones given in [START_REF] Damiand | Removal and contraction for n-dimensional generalized maps[END_REF] for generalized maps. Their validity was indeed proved using the link between maps and generalized maps established by Lienhardt [START_REF] Lienhardt | Topological models for boundary representation: a comparison with n-dimensional generalized maps[END_REF].

After recalling some preliminaries about combinatorial maps and the main results obtained in [START_REF] Fourey | A first step toward combinatorial pyramids in nD spaces[END_REF], we present in this paper two important notions in the design of combinatorial pyramids: connecting walks and connecting darts sequences. These two notions correspond respectively to the notions of reduction window and receptive field within the regular pyramid framework. They also have interesting properties that should allow us to derive, in future works, efficient encoding schemes and operations on pyramids of n-D maps the same way Brun and Kropatsch did for 2-dimensional combinatorial pyramids [START_REF] Brun | Implicit encoding of combinatorial pyramids[END_REF].

Connecting walks which are introduced in Section 4, somehow fill the gap between two consecutive levels of the pyramid. We first provide a definition of connecting walks in generalized maps and establish a link (Proposition 13) with the definition we give for such walks in combinatorial maps. On the other hand, connecting dart sequences (Section 5) link a level of a pyramid of maps to any of its lower levels. The definition of the latter sequence as well as a discussion of its expected use are given in Section 5.

Combinatorial maps

Basic definitions

We recall here the definitions of n-dimensional generalized maps (n-G-maps for short) and n-dimensional combinatorial maps (n-maps).

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 ([ 10
]) 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
Proposition 2 (Associated maps of an n-G-map [START_REF] Lienhardt | Topological models for boundary representation: a comparison with n-dimensional generalized maps[END_REF]) 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
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 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 -6)

(D = D 1 ∪ D 2 , γ 0 , γ 1 ) with 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)
1 Cells are formally defined in subsection 2.2. 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].

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 -1 6 5 4 1 1 2 -2 4 -5 6 5 -4 3 -3 -6 -6 6 3 4 5 2 1 -1 -2 -3 -4 -5 -1 A B C A B C A A B B C Fig. 1. A closed 2-G-map G (left). The 2-maps HV (G) and HV (G) (right). The 2-map HV (G) is (D 1 , γ 0 , γ 1 )
where

γ 0 = (1, 6)(2, 3)(4, 5)(-1, -6)(-2, -3)(-4, -5) γ 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)

Cells in maps

Definition 7 (n-G-maps and cells [START_REF] Lienhardt | Topological models for boundary representation: a comparison with n-dimensional generalized maps[END_REF])

Let 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 8 (n-maps and cells [START_REF] Lienhardt | Topological models for boundary representation: a comparison with n-dimensional generalized maps[END_REF]) Let M = (D, γ 0 , . . . , γ n-1 ) be an nmap. 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:

α 1 α 0 α 2 α 0 α 1 α 2 α 0 = α 0 α 2
∀i ∈ {0, . . . , n -1} C i (d) = < γ 0 , . . . , γi , . . . , γ n-1 >(d) 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 3 ([10])

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) Definition 9 (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. Property 1 ([10]) Following Definition 9, 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 . Notation 1 Let (D, α 0 , . . . , α n ) be an n-G-map. For d ∈ D, we denote by < αk 1 , αk 2 , . . . , αk p >(d)
, where all the involutions are excluded, the orbit < Φ> (d) where • For i ∈ {0, . . . , n -1}, the local degree of C is the number

Φ = {α 0 , . . . , α n } \ {α k 1 , α k 2 , . . . , α k p }. 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}
|{< αi , αi+1 >(b) b ∈ C}| • For i ∈ {1, . . . , n}, the dual local degree of C is the number |{< αi-1 , αi >(b) b ∈ C}| Le local degree (resp. dual local degree) of an n-cell (resp. a 0-cell) is 0.
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 .

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 edge 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 10 all belong to a unique vertex (v 2 ).

Property 2 ([10])

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

Property 3 (Cell with local degree 1 [START_REF] Fourey | A second step toward combinatorial pyramids in nd spaces[END_REF])

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).
It is known since [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] that cells that may be removed or contracted in a Gmap must satisfy a criterion which, although correct, was mistakenly called "having a local degree 2". In [START_REF] Fourey | A first step toward combinatorial pyramids in nD spaces[END_REF][START_REF] Fourey | A second step toward combinatorial pyramids in nd spaces[END_REF], the notion of regularity, recalled below, was introduced in order to state a new criterion based on the correct definition of the local degree (Definitions 10 and 12).

Definition 11 (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)
Any (n -1)-cell is said to be regular too.

The following theorem provides a characterization of cells that may be removed from a G-map. Definition 12 (Local degree in maps [START_REF] Fourey | A first step toward combinatorial pyramids in nD spaces[END_REF]) 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 8, 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 >.

Definition 13 (Regular cell in n-maps [START_REF] Fourey | A first step toward combinatorial pyramids in nD spaces[END_REF]) An i-cell in an n-map, 0 ≤ i < n -1 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:

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: Furthermore, for such a family 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 .

{bγ n-1 , bγ -1 n-1 }∩ < γ 0 , . . . , γ n-3 >(b) = ∅ Any (n -1)-cell
Definition 15 (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 11 and 10). A removal kernel is defined the same way for an n-map M using Definitions 13 and 12 for the notions of regularity and local degree, respectively.

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. However, this definition is both too restrictive to be a valid definition for the local degree 2, and it also does not exclude cells with local degree 1.

Excluding cells with local degree 1 from Grasset's definition yields the notion of regular cells with local degree 2 (Definition 11). 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 slightly simpler and 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 16 (Cells removal in n-G-maps [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] Fourey | A first step toward combinatorial pyramids in nD spaces[END_REF])

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 4 Let G, G be n-G-maps and K r = {R i } 0≤i≤n be a removal kernel as in Definition 16. Since R n = ∅, then dα n ∈ D for all d ∈ D . Remark 2 Let G, G be n-G-maps and K r = {R i } 0≤i≤n be a removal kernel as in Definition 16. 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 16 is stated by the following proposition.

Proposition 5 ([9]

) Definition 16 and the one given in Note 1 are equivalent.

The following definition for the operation of simultaneous removal of cells in an n-map was given in [START_REF] Fourey | A first step toward combinatorial pyramids in nD spaces[END_REF] (see also [START_REF] Fourey | A second step toward combinatorial pyramids in nd spaces[END_REF]).

Definition 17 (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 kernel in M . The n-map M \ S r = (D , γ 0 , . . . , γ n-1 ) obtained after removal of the cells of S r is defined by:

• D = D \ R * ; • ∀i ∈ {0, . . . , n -2}, ∀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 . • For i = n -1, ∀d ∈ D , dγ n-1 = dγ k+1 n-1
where k is the smallest integer such that dγ k+1 n-1 ∈ D .

It was proved ([9, Theorem 2], see also [START_REF] Fourey | A second step toward combinatorial pyramids in nd spaces[END_REF]) that the such defined (n-1)-tuple M \ S r is actually an n-map, this by establishing the link between the removal operation in n-maps and the same operation in n-G-maps. This link required the following definition for the removal kernel in the map of the hypervolumes of an n-G-map, associated with a removal kernel in the latter G-map.

Definition 18 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: We also denote:

• ∀i ∈ {0, . . . , n -1}, R i = {< α n α 0 , . . . , αn α i , . . . , α n α n-1 >(d)|d ∈ R * i } • R n = {< α 0 α 1 , . . . , α 0 α n-1 >(d)|∃C ∈ R n , d ∈ C} 3.2 Cells contraction Definition 19 (Contraction kernel) Let G = (D, α 0 , . . . , α n ) be an n-G- map and K c = {C i } 0≤i≤n be sets of i-cells with C 0 = ∅. Let C = ∪ n i=0 C i . Furthermore,
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 .

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

i-cell in G is an (n -i)-cell in G.
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.

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 [START_REF] Fourey | A first step toward combinatorial pyramids in nD spaces[END_REF], the contraction operation in G-maps is defined as a removal operation in the dual map (Definition 20 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 [START_REF] Damiand | Removal and contraction for n-dimensional generalized maps[END_REF] will be stated by Proposition 7.

Definition 20 (Cells contraction in n-G-maps [START_REF] Fourey | A first step toward combinatorial pyramids in nD spaces[END_REF])

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 re- sulting of the contraction of the cells of K c is G = G \ K c .

Notation 5

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 6 ([9]

) 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 20 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 . Proposition 7 ([9]
) Definition 20 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.

Definition 21 (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 . Proposition 8 ([9]) 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 that

dγ k n-1 (γ i γ -1 i-1 ) k γ i ∈ D .

Connecting walks

The permutations or involutions which define the map resulting from a removal operation are obtained by somehow following a path in the original map until a surviving dart has been found (Definitions 16 and 17). This leads to the notion of the so called connecting walks which we define here and whose main properties are described.

Notation 6 If S = (d 1 , d 2 , . . . , d p ) and S = (b 1 , b 2 , . . . , b q ), p, q ∈ N,
-G-maps) Let G = (D, α 0 , . . . , α n ) be an n-G-map and K r = {R i } 0≤i≤n be a removal kernel in G. Let G = G \ K r = (D , α 0 , . . . , α n ). The i-connecting walk associated to a dart d ∈ D for i ∈ {0, . . . , n}, denoted by CW i G,G (d)
, is the sequence of darts of D defined by:

CW i G,G (d) = (d 0 , d 1 , . . . , d p ) where • d 0 = d, • ∀u, 0 ≤ u ≤ p, d u = d(α i α i+1 ) u , • p = M in k ∈ N|d k α i ∈ D .
The above definition is clearly linked to the one of the removal operation (Definition 16). To make this link explicit, we first prove the following property which states that darts of an i-connecting walk are, except for the first one, darts of i-cells that have been removed. This property as well as the next one is illustrated by Figure 4(b), in the 2D case for the ease of visualization.

∀k ∈ {1, . . . , p}, d k-1 α i ∈ R * i and d k ∈ R * i Proof:
We prove the property by recurrence on k. From the definition of connecting walks, we know that if p ≥ 1 we have

d 0 α i / ∈ D (i.e. d 0 α i ∈ R * ). Suppose that d 0 α i ∈ R j for j = i, in other words that d 0 α i ∈< αj > (d ) for some d ∈ R * j . Since i = j we have d 0 = d 0 α i α i ∈< αj >(d ) ∈ R j , which contradicts the fact that d 0 ∈ D ; therefore d 0 α i ∈ R * i . Since d 0 α i and d 0 α i α i+1 belong to the same i-cell, we also obtain d 1 = d 0 α i α i+1 ∈ R i . Eventually, the property is true for k = 1. Now, suppose that d k ∈ R * i for k < p. Since k < p and p is the smallest integer such that d p α i ∈ D , then d k α i ∈ R * . If we suppose that d k α i ∈ R j with j = i, since d k α i and d k α i α i = d k
belong to the same j-cell, we would obtain that d k belongs to both an i-cell and a j-cell of the removal kernel K r , which is not allowed by Definition 15. Therefore, we have

d k α i = d (k+1)-1 α i ∈ R i . Again, since d k α i and d k α i α i+1 belong to the same i-cell we also have d k α i α i+1 = d k+1 ∈ R i .
G,G (b) = (b = b 0 , b 1 , b 2 ) (second row) and CW 0 G,G (d) = (d = d 0 , d 1 , d 2 ) (third row).
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], Grasset defines connecting walks in G-maps in a slightly different way then what is done by Definition 22. A first difference is that in Grasset's definition, d does not appear at the beginning of the sequence that defines CW i G G (d), whereas the dart d p α i of Definition 22 is added at the end of the sequence. On the other hand, consecutive darts in a connecting walk as defined by Grasset are linked by alternately either an α i or an α i+1 involution when they are always linked by the permutation α i α i+1 in our definition. Thus, our connecting walk for a given dart and dimension counts ((k -1)/2) + 1 darts when the corresponding one with Grasset's definition has k ones.

Following the definition 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], connecting walks that are distinct (up to reverse ordering and after removal of their last dart) are always disjoint [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]Proposition 22]. With our definition the property simply becomes that connecting walks are either equal or disjoint. In other words, a removed dart belongs to at most one connecting walk for some i ∈ {0, . . . , n}. This property, stated by the following proposition, induces a father-child relationship between darts of consecutive levels similar to the reduction windows in the context of regular pyramids.

Proposition 9 Let G = (D, α 0 , . . . , α n ) be an n-G-map, K r be a removal kernel in G, and d be a dart of R * i for 0 ≤ i < n. The dart d belongs to at most one connecting walk. In other words, the two following properties hold:

i) d ∈ b∈D CW i G,G\K r (b) * ⇒ ∃! b ∈ D , d ∈ CW i G,G\K r (b) * ii) ∀j ∈ {0, . . . , n} \ {i}, ∀b ∈ D , d / ∈ CW j G,G\Kr (b) *
Proof: First note that Figure 5(b) shows an example of a removal kernel for which some darts are contained in no connecting walk. From Property 4, CW j G,G (d) * ⊂ R * j for all j ∈ {0, . . . , n} \ {i}. Since all cells of a removal kernel are disjoint (Definition 15) and d ∈ R * i , d may only belong to some i-connecting walks, hence property ii). Now, let us suppose that there exists two darts a and b such that:

• CW i G,G (a) = (a 0 = a, a 1 , . . . , a p ) and d = a k for 0 < k ≤ p; • CW i G,G (b) = (b 0 = b, b 1 , . . . , b q ) and d = b h for 0 < h ≤ q.
Thus, by Definition 22 we have

d = a(α i α i+1 ) k and d = b(α i α i+1 ) h . If a = b, it
is clear that k = h and we may suppose without loss of generality that h < k.

Then, from a(α i α i+1 ) k = b(α i α i+1 ) h we deduce that a(α i α i+1 ) k-h = b Note that 0 < k -h < k, so by Property 4 we have a(α i α i+1 ) k-h ∈ R * i . This contradicts the fact that b ∈ D . It follows that a = b. 2
The following property establishes a one-to-one correspondence between connecting walks, as any i-connecting walk, associated with a dart d ∈ D , may be built from the connecting walk associated with dα i (with the notations of Definition 16). This is illustrated on Figure 4. In fact, the above mentioned correspondence coincides with the application of an involution; it is therefore itself an involution on the set of connecting walks.

Property 5 Let G be an n-G-map and K r be a removal kernel in

G. Let G = G \ K r = (D , α 0 , . . . , α n ). For i ∈ {0, . . . , n -1}, d ∈ D , and b = dα i ; if CW i G,G (d) = (d 0 = d, d 1 , . . . , d p )
we have:

CW i G,G (b) = (b 0 = b, b 1 , . . . , b p ) where b k = d p-k α i for 0 ≤ k ≤ p
Proof: From the definition of connecting walks, we have:

CW i G,G (d) = d, d(α i α i+1 ), d(α i α i+1 ) 2 , . . . , d(α i α i+1 ) p where p = M in h ∈ N d(α i α i+1 ) h α i ∈ D .
With b = dα i , we have:

CW i G,G (b) = b, b(α i α i+1 ), b(α i α i+1 ) 2 , . . . , b(α i α i+1 ) q where q = M in h ∈ N b(α i α i+1 ) h α i ∈ D .
If p = 0, we have CW i G,G (d) = (d) and b = dα i so we immediately obtain bα i = d, therefore CW i G,G (b) = (b). Thus, we suppose in the sequel that p > 0.

Les us prove by recurrence on k that for 0 ≤ k ≤ p, we have:

b(α i α i+1 ) k α i = d(α i α i+1 ) p-k (1)
From Definition 22, we have d p α i ∈ D and (by Property 4) for all k ∈ {0, . . . , p -1},

d k = d(α i α i+1 ) k / ∈ D . It follows from the very definition of α i (Item (3) of Definition 16) that d p α i = dα i , i.e. b = d p α i . Since d p = d(α i α i+1 ) p we obtain b = d(α i α i+1 ) p α i which is (1) for k = 0.
Now, suppose that (1) holds for k < p, we have:

b(α i α i+1 ) k α i = d(α i α i+1 ) p-k b(α i α i+1 ) k α i α i+1 α i = d(α i α i+1 ) p-k α i+1 α i b(α i α i+1 ) k+1 α i = d(α i α i+1 ) p-(k+1)
The latter equality is precisely (1) for k + 1.

Since p > 0, from Property 4 we know that for all k ∈ {0, . . . , p -1}, d(α i α i+1 ) p-k / ∈ D which by (1) means that b(α i α i+1 ) k α i / ∈ D . Furthermore, and again from (1) with k = p, we obtain d = b(α i α i+1 ) p α i so that b(α i α i+1 ) p α i ∈ D (since d ∈ D ). It follows that p is the smallest integer such that b(α i α i+1 ) p α i ∈ D . This shows that q = p and by (1) that b k = d p-k α i for all k ∈ {0, . . . , p}. 2

Additional properties

In Section 5, which is dedicated to the notion of a pyramid of G-maps or maps, we will use the following notion of a Since Property 9 does not guarantee that a dart always belong to a connecting walk, all darts that have been removed may not be traversed by following all the connecting walks. Hence, we define the notion of a simple removal kernel which allows us to state

Definition 23 A removal kernel K r is called simple if ∀i ∈ {0, . . . , n -1}, ∀d ∈ R i , ∃s ∈ D d ∈ CW i G,G (s) *
(Note that by Proposition 9 the dart s is necessarily unique.)

We derive the following property after the suppression of a simple removal kernel from an n-G-map.

Property 6 If G is an n-G-map and K r is a simple removal kernel in G, then we have:

D = D   d∈D , 0≤i≤n-1 CW i G,G (d) *   (2)
where denotes the union of disjoint sets.

Proof:

As a consequence of Proposition 9, CW i G,G (d 1 ) * ∩ CW j G,G (d 2 ) * = ∅ when either d 1 = d 2 or i = j.
Thus, the union within the brackets in ( 2) is indeed a union of disjoint sets; and the leftmost comes from the fact that

CW i G,G (d) * ⊂ R = D \ D .
The ⊃ part is immediate, so we only need to prove the ⊂ part of equality ( 2 When Property 6 applies, the traversal of the connecting walks of all the darts of D is guaranteed to visit all darts of D. In a pyramid, this means that a level may be rebuilt with no hole from the level above it; in other words there is no loss of information when reducing a map using a simple kernel.

Note that the removed vertex in Figure 5(a) constitutes a simple removal kernel, whereas the one made of the two edges in Figure 5(b) does not. As a preliminary remark, we may observe that the edge resulting from the removal of vertex v in Figure 5(b) is a simple removal kernel by itself, thus that the removal of the two edges depicted in this figure may be achieved after the suppression of two simple removal kernels. In fact, not all removal kernel may be decomposed into simple ones. However, using Proposition 10 (below) some removal operations may be delayed in order to obtain a simple kernel between two specified levels. Indeed, simple removal kernels may be characterized, in a computationally more efficient way, using Proposition 10. The proof of this proposition will use the following Lemma.

Lemma 1 Let G = (D, α 0 , . . . , α n ) be an n-G-map, K r be a removal kernel in G, and D be the set of darts of

G \ K r . Let i ∈ {0, . . . , n -1}. If a sequence of darts S = (d 0 , d 1 , . . . , d k ), k ∈ N * , satisfies i) d 0 ∈ D , ii) ∀h ∈ {0, . . . , k}, d h = d 0 (α i α i+1 ) h , iii) ∀h ∈ {1, . . . , k}, d h / ∈ D , iv) d k ∈ R i .
then, the two following properties are also satisfied:

(a) ∀h ∈ {1, . . . , k} we have d h ∈ R i , (b) ∀h ∈ {0, . . . , k -1} we have d h α i ∈ R i .
Proof: We prove this lemma by recurrence on the "length" k of the sequence (d 0 , . . . , d k ). For k = 1 the sequence is (d

0 , d 1 = d 0 α i α i+1 ). Item iv) is d 1 ∈ R i , hence (
a). Now, we note that d 1 and d 1 α i+1 belong to the the same i-cell of G. Since d 1 α i+1 = d 0 α i α i+1 α i+1 = d 0 α i , we thus deduce that d 0 α i also belongs to R i , hence (b). Therefore, the property is valid for any sequence (d 0 , d 1 ), i.e. for k = 1. Now, we assume that the lemma is valid for a sequence (d 0 , . . . , d k ), for a given k > 0, and we consider a sequence S which satisfies items i) to iv). S = (d 0 , d 1 , . . . , d k , d k+1 ) Since d k+1 ∈ R i , and because d k+1 and d k+1 α i+1 belong to the same i-cell of G, we obtain that d k+1 α i+1 = d k α i α i+1 α i+1 = d k α i also belongs to R i . This makes (b) valid in S for h = k + 1. Now, by item iii), we have d k ∈ R. Let us suppose that d k ∈ R j with j = i. In this case, d k and d k α i belong to the same j-cell of R j . However, d k α i cannot belong to both an i-cell of R i , which has been proved to be true, and a j-cell of R j (Definition 15 of a removal kernel). It follows that d k ∈ R i which is (a) for h = k. Now, if d k ∈ R i we obtain that the subsequence S = (d 0 , . . . , d k ) of S is a sequence which satisfies all the conditions of the lemma. Indeed, beside item iv) which is precisely d k ∈ R i , items i) to iii) are true for S , as a subsequence of S . By the recurrence hypothesis, the lemma may be applied to S and we obtain:

• ∀h ∈ {1, . . . , k} we have d h ∈ R i , • ∀h ∈ {0, . . . , k -1} we have d h α i ∈ R i .
Since we have d k+1 ∈ R i and we also proved that d k α i ∈ R i , we deduce that properties (a) and (b) are both valid for the the sequence S , and the lemma holds with k + 1. 2

Proposition 10 A removal kernel K r = {R i } i=0,...,n in an n-G-map G is simple if and only if: ∀i ∈ {0, . . . , n -1}, ∀d ∈ R * i , < α i α i+1 >(d) ∩ D = ∅ ( 3
)
where D is the set of darts of G \ K r .

Proof: (⇐) Since α i α i+1 is a permutation, for all d ∈ R * there exists p ∈ N such that

< α i α i+1 >(d) = {d, d(α i α i+1 ), d(α i α i+1 ) 2 , . . . , d(α i α i+1 ) p } with d(α i α i+1 ) p+1 = d.
By (3), < α i α i+1 >(d) contains at least one dart of D , so p > 0 (since d / ∈ D ) and d(α i α i+1 ) h ∈ D for at least one h ∈ {1, . . . , p}. Let k be the greatest such integer h, and let us denote b k = d(α i α i+1 ) k . Thus we may consider the sequence:

d(α i α i+1 ) k , d(α i α i+1 ) k+1 , . . . , d(α i α i+1 ) k+(p-k) , d(α i α i+1 ) k+(p-k)+1
where

• b k = d(α i α i+1 ) k ∈ D , • d(α i α i+1 ) k+1 , . . . , d(α i α i+1 ) k+(p-k) , d(α i α i+1 ) k+(p-k)+1 = d ⊂ R * , • d(α i α i+1 ) k+(p-k)+1 = d ∈ R * i (by hypothesis).
By Lemma 1, we deduce that

(a) d(α i α i+1 ) k+h+1 ∈ R * i for all h ∈ {0, . . . , (p -k)}, and (b) d(α i α i+1 ) k+l α i ∈ R * i , for all l ∈ {0, . . . , (p -k) -1}.

From (b) and the very definition of the connecting walk CW

i G,G (b k ), it follows that d(α i α i+1 ) k+h+1 ∈ CW i G,G (b k ) * for all h ∈ {0, . . . , (p -k)}. In particular, d(α i α i+1 ) k+(p-k)+1 = d ∈ CW i G,G (b k ) * .
(⇒) Suppose that the removal kernel K r is simple, and let d be a dart of R * i for i ∈ {0, . . . , n -1}. From Definition 23, there exists s ∈ D such that

d ∈ CW i G,G (s) * . It follows that d = s(α i α i+1 ) k for k ∈ N * 2

In combinatorial maps

Definition 24 (Connecting walk in n-maps) Let M = (D, γ 0 , . . . , γ n-1 ) be an n-map and K r = {R i } 0≤i≤n be a removal kernel in M . Let M = M \ K r = (D , γ 0 , . . . , γ n-1 ). The i-connecting walk associated to a dart d ∈ D for i ∈ {0, . . . , n -1}, denoted by CW i M,M (d), is the sequence of darts of D defined by

CW i M,M (d) = (d 0 , d 1 , . . . , d p ) with p = M in k ∈ N d k γ i ∈ D
where

• For i ∈ {0, . . . , n -2}, ∀u, 0 ≤ u ≤ p, d u = d(γ i γ -1 i+1 ) u • For i = n -1, ∀u, 0 ≤ u ≤ p, d u = dγ u n-1
Property 7 With the notations of Definition 24, for all d ∈ D such that

CW i M,M (d) = (d 0 , d 1 , . . . , d p ) we have: ∀k ∈ {1, . . . , p}, d k-1 γ i ∈ R * i and d k ∈ R * i Proof: • (If i < n -1)
We prove the property by recurrence on k. From the definition of connecting walks, we know that if p ≥ 1 we have since d k γ i and d k γ i γ i = d k belong to the same j-cell, we would obtain that d k belongs to both an i-cell and a j-cell of the removal kernel K r , which is not allowed by Definition 15. Therefore, we have

d 0 γ i / ∈ D (i.e. d 0 γ i ∈ R * ). Suppose that d 0 γ i ∈ R j for j = i, in other words that d 0 γ i ∈< γj >(d ) for some d ∈ R * j . Since i = j we have d 0 = d 0 γ i γ i ∈< γj >(d ) ∈ R j , which contradicts the fact that d 0 ∈ D ; therefore d 0 γ i ∈ R * i . Since d 0 γ i and d 0 γ i γ -1 i+1 belong to the same i-cell, we also obtain d 1 = d 0 γ i γ -1 i+1 ∈ R i . Eventually, the property is true for k = 1. Now, suppose that d k ∈ R * i for k < p. Since k < p and p is the smallest integer such that d p γ i ∈ D , then d k γ i ∈ R * . If we suppose that d k γ i ∈ R j with j = i,
d k γ i = d (k+1)-1 γ i ∈ R i . Again, since d k γ i and d k γ i γ i+1 belong to the same i-cell we also have d k γ i γ i+1 = d k+1 ∈ R * i .
Thus, the property is true for k + 1.

• (If i = n -1)
We prove the property by recurrence on k. From the definition of connecting walks, we know that if p ≥ 1 we have

d 0 γ n-1 / ∈ D (i.e. d 0 γ n-1 ∈ R * ). Suppose that d 0 γ n-1 ∈ R j for j = n -1, in other words that d 0 γ n-1 ∈< γj >(d ) for some d ∈ R * j . Since j = n -1 we have d 0 = d 0 γ n-1 γ -1 n-1 ∈< γj > (d ) ∈ R j , which contradicts the fact that d 0 ∈ D ; therefore d 1 = d 0 γ n-1 ∈ R * n-1 .
Eventually, the property is true for k = 1. Now, suppose that d k ∈ R * n-1 for k < p. Since k < p and p is the smallest integer such that

d p γ n-1 ∈ D , then d k γ n-1 ∈ R * . If we suppose that d k γ n-1 ∈ R j with j = n -1, since d k γ n-1 and d k γ n-1 γ -1
n-1 = d k belong to the same j-cell, we would obtain that d k belongs to both an (n -1)-cell and a j-cell of the removal kernel K r , which is not allowed by Definition 15. Therefore, we have

d k γ n-1 = d (k+1)-1 γ n-1 ∈ R n-1 .
Thus, the property is true for k + 1. 2

As for G-map, connecting walks within maps also provide a father-child relationship, as stated by the following proposition:

Proposition 11 Let M = (D, γ 0 , . . . , γ n-1 ) be an n-map, K r be a removal kernel in M , and d be a dart of R * i for 0 ≤ i < n. The dart d belongs to at most one connecting walk. In other words, the two following properties hold:

i) d ∈ b∈D CW i M,M \K r (b) * ⇒ ∃! b ∈ D , d ∈ CW i M,M \K r (b) * ii) ∀j ∈ {0, . . . , n} \ {i}, ∀b ∈ D , d / ∈ CW j M,M \K r (b) *
Where b∈D CW i M,M \K r (b) * represents the set of darts belonging to at least one connecting walk.

Proof: First note that Figure 6(a) shows an example of a removal kernel for which some darts are contained in no connecting walk. From Property 7, CW j M,M (d) * ⊂ R * j for all j ∈ {0, . . . , n} \ {i}. Since all cells of a removal kernel are disjoint (Definition 15) and d ∈ R * i , d may only belong to some i-connecting walks, hence property ii). Now, let us suppose that there exists two darts a and b, with a = b, such that:

• CW i M,M (a) = (a 0 = a, a 1 , . . . , a p ) and d = a k for 0 < k ≤ p; • CW i M,M (b) = (b 0 = b, b 1 , . . . , b q ) and d = b h for 0 < h ≤ q.
-If i < n-1, by Definition 24 we have

d = a(γ i γ -1 i+1 ) k and d = b(γ i γ -1 i+1 ) h . Since a = b, if a(γ i γ -1 i+1 ) k = b(γ i γ -1 i+1
) h we necessarily have k = h (the composition of permutations being a one-to-one map). We may then suppose without loss of generality that h < k. Then, from Using Property 4, it is clear from Definition 16 that we also have the following property, which relates i-connecting walks to the corresponding involution α i in the resulting map.

a(γ i γ -1 i+1 ) k = b(γ i γ -1 i+1 ) h we deduce that a(γ i γ -1 i+1 ) k-h = b Note that 0 < k -h < k, so by Property 7 applied to CW M,M (a) we have a(γ i γ -1 i+1 ) k-h ∈ R * i .
Property 8 Let M = (D, γ 0 , . . . , γ n-1 ) be an n-map, K r be a removal kernel in M , M = M \ K r = (D , γ 0 , . . . , γ n-1 ) and d ∈ D . For all i ∈ {0, . . . , n} we have:

dγ i = last(CW i M,M \K r (d))γ i
Proof: This result is a direct consequence of the definition of a connecting walk (Definition 24), considering Property 7. 2

As for G-maps, the following property establishes a one-to-one correspondence between connecting walks, as any i-connecting walk (i < n-1) associated with a dart d ∈ D , may be built from the connecting walk associated with dγ i (with the notations of Definition 17).

Lemma 2 If M = (D, γ 0 , . . . , γ n- 1) is an n-map and d is a dart of a regular (n -2)-cell C with local degree 2, then dγ n-1 = dγ -1 n-1 .

Proof: Since C is a regular cell, from Definition 13 we have:

dγ -1 n-1 = dγ n-1 or dγ -1 n-1 / ∈< γn-2 , γn-1 >(dγ n-1 )
Let us suppose that dγ

-1 n-1 / ∈< γn-2 , γn-1 > (dγ n-1 ), which implies that < γn-2 , γn-1 > (dγ n-1 )∩ < γn-2 , γ-1 n-1 > (dγ n-1 ) = ∅. By property b) of Defini- tion 13, we also have {dγ n-1 , dγ -1 n-1 }∩ < γn-2 , γn-1 >(d) = ∅.
It follows that the three sets < γn-2 , γn-1 >(d), < γn-2 , γn-1 >(dγ n-1 ), and < γn-2 , γn-1 >(dγ -1 n-1 ) are disjoint sets. Since dγ n-1 and dγ -1 n-1 both belong to C (as n -

1 = n -2), we conclude that < γn-1 , γn-1 >(b) b ∈ C ≥ 3
which contradicts the fact that C has local degree 2 (Definition 12).

Therefore we necessarily have dγ

-1 n-1 = dγ n-1 . 2
As we claimed in our introduction, generalized maps do not allow to manipulate easily notions related with the orientation over the underlying quasimanifold, when the latter is orientable. This in due, in part, to the fact that in this case a G-map, by using twice as many darts as really needed, actually encodes the two possible orientations at the same time. A connecting walk in a G-map G, as defined in this paper, uses a fixed orientation by skipping darts. Indeed, all darts of the walk thus belong to a single connected component of the map of the hypervolumes HV (G) associated to the G-map G (Definition 5). It is therefore consistent with respect to the orientation property since each component of HV (G) corresponds to one orientation of G. These remarks are based on Proposition 13, for which Proposition 12 is an intermediary result.

Proposition 12 With the notations of Definition 24, for all d ∈ D and

i ∈ {0, . . . , n -2}, if CW i M,M (d) = (d 0 , d 1 , . . . , d p ) we have: ∀r ∈ {0, . . . , p}, d r = d 0 (γ i γ i+1 ) r Proof: If i < n -2, γ i+1 is an involution so that dγ i+1 = dγ -1
i+1 for all b ∈ D. The proposition is then straightforward following Definition 24.

If i = n -2, for all r ∈ {0, . . . , p -1} in Definition 24, by Property 7 we have

d r γ n-2 ∈ R * n-2 .
Therefore, from the very definition of a removal kernel d r γ n-2 belongs to a regular (n -2)-cell with local degree 2 so that, by Lemma 2,

d r (γ n-2 γ -1 n-1 ) = d r (γ n-2 γ n-1 ). 2
As shown by the the next property also based on Proposition 12, an involution may also be defined on the set of i-connecting walks in a map, for i < n -1.

Property 9 Let M be an n-map and K r be a removal kernel in

M . Let M = M \ K r = (D , γ 0 , . . . , γ n-1 ). For i ∈ {0, . . . , n -2}, d ∈ D , and b = dγ i ; if CW i M,M (d) = (d 0 = d, d 1 , . . . , d p )
we have:

CW i M,M (b) = (b 0 = b, b 1 , . . . , b p ) where b k = d p-k γ i for 0 ≤ k ≤ p
Proof: From the definition of connecting walks for i < n -1, we have:

CW i M,M (d) = d, d(γ i α -1 i+1 ), d(γ i γ -1 i+1 ) 2 , . . . , d(γ i γ -1 i+1 ) p where p = M in h ∈ N d(γ i γ -1 i+1 ) h γ i ∈ D .
With b = dγ i , we have:

CW i M,M (b) = b, b(γ i γ -1 i+1 ), b(γ i γ -1 i+1 ) 2 , . . . , b(γ i γ -1 i+1 ) q where q = M in h ∈ N b(γ i γ -1 i+1 ) h γ i ∈ D .
If p = 0, we have CW i M,M (d) = (d) and b = dγ i so we immediately obtain bγ i = d, therefore CW i M,M (b) = (b). Thus, we suppose in the sequel that p > 0.

Les us prove by recurrence on k that for 0 ≤ k ≤ p, we have:

b(γ i γ i+1 ) k γ i = d(γ i γ i+1 ) p-k (4)
From Definition 24, we have d p γ i ∈ D and (by Property 7) for all k ∈ {0, . . . , p -1},

d k = d(γ i γ -1 i+1 ) k / ∈ D . It follows from the very definition of γ i (Definition 17) that d p γ i = dγ i , i.e. b = d p γ i . Since d p = d(γ i γ -1 i+1 ) p we obtain b = d(γ i γ -1 i+1 ) p γ i which is (4) for k = 0.
Now, suppose that (4) holds for k < p, we have:

b(γ i γ -1 i+1 ) k γ i = d(γ i γ -1 i+1 ) p-k b(γ i γ i+1 ) k γ i = d(γ i γ -1 i+1 ) p-k (by Proposition 12) b(γ i γ i+1 ) k γ i γ i+1 γ i = d(γ i γ -1 i+1 ) p-k γ i+1 γ i b(γ i γ i+1 ) k+1 γ i = d(γ i γ -1 i+1 ) p-(k+1) (i < n -1 ⇒ γ 2 i = 1 D )
The latter equality is precisely (4) for k + 1.

Since p > 0, from Property 7 we know that for all k ∈ {0, . . . , p -1},

d(γ i γ -1 i+1 ) p-k / ∈ D which by (4) means that b(γ i γ -1 i+1 ) k γ i / ∈ D .
Furthermore, and again from (4) with k = p, we obtain

d = b(γ i γ -1 i+1 ) p γ i so that b(γ i γ -1 i+1 ) p γ i ∈ D (since d ∈ D ). It follows that p is the smallest integer such that b(γ i γ -1 i+1 ) p γ i ∈ D .
This shows that q = p and by ( 4) that b k = d p-k γ i for all k ∈ {0, . . . , p}. 2 Proposition 13 Let G = (D, α 0 , . . . , α n ) be an n-G-map and M = HV (G) be its n-map of the hypervolumes. Let K r be a removal kernel in G, let G = G\K r and M = M \ HV (K r ) = (D , γ 0 , . . . , γ n-1 ). The i-connecting walks of d respectively in G and M (with respect to K r and HV (K r )) satisfy

∀d ∈ D, ∀i ∈ {0, . . . , n -2}, CW i G,G (d) = CW i M,M (d)
Furthermore, we have:

∀d ∈ D, CW (n-1) G,G (d) = reverse(CW (n-1) M,M (dγ -1 n-1 ) )
A first part of the proof of this proposition is achieved through the two following lemmas.

Lemma 3 With the notation of Proposition 13 we have:

∀d ∈ D , CW n-2 G,G (d) = CW n-2 M,M (d)
Proof: Let d ∈ D and HV (K r ) = {R i } following Definition 18; we have:

CW n-2 M,M (d) = (d, d(γ n-2 γ -1 n-1 ), . . . , d(γ n-2 γ -1 n-2 ) p ) where d(γ n-2 γ -1 n-1 ) p γ n-2 ∈ D , and for all k ∈ {1, . . . , p}, d(γ n-2 γ -1 n-1 ) k-1 γ n-2 ∈ R n-2 and d(γ n-2 γ -1 n-1 ) k ∈ R n-2 (Property 7
). In the sequel, we denote

d 0 = d and d k = d(γ n-2 γ n-1 ) k . By Proposition 12, we have CW n-2 M,M (d) = (d, d(γ n-2 γ n-1 ), . . . , d(γ n-2 γ n-1
) p ) and from the definition of the map of the hypervolumes M we may write:

CW n-2 M,M (d) = (d, d(α n α n-2 α n α n-1 ), . . . , d(α n α n-2 α n α n-1 ) p ) = (d, d(α n-2 α n α n α n-1 ), . . . , d(α n-2 α n α n α n-1 ) p ) = (d, d(α n-2 α n-1 ), . . . , d(α n-2 α n-1 ) p )
In other words, we have

d k = d(α n-2 α n-1 ) k = d k-1 (α n-2 α n-1 ) for k ∈ {1, . . . , p}.
From Definition 18 and for all k ∈ {1, . . . , p},

if d k-1 γ n-2 ∈ R * n-2 there ex- ists b ∈ R * n-2 such that d k-1 γ n-2 ∈< α n α 0 , . . . , α n α n-2 , α n α n-1 > (b). Since < α n α 0 , . . . , α n α n-2 , α n α n-1 > (b) ⊂< αn-2 > (b), we deduce that the darts d k-1 γ n-2 and b belong to the same (n -2)-cell, thus d k-1 γ n-2 ∈ R * n-2 .
We may prove in a similar way that d k ∈ R * n-2 . Eventually, we have:

∀k ∈ {1, . . . , p}, d k-1 γ n-2 ∈ R * n-2 and d k ∈ R * n-2 (5)
So far, we have proved that

d k = d(α n-2 α n-1 ) k ∈ R * n-2 for all k ∈ {1, . . . , p} and d k (α n α n-2 ) ∈ R * n-2 for all k ∈ {0, . . . , p-1}. We now prove that d k α n-2 ∈ R *
n-2 for all k ∈ {0, . . . , p-1}. Indeed, from the conditions on the involutions of a G-map, we have

d k α n α n-2 = d k α n-2 α n . Since d k α n-2 α n and d k α n-2 α n α n = d k α n-2 belong to the same (n -2)-cell, from d k (α n α n-2 ) ∈ R * n-2 we deduce that d k α n-2 ∈ R * n-2 .
We also have

d p γ n-2 = d p α n α n-2 = d p α n-2 α n ∈ D .
CW (n-1) G,G (d) = reverse(CW (n-1)
M,M (dγ -1 n-1 ) )

Proof: Following Definition 22 and the one of the map of the hypervolumes M we have: CW

(n-1) G,G (d) = (d, dα n-1 α n , . . . , d(α n-1 α n ) p ) (6) where p is the smallest integer such that d(α n-1 α n ) p α n-1 ∈ D . Following Remark 2 we deduce that d(α n-1 α n ) p α n-1 α n = d(α n-1 α n ) p+1 = d(γ -1
n-1 ) p+1 ∈ D . Furthermore, from the definition of connecting walks in G-maps we have

d(α n-1 α n ) k α n-1 /
∈ D , for k < p and from Property 4 we also know that

d(α n-1 α n ) k = dγ -k n-1 / ∈ D , for k ∈ {1, . . . , p}. It follows from the definition of cells removal in n-maps (Definition 17) that d(α n-1 α n ) p+1 = d(γ -1 n-1 ) p+1 = dγ -1 n-1 .
Now, for h ∈ {1, . . . , p}, we obtain:

dγ -1 n-1 (α n α n-1 ) h = d(α n-1 α n ) p+1 (α n α n-1 ) h = d(α n-1 α n ) p+1-h
where 0 < p + 1 -h ≤ p, so that dγ -1 n-1 (α n α n-1 ) h / ∈ D ((6) and Property 4). On the other hand, dγ -1 n-1 (α n α n-1 ) p+1 = d ∈ D , therefore from the definition of CW n-1 M,M (dγ -1 n-1 ) we have:

CW n-1 M,M (dγ -1 n-1 ) = (dγ -1 n-1 , dγ -1 n-1 (α n α n-1 ), . . . , dγ -1 n-1 (α n α n-1 ) p ) (7) = (dγ -1 n-1 , d(α n-1 α n ) p , . . . , d(α n-1 α n )) (8)
The result comes from ( 6) and ( 8). 2

Proof of Proposition 13:

If i < n -2: CW i M,M (d) = (d, d(γ i γ -1 i+1 ), . . . , d(γ i γ -1 i+1 ) p ) = (d, d(α n α i α i+1 α n ), . . . , d(α n α i α i+1 α n ) p ) = (d, d(α i α n α n α i+1 ), . . . , d(α i α n α n α i+1 ) p ) = (d, d(α i α i+1 ), . . . , d(α i α i+1 ) p )
The cases i = n -2 and i = n -1 are respectively given by Lemma 3 and Lemma 4. 2

Pyramids of maps

In this section we define pyramids of combinatorial n-maps and introduce the connecting dart sequences which will be used to derive a concise encoding of pyramids.

Definition

Definition 25 (Pyramid of n-maps) A pyramid of n-maps with height h is an h-tuple (M 0 , K 1 , . . . , K h ) where M 0 is an n-map and K l , l ∈ {1, . . . , h} is a removal kernel for the map M l-1 , which is defined by M l = M l-1 \ K l for l ∈ {1, . . . , h}.

Notation 7 When dealing with a pyramid of n-maps (M 0 , K 1 , . . . , K h ), h ∈ N * , we usually denote M l = (D l , γ l,0 , . . . , γ l,n-1 ), 0 ≤ l ≤ h, and when no confusion may arise we simply refer to a permutation of M l as γ l,i for i ∈ {0, . . . , n} without mentioning the map M l . We also shorten γ 0,i as γ i for all i ∈ {0, . . . , n -1}. Eventually, we denote K l = {R l,i } i=1,...,n .

Connecting dart sequences

We may now give the definition of a connected dart sequence which makes the link, as shown by two propositions given further on, between any tow levels of a pyramid the same way a connecting walk does between two consecutive levels.

Definition and properties

Definition 26 (Connecting dart sequence) Let (M 0 , K 1 , . . . , K h ) be a pyramid of n-maps and d be a dart of D l for l ∈ {0, . . . , h}. ,d p ) for i ∈ {0, . . . , n-1}, we define the i-connecting dart sequence associated to d at level l, denoted by CDS i l (d), as follows:

If CW i M l-1 ,M l (d) = (d = d 0 , . . .
• For l = 0, CDS i 0 (d) = (d), and • for l ∈ {1, . . . , h}

• If i ≤ n -2, CDS i l (d) = GL i l-1 (d 0 ) • GL i l-1 (d 1 ) • . . . • GL i l-1 (d p ) where:      ∀r ∈ {0, . . . , p -1}, GL i l-1 (d r ) = CDS i l-1 (d r ) • CDS i+1 l-1 (d r γ l-1,i ) GL i l-1 (d p ) = CDS i l-1 (d p ) • If i = n -1, CDS n-1 l (d) = CDS n-1 l-1 (d 0 ) • CDS n-1 l-1 (d 1 ) • . . . • CDS n-1 l-1 (d p ).
Notation 8 Given a pyramid of n-maps (M 0 , K 1 , . . . , K h ), h ∈ N, we may define a set of removed darts at level k, 1 ≤ k ≤ h, denoted K * 0...k , as follows:

K * 0...k = l=0,...,k R∈K l R *
The above unions are disjoint because of the very definition of the removal kernels K l , 1 ≤ l ≤ h and the fact that cells of a removal kernel are disjoint.

Note that we trivially have CDS i 1 (d) = CW M 0 ,M 1 (d) for any d ∈ D 1 . Connecting dart sequences correspond thus to a natural extension of connecting walks.

The such defined connecting dart sequences also induce a father-child relationship between darts of any two levels in a pyramid, as the transitive closure of the one provided by connecting walks for consecutive levels.

One may obviously not expect the darts of a such defined connecting dart sequence to belong to removed cells of a single dimension, as it is the case for connecting walks (Propositions 4 and 7). For example, darts of the connecting dart sequence CDS 0 2 (b) in Figure 7 belong to both 1-cells and 0-cells which have been removed from M 0 and M 1 , respectively. Still, the first dart of a connecting dart sequence at level l is the only dart belonging to D l . Indeed, we have the following proposition. Proof: We prove the property by recurrence on the level l. For l = 1, it is readily seen that we have CDS i 1 (d) = CW i M 0 ,M 1 (d) and the result holds by Property 7.

Thus, we suppose that the property is valid for l ∈ {1, . . . , h -1}.

-If i ≤ n -2. Following Definition 26:

CDS i l+1 (d) = CDS i l (d 0 ) • CDS i+1 l (d 0 γ l,i ) • . . . . . . • CDS i l (d p-1 ) • CDS i+1 l (d p-1 γ l,i ) • CDS i l (d p )
where (d 0 , . . . , d p ) = CW i M l ,M l+1 (d).

From the recurrence hypothesis, CDS i+1 l (d r γ l,i ) ∩D l = ∅ for all r ∈ {0, . . . , p-1}, and CDS i l (d r ) ∩ D l = ∅, so that CDS i l (d r ) ∩ D l = d r , for all r ∈ {1, . . . , p}. From Property 7, d 0 is the only dart of CW i M l ,M l+1 (d) that belongs to D l+1 . Since it is also the first dart of CDS i l (d 0 ), hence the first dart of CDS i l+1 (d), we eventually obtain CDS

i l+1 (d) ∩ D l = ∅.
The property is thus valid at level l + 1. 2

An iterative definition

In this section, we introduce a non-recursive definition of connecting walks, stated by Proposition 17. Thanks to Proposition 15, this definition allows to retrieve the image of an involution at any level of a pyramid using a traversal of the base level map directed by the knowledge of the level at which a dart disappears and the degree of the corresponding cells that has been removed. These two values (level and degree) are formally described by the membership of a dart to a set AR l,i according to the following notation.

Notation 9 If (M 0 , K 1 , . . . , K h ) is a pyramid of n-maps and l is an integer in {1, . . . , h} and 0 ≤ i ≤ n -1, then we denote

AR l,i = l-1 k=0 R * k,i (10)
where "AR" stands for "aggregated removal set", i.e, the union of the i-cells to be removed from every levels of the pyramid below level l (excluded).

We now state several properties of these sets.

Lemma 7 For all l ∈ {0, . . . , h} and all i, j ∈ {0, . . . , n -1} with i = j, we have AR l,i ∩ AR l,j = ∅.

Proof: We prove this result by a recurrence on l. If l = 1, we have AR

1,i = R * 1,i
and AR 1,j = R * 1,j , therefore the result comes from the very definition of a removal kernel (i.e., cells to be removed are disjoint). We thus suppose that the property holds for l ∈ {1, . . . , h -1}. Following [START_REF] Fourey | A second step toward combinatorial pyramids in nd spaces[END_REF], we have AR l+1

,i = AR l,i ∪ R * l,i and AR l+1,j = AR l,j ∪ R * l,j . It follows that AR l+1,i ∩ AR l+1,j = AR l,i ∪ R * l,i ∩ AR l,j ∪ R * l,j
By [START_REF] Fourey | A second step toward combinatorial pyramids in nd spaces[END_REF] we also deduce that R * l,i ∩AR l,j = ∅ since R * l,i ⊂ D l and AR l,j ∩D l = ∅. Similarly, we have AR l,i ∩ R * l,j = ∅. Furthermore, from the very definition of a removal kernel we know that R * l,i ∩ R * l,j = ∅. Eventually, from the recurrence hypothesis we have AR l,i ∩AR l,j = ∅. We thus deduce from the above equation that AR l+1,i ∩ AR l+1,j = ∅, hence the property is valid at level l + 1. 2

We now prove several useful lemmas which [. . . ] Lemma 8 Let (M 0 , K 1 , . . . , K h ) be a pyramid of n-maps for h ∈ N * and let

d 1 , d 2 be two darts of D l , 0 ≤ l ≤ h. If d 1 γ i = d 2 for i ∈ {0, . . . , n -1}, then d 1 γ l,i = d 2 .
Proof: This may be proved by a simple recurrence on k, 0 ≤ k ≤ l, using the very definition of cells removal in an n-map (Definition 17).

Let d 1 , d 2 ∈ D l and i ∈ {0, . . . , n -1} be such that d 1 γ i = d 2 . Using the notation introduced before (Notation 7), this may be written d 1 γ 0,i = d 2 , hence the property is valid for k = 0.

Now we suppose that

d 1 γ k,i = d 2 for k ∈ {0, . . . , l -1}. As d 2 = d 1 γ k,i belongs to D l , it necessarily belongs to D k+1 since k < l. It follows from Definition 17 that d 1 γ k+1 = d 1 γ k , i.e. d 1 γ k+1 = d 2 .
The property is thus satisfied at level k + 1; it is therefore true for all k ∈ {0, . . . , l} and in particular for l. We obtain

d 1 γ l,i = d 2 . 2 Lemma 9 Let (M 0 , K 1 , . . . , K h ) be a pyramid of n-maps for h ∈ N * and d be a dart of D l . If dγ j / ∈ D l for j ∈ {0, . . . , n -1} then dγ j ∈ AR l,j . Proof: If dγ j / ∈ D l then dγ j ∈ R u,k for u ∈ {0, . . . , l-1} and k ∈ {0, . . . , n-1}. Since d ∈ D l ⊂ D u
and dγ j ∈ D u , from Lemma 8 we deduce that dγ j = dγ u,j . If we suppose that k = j, as k < n we obtain that d and dγ u,j belong to the same k-cell of R u ; a contradiction with the fact that d ∈ D l (l > u). Necessarily, we have k = j and therefore dγ j ∈ AR l,j . 2 Lemma 10 Let (M 0 , K 1 , . . . , K h ) be a pyramid of n-maps for h ∈ N * and d be a dart of D 0 , such that d ∈ AR l,i for l ∈ {1, . . . , h} and i ∈ {0, . . . , n -1}. If dγ j ∈ AR l,k for j ∈ {0, . . . , n -1} \ {i} and k ∈ {0, . . . , n -1}, then either k = i or k = j.

Proof: We prove this result by recurrence on the level l.

If l = 1, we have AR 1,i = R * 0,i and AR l,k = R * 0,k . If d ∈ R * 0,i and dγ j ∈ R * 0,k
with i = j, since d and dγ j = dγ 0,j belong the the same i-cell of M 0 (j < n), we necessarily have k = i. Otherwise, dγ j would belong to two cells to be removed at level 0, which is not allowed by the definition of a removal kernel. If i = j and dγ i / ∈ D 1 then dγ i ∈ R 0,k for some k ∈ {0, . . . , n -1}. Let us suppose that k = i, since R 0,n = ∅ it follows that d and dγ i belong to the same k-cell of R 0,k . Again, this would mean that d belongs to both and i-cell of R * 0,i and a k-cell of R * 0,k , which is not allowed from the definition of the removal kernel K 0 . Therefore k = i, i.e. dγ i ∈ AR 1,i . Hence the property is satisfied when l = 1.

We consider the property as satisfied for l ∈ {1, . . . , h-1} and we prove that it is also satisfied at level l+1. Thus, suppose that d ∈ AR l+1,i and dγ j ∈ AR l+1,k for i, j, k ∈ {0, . . . , n -1} with i = j. We have AR l+1,i = AR l,i ∪ R * l,i and AR l+1,k = AR l,k ∪ R * l,k . Therefore, we may distinguish the following cases:

• If d ∈ AR l,i we have d ∈ R * u,i for some u ∈ {0, . . . , l -1}.

Let us suppose that dγ j ∈ R * l,k . In this case dγ j ∈ D l ⊂ D u . It follows from Lemma 8 that dγ j = dγ u,j . As j = i and i < n we obtain that d and dγ u,j belong to the same i-cell of R u,i , which is a contradiction with the fact that dγ u,j ∈ D l with l > u; hence dγ j / ∈ R * l,k , i.e. dγ j ∈ AR l,k . Eventually, since d ∈ AR l,i and dγ j ∈ AR l,k , by the recurrence hypothesis we immediately have k ∈ {i, j}.

• If d ∈ R *
l,i and dγ j ∈ R * l,k . Since in this case both d and dγ j belong to D l , we deduce from Lemma 8 that dγ j = dγ l,j .

Suppose that k = j. As i = j (i.e. k = i), d and dγ l,j would belong to the same i-cell of R * l,i which contradicts the fact that R * l,i ∩ R * l,k = ∅. Hence k = j. It follows that d and dγ l,j belong to the same k-cell of R * l,k . Therefore, k = i would contradict the fact that K l is a removal kernel since d would belong to both an i-cell and a k-cell to be removed; eventually we necessarily have k = i.

• If d ∈ R *
l,i and dγ j ∈ AR l,k , we have dγ j ∈ R * u,k for u ∈ {0, . . . , l -1}. Since d ∈ R * l,i , in particular d ∈ D v for all v ∈ {0, . . . , l} so that d ∈ D u . Thus, as d and dγ j both belong to D u , by Lemma 8 we obtain dγ j = dγ u,j . Now, suppose that j = k. We deduce that d and dγ u,j belong to the same k-cell of K u . In other words, d is to be removed from M u , which is a constradiction with the fact that d ∈ D l with l > u. Hence, we necessarily have k = j.

We conclude that the property is valid at level l + 1, and therefore for all l ∈ {1, . . . , h}. 2 Proposition 16 Let (M 0 , K 1 , . . . , K h ) be a pyramid of n-maps for h ∈ N * with M 0 = (D, γ 0 , . . . , γ n-1 ). If d is a dart of M l , with 1 ≤ l ≤ h, we have: Proof: We prove the property by recurrence on l. If l = 0 we have CDS n-1 l (d) = (d) and there is nothing to be proved. Thus, we suppose that the property holds for l ∈ {0, . . . , h -1}. applied to CDS i l (d). Thus, we suppose in the following that q > 0, which by Lemma 5 implies p > 0.

From Definition 26, the first sequence of darts defining CDS i l+1 (d) is CDS i l (d).

• If CDS i l (d) contains more than one dart, then its second dart is precisely d 1 , which by the recurrence hypothesis belongs to AR l,i ⊂ AR l+1,i .

• If CDS i l (d) = (d), then following Definition 26 d 1 is the second dart of CW M l ,M l+1 (d). From Property 7 of the latter connecting walk we obtain d 1 ∈ R * l,i ⊂ AR l+1,i .

On the other hand, still following Definition 26, the last sequence of darts defining CDS i l+1 (d) is CDS i l (d q ).

• If CDS i l (d q ) = (d q ), then from Property 7 of CW i M l ,M l+1 (d), since q > 0, we have d q ∈ R * l,i ⊂ AR l+1,i . As d q = d p in this case, we obtain d p ∈ AR l+1,i . • Otherwise, CDS i l (d q ) counts more that one dart and by the recurrence hypothesis its last dart belongs to AR l,i , and therefore to AR l+1,i since AR l,i ⊂ AR l+1,i . Furthermore, it is also the last dart of CDS i l+1 (d), i.e. d p . We obtain d p ∈ AR l+1,i .

In both cases, we thus have d 1 ∈ AR l+1,i . Eventually, the property is valid for l + 1, and therefore satisfied for all l ∈ {0, . . . , h}. 2 Proposition 17 Let (M 0 , K 1 , . . . , K h ) be a pyramid of n-maps for h ∈ N * with M 0 = (D, γ 0 , . . . , γ n-1 ). If CDS i l (d) = (d 0 = d, d 1 , . . . , d p ), p ∈ N * , is the i-connecting dart sequence associated to a dart d of M l , with 1 ≤ l ≤ h and 0 ≤ i ≤ n; then for all u ∈ {0, . . . , p-1} we have d u+1 = d u γ tu where t u , which is called the involution subscript associated with d u in CDS i l (d), is defined as follows:

• t 0 = i • For all u ∈ {1, . . . , p -1}

t u =              t u-1 + 1 if t u-1 < n -1 and d u ∈ AR l,t u-1 t u-1 if t u-1 = n -1 and d u ∈ AR l,t u-1 t u-1 -1 if d u ∈ AR l,t u-1 -1 ( 12
)
Moreover t p-1 = n -1 if i = n -1, otherwise t p-1 = i + 1. (Note that p = 0 implies that p > 1 by Lemma 6.)

Proof: If i = n -1, from Proposition 16 we know that d u ∈ AR l+1,n-1 for all u ∈ {0, . . . , p}, and d u+1 = d u γ n-1 for all u ∈ {0, . . . , p -1}. It is therefore readily seen that the proposition holds since, in particular, only the second The next step of this work consists in the definition of an implicit encoding of n-dimensional combinatorial pyramids (see [START_REF] Brun | Implicit encoding of combinatorial pyramids[END_REF]), based on the notion of a connecting dart sequence and Proposition 15, which yields a mean to retrieve the value of any permutation γ l,i and hence to build efficiently any map M l .

Fig. 2 .

 2 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).

Fig. 3 .

 3 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. Definition 10 (Local degree in G-maps) Let C be an i-cell in an n-Gmap.

  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.

Property 4

 4 With the notations of Definition 22, for all d ∈ D such that CW i G,G (d) = (d 0 , d 1 , . . . , d p ) we have:

Fig. 4 .

 4 Fig. 4. A 2-G-map G (top row) from which the two white vertices are to be removed, yielding a map G (bottom row). The connecting walks CW 0 G,G (b) = (b = b 0 , b 1 , b 2 ) (second row) and CW 0 G,G (d) = (d = d 0 , d 1 , d 2 ) (third row).

( a )

 a Removal of a 0-cells. v (b) Removal of two 1-cells. (c) Removal of 4 1-cells.

Fig. 5 .

 5 Fig. 5. (a) Removal of a 0-cells: Each dart of the removed vertex belongs to exactly one 0-connecting walk and no i-connecting walk for i ∈ {1, 2}. (b) Removal of two edges from a 2-G-map: darts of the vertex v belong to no connecting walk. (c) Four regular edges with local degree 2 (dashed circles) which may be removed from a 2-G-map. All the removed darts belong to exactly one 1-connecting walk and to no i-connecting walk for i ∈ {0, 2}.

  ), and we denote by U the set on the right side of the equality. Let b ∈ D. If b ∈ D we immediately obtain b ∈ U , so we suppose that b / ∈ D . In this case, there exists i ∈ {0, . . . , n -1} such that b ∈ R i . The removal kernel being simple, following Definition 23 there exists d ∈ D such that b ∈ CW i G,G (d) * , and again b ∈ U . 2

vFig. 6 .

 6 Fig.[START_REF] Damiand | Removal and contraction for n-dimensional generalized maps[END_REF]. Removed darts which do not belong to any connecting walk.

  This contradicts the fact that b ∈ D . It follows that a = b. -If i = n -1, by Definition 24 we have d = aγ k n-1 and d = bγ h n-1 . Since a = b, if aγ k n-1 = bγ h n-1 we necessarily have k = h. Thus, we may suppose without loss of generality that h < k. Then, from aγ k n-1 = bγ h n-1 we deduce that a(γ n-1 ) k-h = b. Since 0 < k -h < k, by Property 7 applied to CW M,M (a) we obtain aγ k-h n-1 ∈ R * n-1 . This contradicts the fact that b ∈ D . It follows that a = b. 2

Fig. 7 .

 7 Fig. 7. A 3D combinatorial pyramid (M 0 , K 1 , K 2 ). (a) The 3-map M 0 . (b) The 3-map M 1 obtained after removing the edges e 1 and e 2 from M 0 . (c) The map M 2 obtained after removing the vertices v 1 , v 2 , and v 3 from M 1 . Four involutions γ 0 are materialized by two dotted lines. (d) The connecting walk CW 1 M 0 ,M 1 (b ) (black darts). (e) The connecting dart sequence CDS 0 2 (b) (black darts). Proposition 14 Let (M 0 , K 1 , . . . , K h ) be a pyramid of n-maps and l ∈ {1, . . . , h}. For all dart d ∈ D l and i ∈ {0, . . . , n -1} we have CDS i l (d) * ∩ D l = ∅.

i) CDS n- 1 l

 1 (d) * ⊂ AR l+1,n-1 ii) If CDS n-1 l (d) = (d 0 = d, d 1 , . . . , d p ) for p ∈ N * , then d u+1 = d u γ n-1 for all u ∈ {0, . . . , p -1}.

  is said to be regular too.

	Notation 2 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
	3 Cells removal and contraction in G-maps and maps
	3.1 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 * =	E i
	0≤i≤N
	Definition 14 (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 ).

  For all i ∈ {0, . . . , n -1}, d p α n-2 α n and d p α n-2 belong to the same i-cell so that d p α n-2 may not belong to an i-cell to be removed. Since R n = ∅ is follows that d p α n-2 ∈ D . Eventually, we have proved that (d = d 0 , d 1 , . . . , d p ) is the connecting walk associated to the dart d in G according to Definition 22 since d k α n-2 ∈ R *

	n-2

for all k ∈ {0, . . . , p -1} and d p α n-2 ∈ D . 2 Lemma 4 With the notations of Proposition 13 we have:

where (d 0 , . . . , d p ) = CW n-1 M l ,M l+1 (d). The result is again immediate after application of the recurrence hypothesis to the sequences CDS n-1 l (d r ), 0 ≤ r ≤ p, and using the fact that CW n-1 M l ,M l+1 (d) ∩ D l = ∅ (Property 7). 2

Lemma 5 With the notation of Definition 26, for all l ∈ {0, . . . , h} and all d ∈ D l we have first(CDS i l (d)) = d. In particular, CDS i l (d) contains at least one dart: d itself.

Proof: We proceed by recurrence on l. First, if l = 0 we have by Definition 26 CDS i 0 (d) = (d) and the property is verified.

Thus we suppose that the result holds for l ∈ {0, . . . , h -1}. At level l + 1, by Definition 26 we have:

where (d 0 , . . . , d p ) = CW i M l ,M l+1 (d).

In both cases, and by the recurrence hypothesis, CDS i l (d 0 ) is not an empty sequence and we have first(CDS i l (d 0 )) = d 0 . From the very definition of the connecting walk CW i M l ,M l+1 (d) we have d 0 = d. It follows immediately from the above equalities that first(CDS i l+1 (d)) = d, hence the property is verified at level l + 1. 2 Lemma 6 With the notations of Definition 26, a connecting dart sequence CDS i l always counts an odd number of darts when i < n -1.

Proof: We prove the result by recurence on l for l ∈ {0, . . . , h}. The property is true for n = 0 since CDS i 0 (d) = (d). Thus we may assume that the property is valid for some l ∈ {0, . . . , h -1}.

Now, following Definition 26, if CW

If p = 0, the property holds immediately by the recurrence hypothesis. Thus, we now consider the case when p > 0.

For h ∈ {0, . . . , p -1} we have GL

From the recurence hypothesis applied to both CDS i l (d h ) and CDS i+1 l (d h γ l,i ), we deduce that the sequence GL i l (d h ) counts an even number of darts. It follows that the sequence GL i l (d 0 ) • . . . • GL i l (d p-1 ) also counts an even number of darts.

Eventually, GL i l (d p ) = CDS i l (d p ), which, from the recurence hypothesis counts an odd number of darts, hence the result. 2

Connecting dart sequences also share with connecting walks the property that the last dart of an i-connecting dart sequence associated with a dart d at level l is linked with the dart dγ l,i by the permutation γ i .

Proposition 15 Let (M 0 , K 1 , . . . , K h ) be a pyramid of n-maps for h ∈ N * , with the notations of Definition 26. Let d ∈ D l for l ∈ {1, . . . , h}. We have

Proof: We prove the proposition by recurrence on l. If l = 0, from Definition 26 we have CDS i 0 (d) = (d), hence the property is obviously valid. Thus, we suppose that the property is satisfied for l ∈ {0, . . . , h -1}.

Let us consider CDS

where

In [START_REF] Fourey | A first step toward combinatorial pyramids in nD spaces[END_REF], since CDS i l (d p ) has d p as its first dart (Lemma 5), it is in particular not empty and it is therefore readily seen that

By the recurrence hypothesis applied to CDS i l (d p ), we have:

From Property 8 applied to CW i M l ,M l+1 (d) we know that

According to Definition 26, we have: . For all v ∈ {0, . . . , q -1} we may distinguish two cases:

We conclude that property ii) is satisfied for l + 1.

Eventually, both properties are therefore satisfied for all l ∈ {0, . . . , h}. 2

Proof: We prove the lemma by recurrence on l. If l = 0 there is nothing to prove since from Definition 26 we have CDS

We may then suppose that the property is valid for l ∈ {0, . . . , h -1}.

Let CW M l ,M l+1 (d) = (d = d 0 , . . . , d q ). If q = 0, then from Definition 26 we have CDS i l+1 (d) = CDS i l (d) and the property holds by the recurrence hypothesis.

condition of ( 12) applies for all u ∈ {0, . . . , p -1}. Thus, we suppose in the following that i < n -1.

We prove the proposition by recurrence on l. Let H 1 (l) be the property of CDS i l (d) described by the proposition. We first show that the property holds for l = 0. Following Definition 26, if l = 0 we have CDS i l (d) = (d) so that p = 0 and there is nothing left to prove. We may thus suppose that the property H 1 (l) is satisfied and we show that it is also valid for l + 1.

. . , b q ) we have:

We may denote CDS i l+1 = (d 0 , . . . , d p )

If q = 0, we immediately obtain CDS i l+1 (d) = CDS i l (d). In this case, the property is immediate since the recurrence hypothesis applies for CDS i l (d) and AR l,j ⊂ AR l+1,j for all j ∈ {0, . . . , n}. Therefore, we assume in the following that q > 0. Furthemore, as each subsequence in ( 13) is not empty, if q > 0 we necessarily have p > 0. Now, we prove by recurrence on v that the following property H 2 (v), made of the two properties below, holds for all v ∈ {0, . . . , p -1}:

ii) Exactly one of the following conditions holds:

(1)

) * for some k ∈ {0, . . . , q -1}, and t v is the involution subscript associated with

If v = 0, we write CDS i l (d) = (d 0 , . . . , d r ) which is the first sequence of darts of CDS i l+1 (d) following Definition 26. We may thus distinguish two cases:

• If r > 0, then from the recurrence hypothesis H 1 (l) applied to CDS i l (d) we have d 1 = d 0 γ i . Since in this case d 1 = d 1 and d 0 = d 0 , condition i) of the property is valid for v = 0 with t v = i, and only condition (4) of ii) holds.

• If r = 0, we have d 0 = last(CDS i l (b 0 )). We know by Proposition 15 that last(CDS i l (d 0 ))γ i = d 0 γ l,i . Since q > 0 we have d 0 γ l,i = b 1 (from the definition of the connecting walk CW i M l M l+1 (d)) with b 1 = d 1 as r = 0. We eventually obtain d 0 γ i = d 1 . Condition i) of the hypothesis is then valid for v = 0 with t 0 = i, and condition (1) of ii) holds.

We have just shown that property H 2 (0) holds. We may then suppose that H 2 (w) holds for all w ≤ v, with v < p -1; and we condider the dart d v+2 for v ∈ {1, . . . , p -2}. We may distinguish the four following cases:

as illustrated below From Proposition 15, we know that d v+1 γ i = d k γ l,i . Since k < q, from the very definition of CDS i l+1 (d) (see (15)) we have

. By condition (3) of the recurrence hypothesis H 2 (v), we have t v = i + 1. On the other hand, if r = 0 we have

From condition (3) of the recurence hypothesis H 2 (v) we deduce that t v = i + 1. On the other hand, by Lemma 11 we know that

Furthermore, condition (4) of the recurence hypothesis H 2 (v + 1) is satisfied since by the recurence hypothesis H 1 (l) the involution subscript associated with b h in CDS l,i (b h ) is i.

• If s > 0, we may apply the recurrence hypothesis H 1 (l) to CDS i l (b h ) and therefore denote by (t 0 , . . . , t r-1 ) the sequence of involution subscripts associated with CDS i l (b h ). We thus have d s+1 = d s γ t s . Since s > 0 we have b s / ∈ D l , and therefore obtain that d s ∈ AR l,j if and only if d s = d v+1 ∈ AR l+1,j , for all j ∈ {0, . . . , n -1}.

Furthermore, from condition (4) of the recurrence hypothesis H 2 (v), we know that t v is equal to the involution subscript associated with d v (i.e. d s-1 ) in CDS i l (b h ), namely t v = t s-1 . It follows immediately from the definition of t s given by H 1 (l), that the property i) of H 2 (v + 1) is satisfied with t v+1 = t s , which is also precisely the condition (4) of property ii) in the latter hypothesis.

From Proposition 15, since 15)). By condition (1) of the recurrence hypothesis H 2 (v), we have t v = i. On the other hand, since r = 0 we have d v+1 = b k γ l,i and by Property 7 applied to CW i M l ,M l+1 (d) we know that b k γ l,i ∈ R * l,i , thus d v+1 ∈ AR l+1,i . Since t v = i we eventually obtain that d v+1 ∈ AR l+1,t v and d v+2 = d v+1 γ t v +1 , so that the property i) of H 2 (v + 1) is satisfied with t v+1 = t v + 1 = i + 1. Condition (3) of property ii) therefore holds too.

• If r > 0, we may apply the recurrence hypothesis H 1 (l) to CDS i+1 l (b k γ l,i ) and therefore denote by (t 0 , . . . , t r-1 ) the sequence of involution subscripts associated with CDS i+1 l (b k γ l,i ). From the same hypothesis, since r > 0 we have t r-1 = i + 2, and by Lemma 11 we have d v+1 ∈ AR i+1 .

From the recurrence hypothesis H 2 (v), we know that t v is equal to the involution subscript associated with

Eventually, we have

) * for some k ∈ {0, . . . , q -1}. This case is in all parts similar to case (b), considering a connecting dart sequence CDS i+1 l (b k γ l,i ) instead of CDS i l (b k ) for some k ∈ {0, . . . , q -1}.

We conclude that the property H 2 (v + 1) is satisfied, hence it is valid for all v ∈ {0, . . . , p -1}. This shows that the first part of H 1 (l + 1) is valid. Now, from the definition of CDS i l+1 (d) we have d p = last(CDS i l (b q )). As stated before, we only consider the case q > 0.

Let us denote CDS i l (b q ) = (d 0 , . . . , d r ) with r ∈ N.

• If r = 0 we have d p = b q . Since q > 0 we deduce that b q ∈ CW i M l ,M l+1 (d) * and by Property 7 we obtain d p ∈ R i l (d) ⊂ AR l+1,i . Futhermore, by condition (3) of hypothesis H 2 (p -1) we know that t p -1 = i + 1. We conclude that the morevover part of H 1 (l + 1) is satisfied by CDS i l+1 (d). • If r > 0 (i.e. r > 1 by Lemma 6), from the morevover part of the recurence hypothesis H 1 (l) applied to CDS i l (b q ) we deduce that t r-1 = i + 1 (since i < n-1). By the recurence hypothesis H 2 (p -1), t r-1 is also the involution subscript associated with d p -1 (i.e. d r-1 ) in CDS i l+1 (d). We conclude that t p -1 = i + 1 and the morevover part of the recurence hypothesis H 1 (l + 1) is satisfied.

The overall conclusion is that the recurrence hypothesis H 1 (l + 1) is satisfied, it is therefore valid for all l ∈ {0, . . . , h}. 2 Eventually, the following corollary shows that the dimension of cells that are removed and which are traversed by a single connecting dart sequence cannot change radically for consecutive darts. Precisely, the difference is bounded by one, in absolute value.

Corollary 2 Let (M 0 , K 1 , . . . , K h ) be a pyramid of n-maps for h ∈ N * with M 0 = (D, γ 0 , . . . , γ n-1 ). If CDS i l (d) = (d 0 = d, d 1 , . . . , d p ), p ∈ N * , is the iconnecting dart sequence associated to a dart d of M l , with 1 ≤ l ≤ h and 0 ≤ i ≤ n; then for all u ∈ {1, . . . , p} we have d u ∈ AR δu where δ u ∈ {0, . . . , n -1} satisfies:

Proof: We prove the property by recurrence on u. If u = 1, by Lemma 11 we have d u ∈ AR l,i hence δ 1 = i. We may then suppose that the property holds for u ∈ {1, . . . , p -1}.

By Proposition 17, we necessarily have In the two cases, we obtain d u+1 ∈ AR l,δ u ∪ AR l,δ u +1 ∪ AR l,δ u -1 so that the property holds for δ u+1 ∈ {δ u , δ u + 1, δ u -1}. 2

Conclusion and perspectives

Using the definition given in [START_REF] Fourey | A first step toward combinatorial pyramids in nD spaces[END_REF] for the simultaneous removal of cells in an n-map, we have defined here n-dimensional combinatorial pyramids the way Brun and Kropatsch did in the two-dimensional case ( [START_REF] Brun | Combinatorial pyramids[END_REF]) and following the works of Grasset et al. about pyramids of generalized maps ( [START_REF] Grasset-Simon | nD generalized map pyramids: Definition, representations and basic operations[END_REF]). We have defined connecting walks in both maps and G-maps, and established a link between the two definitions. Such walks are analogous to the reduction windows of regular pyramids. Connecting dart sequences, which are analogous to the receptive fields within regular pyramids, have also been defined.