S Alayrangues
email: sylvie.alayrangues@xlim.fr

P Lienhardt
email: pascal.lienhardt@xlim.fr

S Peltier
email: samuel.peltier@xlim.fr

Conversion between chains of maps and chains of surfaces; application to the computation of incidence graphs homology

Many combinatorial cellular structures have been defined in order to represent the topology of subdivided geometric objects. Two main classes can be distinguished. According to the terminology of [8], one is related to incidence graphs and the other to ordered models. Both classes have their own specificities and their use is relevant in different contexts. It is thus important to create bridges between them. So we define here chains of surfaces (a subclass of incidence graphs) and chains of maps without multi-incidence (a subclass of ordered models), which are able to represent the topology of subdivided objects, whose cells have "manifold-like" properties. We show their equivalence by providing conversion operations. As a consequence, it is hence possible to directly apply on each model results obtained on the other. We extend here classical results related to homology computation obtained for incidence graphs corresponding to regular CW -complexes and recent results about combinatorial cell complexes where cells are not necessarily homeomorphic to balls.

Introduction

Many simplicial and cellular structures have been defined in geometric modeling, image analysis and computational geometry (e.g. [START_REF] Baumgart | A polyhedron representation for computer vision[END_REF][START_REF] Cardoze | Representing topological structures using cell-chains[END_REF][START_REF] Floriani | Decomposing non-manifold objects in arbitrary dimensions[END_REF][START_REF] Lienhardt | Topological models for boundary representation: a comparison with n-dimensional generalized maps[END_REF][START_REF] Lienhardt | N-dimensional generalized combinatorial maps and cellular quasi-manifolds[END_REF][START_REF] Lee | Partial entity structure : a fast and compact nonmanifold boundary representation based on partial topological entities[END_REF][START_REF] Peltier | Simploidals sets: Definitions, operations and comparison with simplicial sets[END_REF][START_REF] Weiler | Edge-based data structures for solid modelling in curved-surface environments[END_REF][START_REF] Bertrand | Topological encoding of 3d segmented images[END_REF][START_REF] Brun | Contraction kernels and combinatorial maps[END_REF][START_REF] Daragon | Discrete frontiers[END_REF][START_REF] Meine | The geomap : a unified representation for topology and geometry[END_REF][START_REF] Brisson | Representing geometric structures in d dimensions: topology and order[END_REF][START_REF] Dobkin | Primitives for the manipulation of threedimensional subdivisions[END_REF][START_REF] Edelsbrunner | Algorithms in Computational Geometry[END_REF][START_REF] Guibas | Primitives for the manipulation of general subdivisions and the computation of voronoi diagrams[END_REF]). We focus here on cellular structures used to encode the topology of finite n-dimensional space subdivisions in which cells are more general than simplices or cubes. More precisely the structures we are interested in can have cells which are not homeomorphic to balls.

Schematically, such structures are defined according to two main approaches. Incidence graph based representations rely on an explicit definition of the cells and their incidence relations [START_REF] Bertrand | New notions for discrete topology[END_REF][START_REF] Edelsbrunner | Algorithms in Computational Geometry[END_REF][START_REF] Rossignac | Sgc : A dimension-independant model for pointsets with internal structures and incomplete boundaries[END_REF][START_REF] Sobhanpanah | Extension of a boundary representation technique for the description of n-dimensional polytopes[END_REF]. Ordered models, as combinatorial map derived structures, are based upon elements which are more basic than cells, and are linked by functions allowing to retrieve the notions of cell and incidence [START_REF] Brisson | Representing geometric structures in d dimensions: topology and order[END_REF][START_REF] Lienhardt | N-dimensional generalized combinatorial maps and cellular quasi-manifolds[END_REF][START_REF] Vince | Combinatorial maps[END_REF]. In both approaches, a simplicial analog can be associated with any structure. For an incidence graph, it is simply an abstract simplicial complex whereas for ordered models it is a less constrained kind of simplicial set. This simplicial analog defines the topology of the structure. Through its simplicial analog a CW -complex can always be associated with any of these structures but it is not always possible to directly associates a CW -complex with the cellular structure itself. For instance, an incidence graph may contain edges incident to more than two vertices. Obviously such an edge cannot be associated with a 1-dimensional ball. Note that when the cellular structure can directly be associated with a CW -complex, its simplicial analog is simply the barycentric triangulation of the cellular structure.

Both approaches have their own characteristics that make their use accurate in different contexts. Incidence graphs intrinsically provide a direct access to the cells and to their incidence relations. But they suffer from three major limitations. First they are definitely not able to encode subdivisions with any kind of multi-incidence (for instance a loop edge, in which the vertex is twice incident to the edge). Then they do not make any assumption on the topology of the cells. For instance, in such a representation, nothing prevents an edge to be incident to more than two vertices. To tackle this difficulty, subclasses of such structures have been exhibited, e.g. n-surfaces [START_REF] Bertrand | New notions for discrete topology[END_REF][START_REF] Evako | Dimensional properties of graphs and digital spaces[END_REF]. But the properties they have to fulfill are expensive to check. Finally such cellular representations have only been equipped with a few operations, because they are not able to easily provide control over the evolution of their topology 1 .

Ordered models overcome most drawbacks of incidence graphs. They are able to encode subdivisions with multi-incidence. It is particularly useful in geometric modeling when handling free-form objects, e.g. splines, for CAD applications for instance. Topological properties of cells are contained in their very definition, and thus topological modifications induced by local operations are naturally monitored. As an expectable counterpart, the memory cost of such representations is usually higher.

It is thus important to create bridges between incidence graphs and ordered models, in order to be able to switch from one framework to the other. Theoretical results and/or algorithms can hence be transferred from one to another: it is both useful from a theoretical point of view and from a more practical one as it allows to take into account the specific needs of a given application. A first work has been achieved, linking n-surfaces and generalized maps (gmaps) [START_REF] Alayrangues | Equivalence between closed connected n-g-maps without multi-incidence and n-surfaces[END_REF]. Such models are respectively an incidence graph and an ordered model which can represent "manifold-like" subdivided objects (cf. section 4). We generalize here these results for a larger class of objects.

More precisely, we define in this paper chains of maps without muti-incidence (definition 8), a restriction of chains of maps (cmaps), which is an ordered model defined in [START_REF] Elter | Cellular complexes as structured semi-simplicial sets[END_REF]. We also define an incidence graph based representation, namely chains of surfaces (definition 4), which is a subclass of orders and an extension of n-surfaces [START_REF] Bertrand | New notions for discrete topology[END_REF]. The cells of both models, though not necessarily homeomorphic to balls, present useful "manifold-like properties" (cf. section 4). Moreover the assembly of the cells can be done in a quite general way. We construct conversion operators between both models (lemmas 1 and 2) and show that they are inverse to each other up to isomorphism (lemma 3). We deduce from this the equivalence of both representations (theorem 1). We show then that the simplicial analogs of two equivalent chain of maps without multi-incidence and chain of surfaces also are isomorphic (theorem 2).

As an example of the interest of establishing bridges between incidence graphs and ordered models, we study (the links between) the homology definitions for both cellular models. Homology provides useful information about the holes of an object (connected components, tunnels, cavities, etc) [START_REF] Agoston | Algebraic Topology, a first course[END_REF][START_REF] Hatcher | Algebraic Topology[END_REF], and many works have been devoted to the computation of the homology of simplicial and cellular structures, for instance [START_REF] Agoston | Algebraic Topology, a first course[END_REF][START_REF] Munkres | Elements of Algebraic Topology[END_REF][START_REF] Peltier | Computation of homology groups and generators[END_REF][START_REF] Dumas | On efficient sparse integer matrix smith normal form computations[END_REF][START_REF] Giesbrecht | Probabilistic computation of the smith normal form of a sparse integer matrix[END_REF][START_REF] Storjohann | Near optimal algorithms for computing smith normal forms of integer matrices[END_REF][START_REF] González-Díaz | Chain homotopies for object topological representations[END_REF][START_REF] Kaczynski | Computational Homology[END_REF][START_REF] Dlotko | Coreduction homology algorithm for regular cw-complexes[END_REF][START_REF] Edelsbrunner | Topological persistence and simplification[END_REF][START_REF] Zomorodian | Localized homology[END_REF]. The homology of a cellular structure is classically defined as the homology of its simplicial analog. But the conversion from a cellular structure to its simplicial analog and the computation of homology on this simplicial structure that contains many more cells than its cellular counterpart has a cost. It is hence more interesting to compute homology directly on the cellular structure itself. This approach has already been validated for chains of maps [START_REF] Alayrangues | A boundary operator for computing the homology of cellular structures[END_REF]. But it has not yet been published for chains of surfaces. Through the conversion operators previously defined, the homology of a chain of surfaces could obviously be computed on the equivalent chain of maps. But the conversion still has a cost and the amount of data to deal with on the chain of maps is also much greater than on the original chain of surfaces.

Note that the results we obtain here are already well known for regular CW -complexes but even if such subdivisions can be represented with incidence graphs, the structures we deal with are able to encode a wider range of objects. Cells of a chain of surfaces may for instance have a boundary which is not homeomorphic to a sphere. An example is given in Annex where a chain of surfaces encoding a CW -complex has a dual which is still a chain of surfaces but not a regular CW -complex.

Note also that a similar work on incidence graphs has been achieved by Basak [START_REF] Basak | Combinatorial cell complexes and poincaré duality[END_REF]. The subclass of incidence graphs, he studied, namely "combinatorial cell complexes", is very close to the subclass of chains of surfaces though a bit different. Some configurations are forbidden in Basak's graphs. For instance, two distinct cells of a combinatorial cell complex must have different boundaries whereas two distinct cells of a chain of surfaces can share exactly the same boundary. But Basak's graphs require less "connectedness" than chains of surfaces (cf. Fig. 3

page 10).

Homology of chains of maps is studied in [START_REF] Alayrangues | A boundary operator for computing the homology of cellular structures[END_REF], and we define here the homol-ogy of chains of surfaces, with coefficients in Z and in Z/2Z2 . We prove then the equivalence of the homologies of equivalent cellular structures. Since the homology of a chain of maps is equivalent to the homology of its simplicial analog under some conditions, we deduce a similar result for chains of surfaces.

To sum up, main contributions of this work are twofold. First, definitions of subclasses of incidence graphs and combinatorial maps are given which are proved to encompass exactly the same set of cellular subdivisions. And conversions operators from one to the other are exhibited. Second, a direct computation of homology on chains of surfaces is provided through the definition of a suitable boundary operator and proved to be equivalent to the homologies of the associated chain of maps and of the associated simplicial analog. By the way, we prove that the arguments used in [START_REF] Massey | A Basic Course in Algebraic Topology[END_REF][START_REF] Dlotko | Coreduction homology algorithm for regular cw-complexes[END_REF] can be applied to a class of incidence graphs wider than the one studied in [START_REF] Basak | Combinatorial cell complexes and poincaré duality[END_REF].

The paper is organized as follows. The definitions of orders, n-surfaces and chains of maps are reminded in section 2, where we also define the notion of chains of surfaces. The definition of chains of maps without multi-incidence is given in section 3, and we show, by using conversion operators, that they are equivalent to chains of surfaces. The definitions of the simplicial analogs of chains of maps and chains of surfaces are reminded in section 4, and we show their equivalence for equivalent cellular structures. Then we define in section 5 the cell orientability notion for chains of surfaces, and incidence numbers which make it possible to define a boundary operator and hence a cellular homology for chains of surfaces. These definitions are similar to that of [START_REF] Basak | Combinatorial cell complexes and poincaré duality[END_REF], and [START_REF] Massey | A Basic Course in Algebraic Topology[END_REF][START_REF] Dlotko | Coreduction homology algorithm for regular cw-complexes[END_REF] for incidence numbers (the cell orientability notion always being satisfied for a regular CW -complex). We remind also similar notions for chains of maps, and the conditions under which their cellular homology is equivalent to the homology of their simplicial analog. We then prove the equivalence of incidence numbers associated with equivalent chains of surfaces and chains of maps, hence showing the equivalence of their homologies. We can then deduce the equivalence of the conditions which have to be satisfied by chains of surfaces and combinatorial cell complexes in order to get a cellular homology which is equivalent to the homology of their simplicial analogs (such conditions are always satisfied for incidence graphs corresponding to regular CW -complexes).

Cellular structures 2.1 Incidence graph based structures

Many incidence graphs (or equivalent structures) have been designed and adapted to different kinds of applications, e.g. [START_REF] Sobhanpanah | Extension of a boundary representation technique for the description of n-dimensional polytopes[END_REF][START_REF] Rossignac | Sgc : A dimension-independant model for pointsets with internal structures and incomplete boundaries[END_REF][START_REF] Edelsbrunner | Algorithms in Computational Geometry[END_REF]. Their differences lie either on the way they are defined (e.g. with an explicit or implicit dimension associated with each vertex of the graph) or on the kinds of subdivisions they encode: in the latter case, additional constraints can be added in order to ensure some topological properties of the represented subdivisions (e.g. to grant some similarities with manifolds : cf. definition 3). We choose here an order-based representation of incidence graphs where the dimension of cells is implicitly defined.

Orders

Definition 1 (CF -order [START_REF] Bertrand | New notions for discrete topology[END_REF]). An order is a pair |X| = (X, α), where X is a set and α a reflexive, antisymmetric, and transitive binary relation. We denote β the inverse of α and θ the union of α and β. CF -orders are orders which are countable, i.e. X is countable, and locally finite, i.e. ∀x ∈ X, θ(x) is finite.

We introduce some vocabulary and notations, based on [START_REF] Daragon | Discrete frontiers[END_REF][START_REF] Daragon | Discrete surfaces and frontier orders[END_REF]. The set α(x) is called the α-adherence of x, or the closure of cell x. The set β(x) is similarly called β-adherence of x, or the star of x. The θ-adherence of x is simply the union of the closure and of the star of x. The strict α-, β-and θadherences are respectively denoted by α , β , and θ and contain all elements of the corresponding adherence except x itself: for instance, the boundary of x is α (x). The main cells are the cells whose strict stars are empty 3 . The notion of α-closeness of x, denoted by α • (x), also proves useful. It is the set: {y ∈ α (x), α (x) ∩ β (y) = ∅}, which contains the elements of the boundary of x which are the closest to x according to α. The β-and θ-closeness are similarly defined.

There are many ways to visually represent orders. We choose here to use simple Directed Acyclic Graphs (DAG), whose vertices are exactly the elements of X and each oriented edge relates an element x to an element of α • (x). We use hence the DAG (X, α • ) to represent the order (X, α). The set α(x) is naturally obtained from the DAG by extracting the transitive closure of α • (x) (see Fig. 1 If S is any subset of X, (S, α ∩ S × S) is a suborder of |X| and is denoted by |S| = (S, α |S ).

A sequence x 0 , x 1 , . . . , x n such that x i belongs to θ (x i+1 ) is called a θ-chain of length n, n-θ-chain or simply a path. An order is said to be connected if it is path-connected. Note that α-, α • -, β-, β • -chains are similarly defined. The rank of an element denoted by ρ(x, |X|) is defined as the length of the longest α • -chain beginning at it. Note that the α-adherence contains x and all cells of lower ranks incident to x and the β-adherence of x contains x and all cells of greater ranks to which x is incident. A pure order is such that all main cells have the same rank. The rank of an order is simply the highest rank of its elements.

The rank of an element can be seen as its implicit dimension. To grant that this implicit dimension is consistent, we only deal with subdivisions which can be encoded by closed CF -orders.

Definition 2 (closed order [START_REF] Bertrand | New notions for discrete topology[END_REF]). Let |X| be an order, |X| is said to be closed if for any x ∈ X and y ∈ α (x):

∀i ∈]ρ(y, |X|), ρ(x, |X|)[ 4 , ∃z ∈ α (x) ∩ β (y), ρ(z, |X|) = i
In other words, the closeness condition prevents any "dimensional gap" from occurring in the order (cf. counterexample in Fig. 1(e)).

Chains of n-surfaces

The orders described so far are so little constrained that they would be able to encode "pathologic subdivisions" where, for instance, three vertices could be incident to an edge (cf. Fig. 1(i),Fig. 1(j)). We focus here on two families of orders: n-surfaces (cf. Definition 3 (n-surface5 ). Let |X| = (X, α) be a non-empty CF -order.

• The order |X| is a 0-surface if X contains exactly two elements x and y such that y ∈ α(x) and x ∈ α(y);

• The order |X| is an n-surface, n > 0, if |X| is connected and if, for each x ∈ X, the order |θ (x)| is an (n -1)-surface.

n-surfaces are defined and studied in [START_REF] Alayrangues | Equivalence between closed connected n-g-maps without multi-incidence and n-surfaces[END_REF][START_REF] Bertrand | New notions for discrete topology[END_REF][START_REF] Daragon | Discrete frontiers[END_REF]. We focus here on a wider class of orders, which we define below and name chain of surfaces.

Definition 4 (chain of surfaces). Let |X| = (X, α) be a non-empty connected CF -order. |X| is a k-dimensional chain of surfaces if ∀i, 1 ≤ i ≤ k, ∀x i main cell of |X|, α (x i ) is an (i -1)-surface 6 .

Chains of surfaces are a generalization of n-surfaces: the boundaries of icells have to be (i -1)-surfaces but the whole subdivision does not have to. Otherwise said the topology of each cell is restricted but their attachment can be achieved more loosely. This subclass of incidence graphs inherits some interesting properties of n-surfaces. First, whenever a (k -2)-cell is incident to a k-cell, exactly two (k -1)-cells exist between them (diamond configuration). Similarly any 1-cell has exactly two incident 0-cells. To obtain an homogeneous definition of this so-called switch-property, a fictive element x -1 is added to X such that x -1 belongs to the α-adherence of any element of X (i.e. x -1 is a "sink" for |X|).

Useful properties of chains of surfaces

Prop 2.1 (switch-property). Let |X| be a k-dimensional chain of surfaces.

∀(x, y) ∈ (X ∪ {x -1 }) × (X ∪ {x -1 }), β • (x) ∩ α • (
y) is either empty or made of exactly 2 elements.

Note that this switch-property is a generalization of the switch-property satisfied by n-surfaces [START_REF] Alayrangues | Equivalence between closed connected n-g-maps without multi-incidence and n-surfaces[END_REF][START_REF] Brisson | Representing geometric structures in d dimensions: topology and order[END_REF].

Prop 2.2. Let |X| be an n-dimensional chain of surfaces, then ∀x i ∈ X, |α (x i )| is a connected (i -1)-surface.
Proof. This property actually comes from the very definition when x i is a main cell of the subdivision. Any other i-dimensional element x i of the chain of surfaces belongs to a p-surface, where p is the dimension of a main cell having x i in its α-adherence: α (x i ) is also hence a connected (i -1)-surface (see proof in [START_REF] Daragon | Discrete surfaces and frontier orders[END_REF]).

Prop 2.3. Let |X| be an n-dimensional chain of surfaces, each suborder built on X i = x i ∈X {α(x i )}, i ∈ {0, . . . , n}, is itself a chain of surfaces whose each switch i k -operator, k ∈ {0, . . . , i -1}, is simply the restriction of the switch koperator of X on X i .

Proof. Main cells of such a suborder are i-cells of the original order. Their strict α-adherences are hence (i -1)-surfaces (Property 2.2). This corresponds precisely to the definition of chains of surfaces (see definition 4). The construction of switch-operators is straightforward.

On n-surfaces, the switch-property also holds for (n -1)-elements and a fictive "source" x n+1 . Moreover this property induces (n + 1) operators on nβ • -chains, denoted by switch i , i ∈ {0, . . . , n}, each of which acts on the idimensional element of the chain. The operator switch i actually transforms the chain (x 0 , . . . , x i-1 , x i , x i+1 , . . . , x n ) into (x 0 , . . . , x i-1 , x i , x i+1 , . . . , x n ), where [START_REF] Brisson | Representing geometric structures in d dimensions: topology and order[END_REF]).

β • (x i-1 ) ∩ α • (x i+1 ) = {x i , x i } (see
Prop 2.4. Let |X| be a k-dimensional chain of surfaces and x i be an element of X. The suborder built on all elements of α (x i ) having dimensions (i -2) and (i -1) is connected (cf. Fig. 2). Proof. |α (x i )| is an (i -1)-surface (see Property 4 of [START_REF] Daragon | Discrete surfaces and frontier orders[END_REF]). Then it is chainconnected (see [START_REF] Alayrangues | Equivalence between closed connected n-g-maps without multi-incidence and n-surfaces[END_REF]), which means that any two (i -1)-β • -chains having elements in common can be obtained from one another by a composition of switchoperators involving elements that are not shared by both chains. Let y and z be two elements belonging to the suborder of |α (x i )| built on (i -1)-and (i -2)-elements. We show that there exists a path in this very suborder linking both elements by building it step by step. Let C y and C z be two (i -1)-β • -chains respectively containing y and z. Note that each such chain contains exactly two elements of the suborder. If y ∈ C z or z ∈ C y , then y and z are connected. Else, as |α (x i )| is chain-connected, C z is the image of C y under a composition of switch k operators. This composition of involutions contains at least one switch i-1 or one switch i-2 involution. Let C y be the image of C y by the subsequence of consecutive involutions ending with the first involution whose index, k 0 , is equal to i-1 or i-2. And let C 0 y the chain obtained by applying the same sequence of operators and ending with the involution preceding switch k0 . In the following let us denote respectively by y i-3 , y i-2 and y i-1 the (i -3)-, (i -2)-and (i -1)-cells of C 0 y . Note that both y i-2 and y i-1 belong to the suborder of |α (x i )| built on its (i -1)-and (i -2)-elements and that y is either

y i-1 or y i-2 .
Let y k0 be the k 0 -dimensional element of C y . If k 0 is equal to i-1, then, y i-2 belongs both to C y and to C 0 y . And

y k0 = α • (x i ) ∪ β • (y i-2 )\{y i-1 }. The chain y i-1 , y i-2 , y k0 is a path in the suborder. If k 0 is equal to i -2, then y i-1 still belongs to C y . Moreover y k0 = α • (y i-1 ) ∪ β • (y i-3
)\{y i-2 } and y i-2 , y i-1 , y k0 is a path in the suborder. There exists hence a path between y and y k0 . If y k0 = z then we are done. Else we go on applying involutions and building a path step by step.

Related structures

Orders and incidence graphs like structures do not guarantee a priori any property on the cells they contain. The only information that is encoded in such structures is the link between a cell and its boundary.

There are two main approaches to constrain the represented objects. The first one is purely combinatorial. The definition of some classes of structures only relies on combinatorial properties. For instance, combinatorial cell complexes [START_REF] Basak | Combinatorial cell complexes and poincaré duality[END_REF], which are very close to chains of surfaces, are incidence graphs explicitly fulfilling a set of combinatorial properties. The definition contains 4 points. Points 1 and 2 correspond to the notion of closed order. Point 4 corresponds to the switch-property. And due to point 3, two cells can not share the same boundary, contrary to n-surfaces and chains of surfaces (cf. Fig. 1(f),Fig. 1(g)). But they can also encode subdivisions that cannot be represented by chains of surfaces because, for instance, the boundaries of maximal cells are not necessarily connected (cf. Fig. 3).

Other classes are defined through existential properties. For instance, stellar manifolds are defined through the existence of a sequence of stellar transformations (which are purely combinatorial transformations). Any combinatorial object can directly be tested in order to check whether it fulfills the first kind of definitions, it is obviously not the case for the second one.

The second approach includes the use of non combinatorial properties. For example, cells of regular CW-complexes are homeomorphic to balls. Such a property cannot be combinatorially tested. Of course, convex cells have this property and they are often used in practice. But in some applications, e.g. free-form sur- Figure 3: This incidence graph encodes a combinatorial cell complex as defined by Basak [START_REF] Basak | Combinatorial cell complexes and poincaré duality[END_REF], but the boundary of each 2-cell is not connected. Hence it is no chain of surfaces.

faces, concave cells are very useful. CW-complexes have been deeply studied in algebraic topology and many interesting results are available. Nevertheless due to their non combinatorial nature, it is difficult to deal with them. Moreover some important topological properties cannot be defined on them. For instance, Poincaré duality cannot be defined on all regular CW-complexes because some of them have a dual which is not a regular CW-complex (see Section 7).

Combinatorial maps

Combinatorial maps based structures ( [START_REF] Edmonds | A combinatorial representation for polyhedral surfaces[END_REF][START_REF] Jacque | Constellations et graphes topologiques[END_REF][START_REF] Vince | Combinatorial maps[END_REF]) are dedicated to the representation of cellular subdivisions whose cells have regularity properties close to those of manifolds. Since cells can be multi-incident to each other, these structures are not constructed directly from the cells of the subdivision but from a more elementary object, called a dart.

Definition 5 (gmap [START_REF] Lienhardt | N-dimensional generalized combinatorial maps and cellular quasi-manifolds[END_REF]).

Let n ≥ 0, an n-dimensional gmap or n-gmap is defined by an (n + 2)-tuple • D is a finite set of elements called darts;

G = (D, α 0 , • • • , α n ) such that (cf.
• ∀i, 0 ≤ i ≤ n, α i : D → D is an involution 7 ; • ∀i, 0 ≤ i ≤ n -2, ∀j, i + 2 ≤ j ≤ n, α i α j is an involution. Related notions: dart d is a fixed point of involution α i means that dα i = d.
When all involutions are without fixed points, the gmap is closed. The notions of connected component and cell are defined through the following notion of orbit. Let Φ = {π 0 , • • • , π n } be a set of permutations defined on a set D.

Φ = π 0 , • • • , π n = [0,n] denotes the permutation group of D generated by Φ. Orbit Φ (d) is the set {dφ | φ ∈ Φ } 8 . The connected component of n-gmap G incident to dart d is the orbit α 0 , • • • , α n (d).
The i-dimensional cell (or 7 i.e. a one-to-one mapping (a permutation) such that α i = α -1 i . dα i (resp. dα i α j ) will often denote α i (d) (resp. α j (α i (d))).

8 It denotes also the structure (

D d = Φ (d) , π 0 /D d , • • • , πn/D d ), where π i /D d denotes the restriction of π i to D d . (a) (b) (c) (d) (e) (f) (g) (h) (i) (j)
i-cell) incident to dart d is the orbit α 0 , • • • , αi , • • • , α n (d)
, where αi denotes that involution α i is removed. The (n-1)-gmap (D, α 0 , . . . , α n-1 ) is the canonical boundary of the n-gmap (D, α 0 , . . . , α n ). A closed connected n-gmap is orientable if and only if it contains exactly two distinct orbits

α 0 α 1 , • • • , α 0 α n .
Definition 6 (cmap [START_REF] Elter | Cellular complexes as structured semi-simplicial sets[END_REF]). An n-dimensional cmap or n-cmap is a tuple :

C = ((G i ) i=0,...,n , (σ i ) i=1,...,n ) such that (cf. Fig. 4(h)): 1. ∀i, 0 ≤ i ≤ n, G i = (D i , α i 0 , . . . , α i i-1 , α i i = ω) is an i-gmap such that ω is undefined on D i ; 2. ∀i, 1 ≤ i ≤ n, σ i : D i -→ D i-1 ; for i ≥ 2, σ i satisfies, for any dart d of D i : (a) σ i is an isomorphism 9 between any orbit α i 0 , • • • , α i i-2 of G i and an orbit α i-1 0 , • • • , α i-1 i-2 of G i-1 ; (b) dα i i-1 σ i σ i-1 = dσ i σ i-1 .
Any connected component of an i-gmap is an i-dimensional cell, or i-cell (that is why α i i = ω is undefined). The cells are linked by face operators σ i . An j-cell, c j , is incident to an i-cell, c i , i > j, when there exists a dart incident to c i whose image by the composition: σ i . . . σ j+1 is incident to c j . The boundary of an i-cell, c i , is the set of cells incident to this cell in the cmap. It is associated with the (i -1)-cmap

B ci = ((G k ci ) k=0,...,i-1 , (σ k ) k=1,...,i-1 ) where G k ci is the gmap (D k ci = D i ci σ i • • • σ k+1 , α k 0 D k c i , . . . , α k k-1 D k c i , ω). The canonical boundary of an i-cell (D ci , α i 0 , . . . , α i i-1 , α i i = ω) is the (i -1)-gmap (D ci , α i 0 , . . . , α i i-1
). Note that a cmap can be associated with any gmap (cf. Fig. 4(i),Fig. 4(j)).

Conversion between chains of surfaces and chains of maps

Structures derived from combinatorial maps are able to encode subdivisions containing multi-incidence (cf. Fig. 4(d),Fig. 4(e)) whereas incidence graphs cannot. In order to define conversion processes between chains of surfaces and cmaps, we have hence to add constraints for avoiding multi-incidence.

Definition 7 (gmap without multi-incidence [START_REF] Alayrangues | Equivalence between closed connected n-g-maps without multi-incidence and n-surfaces[END_REF]).

An n-gmap G = (D, α 0 , . . . , α n ) is without multi-incidence if and only if ∀d ∈ D, ∀I ⊆ N = {0, • • • , n}, N -I (d) = ∩ i∈I N -{i} (d).
It has been proved in [START_REF] Alayrangues | Equivalence between closed connected n-g-maps without multi-incidence and n-surfaces[END_REF] that closed n-gmaps without multi-incidence are equivalent to n-surfaces. We generalize here this result by establishing a similar equivalence between chains of surfaces and cmaps without multi-incidence:

Definition 8 (cmap without multi-incidence). An n-cmap without multi-incidence is an n-cmap C = ((G i = (D i , α i 0 , . . . , α i i-1 , α i i = ω)) i=0,...,n , (σ i ) i=1,...,n ) such that: 1. ∀i, 0 ≤ i ≤ n, the canonical boundary of G i is a closed (i -1)-gmap without multi-incidence;
2. ∀i, 0 ≤ i ≤ n, the canonical boundary of each i-cell is isomorphic to its boundary.

Note that the boundary of an i-cell, c i , is always an homogeneous (i -1)cmap. Moreover when the cmap containing the i-cell is without multi-incidence its boundary is isomorphic to its canonical boundary and hence equivalent to the structure (G i-1 c i , R i-2 ). Under these assumptions, this structure is in turn equivalent to the (i-1)-gmap (D i ci σ i , α i-1

0 D i c i σ i , . . . , α i-1 i-2 D i c i σ i , R i-2 ) where R i-2 is defined by (d, d ) ∈ R i-2 ⇔ dσ i-1 = d σ i-1 .
Lemma 1. (construction of an n-dimensional chain of maps from an n-dimensional chain of surfaces) Let |X| be an n-dimensional chain of surfaces.

1. ∀i ∈ {0, . . . , n}, let D i be the set of all i-α • -chains of |X| rooted at some element of rank i, i.e.

D i = {i-α • -chains of α(x i ), x i ∈ X};
2. ∀i ∈ {0, . . . , n}, ∀k ∈ {0, . . . , i -1}, let α i k be the involution switch i k induced on the chain of surfaces | x i ∈X {α(x i )}|;

3. ∀i ∈ {1, . . . , n}, let σ i be the application which associates with each i-α •chain of |α(x i )|, (x 0 , . . . , x i-1 , x i ), the (i -1)-α • -chain of |α(x i-1 )|, (x 0 , . . . , x i-1 ).

Then C = ((D i , α i 0 , . . . , α i i-1 , α i i = ω) i∈{0,...,n} , {σ i } i∈{1,...,n} )
, where ω is undefined on D i , ∀i ∈ {0, . . . , n}, is an n-dimensional chain of maps without multi-incidence whose main cells have closed connected boundaries.

Proof.

In the sequel we denote by

D k |Y where Y is a k-dimensional suborder of |X|, the set of k-α • -chains belonging to Y . Remark 1: each set D i can be decomposed into the disjoint union of restric- tions of D i to suborders |α(x i )|, i.e. D i = x i ∈|X| D i |α(x i ) .
1. We first prove that C = ((D i , α i 0 , . . . , α i i-1 , α i i = ω) i∈{0,...,n} , {σ i } i∈{1,...,n} ) is a cmap. Otherwise said that C fulfills requirements of definition 6.

6.1 Let us show that ∀i ∈ {0, . . . , n}, (D i , α i 0 , . . . , α i i-1 , α i i = ω) is an i-dimensional generalized map where α i i is undefined on D i . As |X| is an n-dimensional chain of surfaces, each α (x i ) is a connected (i -1)-surface (see property 2.2).

(D i-1 |α (x i ) , switch i-1 0 , . . . , switch i-1 i-1
) is hence a closed connected (i-1)-generalized map without multi-incidence [START_REF] Alayrangues | Equivalence between closed connected n-g-maps without multi-incidence and n-surfaces[END_REF].

Moreover there is a bijection

φ x i between D i-1 |α (x i ) and D i |α(x i ) which is such that ∀k ∈ {0, . . . , i -1}, ∀d ∈ D i-1 |α (x i ) , dswitch i-1 k φ x i = dφ x i switch i k . Hence, Remark 1 implies that ∀i ∈ {0, . . . , n}, (D i = x i ∈|X| D i |α(x i ) , α i 0 , . . . , α i i-1 , ω
) is a closed i-generalized map without multi-incidence made of several connected components, each corresponding to some i-dimensional cell of the order; 6.2 Both equalities involving σ i are quite straightforward. For instance, when i ≥ 2, for 0 ≤ k ≤ i -2:

dα i k σ i = (x 0 , . . . , x k-1 , x k , x k+1 , . . . , x i-1 , x i )α i k σ i = (x 0 , . . . , x k-1 , x k , x k+1 , . . . , x i-1 , x i )σ i = (x 0 , . . . , x k-1 , x k , x k+1 , . . . , x i-1 ) = (x 0 , . . . , x k-1 , x k , x k+1 , . . . , x i-1 )α i-1 k = (x 0 , . . . , x k-1 , x k , x k+1 , . . . , x i-1 , x i )σ i α i-1 k = dσ i α i-1 k
We prove in a similar way that

dα i i-1 σ i σ i-1 = dσ i σ i-1 .
2. We now prove that this cmap is without multi-incidence.

As stated previously,

(D i-1 |α (x i ) , switch i-1 0 , . . . , switch i-1 i-1
) is a closed connected (i -1)-generalized map without multi-incidence. The cmap corresponding to the cell x i is the same cmap with one more involution: α i i = ω. It can hence be proved that it has no multi-incidence and that it has a boundary. The bijection φ x i defined previously implies that this boundary is the canonical one and hence that they are isomorphic.

Lemma 2. (construction of an n-dimensional chain of surfaces from an n-dimensional chain of maps without multi-incidence) Let C = ((D i , α i 0 , . . . , α i i-1 , α i i = ω) i∈{0,...,n} , {σ i } i∈{1,...,n} ) be an n-dimensional chain of maps without multi-incidence, where ω is undefined on D i , ∀i ∈ {0, . . . , n}.

1. ∀i ∈ {0, . . . , n}, let X i be the set of α i 0 , . . . , α i i-1 -orbits, i.e. of connected components, of (D i , α i 0 , . . . , α i i-1 , α i i = ω). Let us denote by X the set:

x i ∈X i i=0,...,n {x i }
2. let α be defined on X × X, as the transitive closure of the relation α • :

x i-1 ∈ α • (x i ) ⇔ D i-1 x i-1 ⊆ D i x i σ i
where the orbit represented by

x i ∈ X i is denoted by D i x i
and let α = α ∪ (x, x).

Then |X| = (X, α) is an n-dimensional chain of surfaces.

Proof.

1. By construction of α, |X| is obviously an order;

2. Let x i be a main cell of |X|. As the chain of maps is without multiincidence, σ i induces an isomorphism between the canonical boundary of x i , i.e. gmap (D i |x i , α i 0 , . . . , α i i-1 ), which is a closed connected (i -1)gmap without multi-incidence and the (i -1)-gmap corresponding to the boundary of x i . As the canonical boundary is a closed connected gmap without multi-incidence, α (x i ) is hence an (i -1)-surface [START_REF] Alayrangues | Equivalence between closed connected n-g-maps without multi-incidence and n-surfaces[END_REF]. Note also that the switch i k -operators, k ∈ {1, . . . , i -1}, naturally induced on each |α(x i )| are deeply related to the α i k involutions of the corresponding map (see [START_REF] Brisson | Representing geometric structures in d dimensions: topology and order[END_REF]). Lemma 3. Constructions described in lemma 1 and lemma 2 are inverse to each other up to isomorphism.

Proof. Actually, the first construction builds a chain of maps whose set of icells is in bijection with the set of {α(x i ), x i ∈ X} of the chain of surfaces. The second construction builds a chain of surfaces whose set of i-cells is in bijection with the set of i-cells of the chains of maps and there is a straightforward bijection between the set of i-cells and the set of α-adherences of i-cells. Moreover two darts of G i related by some α k correspond to two i-α • -chains of the corresponding chain of surfaces related by switch i k and reciprocally.

An obvious consequence of the three previous lemmas is:

Theorem 1. A one-to-one mapping exists between the set of chains of surfaces and the set of chains of maps without multi-incidence.

This equivalence leads to useful properties.

Prop 3.1.

Let C = ((D i , α i 0 , . . . , α i i-1 , α i i = ω) i∈{0,...,n} , {σ i } i∈{1,...,n} ) and |X| = (X, α) be equivalent n-dimensional chain of maps without multi-incidence and n-dimensional chain of surfaces, then the following properties hold:

1. ∀i ∈ {1, . . . , n}, ∀k ∈ {0, . . . , i -1}, x k ∈ α(x i ) ⇔ D k x k ⊆ D i x i σ i σ i-1 . . . σ k+1 ; 2. ∀p ∈ {1, . . . , n}, (p + 1)-α-chain (x k0 , . . . , x kp ) ⇔ K p -{k0,...,kp} (d) ⊆ D kp
x kp where K p = [0, . . . , k p ] and d corresponds to a (k p + 1)-α • -chain containing (x k0 , . . . , x kp ); 3. ∀p ∈ {1, . . . , n}, ∀k ∈ {1, . . . , p}, if d p corresponds to the (p + 1)chain (x 0 , . . . , x p ) then d p σ p . . . σ k+1 corresponds to the (k + 1)-chain (x 0 , . . . , x k ).

Proof.

1. directly comes from transitivity of α and point 2 of lemma 2;

chain of surfaces chain of maps (X, α) (G i i∈{0,...,n} , σ i i∈{1,...,n} )

α(x i ) connected component of G i : D i α(x i ) x i i-cell x k ∈ α(x i ) D k x k ⊆ D i x i σ i σ i-1 . . . σ k+1 (i + 1)-α • -chain (x 0 , . . . , x i ) d i ∈ D i switch i k α i k (p + 1)-α-chain (x k0 , . . . , x kp ) α kp k k∈K p \{k0,••• ,kp} ⊆ D kp x kp switch kp k k∈K p \{k0,••• ,kp}
where K p = [0, . . . , k p ] where K p = [0, . . . , k p ] Table 1: Correspondence between equivalent chain of surfaces and chain of maps.

2. directly comes points 1 and 2 of lemma 1;

3. is highly related to point 1.

The correspondences between a chain of surfaces and a chain of maps representing the same subdivision are displayed on table 1.

Simplicial analogs of chains of surfaces and chains of maps 4.1 Simplicial structures

Definition 9 (abstract simplicial complex [START_REF] Agoston | Algebraic Topology, a first course[END_REF]). An abstract simplicial complex (V, ∆) is a set of vertices V together with a family ∆ of finite non-empty subsets of V , called simplices, such that

∅ = τ ⊆ σ ∈ ∆ implies τ ∈ ∆.
The dimension of a simplex σ in ∆, dim ∆ (σ) is its cardinality less 1.

Definition 10 (semi-simplicial set [START_REF] May | Simplicial objects in algebraic topology[END_REF]). An n-dimensional semi-simplicial set S = (K, (d j ) j=0,...,n ) is defined by: • K = i=0,...,n K i , where K i is a finite set of elements called i-simplices;

(a) (b) 0 (v1) 1 (e1) 1 (e2) 2 (f1) 3 (V) (c) (d)
• ∀j ∈ {0, . . . , n}, face operator d j : K -→ K is s.t.:

-∀i ∈ {1, . . . , n}, ∀j ∈ {0, . . . , i}, d j : K i -→ K i-1 ; ∀j > i, d j is undefined on K i , and no face operator is defined on K 0 ;

-∀i ∈ {2, . . . , n}, ∀j, k ∈ {0, . . . , i}, d j d k = d k d j-1 for k < j.

Semi-simplicial sets allow multi-incidence, but not abstract simplicial complexes. Given an abstract simplicial complex, it is possible to associate a semisimplicial set with it, by defining an order on the vertices, and associating a sequence of vertices with each simplex. An abstract simplex is then associated with each sequence of vertices, and the boundary operators can directly be deduced from the ordering of vertices10 (cf. Fig. 5(a), Fig. 5(b)).

Simplicial analogs

Usually any order is associated with a simplicial interpretation built on the α-chains of the order [START_REF] Daragon | Discrete frontiers[END_REF] (see Fig. 5(c)). The order complex of an order |X|, denoted by ∆(|X|) is a numbered abstract simplicial complex and it defines the topology of the order. Vertices of the order complex are exactly the elements of the order. And there is a bijection between the sets of k-simplices and the sets of k-α-chains. Obviously the incidence relations between simplices are deduced from the inclusion relations between α-chains. A numbering of the vertices exists, such that the vertices of each main i-simplex are numbered from 0 to i.

Labeling each element of a closed order with its implicit dimension provides such a numbering. Note that when the closed order is also pure, all main simplices are numbered from 0 to n. This numbering induces a notion of cell: an i-cell is defined by a 0-simplex σ numbered i and all the simplices of dimension 1 to i incident to σ which are numbered by integers lower than i. The cells make a partition of the numbered semi-simplicial set.

In a similar way, a numbered semi-simplicial set T (C) can be associated with any cmap C in the following way [START_REF] Elter | Cellular complexes as structured semi-simplicial sets[END_REF] (see Fig. 5(d)): let c i be an i-cell of C, d be a dart of c i , and I = [0, i]:

• For 0 ≤ j ≤ i, a j-dimensional simplex numbered {k 0 , • • • , k j-1 , i} is asso- ciated with the orbit I-{k0,••• ,kj-1,i} (d), denoted T ( I-{k0,••• ,kj-1,i} (d)); • if j ≥ 1; -T ( I-{k0,••• ,k l ,••• ,kj-1,i} (d))d l = T ( I-{k0,••• , kl ,••• ,kj-1,i} (d)), for any l, 0 ≤ l ≤ j -1; -T ( I-{k0,••• ,kj-1,i} (d))d j = T ( Kj-1-{k0,••• ,kj-1} (dσ i • • • σ kj-1+1 )), where K j-1 = [0, • • • , k j-1 ]. • 0-simplex T ( I-{i} (d)) is numbered i.
Note that α i is never taken into account for an i-cell: this is consistent with the fact that α i is undefined. Since gmaps are equivalent to a subclass of cmaps, it is possible to associate numbered semi-simplicial sets with gmaps. Such numbered semi-simplicial sets are called cellular quasi-manifolds [START_REF] Lienhardt | N-dimensional generalized combinatorial maps and cellular quasi-manifolds[END_REF]. They are precisely the structures that have so far been informally said to have "manifoldlike properties".

Equivalence between simplicial analogs

The topology of both (chains of) surfaces and (chains of) maps is directly related to their simplicial interpretation. It has been proved that the simplicial analogs of equivalent n-surfaces and n-gmaps are isomorphic [START_REF] Alayrangues | Equivalence between closed connected n-g-maps without multi-incidence and n-surfaces[END_REF]. We focus here on equivalent chains of surfaces and cmaps. It means that there is no multiincidence in the associated subdivision, and that associated numbered simplicial sets are numbered simplicial complexes.

Theorem 2. The simplicial analogs of a chain of surfaces and of its equivalent cmap without multi-incidence are isomorphic.

Proof.

The numbered simplices associated with incidence graph are built on its α-chains, whereas numbered simplices associated with a cmap are built on orbits of darts. More precisely a numbered j-simplex of a chain of surfaces is a (j + 1)-α-chain, (x k0 , . . . , x kj-1 , x i ), which is naturally included in α(x i ). Let us recall that the number of each vertex is the rank of the corresponding element abstract simplicial complex chain of surfaces cmap (X, α)

(G i i∈{0,...,n} , σ i i∈{1,...,n} ) j-simplex (x k0 , . . . , x kj-1 , x i ) I-{k0,••• ,kj-1,i} (D i α(x i ) )
Table 2: Simplicial correspondence between equivalent chain of surfaces and cmap.

in the order, i.e. the simplex is numbered {k 0 , . . . , k j-1 , i}. A j-simplex of a cmap, numbered (k 0 , . . . , k j-1 , i), is an orbit

I-{k0,••• ,kj-1,i} of D i α(x i )
, where

I = [0, • • • , i].
According to property 3.1.2, there is hence a bijection between the set of i-simplices associated with a chain of surfaces and the set of i-simplices associated with its corresponding cmaps (see table 2).

Face relations between simplices are preserved by this bijection. Let S j S = (x k0 , . . . , x kj-1 , x i ) and S j M = T ( I-{k0,••• ,kj-1,i} (d i )) be two corresponding simplices respectively associated with a chain of surfaces and an equivalent cmap. The face of S j S , obtained through d l -operator, l ∈ {k 0 , . . . , k kj-1 , i} is the (j -1)-simplex obtained by removing x l from S j S . When l = i, the smallest cell of the subdivision containing the (j -1)-simplex remains x i . The image of this j-α-chain is simply the orbit

I-{k0,••• , l,••• ,kj-1,i} (d i ). The corresponding simplex is hence T ( I-{k0,••• , l,••• ,kj-1,i} (d i )), which is equal to T ( I-{k0,••• ,kj-1,i} (d i ))d l .
When l = i, then the smallest cell of the subdivision containing the (j -1)-simplex is x kj-1 . The image of (x k0 , . . . , x kj-1 ) is the orbit

[0,kj-1]-{k0,••• ,kj-1} (d kj-1 ) where d kj-1 = d i σ i σ i-1 . . . σ kj-1+1 .

Equivalence of homologies 5.1 Homology

For each dimension i = 0..n, the i th homology group H i of an nD object characterizes its i-dimensional holes (connected components for H 0 , tunnels for H 1 , cavities for H 2 ...) [START_REF] Munkres | Elements of Algebraic Topology[END_REF]. Homology groups are defined from a chain com-

plex (C * , ∂), i.e. a sequence C n ∂n -→ C n-1 ∂n-1 -→ • • • ∂1 -→ C 0 ∂0 -→ 0, where C * = (C i ) i=0,.
..,n is a family of abelian groups and ∂ = (∂ i ) i=0,...,n is a family of (boundary) homomorphisms satisfying ∂∂ = 0.

A chain complex can be associated with a subdivided object A in the following way: each chain group C i is generated by all the i-cells of A. The boundary homomorphisms are defined over chains of cells as linear extensions of the basic boundary operators defined for each cell.

A cycle z is a chain satisfying z∂ = 0, a chain b is a boundary if there exists a chain c satisfying c∂ = b. The set Z i of i-cycles (resp. B i of i-boundaries) equipped with the addition is a subgroup of C i (resp. Z i , since ∂∂ = 0). H i is the quotient group Z i /B i .

Homology groups are finitely generated abelian groups, so the following theorem describes their structure [START_REF] Hatcher | Algebraic Topology[END_REF].

Every finitely generated abelian group G is isomorphic to a direct sum of the form:

Z ⊕ ... ⊕ Z β ⊕Z/t 1 Z ⊕ ... ⊕ Z/t k Z.
where 1 < t i ∈ Z and t i divides t i+1 .

The rank β of a homology group is also called its Betti number, and the t i are its torsion coefficients.

Homology groups can be computed with any coefficient group (e.g. homology on Z/2Z or Q). The universal coefficient theorem [START_REF] Hatcher | Algebraic Topology[END_REF] ensures that all the homological information is contained in homology groups with coefficients in Z. But for optimisation purposes, it may be useful to compute them with other coefficients. In particular, homology groups over Z/2Z are isomorphic to homology groups over Z for torsion-free objects.

Cellular homology of incidence graphs

We study the definition of a boundary operator for chains of surfaces. We distinguish between homology over Z and homology over Z/2Z, since it is necessary to restrict the set of chains of surfaces in the first case. The corresponding homology is referred to as cellular homology.

Definition 11 (chain groups associated with a chain of surfaces). Let |X| be a chain of surfaces.

C * = {C i } i=0,...,n is a family of chain groups associated with |X|, such that each C i is an additive group generated by the elements of X i (i.e. the i-cells of the chain of surfaces).

In the sequel, such groups are defined with coefficients over Z/2Z (unsigned case) or Z (signed case).

Definition 12 (∂ G operator on chain groups). Let |X| be a chain of surfaces on which a function acts, that associates with each pair of cells (x i , x i-1 ) its "incidence number" denoted by (x i : x i-1 ). Let C * = {C i } i=0,...,n be the family of chain groups associated with C. Operator ∂ i is the linear extension of the operator acting on the i-cells of X i , which is defined by:

x i ∂ = x i-1 ∈α • (x i ) (x i : x i-1 )x i-1 ∂ G denotes {∂ i : C i -→ C i-1 } i=0,...,n .

Unsigned boundary operator

The unsigned incidence number counts the number of times a cell is incident to another. As subdivisions encoded by incidence graphs cannot contain any multi-incidence, the value of the unsigned incidence number for any couple of consecutive cells is either 1 or 0, depending on whether one cell belongs to the boundary of the other or not.

Definition 13 (unsigned incidence number). Let |X| be a k-dimensional chain of surfaces, let x i and x i-1 be two elements of X, the unsigned incidence number, (x i : x i-1 ) is defined to be equal to 1 if

x i-1 ∈ α • (x i ), else it is equal to 0.
Let ∂ G be the boundary operator (according to definition 12). We have hence the following property: Prop 5.1. Let i ∈ {1, . . . , n}. Let x i be an i-dimensional cell of a chain of surfaces |X|,

x i ∂ G = x i-1 ∈α • (x i ) x i-1
with the sum done over Z/2Z. Operator ∂ G is extended by linearity upon any sum of cells of |X|.

∂ G is a boundary operator on

|X| (i.e. ∂ G ∂ G = 0).
Proof. Let x i be an element of a k-dimensional chain of surfaces:

x i ∂ G = x i-1 ∈α • (x i ) x i-1 x i ∂ G ∂ G = x i-1 ∈α • (x i ) (x i-1 ∂ G ) = x i-1 ∈α • (x i ) x i-2 ∈α • (x i-1 )
x i-2

The switch-property says that each element x i-2 incident to x i , is incident to exactly two (i -1)-elements of α • (x i ). It implies that x i-2 is present exactly twice in the boundary of x i , one for each (i -1)-element it is incident to. As coefficients of ∂ G belong to Z/2Z, the sum is hence equal to 0.

Signed boundary operator

The signed incidence number describes not only the number of times a cell is incident to another but also the relative orientations of both cells. It has hence to be defined on subdivisions whose cells can have an orientation. Definition 14 (oriented cell). (cf. Fig. 6) Let |X| be a k-dimensional chain of surfaces, and x i be an element of |X|, x i is oriented by adding a + ormark on each α • -relation of α(x). The marked α • -relation between x i and x i-1 is denoted by sg (x i , x i-1 ) 11 . The inductive orientation process is (cf. Fig. 7):

∀i ≥ 2, ∀x i-2 ∈ α(x i ), let {x i-1 , x i-1 } = β (x i-2 ) ∩ α (x i ), then sg (x i , x i-1 ).sg (x i-1 , x i-2 ) = -sg (x i , x i-1 ).sg (x i-1 , x i-2 )
11 According to the context, the value of sg (x i , x i-1 ) is + or -, or +1 or -1.

x i is orientable if and only if such a mark can be consistently added on each α • -relation 12 .

We can show (cf. section 5.4.2) that this definition is equivalent to that given in [START_REF] Basak | Combinatorial cell complexes and poincaré duality[END_REF] for combinatorial cell complexes (where the definition is closer to that of gmaps orientability: cf. section 2). Note also that cells are always orientable for incidence graphs corresponding to regular CW -complexes (cf. theorem 3.1 in [START_REF] Dlotko | Coreduction homology algorithm for regular cw-complexes[END_REF]). We restrict here to chains of surfaces satisfying the following condition: for all i, all i-cells are orientable.

A B E F A C D A B D B C B F E B F E A F D E B D E B E ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ (a) A B C D E F (b)
Definition 15 (signed incidence number). Let |X| be a k-dimensional chain of surfaces. Let x i and x i-1 be two oriented elements of X, the incidence number,

(x i : x i-1 ) is equal to 0 if x i-1 ∈ α • (x i ), else (x i : x i-1 ) = sg(x i , x i-1
).

On subdivisions represented by incidence graphs where cells cannot be multiply incident to each other, the value of the signed incidence number between two cells is equal to either -1, 1, or 0. Prop 5.2. Let i ∈ {1, . . . , n}. Let x i be an i-dimensional cell of a chain of surfaces |X| whose cells are all orientable,

x i ∂ G = x i-1 ∈α • (x i ) sg(x i , x i-1 )x i-1
with the sum done over Z. Operator ∂ G is extended by linearity upon any sum of cells of |X|.

∂ G is a boundary operator on

|X| (i.e. ∂ G ∂ G = 0).

Proof.

The proof is similar to that given in [START_REF] Basak | Combinatorial cell complexes and poincaré duality[END_REF]. The key argument is the fact that since each i-dimensional cell x i is orientable, the coefficient of each

(i -2)-dimensional cell x i-2 which appears x i ∂ G ∂ G is hence (x i : x i-1 )(x i-1 : x i-2 ) + (x i : x i-1 )(x i-1 : x i-2 ) = 0
, where x i-1 and x i-1 are the two (i -1)-dimensional cells incident to both x i and x i-2 (cf. definition 14).

Algorithm

The signed incidence number linking two incident cells is directly deduced from their relative orientation. Hence we can define an algorithm for computing incidence numbers while assigning an orientation to each cell of the subdivision. Therefore, the computations of orientations and of incidence matrices are achieved during the same traversal of the graph. The algorithm begins with elements of rank 0 and successively computes the incidence numbers of every element of rank i for i growing from 0 to the dimension of the subdivision. To initialize the process, each 0-element is equipped with a positive orientation by assigning the value 1 to the incidence relation between each 0-element and x -1 . The main procedure consists in computing the orientation of an i-cell and the corresponding row of the i th incidence matrix (cf. Procedure compute E i Row page 26). The principle follows definition 14, and it is close to that of the algorithm presented in [START_REF] Dlotko | Coreduction homology algorithm for regular cw-complexes[END_REF]. But here, we have also to detect non-orientable cells (and thus to check all diamond configurations). If such a cell is found, the process must stop. Hence, the algorithm consists in:

1. fix a sign in the boundary of x i , i.e. mark an α • -relation with sign + for instance;

2. go through all diamonds rooted at x i having at least one signed branch (see Figure 7).

Two cases may occur:

(a) One branch in the diamond has not yet been equipped with a sign. Its sign is computed applying definition 14;

(b) Both branches are already signed. If signs are not consistent, then a non orientable cell has been detected.

The traversal has to grant that at least one branch of the current diamond has already a sign (to be able to complete the signing) and that all diamonds are traversed in a finite number of steps.

Remind that when dealing with the signing of the boundary of some x i , the boundaries of all its x i-1 -faces have already been signed. Point 1 is achieved by randomly picking an (i -1)-element in the boundary of x i , says x i-1 , and assigning a + sign to the branch x i , x i-1 . Each diamond built on x i and x i-1 has then a fully signed branch : x i , x i-1 , some x i-2 belonging to α • (x i-1 ) and, due to switch-property, one and only one partial signed one :

x i , β • (x i-2 ) ∩ α • (x i )\{x i-1 }, x i-2 .
There exists actually k such diamonds in α(x i ), k being the cardinal of α • (x i-1 ). Any of these k diamonds can be fully signed. Let us choose one, say x i-2 and sign the associated diamond. The signing process is well initiated.

To achieve Point 2, note first that traversing all diamonds built on x i is equivalent to traversing all (i -2)-elements of α(x i ) once, because, due to switchproperty, there is a bijection between the set of diamonds rooted at x i and this set of (i -2)-elements. We have hence to grant that all (i -2)-elements belonging to α(x i ) are traversed exactly once. Let us now prove that our algorithm completes the task.

Property 2.4 page 9 guarantees that the suborder built on all (i -1)-and (i -2)-elements of α(x i ) is connected. Of course, each path in this suborder is an alternating sequence of (i -1)-and (i -2)-cells. Our algorithm implictly builds all paths in the suborder beginning at the x i-1 chosen in the first step. It ensures hence that all (i -2)-elements belonging to α(x i ) are found.

Let us prove that our algorithm grants that an (i -2)-element cannot be treated more than once. The set of (i -2)-cells is initialized with the strict α-adherence of an (i -1)-element arbitrarily chosen in α(x i ). At each iteration, an (i -2)-cell of the current set is arbitrarily picked to be treated and removed from the set. Let x i-2 be the (i -2)-cell treated by the current iteration. There are exaclty two (i -1)-cells in the α-adherence of x i , say x i-1 and x i-1 , having x i-2 in their α-adherence. At the end of the iteration, the treated diamond is fully signed which means that the values of E i (x i , x i-1 ) and E i (x i , x i-1 ) have been computed. Otherwise said, whenever x i-1 and x i-1 are encountered again, no element will be added to the set of (i -2)-cells (see "else" branch, line 14 of the algorithm). Moreover at each iteration the set of (i -2)-cells is at most enriched with the (i -2)-cells belonging to one of the (i -1)-cells having the current (i -2)-cell in their α-adherence. Hence x i-2 will never be added again to the set of (i -2)-cells.

Roughly speaking, our algorithm is equivalent to a breadth first search algorithm where an (i -1)-cell is implictly marked when the branch relating it to the i-cell is given a sign and where (i -2)-cells need not been explictly marked because, due to properties of the graph, they can be at most encountered once during the traversal.

Cellular homology of chains of maps

The definitions and results presented here are stated in [START_REF] Alayrangues | A boundary operator for computing the homology of cellular structures[END_REF].

Procedure compute E i Row(x i , E i-1 ) ; Computation of the row of the i th incidence matrix of an n-dimensional chain of surfaces corresponding to a given i-cell, x i . The algorithm detects whether each cell is orientable. If this condition is not fulfilled the algorithm stops with an information message.

Data:

GI = (X ∪ {x -1 }, α • , β • ) ;
x i : i-cell of GI ; E i-1 : incidence matrix describing the incidence relations between (i -1)and (i -2)-cells;

Result: E i (x i , * ): row of E i describing the incidence relations of x i ; Variables:

x i-1 , x i-1 : (i -1)-cells belonging to α • (x i ) ; lesser C: (i -2)-cells belonging to the boundary of the current i-cell ;

1 x i-1 ←-pickCell(α • (x i )) ; 2 E i (x i , x i-1 ) ←-1; 3 lesser C ←-α • (x i-1 ) ; 4 while (lesser C = ∅) do 5 x i-2 ←-pickCell(lesser C); 6 lesser C ←-lesser C\{x i-2 }; 7 (x i-1 , x i-1 ) ←-β • (x i-2 ) ∩ α • (x i ); 8 if E i (x i , x i-1
) not defined then 9 swap(x i-1 , x i-1 );

10 end 11 if E i (x i , x i-1 ) not defined then 12 E i (x i , x i-1 ) ←- (-1) * E i (x i , x i-1 ) * E i-1 (x i-1 , x i-2 ) * E i-1 (x i-1 , x i-2 ); 13 lesser C ←-lesser C ∪ (α • (x i-1 )\{x i-2 }); 14 else 15 if E i (x i , x i-1 ) * E i-1 (x i-1 , x i-2 ) = -E i (x i , x i-1 ) * E i-1 (x i-1 , x i-2 ) then 16
exit(the cell is non orientable.) ;

(c i : c i-1 ) = (c i (d i ) : c i-1 (d i-1 )) = card((σ i ) -1 (d i-1 ) ∩ c i (d i ))(mod 2)
where d i and d i-1 are darts of respectively c i and c i-1 , and (σ i ) -1 (d i-1 ) denotes the set of darts which have d i-1 as image by σ i .

In other words, the number of times an (i -1)-cell c i-1 appears in the boundary of an i-cell c i is, given a dart d i-1 of c i-1 , the number of darts of c i which have d i-1 as image by σ i .

Let ∂ M be the corresponding boundary operator, according to definition 12. Chains of maps without multi-incidence satisfy the condition under which ∂ M ∂ M = 0 13 , so ∂ M defines a (cellular) homology on cmaps without multiincidence, with coefficients in Z/2Z.

Signed boundary operator

We restrict here to cmaps without multi-incidence satisfying the following cell orientability condition: for all i, all i-cells are orientable 14 .

A possible way for representing this property consists in associating a sign (+ or -) with any dart d (denoted sg(d)), such that sg(d) = sg(dα i j )∀j. In practice, this can be done easily during a traversal of the whole chain of map, i.e. in a linear time according to the number of darts.

Definition 17 (signed incidence number). Let C be a cmap, and let i ∈ {1, . . . , n}. Let c i (d i ) and c i-1 (d i-1 ) be two cells of C. The signed incidence number, (c i (d i ) : c i-1 (d i-1 )), is equal to n + -n -, where: n + is the number of preimages (related to σ i ) of d i-1 in c i whose sign is equal to sg(d i-1 ), n -is the number of preimages (related to σ i ) of d i-1 in c i whose sign is different from sg(d i-1 ). cmaps without multi-incidence satisfying the cell orientability condition satisfy the conditions under which the corresponding operator ∂ M is a boundary operator, i.e. ∂ M ∂ M = 0 (cf. [START_REF] Alayrangues | A boundary operator for computing the homology of cellular structures[END_REF]). So, this boundary operator defines a (cellular) homology on the corresponding set of cmaps, with coefficients in Z.

Equivalence with simplicial homology

We restrict here to cmaps without multi-incidence satisfying the following condition:

Definition 18 (Condition Eq). A cmap C satisfies condition Eq if and only if: 13 i.e. all involutions are without fixed points: cf. [START_REF] Alayrangues | A boundary operator for computing the homology of cellular structures[END_REF]. 14 An i-cell (D, α i 0 , . . . , α i i-1 , α i i = ω) is orientable iff its canonical boundary is orientable.

• C satisfies the cell orientability condition (for homology over Z);

• for each cell, the cmap corresponding to its canonical boundary has the homology of an (i -1)-dimensional sphere.

Theorem 3. Under condition Eq, the cellular homology of a cmap (over Z/2Z or over Z) is equivalent to the homology of its simplicial analog.

Equivalence of homologies

Proof.

As there is no multi-incidence in this context, the unsigned incidence number linking two cells is either equal to 1 or to 0. We proved that there is a bijection between the set of cells associated to a chain of surfaces and the set of cells associated to the corresponding cmap. We just need to show that the unsigned incidence number between any two cells is preserved through this bijection which grants that boundary operators are equivalent and lead to same homology.

First note that definition 16 of unsigned incidence number on cmap (page 27) implies that when there is no multi-incidence (c i (d i ) : c i-1 (d i-1 ) = 1 is equivalent to D i-1

x i-1 (d i-1 ) ⊆ D x i (d i ) σ i . The equivalence between both unsigned incidence numbers comes then from the fact that x i-1 ∈ α(x i ), i.e. (x i : x i-1 ) = 1 implies that D i-1

x i-1 ⊆ D i x i σ i and reciprocally.

Signed boundary operators equivalence

Lemma 5. Let CS be a chain of surfaces and CM be its equivalent cmap without multi-incidence. Then the chains complexes associated with CS and CM (with coefficients in Z) are isomorphic.

Proof.

Like above, there is no multi-incidence, and the signed incidence number linking two cells is either equal to 1, -1 or 0. The value of this number depends on the value of the unsigned incidence number and on the relative orientation of both cells. We hence have to prove that orienting a chain of surfaces and a cmap lead to the same signed incidence number.

Orienting the cells of a chain of surfaces consists in marking each α • -relation with a + or a -. Based on these orientations, a sign can also be associated with each i-α • -chain as the product of all signs of α • -relations included in the chain. Due to the orientation process, two i-α • -chains obtained from one another by a switch k -operator, k ∈ {0, . . . , i -1}, have different signs. Indeed they differ only on one branch on the diamond configuration related to switch k . Otherwise said, the orientation of i-α • -chains leads to a consistent orientation of darts of D i .

On the contrary, let d i and d i-1 be two oriented darts of D i and D i-1 , such that d i σ i = d i-1 . Let x i and x i-1 be the cells corresponding to the connected component of D i and D i-1 respectively associated with d i and d i-1 . Let us mark the α • -relation between x i-1 and x i by the product of the signs of d i and d i-1 . Note that this sign does not depend on the chosen darts. Let us consider a diamond configuration i.e. four cells

x i-2 , x i-1 , x i-1 , x i such that {x i-1 , x i-1 } = β • (x i-2 ) ∩ α • (x i
). Let d i and d i be darts corresponding to two α-chains containing respectively x i-2 , x i-1 , x i , and x i-2 , x i-1 , x i . Let d i-1 , d i-1 be darts corresponding to both previous chains where x i was removed. And let d i-2 be the dart associated with the intersection of both chains and α(x i-2 ). By construction d i = d i α i i-1 . Both darts have hence opposite signs. Then:

sg (x i , x i-1 ) * sg (x i-1 , x i-2 ) + sg (x i , x i-1 ) * sg (x i-1 , x i-2 ) = (sg(d i ) * sg(d i-1 )) * (sg(d i-1 ) * sg(d i-2 )) +(sg(d i ) * sg(d i-1 )) * (sg(d i-1 ) * sg(d i-2 )) = sg(d i ) * sg(d i-2 ) + sg(d i ) * sg(d i-2 ) = 0
A consistent orientation has hence been defined on the chain of surfaces.

Correspondences between orientations chain of surfaces cmap

k=i k=1 sg(x k : x k-1 ) sg(d i ) where d i corresponds to (x 0 , x 1 , . . . , x i ) sg(x i : x i-1 ) sg(d i (x i )) * sg(d i-1 (x i-1 )) where d i-1 (x i-1 ) = d i (x i )σ i
The corresponding signed incidence numbers of CS and CM are hence equal.

Moreover definition 17 of signed incidence number on cmaps (page 27) can be simplified when there is no multi-incidence. In this context, the signed incidence number (c i : c i-1 ) is equal to 1 if there exists d i in c i such that d i σ i in c i-1 and sg(d i ) = sg(d i σ i ). It is equal to -1 if there exists d i in c i such that d i σ i in c i-1 and sg(d i ) = -sg(d i σ i ). Else it is equal to 0.

Consequences

Theorem 4. Let CS be a chain of surfaces and CM be its equivalent cmap without multi-incidence. Then their cellular homologies are equivalent. Moreover, under condition Eq, the cellular homology of a chain of surfaces is equivalent to its simplicial homology.

Proof. The first assertion of the theorem is a direct consequence of lemma 4 and lemma 5. The second assertion is a direct consequence of theorem 2 and theorem 3.

For practical use, note that condition Eq can be enounced directly on chain of surfaces.

Conclusion

The main result of this paper is the proof of the equivalence between two families of structures: chains of surfaces, a subclass of incidence graphs and chains of maps without multi-incidence, a subclass of combinatorial maps. This equivalence is obtained through the construction of explicit conversion operators. Such an equivalence is very useful to extend theoretical and practical results obtained on one structure onto the other. We illustrate this by defining a boundary operator and hence a cellular homology on chains of surfaces, using a work already achieved on chains of maps [START_REF] Alayrangues | A boundary operator for computing the homology of cellular structures[END_REF].

Note that chains of surfaces are very close to combinatorial cell complexes, independantly defined by Basak in [START_REF] Basak | Combinatorial cell complexes and poincaré duality[END_REF]. We quite naturally retrieve similar results about homology over Z. In particular, we retrieve the two conditions necessary for the equivalence to be true: the cell orientability condition and the equivalence of the homology of the boundary of each cell with the homology of a sphere 15 (corresponding in Basak's paper to acyclic cells 16 ). But our proof is completely different. Indeed, Basak shows how to transform the cellular structure into its simplicial analog by (combinatorial) barycentric triangulation. Our result is mainly obtained in an incremental way [START_REF] Alayrangues | A boundary operator for computing the homology of cellular structures[END_REF], by studying the properties of the basic operations which make it possible to construct any chain of maps.

Moreover, incidence graphs associated with regular CW -complexes[31, 14] make a subclass of chains of surfaces where condition Eq is always satisfied. Thus we retrieve also their results about homology. It can be interesting to generalize some results. For instance, some important notions such as duality can be useful within some classes (e.g. n-surfaces, which have, as said before, "manifold-like" properties). But, it may be difficult to define this notion, for instance for the 15 It is a condition on the canonical boundaries of cells for cmaps, thus on the boundaries of cells for cmaps without multi-incidence, since for such cmaps, the canonical boundary of each cell is isomorphic to the boundary of the cell: cf point 2 of definition 8. 16 An acyclic cell is a cell such that its closure has the cellular homology of a cone. So the boundary of the cell has the cellular homology of a sphere. subclass of n-surfaces which correspond to regular CW -complexes. Actually the dual of a regular "manifold-like" CW -complex is maybe not a regular CW -complex (see an example in Appendix).

Appendix

In the following, we describe an example of regular CW -complex C (Fig. 9) which dual C d (Fig. 8) is not a CW -complex. As the regular CW -complex is not embeddable in R 3 , we first describe its dual. Figure 8(b) describes the incidence relations between the volumes and the faces, and the boundaries of the volumes are represented in Fig. 8(c -d)(f -g). In particular, V4 is the outer volume and V1 is a cone on a torus, i.e. it is not a 3-ball as its boundary is a torus (so, the volume cannot be embedded into R 3 , even if it is possible for its boundary): thus C d is not a CW -complex. The whole incidence graph is represented in Fig. 8(e).

The incidence graph of the regular CW -complex C is obtained from Fig. 8(e) by exchanging relations α and β. C can be constructed by identifying the boundaries of four 3-dimensional balls v1, v2, v3 and v4 as described in Fig. 9.

  (a),Fig. 1(b),Fig. 1(c),Fig. 1(d)).

  Fig. 1(f),Fig. 1(g),Fig. 1(h)) and chains of surfaces (cf. Fig. 1(a),Fig. 1(b)), which avoid such configurations.

Figure 1 :

 1 Figure 1: (a) A subdivision of a part of the plane; the main cells are faces f 1, f 2 and f 3, and edge e9. (b) The corresponding DAG. (c) The suborder corresponding to α(f 1). (d) The suborder corresponding to θ(e5). (e) A non closed order, since the ranks of e2 and v are equal to 1 and 3, and no 2-dimensional cell is incident to both e2 and v. (f) A subdivision of a sphere. (g) The corresponding 2-surface. (h) | θ (e1) | = | θ (e2) | is a 1-surface. (i) edge e is incident to vertices v1, v2 and v3. (j) The corresponding order.

Figure 2 :

 2 Figure 2: (a) A cube v. (b) The suborder α(v) restricted to 1-and 2-dimensional cells is connected.

  Fig. 4(a)-Fig. 4(g)):

Figure 4 :

 4 Figure 4: (a) A subdivision of a part of the plane. (b) The corresponding 2-gmap. Darts are represented by points, α 0 by dashed lines, α 1 by full lines, α 2 by double lines. (c) The 2-gmap corresponding to the subdivision depicted on Fig. 1(f). (d) A subdivision of a sphere. (e) The corresponding 2-gmap. (f) A subdivision of the projective plane. (g) The corresponding 2-gmap. (h) The chain of maps corresponding to the subdivision depicted on Fig. 1(a). σ 1 is represented by arrows, σ 2 by double arrows. (i) The chain of maps corresponding to the 2-gmap depicted on Fig. 4(b). (j) The chain of maps corresponding to the 2-gmap depicted on Fig. 4(c).

Figure 5 :

 5 Figure 5: (a) A representation of an abstract simplicial complex which contains 3 main cells (2 triangles and an edge). (b) A corresponding semi-simplicial set. (c) The order complex corresponding to the order depicted on Fig. 1(e). It contains two main simplices corresponding to (v1, e1, f 1, v) and (v1, e2, v). (d) The order complex corresponding to the chains of surfaces depicted on Fig. 1(b) and to the cmap depicted on Fig. 4(h).

Figure 6 :

 6 Figure 6: (a) Orientation of the cells of a 2-dimensional chain of surfaces. (b) Corresponding orientation of the cells of the associated subdivision.

Figure 7 :

 7 Figure 7: Inductive orientation process according to the switch-property.

17 end 18 end 5 . 3 . 1

 1718531 Unsigned boundary operator Definition 16 (unsigned incidence number). Let i ∈ {1, . . . , n}. Let c i and c i-1 be two cells of a cmap C. The unsigned incidence number is

Figure 8 :

 8 Figure 8: (a) A representation of a subdivision C d made of four volumes. (b) The faces incident to each volume. The boundary of volume V1 (resp. V2, V3, V4) is represented in (f ) (resp. (d), (g), (c)). The incidence graph of C d is represented in (e).

Figure 9 :

 9 Figure 9: A regular CW -complex C, which dual is represented in Fig. 8. C is made of four volumes v1..v4, eight faces e1..e8, seven edges f 1..f 7 and four vertices V1.. V4. On (a) -(d), the boundaries of volumes v1, v2, v3, v4 ; on (a ) -(d ), the corresponding incidence graphs.

  Let CS be a chain of surfaces and CM be its equivalent cmap without multi-incidence. Then the chain complexes associated with CS and CM (with coefficients in Z/2Z) are isomorphic.

	5.4.1 Unsigned boundary operators equivalence
	Lemma 4.

For instance, when handling important subclasses of incidence graphs, as n-surfaces which are close to manifolds, the properties of these subclasses are not taken into account directly in the very definition of incidence graphs; so the operations have to check that they construct objects of these subclasses, and this may be difficult or computationally expensive.

Computing the homology over Z/2Z can be more efficient in practice, without loss of information when the object is torsion-free.

All these notions: main cells, star, boundary, etc. are defined in a similar way for other combinatorial models.

]a, b[ denotes the interval bounded by a and b excluded.

The subdivisions corresponding to n-surfaces have manifold-like properties and constitute a subset of pseudo-manifolds[START_REF] Agoston | Algebraic Topology, a first course[END_REF]: they are cellular quasi-manifolds[START_REF] Lienhardt | N-dimensional generalized combinatorial maps and cellular quasi-manifolds[END_REF], as described in section 4.

[START_REF] Bertrand | New notions for discrete topology[END_REF] In the remaining of the paper, the symbol representing an element of an order is superscripted by its rank whenever the dimension of the element has to be taken into account

i.e. σ i is a one-to-one mapping between the darts of the orbits, such that for any j, 0 ≤j ≤ i -2, α i j σ i = σ i α i-1 j. This condition is more restrictive than that given in[START_REF] Elter | Cellular complexes as structured semi-simplicial sets[END_REF].

For any i, face operator d i is defined in such a way that it corresponds to remove the i th vertex of the simplex.

Note that if a cell is orientable, then it can be equipped with two different orientations.