Sylvie Alayrangues
email: sylvie.alayrangues@xlim.fr

Guillaume Damiand
email: guillaume.damiand@liris.cnrs.fr

Pascal Lienhardt
email: pascal.lienhardt@xlim.fr

Samuel Peltier
email: samuel.peltier@xlim.fr

Homology of Cellular Structures Allowing Multi-incidence

Keywords: homology computation, boundary operator, combinatorial maps 1 Introduction

published or not. The documents may come

morphism between two topological spaces. So topological invariants (i.e. properties that are preserved by homeomorphisms) have been introduced: for instance, the number of connected components, the Euler characteristic, the fundamental group, the homology groups or the orientability. In particular, homology groups contain meaningful topological information (e.g. connected components, orientability of closed manifolds, Betti numbers) and are computable similarly in any dimension [START_REF] Agoston | Algebraic Topology, a first course[END_REF][START_REF] Hatcher | Algebraic Topology[END_REF]. Intuitively, these groups describe different kinds of "holes" (e.g. connected components, tunnels, cavities); generators of these groups provide a representation of the homological information. In practice, homology is often computed on combinatorial structures.

Many such structures exist. For some applications, e.g. reconstruction from point clouds, simplicial or cubical meshes generation, computation of Voronoï diagrams, it is sufficient to use structures as abstract simplicial complexes for simplicial complexes, or a subclass of incidence graphs for regular CW -complexes [START_REF] Fritsch | Cellular Structures in Topology[END_REF][START_REF] Massey | A Basic Course in Algebraic Topology[END_REF][START_REF] Dlotko | Coreduction homology algorithm for regular cw-complexes[END_REF]. In such applications, cells are usually convex ones. Thus, multiincidence between cells does not occur, and cells are homeomorphic to balls. So, operations applied on the structures that could introduce multi-incidence or alter the topology of the cells are forbidden. Under these strong assumptions, the classical definition of homology applies.

Our work takes place in another context. For some applications (e.g. constructive ones, as those addressed by commercial and free 3D modeling softwares), both previous properties cannot be taken for granted. Cells are not necessarily convex: this is the case when cells are embedded as parts of free-form curves, surfaces, etc; this can be the case when cells are embedded as parts of straight lines, planes, etc. A very basic construction operation consists in identifying cells (e.g. take a usual four sided sheet of paper and glue together two opposite sides; this consists in identifying the four initial vertices into two resulting vertices, the two opposite edges into one resulting edge). It is thus very easy to construct objects in which a cell is incident several times to another cell (e.g. the face corresponding to the sheet of paper is incident twice to an edge). Several higher-level operations can also produce such objects, which do not correspond to regular CW -complexes: cf. Fig. 1. So, more general structures have been defined to handle such objects, for instance in geometric modeling, algebraic topology, computational geometry, image analysis, etc., e.g.:

INTRODUCTION

-(semi-)simplicial sets, in which cells are simplices [START_REF] Hu | On the realizability of homotopy groups and their operations[END_REF][START_REF] May | Simplicial objects in algebraic topology[END_REF][START_REF] Lane | Homology. Classics in Mathematics[END_REF][START_REF] Lang | Simplicial sets and triangular patches[END_REF]; -cubical structures and simploidal sets, in which cells are products of simplices [Ser51, NSK + 02, KMM04, PFL09]; -cellular structures, in which cells are not so regular, and may not be topologically equivalent to a ball [Bau75, GS85, Wei86, DL89, GP90, Lie91, Spe91, Lie94, CCM97, BDF00, LL01, BDDV03, BSP + 05, MK05a, CMP06, DD08].

These many structures have been proved to be equivalent to structures derived from combinatorial maps [START_REF] Edmonds | A combinatorial representation for polyhedral surfaces[END_REF][START_REF] Jacque | Constellations et graphes topologiques[END_REF][START_REF] Tutte | Graph Theory. Encyclopaedia of Mathematics and its Applications[END_REF][START_REF] Vince | Combinatorial maps[END_REF]. Combinatorial maps represent a class of objects much wider than regular CW -complexes as their cells do not need to be homeomorphic to balls; cells in such structures can also be attached more loosely; moreover these structures are able to represent multiply incident cells. Operations on such structures can lead to complex topological changes of the represented object. For instance, even if each cell of the initial cellular subdivision is homeomorphic to a ball, one cannot take for granted that they still are after the application of a sequence of arbitrary operations. It is hence essential to control the topological evolution of an object at each step of its construction process. A partial control can be achieved through the computation of topological properties as homology. The problem is that homology theory is classically defined on CW -complexes and the structures we deal with are not. They are a superset of regular CW -complex. So, no homology theory has so far been defined on such structures. Moreover, we are not even able to characterize the subclass of combinatorial maps which are CW -complexes: as far as we know, no combinatorial characterization of balls exists. There even exist well-known topological spaces which are homologically equivalent to spheres but not homeomorphic to spheres, namely Poincaré homology sphere. The goal of our work is hence to study homology on combinatorial maps. And due to their similarities with them, our results can be straightforwardly transferred to all previously mentioned cellular structures.

More precisely we focus on homology computation for chains of maps [START_REF] Elter | Cellular complexes as structured semi-simplicial sets[END_REF], a cellular structure derived from combinatorial maps. First note that chains of maps have a simplicial interpretation: a semi-simplicial set can be associated with any chain of maps 1 (in a similar way, any incidence graph has a simplicial interpretation, which is an abstract simplicial complex). Note also that when the object associated with the chain of maps is a CW -complex, its simplicial analog is simply the barycentric subdivision of the CW -complex. So, a first approach for computing the homology of a cellular object would be to compute the homology of its associated simplicial object. But this option has the main disadvantage of losing the cellular optimization in terms of number of cells (there are less cells in a chain of maps than simplices in the associated semi-simplicial set) 2 .

Our objective is to follow a second approach consisting in taking advantage of the cell structuring. We are looking for optimization (regarding the number of cells), which means that we have to define a homology theory directly on the cellular structure. The main contribution of this work (Theorem 1 page 22) is:

1. INTRODUCTION S. Alayrangues et al.
to provide a subclass of chains of maps on which homology can be directly computed; -to prove that this homology is equivalent to the simplicial homology of its simplicial analog.

More precisely, two homologies are studied: homology with coefficients over Z/2Z and homology with coefficients over Z. The second one is obviously more general than the first one, and the distinction is simply made to clearly introduce the several conditions required to obtain the results. For instance, the first homology can be defined for a subclass of chains of maps which contains the subclass for which the second homology can be defined. Note also that the exhibited subclasses are characterized by combinatorial properties (Condition C3 page 21) that can be computed on any chain of maps.

To achieve this goal we first characterize a subclass of chains of maps on which a boundary operator can be constructed. This is also a contribution of this work as only subclasses of generalized maps were previously exhibited [START_REF] Alayrangues | Border operator for generalized maps[END_REF]. This subclass is still more general than regular CW -complexes. It contains regular CWcomplexes, CW -complexes which are not regular and even objects that are no CW -complexes at all. We prove then that under some constraints, the homology of a chain of maps induced by our boundary operator is equivalent to the homology of its simplicial analog.

We perform this work successively in two different frameworks. We first focus on Z/2Z homology, and study then homology over Z. It allows us to obtain a progressive presentation of our results in order to clearly identify the conditions for computing a homology3 and prove its equivalence with the simplicial one. Finally, we optimize our results on two important sub-classes of chains of maps: generalized maps and maps. Generalized maps (resp. maps) describe the topology of manifold-like cellular objects (resp. orientable manifold-like without boundaries). We retrieve here partial results obtained previously for generalized maps, presented in [START_REF] Alayrangues | Border operator for generalized maps[END_REF].

The paper is organized as follows: Section 2 covers the whole background of the paper. It briefly recalls essential notions about homology theory and associated computation methods (Subsection 2.1). Then it presents the combinatorial structures that are used in this work: semi-simplicial sets in Subsection 2.2, generalized maps and chains of maps in Subsection 2.3. This presentation ends in Subsection 2.4 with the simplicial interpretation that can be associated with generalized maps and chains of maps. In order to obtain a progressive presentation and improve the clarity of the discussion, we first define a subclass of chains of maps on which a boundary operator, and hence a homology, can be defined (Section 3). A more restricted subclass is then defined (Section 4) on which the computed homology is equivalent to the simplicial one. More precisely, in Section 3, the notion of unsigned incidence number is defined and proved to lead to a consistent boundary operator over Z/2Z (Subsection 3.1). Afterwards, this notion is extended to signed incidence number and a boundary operator over Z is obtained (Subsection 3.2). Algorithms for computing incidence numbers are provided in Subsection 3.3. Then, the proof of the equivalence between the cellular homology defined on chains of maps and the classical simplicial one is detailed in Section 4. It is based on the correspondence between cellular and simplicial chains. We show that this correspondence preserves both cycles and boundaries under specific conditions. Section 5 presents optimizations of our results for more specialized structures: generalized maps in Subsection 5.1 and maps in Subsection 5.2. Finally, we conclude and give some insight into future works in Section 6.

Background

Homology

Among all the existing topological invariants, we focus on homology groups which are classically studied in algebraic topology [START_REF] Munkres | Elements of Algebraic Topology[END_REF]. For each dimension i = 0, . . . , n, the i th homology group H i of an n-dimensional object (or nD object) characterizes its i-dimensional holes (e.g. connected components for H 0 , tunnels for H 1 , cavities for H 2 ). From a computational point of view, homology groups are defined in the same way in any dimension from the boundaries of the cells.

Chain complex, cycles, boundaries, homology groups

Homology groups are defined from an algebraic structure called a chain complex, i.e. a sequence

Cn ∂n -→ C n-1 ∂n-1 -→ • • • ∂1 -→ C 0 ∂0
-→ 0 of (boundary) homomorphisms of abelian groups, called chain groups, satisfying4 ∂∂ = 0. Such a chain complex is denoted by (C * , ∂), where C * denotes the family of chain groups. A chain complex can be associated with a subdivided object O in the following way: each chain group C i is generated by all the i-cells of O. The boundary homomorphisms are defined over chains of cells as linear extensions of the basic boundary operators defined on the cells.

Among all the possible chains, homology consider two particular kinds of chains: cycles and boundaries. A cycle z is a chain satisfying5 z∂ = 0. A chain b is a boundary iff there exists a chain c satisfying c∂ = b. The set of i-cycles equipped with the addition is a subgroup of C i , denoted Z i . The set of i-boundaries equipped with the addition is a subgroup of Z i , denoted B i (a boundary is a cycle as ∂∂ = 0).

Homology groups H i are defined as the quotient groups Z i /B i . So the elements of the homology group H i are equivalence classes such that two cycles are in the same equivalence class if they differ by a boundary (two such cycles are homologous).

The algebraic notions of chain, cycle, boundary, and homology generator, are illustrated on Fig. 2.

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 an homology group is also called its Betti number, and the t i are its torsion coefficients.

Computing homology

Depending on what is expected, "computing homology" may have different meanings. For example, the number of i-dimensional holes of a given object is completely defined by the Betti numbers and the torsion coefficients. But in case homology generators are needed, these numbers are not enough: cycles have to be explicitly computed as representatives of each group.

In the previous section, it was implicit that all the chains are considered with coefficients over Z, but 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 optimization 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.

Several algorithms have been designed to compute Betti numbers, torsion coefficients and eventually homology groups generators. The most classical approach is based on reductions of incidence matrices into their Smith Normal Form [START_REF] Agoston | Algebraic Topology, a first course[END_REF][START_REF] Munkres | Elements of Algebraic Topology[END_REF][START_REF] Kannan | Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix[END_REF][START_REF] Peltier | Computation of homology groups and generators[END_REF]. Generally the incidence matrices of the whole object are handled, involving high computational cost and memory issues since huge integers may occur during the computational process [START_REF] Kannan | Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix[END_REF]. Many works aim at optimizing this process [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]. Others aim at simplifying the structure while preserving its topology [DKMW10, GDJMR09, KMS98, KMM04]. Some works follow an incremental constructive approach [START_REF] Damiand | Computing Homology Generators for Volumes Using Minimal Generalized Maps[END_REF][START_REF] Delfinado | An incremental algorithm for betti numbers of simplicial complexes on the 3-sphere[END_REF]. More recently, persistent homology theory has been introduced [START_REF] Edelsbrunner | Topological persistence and simplification[END_REF] and allows to describe the topology of an object at different scales. In particular, persistent homology led to the notion of localized homology for computing "nice" generators [START_REF] Zomorodian | Localized homology[END_REF].

Simplicial structures

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 τ ∈ ∆ [START_REF] Agoston | Algebraic Topology, a first course[END_REF]. Simplex τ is a proper face of simplex σ iff τ ⊂ σ. The boundary of σ is the set of its proper faces. The star of σ is the set of simplices of which σ is a proper face. σ is a main simplex iff its star is empty6 .

Abstract simplicial complexes are widely used in geometric modeling, computational geometry, etc. For instance, the abstract simplicial complex fully defined by its main simplices: {{B}, {A, F }, {C, D, E}, {E, F, G}} is geometrically represented on Fig. 3(a). Definition 1 (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; -∀j ∈ {0, . . . , n}, face operator d j : K -→ K is s.t.7 :

-∀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 ;

commutation property of face operators: ∀i ∈ {2, . . . , n}, ∀j, k ∈ {0, . . . , i},

d j d k = d k d j-1 for k < j.
Simplex τ is a proper face of simplex σ if a non empty sequence of face operators

d i1 , • • • , d i k exists such that τ = σd i1 • • • d i k .
All notions of boundary, star, main simplex, etc. are defined in an obvious way.

When a numbering of the vertices exists, such that the vertices of each main i-simplex are numbered from 0 to i, then the semi-simplicial set equipped with such a numbering is called a numbered semi-simplicial set: cf. Fig. 8.

Semi-simplicial sets are more "flexible" than abstract simplicial complexes in the sense that they allow multi-incidence8 : for instance, a k-simplex can be incident to less than k + 1 vertices (cf. Fig. 3(b) and Fig. 3(e)), distinct simplices can have the same boundary (cf. Fig. 3(c) and Fig. 3(f)). So, it is not always possible to directly associate an abstract simplicial complex with a semi-simplicial set, but the converse is true: given an abstract simplicial complex, we can define an order on the vertices, and associate a sequence of vertices with each simplex (note that this induces an orientation for the simplices). An abstract simplex is then associated with each sequence of vertices, and the boundary operators can directly be deduced from this ordering9 (cf. Fig. 3(d); let σ be the 2-simplex corresponding to (C, D, E): then σd 0 (resp. σd 1 , σd 2 ) corresponds to (D, E) (resp. (C, E), (C, D))).

The definition of homology for simplicial objects is well-known: it consists in defining the chain groups (which is straightforward) and the boundary operators. These boundary operators are defined as linear extensions of basic boundary operators which act on simplices. For abstract simplicial complexes, we can define an homology on Z/2Z by defining the basic boundary operator in the following way:

{v 0 , • • • , v i , • • • , v k }∂ S = 0≤i≤k {v 0 , • • • , vi , • • • , v k }
where vi means that vertex v i is removed. For semi-simplicial sets, as said before, simplices are implicitly oriented, and we can define an homology on Z by defining the basic boundary operator as: σ∂ S = (-1) i σd i . Note that the commutation property of face operators has for consequence that ∂ S ∂ S = 0.We will follow this idea later for defining a homology for cellular structures: first defining a homology on Z/2Z, then adding an orientation of the cells for defining a homology on Z.

In the following, ∂ S denotes a simplicial boundary operator: no specific notation will be used to distinguish between boundary operators acting on Z/2Z or Z, on abstract simplicial complexes or semi-simplicial sets. The context is sufficient to achieve this distinction.

Chain of maps

Combinatorial maps based structures are by construction dedicated to the representation of manifold-like "cellular objects".They are used in different applications related to geometrical modeling as well as image analysis [BG88, BDF00, BDDV03, DBF04, BSP + 05, MK05b, CMP06, TGM + 09, BPA + 10, UCB13]. They are also known to be equivalent to other combinatorial structures, such as cell-tuples, facetedge, quad-edge for instance [START_REF] Brisson | Representing geometric structures in d dimensions: topology and order[END_REF][START_REF] Dobkin | Primitives for the manipulation of three-dimensional subdivisions[END_REF][START_REF] Guibas | Primitives for the manipulation of general subdivisions and the computation of voronoi diagrams[END_REF][START_REF] Lienhardt | Topological models for boundary representation: a comparison with n-dimensional generalized maps[END_REF]. Several families of combinatorial maps have been defined depending on the constraints imposed upon the arrangement of such cells.

Since cells can be multi-incident to each others, these structures are not constructed directly from the cells of the subdivision but from a more elementary object, called a dart (cf. Fig. 4(b)). The set of darts is structured through functions that describe how they are linked to each other (cf. Fig. 4 and Fig. 5). Such a representation provides an implicit description of cells as sets of darts and conveys hence a precise description of how the cells of the subdivision are attached together, even when cells are multi-incident to each others.

Chains of maps (cmaps), defined below, impose only few constraints on the way cells that are glued together. We first present generalized maps (gmaps), since they are involved in the definition of cmaps. For more details about gmaps and cmaps, see [START_REF] Lienhardt | N-dimensional generalized combinatorial maps and cellular quasimanifolds[END_REF] and [START_REF] Elter | Cellular complexes as structured semi-simplicial sets[END_REF].

gmaps

Definition 2 (gmap) Let n ≥ 0; an n-dimensional gmap, or n-gmap, is defined by an (n + 2)-tuple G = (D, α 0 , • • • , αn) such that: -D is a finite set of elements called darts; -∀i, 0 ≤ i ≤ n, α i : D → D is an involution 10 ; -∀i, 0 ≤ i ≤ n -2, ∀j, i + 2 ≤ j ≤ n, α i α j is an involution.
Examples of gmaps and related subdivisions are presented in Fig. 4 and Fig. 5. When there is no muti-incidence, a dart can be seen as a tuple of incident cells, and involution α i exchanges the i-cells of the corresponding tuples [START_REF] Brisson | Representing geometric structures in d dimensions: topology and order[END_REF] (cf. Fig. 6). Subdivisions encoded by gmaps are precisely what we have called so far "manifold-like" subdivisions and are formally known as "cellular quasi-manifolds" (see Subsection 2.4.1 and [START_REF] Lienhardt | N-dimensional generalized combinatorial maps and cellular quasimanifolds[END_REF]). From a practical point of view, gmaps can be seen as valued graphs, and several notions can be directly adapted (e.g. connected component). Dart d is a fixed point of involution α i iff dα i = d. When all involutions are without fixed points, the gmap is without boundaries. Two darts d 1 and d 2 are linked by α i iff d 1 α i = d 2 (and thus d 2 α i = d 1 ). We retrieve the notions of connected component and cell through the following notion of orbit. Orbit < α 0 , α 1 > (1) = {1, 2, 3, 4, 5, 6, 7, 8} corresponds to the face, incident to 4 edges (corresponding to the four orbits < α 0 , α 2 >, i.e. {1, 2}, {3, 4}, {5, 6}, {7, 8}), and to 4 vertices (corresponding to the 4 orbits < α 1 , α 2 >, i.e. {1, 8}, {2, 3}, {4, 5}, {6, 7}). (c) A 2-gmap corresponding to the cylinder represented in (d), made of 1 face, 3 edges ({1, 2}, {3, 4, 7, 8}, {5, 6}), and 2 vertices ({1, 2, 3, 8}, {4, 5, 6, 7}). (e) A 2-gmap corresponding to a torus (1 face, 2 edges {1, 2, 5, 6}, {3, 4, 7, 8} and 1 vertex). (f) A 2-gmap corresponding to a Klein bottle (1 face, 2 edges {1, 2, 5, 6}, {3, 4, 7, 8} and 1 vertex).

Definition 3 (orbit) Let Φ = {π 0 , • • • , πn} be a set of permutations defined on a set D. We denote

Φ = π 0 , • • • , πn = [0,n] the permutation group of D generated by Φ. The orbit of an element d ∈ D relatively to Φ , denoted Φ (d) is the set {dφ | φ ∈ Φ }. 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 d11 . The connected component of gmap G incident to dart d is the orbit α 0 , • • • , αn (d). For example, Figure 6(a) represents a 2-gmap with only one connected component. Figures 10(a) and 10(c) display 1-gmaps with respectively 7 and 2 connected components. The i-dimensional cell (or i-cell) incident to dart

d is the orbit α 0 , • • • , αi , • • • , αn (d)
, where αi denotes that involution α i is removed 12 . Two cells which share a dart are incident one to the other. When αn is the identity on D, the (n -1)-gmap (D, α 0 , . . . , α n-1 ) is the canonical boundary of the n-gmap (D, α 0 , . . . , αn). A connected n-gmap without boundaries is orientable if and only if it contains exactly two orbits α 0 α 1 , • • • , α 0 αn (cf. [START_REF] Lienhardt | N-dimensional generalized combinatorial maps and cellular quasimanifolds[END_REF] and Subsection 5.2). For instance the torus in Fig. 5(e) contains two orbits {1, 3, 5, 7} and {2, 4, 6, 8} for α 0 α 1 , α 0 α 2 , but the Klein bottle in Fig. 5(f) contains only one orbit {1, 2, 3, 4, 5, 6, 7, 8}.

Chains of maps

Definition 4 (cmap)

An n-dimensional cmap is a tuple C = ((G i ) i=0,...,n , (σ i ) i=1,...,n ) such that:

1. ∀i, 0 ≤ i ≤ n, G i = (D i , α i 0 , . . . , α i i-1 , α i i = ω) is an i-dimensional 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 13 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 .
In this definition, any connected component of an i-gmap is an i-dimensional cell, or i-cell (that is why α i i = ω is undefined: cf. simplicial interpretation of gmaps in Subsection 2.4.1). The canonical boundary of an i-cell (D ci , α i 0 , . . . ,

α i i-1 , α i i = ω) is (D ci , α i 0 , . . . , α i i-1
). The cells are linked by face operators σ i . Two cells are incident if a dart of one cell can be obtained starting from a dart of the other cell by successive applications of face operators. So, a cmap describes the topology of a subdivision in which cells are quasi-manifolds, linked along the cells of their boundaries (cf. Fig. 7). More precisely, any i-cell can be structured into orbits

α i 0 , • • • , α i
i-2 ; these orbits are linked with (i -1)-cells by operator σ i , defining the boundary of the i-cell. For instance, the 2-cells of the objects represented Fig. 7 are structured in order to correspond to the 1-cells of their boundaries, i.e. orbits α 2 0 , α 2 1 can be partitionned into orbits α 2 0 , which are linked with orbits α 1 0 by σ 2 . The fact that ∀i, σ i restricted to an orbit α i 0 , • • • , α i i-2 is an isomorphism between this orbit and an (i -1)-cell implies that there is a strong correspondence between the structure of the interior of a cell and the structure of its boundary, even when cells are multi-incident ones to the others. This means that there exists some redundancy which can be taken into account in order to reduce the amount of explicit information within a data structure. From a practical point of view, cmaps can be implemented as valued (oriented) graphs.

Simplicial interpretation of combinatorial maps

Simplicial interpretation of a gmap

It is not possible to associate directly a CW -complex with a gmap (or a cmap), since it is not possible to associate a topological ball with any cell14 . But a numbered semi-simplicial set T (G) can always be associated with any gmap G = (D, α 0 , • • • , αn), in the following way (cf. Fig. 8 and [START_REF] Lienhardt | N-dimensional generalized combinatorial maps and cellular quasimanifolds[END_REF]):

-Simplices. For 0 ≤ i ≤ n, an i-dimensional simplex is associated with any orbit N -{k0,••• ,ki} (d), denoted T ( N -{k0,••• ,ki} (d)), where d is a dart, 0 ≤ k 0 , • • • , k j ≤ n and N = {0, • • • , n} ; -Face operators (d l ) l∈[0,••• ,i] , if i ≥ 1; T ( N -{k0,••• ,k l ,••• ,ki} (d))d l = T ( N -{k0,••• , kl ,••• ,ki} (d)); -each 0-simplex T ( N -{i} (d)) is associated with i.
Note that the 0-simplices are numbered from 0 to n, and, for a given simplex

T ( N -{k0,••• ,ki} (d))
, all its incident 0-simplices are associated with distinct in- tegers k 0 , • • • , k i . 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. A numbered semi-simplicial set associated with a gmap is a cellular quasi-manifold. Note that a cellular quasi-manifold may not be a manifold (see Fig. 9(c)), but it is a pseudo-manifold: for more precisions about manifolds, pseudomanifolds and quasi-manifolds, see [START_REF] Agoston | Algebraic Topology, a first course[END_REF] and [START_REF] Lienhardt | N-dimensional generalized combinatorial maps and cellular quasimanifolds[END_REF]. Cellular quasi-manifolds can also be characterized constructively (cf. Fig. 10): a 0-dimensional cellular quasi-manifold is a collection of sets of one or two vertices. An n-dimensional cellular quasi-manifold containing isolated n-cells is obtained from an (n -1)-dimensional cellular quasi-manifold by cone operations over each connected component. The n-cells can then be glued together by identifying (n -1)-cells (and their boundaries) in such a way that there is at most two n-cells around an (n -1)-cell15 . 10 (a) A 1-gmap (D, α 0 , id) and its corresponding numbered semi-simplicial set. Each edge is a cone on a 0-sphere (i.e. two vertices, corresponding to two darts linked by α 0 ). (c) After identifications of 0-cells, we obtain a new 1-gmap (D, α 0 , α 1 ). Its corresponding numbered semi-simplicial set is represented in (d). (e) A 2-gmap (D, α 0 , α 1 , id) and its corresponding numbered semi-simplicial set on (f). Each 2-cell is a cone over a 1-sphere. Then, by identifying one edge of the square and one edge of the triangle, we obtain the 2-gmap represented in Fig. 6(a). Note that a simplified graphical representation of numbered semi-simplicial sets is used for (b), (d) and (f), i.e. the boundary of a cell is glued with the cell.

BACKGROUND

Simplicial interpretation of a chain of maps

A numbered semi-simplicial set T (C) can be associated with any cmap C in the following way (cf. Fig. 7(c) and [START_REF] Elter | Cellular complexes as structured semi-simplicial sets[END_REF]). 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 associated with the orbit I-{k0,••• ,kj-1,i} (d), denoted T ( I-{k0,••• ,kj-1,i} (d)); -if j ≥ 1; -for any l, 0 ≤ l ≤ j -1, T ( I-{k0,••• ,k l ,••• ,kj-1,i} (d))d l = T ( I-{k0,••• , kl ,••• ,kj-1,i} (d)); -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 (cf. Definition 4).

3 Boundary operator Definition 5 (chain groups associated with a cmap) Let C = ((G i ) i=0,...,n , (σ i ) i=1,...,n )) be a cmap. C * = {C i } i=0,...,n is a family of chain groups associated with C, such that each C i is an additive group generated by the connected components of G i (i.e. the i-cells of the cmap).

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

Notation: c i generally denotes an i-cell and when necessary, c i (d i ) specifies that c i is incident to dart d i .

Definition 6 (∂ M operator on chain groups)

Let C = ((G i ) i=0,...,n , (σ i ) i=1,...,n
)) be a cmap on which a function acts, that associates with each pair of cells (c i , c i-1 ) its "incidence number" denoted by (c i : c 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 G i , which is defined by:

c i ∂ i = c i-1 ∈G i-1 (c i : c i-1 )c i-1 ∂ M denotes {∂ i : C i -→ C i-1 } i=0,...,n .
In this section, we study under which conditions ∂ M is a boundary operator, i.e. ∂ M ∂ M = 0. This implies to restrict the set of cmaps which are taken into account (cf. Fig. 11). We also distinguish between homology over Z and homology over Z/2Z, since the corresponding subsets are distinct.

Unsigned boundary operator

Definition 7 (unsigned incidence number) Let i ∈ {1, . . . , n}. Let c i and c i-1 be two cells of the cmap C. The unsigned incidence number is

(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 . Since σ i restricted to an orbit α i 0 , • • • , α i i-2 is an isomorphism between this orbit and an (i -1)-cell (cf. Property 2a of Definition 4), this number is the same whereas the chosen dart d i-1 is16 . So the definition is consistent.

Also due to Property 2a of Definition 4, this number is equal to the number of orbits α i 0 , • • • , α i i-2 of c i which have c i-1 as image (since each dart which image by σ i is d i-1 identifies such an orbit). An alternative definition of the incidence number is then the following: let {p j } j=1•••k be a set of darts such that the orbits

{ α i 0 , • • • , α i i-2 (p j )} j=1•••k make a partition of c i , then (c i : c i-1 ) = card({p j , j = 1 • • • k|p j σ i ∈ c i-1 })mod2.
Let ∂ M be the corresponding operator, according to Definition 6. So we have the following property:

Property 1 Let i ∈ {1, . . . , n}. Let c i be a cell of the cmap C. Let {p j } j=1•••k be a set of darts such that the orbits { α i 0 , • • • , α i i-2 (p j )} j=1•••k make a partition of c i , c i ∂ M = pj ,j=1•••k c i-1 (p j σ i ),
and the sum is done upon Z/2Z. Operator ∂ M is extended upon any sum of cells by linearity.

We prove that under condition C1 below, ∂ M is a boundary operator, i.e. ∂ M ∂ M = 0. So, this boundary operator defines a homology on the corresponding set of cmaps, with coefficients in Z/2Z, which will be referred to as cellular homology.

Condition C1: C is a cmap such that all involutions are without fixed points.

The fact that all involutions are without fixed points implies that the boundary of each cell is "complete" (cf. couterexample in Fig. 11(a); note that the property is still satisfied under less restrictive conditions: cf. Fig. 11(c)). The cost of checking condition C1 is linear in the number of darts of the cmap times its dimension.

We restrict here to cmaps satisfying condition C1. A chain of simplices can be associated with any cell in the following way: Definition 8 Let C = ((G i ) i=0,...,n , (σ i ) i=1,...,n ) be a cmap, S be its associated semi-simplicial set, C * be the chain groups associated with C and (S * , ∂ S ) be the chain complex associated with S.

τ : C * → S * is defined by:

∀i, 0 ≤ i ≤ n, ∀c i ∈ G i , c i τ = d∈c i T ( (d)),
extended by linearity with coefficients in Z/2Z to the chains of C * .

Such a sum is an unsigned chain of cells.

Lemma 1 τ satisfies:

xτ ∂ S = x∂ M τ
for any unsigned chain of cells x of dimension greater than or equal to 1.

Proof We prove that any i-dimensional cell c i , with 1 ≤ i, satisfies c i τ ∂ S = c i ∂ M τ , and the lemma is deduced by linearity. c i τ is a chain of i-simplices; since all involutions of the cmap are without fixed points, all (i -1)-simplices "internal" to c i are incident to exactly two distinct i-simplices (cf. Fig. 7(c)). So, when taking the simplicial boundary of c i τ , all internal (i -1)-simplices vanish and we get the chain of (i -1)-simplices associated with c i ∂ M .

Lemma 2 τ associates a simplicial cycle (resp. boundary) with any cellular cycle (resp. boundary).

Proof Let z be a cellular cycle, i.e. z∂ M = 0. So z∂ M τ = 0 = zτ ∂ S , and zτ is a simplicial cycle. Let b, c i+1 be such that Proof First, we can show that, for any chain of cells x, xτ = 0 ⇒ x = 0, since the simplicial chain associated with a cell is not null, and the chains associated with two distinct cells are generated by sets of simplices the intersection of which is empty. Second, we can deduce from Lemma 1 that [START_REF] Alayrangues | A boundary operator for computing the homology of cellular structures[END_REF] in which a direct proof is provided, which does not use the equivalence between cmaps and semi-simplicial sets).

b = c i+1 ∂ M . Then bτ = c i+1 ∂ M τ = c i+1 τ ∂ S ,
x∂ M ∂ M τ = xτ ∂ S ∂ S = 0, since ∂ S satisfies ∂ S ∂ S = 0. Thus x∂ M ∂ M = 0 (see also

Signed boundary operator

We restrict here to cmaps satisfying the following condition denoted C2:

Condition C2: C is a cmap such that:

-C satisfies C1; -For all i, all i-cells are orientable 17 .

The orientability condition corresponds to the fact that all darts of any cell can be partitioned into two distinct subsets, such that if dart d belongs to one of these subsets, all darts dα i j belong to the other subset. A possible way for representing this property consists in associating a sign (+1 or -1) with any dart d, denoted 17 cf. Subsection 2.3. Note that we don't take involutions α i i into account, since they are undefined. Formally, this means that an i-cell (D, α i 0 , . . . , α i i-1 , α i i = ω) is orientable iff its canonical boundary (D, α i 0 , . . . , α i i-1 ) is orientable. There exists non orientable cells, for instance a 3-cell which boundary corresponds to the 2-gmap of Fig. 5(f), i.e. corresponding to a Klein bottle. At last, note that the fact that all cells are orientable does not involve that the whole cmap is orientable. sg(d), such that sg(d) = sg(dα i j )∀j. Let c i be the i-cell incident to d: choosing an orientation for c i consists in choosing a sign for d, the signs of the other darts of the cell are deduced from sg(d). In practice, this can be done easily during a traversal of the whole cmap, i.e. in linear time according to the number of darts. So, the cost of checking condition C2 is the cost of condition C1, linear in the number of darts times the dimension of the cmap.

Definition 9 (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 ); nis the number of preimages (related to σ i ) of d i-1 in c i whose sign is different from sg(d i-1 ).

The signed incidence number (c i : c i-1 ) is well defined, independently from the chosen darts: since c i is orientable, any orbit

α i 0 , • • • , α i i-2 of c i is orientable. Since σ i restricted to an orbit α i 0 , • • • , α i i-2
is an isomorphism, we can show that for any darts d and d of this orbit, sg(d).sg(dσ i ) = sg(d ).sg(d σ i ).

As for the unsigned boundary operator, we can provide an alternative definition: let

{p j } j=1•••k be darts of c i such that { α i 0 , • • • , α i i-2 (p j )} j=1•••k makes a partition of c i . Then (c i : c i-1 ) = pj ,j=1•••k|pj σ i ∈c i-1 sg(p j ).sg(p j σ i ).
This alternative definition is equivalent to the original one, due to Property 2a of Definition 4. The corresponding operator ∂ M acts on any i-cell c i in the following way:

Property 3 Let i ∈ {1, . . . , n}. Let c i be a cell of the cmap C. Let {p j } j=1•••k be a set of darts such that the orbits

{ α i 0 , • • • , α i i-2 (p j )} j=1•••k make a partition of c i , c i ∂ M = pj ,j=1•••k sg(p j ).sg(p j σ i )c i-1 (p j σ i ).
Operator ∂ M is extended on any sum of cells taken with any integer coefficients, by linearity.

We will prove below that under condition C2 above, ∂ M is a boundary operator, i.e. ∂ M ∂ M = 0. So, this boundary operator defines a homology on the corresponding set of cmaps, with coefficients in Z, which will be referred to as cellular homology, as for the unsigned case, since no ambiguity will be induced.

We restrict here to cmaps satisfying condition C2.

Definition 10 Let C = ((G i ) i=0,...,n , (σ i ) i=1,...,n be a cmap, S be its associated semi-simplicial set, C * be the chain groups associated with C and (S * , ∂ S ) be the chain complex associated with S. τ : C * → S * is defined by:

∀i, 0 ≤ i ≤ n, ∀c i ∈ G i , c i τ = d∈c i sg(d)T ( (d)),
extended by linearity with integer coefficients to the chains of C * .

Such a sum is a signed chain of cells.

Lemma 3 τ satisfies:

xτ ∂ S = (-1) i x∂ M τ
for any signed chain of cells x of dimension i greater than or equal to 1.

Proof The proof is similar to that of Lemma 1, by taking also into account:

in any i-cell, two i-simplices sharing an (i -1)-simplex are oriented in opposite ways, since cells are orientable; so, when taking the boundary of the simplicial chain associated with an i-cell, the (i -1)-simplices "internal" to the cell vanish; -cellular face operator σ i corresponds to simplicial face operator d i , involving a (-1) i coefficient (cf. definition of simplicial boundary operator in Subsection 2.2).

See also [START_REF] Alayrangues | A boundary operator for computing the homology of cellular structures[END_REF] for a more detailed proof.

Lemma 4 τ associates a simplicial cycle (resp. boundary) with any cellular cycle (resp. boundary).

Property 4 ∂ M is a boundary operator, i.e. ∂ M ∂ M = 0, and (C * , ∂ M ) is a chain complex.

The proofs of Lemma 4 and Property 4 are similar to the unsigned case (cf. also [START_REF] Alayrangues | A boundary operator for computing the homology of cellular structures[END_REF]).

Algorithm

We present now Algorithm 1 which computes the i th incidence matrix E i , i.e. incidence numbers between all i-cells and (i -1)-cells, for any cmap satisfying condition C2. Remember that cells in cmaps are linked together by the σ i operator.

When only σ i operators are represented in data structures, it is more efficient to run through darts in c i and to count the number of times a dart belonging to c i-1 is found than to run through darts in c i-1 and finding its number of preimages in c i by σ i . For this reason, we use in our algorithm the formulation of the boundary operator as stated in Property 3. This algorithm takes as input a signed cmap C, i.e. each dart d of C is marked with sg(d), and computes the i th incidence matrix E i .

Notation: given a gmap G, let card(G) denote the number of connected components of G.

The case i = 0 is specific since there is no (-1)-cell thus the 0 th incidence matrix is a zero matrix having card(G 0 ) columns and one line.

Otherwise, the incidence matrix E i is initialized to a zero matrix having card(G i ) columns and card(G i-1 ) lines. Then we run through all the darts d ∈

G i . If d is not marked, its i-cell c i (d)
is not yet processed. Thus we enter in the second loop to compute all the incidence numbers between c i (d) and its incident (i -1)-cells. For that we only run through the darts d ∈ c i (d) and consider each (i -1)-cell Algorithm 1: Computation of the i th incidence matrix

Data: C = ((G i ) i=0,...,n , (σ i ) i=1,...,n ): a signed n-dimensional cmap i: a dimension, 0 ≤ i ≤ n Result: The incidence matrix E i 1 if i=0 then 2 E i ← zeroMatrix(card(G 0 ),1); 3 else 4 E i ← zeroMatrix(card(G i ),card(G i-1 )); 5 foreach dart d ∈ G i do 6 if d is not marked treated then 7 foreach dart d ∈ c i (d) do 8 if d is not marked treated then 9 E i (c i (d), c i-1 (d σ i )) ← E i (c i (d), c i-1 (d σ i )) + sg(d ).sg(d σ i ); 10 mark treated all the darts of α i 0 , • • • , α i i-2 (d ); 11 return E i ; c i-1 (d σ i ).
Indeed, other (i -1)-cells do not belong to the boundary of c i (d), and thus the incidence number between these cells and c i (d) is zero.

For each (i -1)-cell, we mainly add or subtract 1 depending if d and d σ i have the same sign or not. After having considered all the darts of c i (d), all the (i -1)-cells incident to c i (d) have been treated, thus all the incidence numbers involving c i (d) have been computed. At the end of Algorithm 1, all the i-cells of the cmap have been treated, and thus the matrix E i is the i th incidence matrix.

The complexity of Algorithm 1 is linear in the number of darts of G i . Indeed, each dart is considered exactly once during the second loop thanks to the treated mark, and for each dart, we have a direct access to each value used to compute the incidence number (i.e. d σ i , sg(d ) and sg(d σ i )).

Note that we can define in a similar way an algorithm to compute the signed incidence number (c i (d) : c i-1 (d )) for any cells c i (d) and c i-1 (d ).

To compute all the incidence matrices for a given n-dimensional cmap, we need first to orient each cell of the cmap; second to run Algorithm 1 for each i, 0 ≤ i ≤ n. The complexity of the overall process is thus linear in the number of darts, i.e. in the size of the cmap.

This process can be compared with the "simplicial homology computation", which consists in:

compute the simplicial analog of the given cmap. So, it is necessary to compute all possible orbits of the cmap (cf. Subsection 2.4.2), for any combination of involutions. Since the cost is 2 n times the number of darts for a n-dimensional gmap, it is easy to deduce that the cost of computing an orientation for each cell of a cmap is less than the cost of computing its simplicial analog; -then compute the incidence matrices: this is linear in the number of simplices times the dimension of the cmap. It is clear that there are less cells in the cmap than simplices in its simplicial analog. See for instance the five objects shown in Fig. 12 plus the Poincaré homology sphere (not shown). The first three objects are surfacic (i.e. they are 2D combinatorial objects embedded in 3D space) while the last three ones are topologically 3-dimensional ones. We give in Table 1 the number of cells of each object for each dimension, and compare these numbers with the number of simplices of the corresponding simplicial object: it is thus possible to compare the sizes of the incidence matrices associated with the cellular objects and their simplicial analogs.

So, we can easily deduce that it is more efficient to compute the homology of a cmap with the method presented in this paper, when it is possible, than to compute the homology of its simplicial analog.

At last, note that we can also deduce an algorithm for computing the unsigned incidence number, the only difference being that the considered cmap is no more signed:

so, it is useless to orient the cells before computing the incidence matrices; -the incidence number can be represented by a Boolean initialized to false, and negated at each time the condition d is not marked treated and dσ i ∈ c i-1 (d ) is satisfied (since the computation is done over Z/2Z).

Conditions and proof of the equivalence between cellular and simplicial homology on chains of maps

We restrict here to cmaps satisfying the following condition denoted C3:

Condition C3: C is a cmap such that:
-C satisfies condition C1 (homology over Z/2Z) or condition C2 (homology over Z);

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

H 0 = Z, H j = 0, 1 ≤ j ≤ i -2, H i-1 = Z).
The cost of checking condition C1 or C2 has been discussed in the previous section. The cost related to condition C3 is mainly the cost of checking that the canonical boundary of each cell has the homology of a sphere. As said in introduction, it is important to check the constructed object during a construction process: so, checking the homology of the boundary of a cell can naturally be done when the cell is constructed or modified.

We prove that under condition C3, the defined homology of a cmap is equivalent to the homology of its simplicial analog. Otherwise stated: The following lemma19 is needed for the proof of Theorem 1:

Lemma 5 Let zs be a simplicial cycle (resp. boundary), i.e. a cycle (resp. boundary) in the semi-simplicial set associated with a cmap. Then a cellular cycle (resp. boundary) z exists in the cmap, such that zτ is homologous to zs.

Its proof uses the following lemma illustrated in Fig. 14: Lemma 6 Let xs be a simplicial chain, such that:

all simplices of xs belong to T (cel), where cel is a cell which dimension is strictly greater than that of xs; the simplices of the boundary of xs belong to the semi-simplicial subset associated with the boundary of cel.

Then a simplicial chain x s exists, which is homologous to xs (and thus which has the same boundary as xs), such that all simplices of x s are in the semi-simplicial subset associated with the boundary of cel.

Proof of Theorem 1

A consequence of lemmas 2, 4 and 5 is the existence of a one-to-one mapping between the classes of cellular cycles (resp. boundaries) of a cmap and the classes of simplicial cycles (resp. boundaries) of the associated semi-simplicial set.

Note that a particular boundary operator ∂ M depends on the chosen cell orientations when considering homology over Z. The theorem shows that the corresponding homology is equivalent to the simplicial homology of the semi-simplicial set associated with the cmap, independently of the cell orientations. The cellular homology defined by a particular operator ∂ M is thus independent of the cell orientations which have been chosen for defining this operator.

Proof of Lemma 5

We first prove Lemma 5, assuming Lemma 6 is true.

Correspondence of cycles.

Let zs be a k-dimensional simplicial cycle (i.e. zs∂ S = 0, where ∂ S denotes the simplicial boundary operator with coefficients in Z/2Z or in Z). We can define a partition of the simplices of zs according to the cells which triangulations produce these simplices, i.e. zs = ci j

ν ij s ij , where s ij is a simplex of T (c i ) and ν ij is its coefficient (in Z/2Z or in Z).
-Assume that ∀i, the dimension of c i is equal to the dimension of zs. Then ∀i, j ν ij s ij = ν i c i τ . If it is not the case, it is easy to prove that the boundary of this "subchain" contains simplices of T (c i ), which cannot be removed by the boundary of an other "subchain", involving that the boundary of zs is not null: contradiction.

-Assume that cells exist which dimension is strictly greater than that of zs.

Let c i be such a cell, such that its dimension is maximal. The simplices of ( j ν ij s ij )∂ S are in the semi-simplicial set associated with the boundary of c i :

otherwise, and due to the definition of face operators of the semi-simplicial set associated with a cmap, the boundary of this "subchain" contains simplices of T (c i ), which cannot be removed by the boundary of an other "subchain": as before, we get a contradiction. Using the lemma, a chain z i exists, such that its simplices are in the semi-simplicial set associated with the boundary of c i , and which is homologous to j ν ij s ij . We can thus replace this subchain by z i in zs. By iterating the process, we can replace zs by an homologous cycle which satisfies the conditions of the first case.

Correspondence of boundaries.

Let bs be a simplicial boundary: since a boundary is a cycle, a cellular cycle z exists, such that zτ is homologous to bs; zτ is thus a simplicial boundary, i.e. a simplicial chain xs exists, such that zτ = xs∂ S . As before, we can define a partition of the simplices of xs according to the cells which triangulations produce these simplices, i.e. xs = ci j ν ij s ij , where s ij is a simplex of T (c i ). We prove that xs is homologous to the image by τ of a cellular chain as before, i.e. by distinguishing the cases:

assume that ∀i, the dimension of c i is equal to the dimension of xs. Then ∀i,

j ν ij s ij = ν i c i τ .
If it is not the case, this leads to a contradiction, since the boundary of c k is associated by τ with a cellular chain; -assume that cells exist which dimension is strictly greater than that of xs.

Let c i be such a cell, such that its dimension is maximal. Using the lemma Lemma 6, a chain z i exists, such that its simplices are in the semi-simplicial set associated with the boundary of c i , and which is homologous to

j ν ij s ij .
We can thus replace this subchain by z i in xs. By iterating the process, we can replace xs by an homologous chain which satisfies the conditions of the first case.

Proof of Lemma 6

We now prove Lemma 6. We use the fact that any cmap can be constructed in the following way [START_REF] Elter | Cellular complexes as structured semi-simplicial sets[END_REF] (see Fig. 13):

create any main i-dimensional cell20 [START_REF] Lienhardt | N-dimensional generalized combinatorial maps and cellular quasimanifolds[END_REF] and its boundary (this boundary is a cmap equivalent to the canonical boundary of the i-cell). We restrict here this operation to the creation of cells which boundaries have the homology of an (i -1)-dimensional sphere; -identify j-dimensional cells (0 ≤ j ≤ i -1) which share a same boundary (we assume that the boundary of a vertex is null).

We will show for each operation that if the lemma is satisfied before applying the operation, it is still satisfied after. Creating an i-cell and its boundary.

A connected gmap G = (D, α 0 , • • • , αn) such that αn = identity defines an n-cell and its boundary, and it is possible to associate an equivalent cmap with it. More generally, given a gmap G = (D, α 0 , • • • , αn), we can associate with it a cmap

C = ((G i = (D i , α i 0 , • • • , α i i-1 , ω)) i=0•••n , (σ i ) i=1•••n )
, such that the corresponding quasi-manifolds are isomorphic (cf. [START_REF] Elter | Cellular complexes as structured semi-simplicial sets[END_REF] and Subsection 5.1). There is a oneto-one mapping B between the orbits α i+1 , • • • , αn of G and the darts of D i . Moreover, ∀d ∈ D:

-B( α i+1 , • • • , αn (d))α i j = B( α i+1 , • • • , αn (dα j )), ∀0 ≤ j ≤ i -1 < n; -B( α i+1 , • • • , αn (d))σ i = B( α i , α i+1 , • • • , αn (d)), ∀1 ≤ i ≤ n.
Creating an i-dimensional cell and its boundary consists in creating a cell c i defined by (D, α 0 , • • • , α i-1 , ω), a cmap corresponding to its canonical boundary (D, α 0 , • • • , α i-1 ), and σ i is defined by: ∀d ∈ D, dσ i = B( (d)). The resulting cmap corresponds to the gmap (D, α 0 , • • • , α i-1 , α i = identity), and it is shown in [START_REF] Lienhardt | N-dimensional generalized combinatorial maps and cellular quasimanifolds[END_REF] that the corresponding semi-simplicial set is a cone (cf. Fig. 10). Its simplicial homology is thus trivial (i.e. H 0 = Z, H j = 0, ∀j ≥ 1). Moreover, as said before, we restrict here the construction to gmaps such that the cmap associated to (D, α 0 , • • • , α i-1 ) has the cellular homology of a sphere. By the recursion hypothesis, the simplicial homology of the associated semi-simplicial set is also that of a sphere. c i is the unique i-dimensional cell, and the cells of c i ∂ M (where ∂ M is the cellular boundary operator defined on chains of maps, with coefficients in Z/2Z or in Z) are (i -1)-dimensional cells. Since a boundary is a cycle, c i ∂ M is an element of the unique class of the (i -1)-dimensional cycles, and it is now a boundary. The cellular homology of c i and its boundary is thus the homology of a cone, equal to the simplicial homology of the corresponding semi-simplicial set.

Let xs be a k-dimensional simplicial chain, such that 1 ≤ k ≤ i -1, the simplices of xs are simplices of T (c i ), and the simplices of xs∂ S are simplices of the semi-simplicial set associated with the boundary of c i : cf. Fig. 14. xs∂ S is thus a cycle made with simplices contained in the semi-simplicial set associated with the boundary of c i . Since the simplicial homology of the boundary of c i is the homology of a sphere, any (k -1)-cycle is a boundary, and a k-dimensional chain x s exists, which simplices are contained in the semi-simplicial set associated with the boundary of c i , and such that x s ∂ S = xs∂ S . Thus xs -x s is a cycle, and since any k-dimensional cycle is a k-dimensional boundary (the homology of the cmap is the homology of a cone), a simplicial chain x s exists, which simplices are contained in T (c i ) and in the semi-simplicial set associated with its boundary, such that x s = xs + x s ∂ S . So, if the lemma is satisfied before creating a cell and its boundary, it is still satisfied after.

Identifying two cells.

The identification of two cells corresponds to the following operation: let c i and c i be two distinct isomorphic i-dimensional cells (having the same boundary if i ≥ 1), i.e. an isomorphism φ exists, such that ∀d ∈ c i , ∀j, 0 ≤ j ≤ i -1, dα i j φ = dφα i j , and dσ i = dφσ i . The cmap is then modified by dividing it by φ, i.e. by identifying d with dφ for all darts d of c i . Let us denote c i the cell resulting from the identification of c i and c i . Due to the definition of the identification operation, a morphism exists between the initial cmap and the cmap resulting from the identification operation: this morphism can be extended onto a morphism between the associated semisimplicial sets, and finally onto a morphism Φ between the associated simplicial chain complexes. By definition of a morphism, we have the following property: let xs be a simplicial chain, the simplices of which belong to the initial cmap, then

xs∂ S Φ = xsΦ∂ S .
Assume that Lemma 6 is satisfied before an identification operation. After operation, let x s be a simplicial chain which simplices are contained in T (cel), where cel is a cell of the cmap, and such that the simplices of x s ∂ S are contained in the semi-simplicial set associated with the boundary of cel. We are now going to show that Lemma 6 is still satisfied. For this we are considering the following three possible cases of identification. case 1: c i = cel. The chain x corresponds thus to a chain x 1 and to a chain x 2 , such that the simplices of x 1 (resp. x 2 ) are contained in T (c i ) (resp. T (c i )), and they are isomorphic to each other (by φ extended to T (c i ) and to the associated chains of simplices). Since x 1 ∂ S = x 2 ∂ S , and the corresponding simplices are contained in T (c i )∂ S = T (c i )∂ S , by the recursion hypothesis, a chain x 1 exists, which simplices are contained in T (c i )∂ S , a chain x" 1 exists, which simplices are contained in T (c i ) and in T (c i )∂ S , such that x 1 = x 1 + x" 1 ∂ S , and

x 2 = x 1 + x" 1 Φ∂ S .
The identification operation results in identifying x 1 with x 2 into x , x" 1 with x" 1 Φ into x", and we get: x = x 1 + x"∂ S , where the simplices of x 1 are contained in T (cel)∂ S , and the simplices of x" are contained in T (cel) and in T (cel)∂ S .

case 2: c i is in the boundary of cel. First, we show that x satisfied the lemma conditions before identification. We know that cel was not affected by the identification, so before identification, x was a simplicial chain the simplices of which are contained in T (cel). Moreover, the fact that Φ is a morphism ensures that the simplices of x ∂ S were in T (cel)∂ S . So, before identification, x satisfied the lemma conditions, and x = x + x"∂ S , where the simplices of x (resp. x") belong to T (cel)∂ S (resp. to T (cel) ∪ T (cel)∂ S ). More precisely, the chain x can be decomposed as follow: 1. α 0 , . . . , α i-1 (d) ∩ α i+1 , . . . , αn (d) = {d}; 2. the simple cell ( α 0 , . . . , α i-1 (d), α 0 , . . . , α i-1 ) is isomorphic to the compacted cell (c i (d)/ α i+1 , . . . , αn , α 0 , . . . , α i-1 ), where c i (d) = α 0 , . . . , α i-1 , α i+1 , . . . , αn (d). More precisely, c i (d)/ α i+1 , . . . , αn means that a dart is associated with each orbit α i+1 , . . . , αn of c i (d); since α k α l = α l α k for k ≤ l -2, we get (by abuse of notations) that ( α i+1 , . . . , αn (d

x = (x 1 + x 2 + x 3 ) + (x" 1 + x" 2 + x" 3 + x" 4 )∂ S where: -the simplices of x 1 (resp. x 2 , x 3 ) belong to T (cel)∂ S -T (c i )-T (c i ) (resp. T (c i ), T (c i )); -the simplices of x" 1 (resp. x" 2 , x" 3 , x" 4 ) belong to T (cel) (resp. T (c i ), T (c i ), T (cel)∂ S -T (c i ) -T (c i )).
))α k = α i+1 , . . . , αn (dα k ) for 0 ≤ k ≤ i -1.
This property is a direct consequence of similar properties of cmaps detailed and proved in [START_REF] Alayrangues | A boundary operator for computing the homology of cellular structures[END_REF]. An important consequence of this property is the following. Let C = ((G i ) i=0,...,n , (σ i ) i=1,...,n ) be a cmap satisfying condition C1 and corresponding to a quasi-manifold, and let G = (D, α 0 , . . . , αn) be the equivalent gmap. All involutions α i are without fixed points for 0 ≤ i ≤ n -1. For 0 ≤ i ≤ n, there is a one-to-one mapping between the i-cells of C and orbits (D/ α i+1 , . . . , αn , α 0 , . . . , α i-1 ) of G (see Fig. 15). More precisely, each dart of G i corresponds to an orbit α i+1 , . . . , αn , and α i+1 , . . . , αn (d)σ i = α i , . . . , αn (d) [START_REF] Alayrangues | Border operator for generalized maps[END_REF].

Boundary operators

With this equivalence, we can thus extend the results presented above for chains of maps onto gmaps. First, we define the unsigned incidence numbers:

Definition 11 (unsigned incidence number) Let i ∈ {1, . . . , n}. Let c i (d) and c i-1 (d ) be two cells of G. The unsigned incidence number, (c i (d) :

c i-1 (d )), is: card({ α i+1 , . . . , αn (d ) ⊆ α i , . . . , αn (d ) s.t. α i+1 , . . . , αn d ⊆ c i (d)}).
This definition is a direct translation of the unsigned incidence numbers on chains of maps. We can simplify the definition in the following way :

(c i (d) : c i-1 (d )) = card({ α i+1 , . . . , αn (d )|d" ∈ α i , . . . , αn (d ), d" ∈ c i (d)})
As for cmaps, we can provide the following alternative definition: Property 6 Let {p j } j=1...k be a set of darts such that the orbits { α 0 , . . . , α i-2 (p j )} j=1...k make a partition of α 0 , . . . , α i-1 (d); then

(c i (d) : c i-1 ) = card({p j , j = 1 . . . k|p j ∈ c i-1 })
Then we define the signed incidence numbers, for gmaps whose cells are orientable, i.e. satisfying: for any i-cell c i = α 0 , . . . , α i-1 , α i+1 , . . . , αn (d), there are two distinct orbits α 0 α 1 , . . . , α 0 α i-1 , α 0 α i+1 , . . . , α 0 αn (d) and α 0 α 1 , . . . , α 0 α i-1 , α 0 α i+1 , . . . , α 0 αn (dα 0 ) (cf. [START_REF] Lienhardt | N-dimensional generalized combinatorial maps and cellular quasimanifolds[END_REF] and Subsection 5.2). We then choose an orientation for the associated compacted cell, i.e. each dart d of the i-cell is marked with a sign (+1 or -1) denoted sg i (d) such that sg i (d) = sg i (dα j ) ∀j: 0 ≤ j < i, and sg i (d) = sg i (dα j ) ∀j: i < j ≤ n21 . Note that, as for cmaps, the gmap itself can be non orientable.

Definition 12 (signed incidence number) Let i ∈ {1, . . . , n}. Let c i (d) and c i-1 (d ) be two cells of G. The signed incidence number, (c i (d) : c i-1 (d )), is: αi+1,...,αn (d )⊆ αi,...,αn (d )

s.t. d ∈c i (d) sg i (d ).sg i-1 (d )
It has been shown in [START_REF] Alayrangues | Border operator for generalized maps[END_REF] that the incidence number does not depend on the chosen darts, and thus that the definitions are consistent. As for unsigned incidence numbers, we will use the following alternative definition:

Property 7 Let {p j } j=1...k be a set of darts such that the orbits { α 0 , . . . , α i-2 (p j )} j=1...k make a partition of α 0 , . . . , α i-1 (d); then (c i (d) : c i-1 ) = pj ,j=1...k|pj ∈c i-1 sg i (p j ).sg i-1 (p j ) Let ∂ M be the corresponding boundary operator, according to Definition 6: we can easily prove that ∂ M satisfies ∂ M ∂ M = 0 when involutions α i are without fixed point for 0 ≤ i ≤ n -1. Moreover, we have:

Theorem 2 The homologies defined on gmaps by these boundary operators are equivalent to the simplicial homologies of the associated quasi-manifolds when the homology of the canonical boundary of each i-cell is that of an (i -1)-sphere.

Proof We have mentioned above the equivalence between cmaps such that all involutions are without fixed point, and gmaps without self-bending, such that all involutions except αn are without fixed point. This equivalence still holds when the cells are orientable. We can also show easily that a gmap and its corresponding cmap correspond to the same quasi-manifold, and that the incidence numbers defined for the gmap are the same as those defined for the associated cmap. The result comes from the fact that the homology of the cmap is equivalent to the homology of the quasi-manifold. Note that the two connected components of the map of the orientations of G are M and M .

We have not found a simple direct characterization of the self-bending condition that maps have to fulfill in order to define an homology which is equivalent to the homology of their simplicial interpretation. Given a map, we think the most easy way consists in computing the associated gmap, and in checking the conditions. The cost of the conversion map-gmap is linear in the size of the map, so it doesn't change the complexity of the whole computation. In practice, it is more efficient to control the construction of the map, in order to get a map without self-bending; as for gmaps, it is easy and not costly.

Maps correspond to oriented quasi-manifolds without boundary. So, all cells are orientable, and the cmap associated with any map without self-bending satisfies condition C2. Moreover, main cells are oriented; but it remains necessary to define an orientation for non main cells, in order to compute incidence numbers. Here again, it seems that the most easy way for computing incidence matrices consists in computing the associated gmap and in applying the results obtained for gmaps22 .

Conclusion and perspectives

We have provided in this paper a direct definition of "cellular" homology for cmaps, gmaps and maps, i.e. where the chain groups are generated by the cells of the corresponding structure. The present study is, to our knowledge, the first one that tackles the problem of the definition and computation of a consistent cellular homology on quite generic and purely combinatorially defined cellular structures which allow multi-incidence between cells. Though it is always possible to compute the simplicial homology of a cellular structure on its simplicial analog, we take here advantage of the structuration into cells in order to improve the complexity of the homology computation (a cellular structure contains less cells than its simplicial analog contains simplices).

To achieve this objective, we have defined for cmaps the notions of (unsigned and signed) incidence numbers, and studied the combinatorial conditions under which a homology is defined over Z/2Z and over Z. The two cases are distinguished since the corresponding conditions are distinct, but also for optimization issues. We prove that the "cellular" homology is equivalent to the simplicial one when (mainly) the boundary of each cell is homologically equivalent to a sphere, which is also a purely combinatorial constraint. A similar equivalence for gmaps is also proved as a consequence of well-known relations between gmaps and cmaps. We didn't found how to optimize the computation for maps relatively to gmaps, and we think the best way for computing the homology of maps is to compute the homology of the corresponding gmaps.

Algorithms are provided for computing the incidence matrices, which are linear in the size of the corresponding structure. We have implemented the computation of incidence matrices for gmaps, and use these matrices to compute homology of 2D and 3D objects by using the method presented in [START_REF] Peltier | Computation of Homology Groups and Generators[END_REF]. The dimension is for the moment restricted to 3 because the software used to develop these methods is Moka [START_REF] Vidil | Moka[END_REF], which is a 3D modeling software. But all the functions which compute incidence matrices and homology are generic in any dimension.

We plan to improve the complexity of cellular homology computation by adapting techniques proposed for the simplicial framework or for regular CW -complexes (e.g. optimization of matrices reductions [START_REF] Storjohann | Near optimal algorithms for computing smith normal forms of integer matrices[END_REF], elementary reductions [START_REF] Kaczynski | Homology computation by reduction of chain complexes[END_REF][START_REF] Dlotko | Coreduction homology algorithm for regular cw-complexes[END_REF]). We also study the conversions between structures derived from combinatorial maps and incidence graphs: they make it possible for instance to apply our results for the definition and the computation of the homology of cellular structures without multi-incidence [START_REF] Alayrangues | A boundary operator for computing the homology of cellular structures[END_REF][START_REF] Alayrangues | Conversion between chains of maps and chains of surfaces; application to the computation of incidence graphs homology[END_REF].

Fig. 1

 1 Fig. 1 (a) A polygonal face (b) Identification of edges a and b creates an annulus. The face is incident twice to edge a = b (c) Polygonal faces F 1 and F 2 are glued together by identifying three edges and their boundaries. Subdivisions of surfaces depicted in (b) and (c) are not regular CW -complexes.

Fig. 2

 2 Fig. 2 A cellular subdivision having the following homology groups: H 0 H 1 Z, H i 0 for i > 1. 3A -6B and C + 2B are 1-chains. A + B is a 1-cycle as (A + B)∂ = D -E + E -D = 0 and B -C is a 1-boundary as B -C = F ∂. The 1-chains A + B and A + C are homologous as A + C + F ∂ = A + B. D is a generator for H 0 and A + C is a generator of H 1 .

Fig. 3

 3 Fig. 3 (a) Representation of an abstract simplicial complex. (b) The triangle is incident to two vertices. (c) Two edges have the same boundary. Subdivisions (b) and (c) can be described by semi-simplicial sets but not by abstract simplicial complexes. (d) Semi-simplicial set associated with (a). (e) Semi-simplicial set associated with (b). (f) Semi-simplicial set associated with (c).

Fig. 4

 4 Fig.4(a) A loop, i.e. an edge incident twice to a vertex. In order to represent multi-incidence, the two "endpoints" of the edge must be distinguished. (b) Gmap representation of the loop (a). Intuitively, the two darts (represented by points) correspond to the two endpoints of the edge. They are linked by α 0 (dotted line) in order to represent the edge, and by α 1 (full line) in order to represent the vertex. (c) An edge incident to two different vertices, represented by the gmap (d). (e) A cycle of four edges represented by the gmap (f), made of 8 darts. As before, two darts linked by α 0 correspond to an edge and two darts linked by α 1 correspond to a vertex.

Fig. 5

 5 Fig.5(a) A 2-gmap (α 2 is represented by double lines) representing the face in (b). Orbit < α 0 , α 1 > (1) = {1, 2, 3, 4, 5, 6, 7, 8} corresponds to the face, incident to 4 edges (corresponding to the four orbits < α 0 , α 2 >, i.e. {1, 2}, {3, 4}, {5, 6}, {7, 8}), and to 4 vertices (corresponding to the 4 orbits < α 1 , α 2 >, i.e. {1, 8}, {2, 3}, {4, 5}, {6, 7}). (c) A 2-gmap corresponding to the cylinder represented in (d), made of 1 face, 3 edges ({1, 2}, {3, 4, 7, 8}, {5, 6}), and 2 vertices ({1, 2, 3, 8}, {4, 5, 6, 7}). (e) A 2-gmap corresponding to a torus (1 face, 2 edges {1, 2, 5, 6}, {3, 4, 7, 8} and 1 vertex). (f) A 2-gmap corresponding to a Klein bottle (1 face, 2 edges {1, 2, 5, 6}, {3, 4, 7, 8} and 1 vertex).

Fig. 6

 6 Fig.6(a) A 2-gmap corresponding to the subdivision depicted on (b). Dart 5 corresponds to the cell tuple (V 4, E4, F 1), dart 6 corresponds to the cell tuple (V 5, E4, F 1), dart 4 corresponds to the cell tuple (V 4, E6, F 1), dart 10 corresponds to the cell tuple (V 4, E6, F 2).

Fig. 7

 7 Fig. 7 (a) A 2-cmap corresponding to the subdivision represented in (b). σ 2 (resp. σ 1 ) is represented by red (resp. black) arrows. Orbit < α 2 0 , α 2 1 > (1) corresponds to the square face. Orbit < α 1 0 > (2) corresponds to an edge. Orbit <> (3) corresponds to a vertex. (c) The numbered semi-simplicial set corresponding to the cmap depicted on Fig. 7(a). The simplices of any cell are graphically glued together. (d) A 2-cmap corresponding to the subdivision (e).

Fig. 5

 5 Fig. 5(e) (a torus) or Fig. 5(f) (a Klein bottle). Conversely, note that a cmap can be associated with any regular CW -complex [ADLP11].

Fig. 8

 8 Fig. 8 (a) A numbered semi-simplicial set (the numbers of the vertices are depicted on (b)) which corresponds to the 2 -gmap of Fig. 6(a). (b) The corresponding cells.

Fig. 9

 9 Fig. 9 (a) A non manifold. (b) A pseudo-manifold (non quasi-manifold). (c) A quasi-manifold (non-manifold). This object can be obtained by gluing two opposite triangular faces of a square based pyramid. (d) A manifold.

Fig. 11

 11 Fig. 11 (a) A cmap having some involutions with fixed points. (b) Its corresponding subdivision, made of 1 face, 3 edges and 3 vertices. The boundary of the face is not a cycle of edges, nevertheless, this cmap has a topological interpretation (see Subsection 2.4.2). Note that f ∂ M ∂ M = 0, where f denotes the face, since a vertex exists which is incident to only one edge. (c) A cmap satisfying the condition f ∂ M ∂ M = 0 where f denotes the face. (d) The corresponding subdivision.

Fig. 12

 12 Fig. 12 Cellular objects. (a) A torus with two holes (surfacic). (b) A Klein bottle (surfacic). (c) A pinion (surfacic). (d) A tower (volumic). (e) A Menger sponge (volumic).

Theorem 1

 1 Let C be a cmap satisfying condition C3, S be its associated semi-simplicial set, (C * , ∂ M ), (S * , ∂ S ) and τ : C * → S * be their associated chain complexes and morphism. Let H * (C) and H * (S) be the corresponding homology groups. τ induces an isomorphism τ * : H * (C) → H * (S).

Fig. 13

 13 Fig.13(a) First step for building a cmap of dimension 2: each cmap, corresponding to a main cell and its boundary, is built. (b) Second step: vertex identifications. (c) The resulting cmap after edge identification.

Fig. 14

 14 Fig.14(b) A 1d-chain x having all its simplices in a 3d-cell, such that the simplices of its boundary are in the boundary of the 3d-cell. (c) A 1d-chain x homologous to x having all its simplices in the boundary of the 3d-cell. (d) 2d-chain x" such that x = x + x"∂ S . (a) x , x and x" on the same figure.

Fig. 15

 15 Fig. 15 (a) A 2-gmap. (b) Using the notion of compacted cells (see Property 5, point 2), an i-gmap can be associated with each i-cell of the gmap. (c) The corresponding cmap.

Fig

  Fig. 16 (a) A 2-gmap representing a decomposition of S 2 with 3 faces. (b)-(c) Its two corresponding oriented maps. Note that the points corresponding to two darts d and d such that dβ 1 = d (resp. dβ 2 = d ) are linked by a black arrow (resp. a red dashed line). Note also that dβ 1 (resp. dβ 2 ) corresponds to dα 0 α 1 (resp. dα 0 α 2 ).

  and bτ is a simplicial boundary. 2 ∂ M is a boundary operator, i.e. ∂ M ∂ M = 0, and (C * , ∂ M ) is a chain complex.

	Property

Table 1

 1 ). Numbers of cells of the objects shown in Fig.12, and of Poincaré sphere.

	Object		Cellular object			Simplicial analog
	Cell dimension	0	1	2	3	0	1	2	3
	2-torus	151 294 142	-	588 1,770 1,180	-
	Klein bottle	324 648 324	-1,296 3,888 2,592	-
	Pinion	470 701 231	-1,402 4,206 2,804	-
	Tower	228 452 226	4	910 3,824 4,928 2,016
	Menger sponge	64 144	96 20	324 1,576 2,208	960
	Poincaré sphere	5	10	6	1	22	142	240	120

The conditions are not exactly the same for Z/2Z and Z. Moreover, it suffices to compute the homology over Z/2Z for torsion-free objects, in order to get the whole homological information, and the computation can be more efficient with coefficients in Z/2Z.

Usually, we do not explicitly denote the dimensions of the boundary homomorphisms.

z∂ denotes ∂(z) and z∂∂ denotes ∂(∂(z)). Similar notations will be used in the whole paper.

These notions will be used for others structures without being formally redefined.

d 0 , • • • , d i associate its (i + 1) (i -1)-faces with each i-simplex.

BACKGROUND

The geometric realization of a semi-simplicial set is a CW -complex, and the geometric realization of an abstract simplicial complex is a simplicial complex[START_REF] May | Simplicial objects in algebraic topology[END_REF][START_REF] Agoston | Algebraic Topology, a first course[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 we thus get the commutation property of face operators.

i.e. a one-to-one mapping (a permutation) such that α i = α -1 i .

We often omit to explicitly indicate the restriction, since it is usually obvious. Due to the relation between gmaps and graphs, an orbit can be seen as a subgraph.

In other words, ani-cell is a connected component of the (n -1)-gmap (D, α 0 , • • • , αi , • • • , αn).

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], where σ i can be a homomorphism for instance.

For instance, take a 3-gmap where α 3 = identity, containing one connected component, i.e. one 3-dimensional cell, such that its canonical boundary corresponds to the 2-gmap of

We then come up to the definition of gmaps: the fact that at most two i-cells share an (i -1)-cell in the boundary of an (i + 1)-cell is ensured by the first condition over the α i , i.e. α i is an involution, for all i s.t. 0 ≤ i ≤ n; the fact that cells are cellular quasimanifolds is ensured by the second condition over the α i , i.e. α i α j is an involution for all i, j s.t. 0 ≤ i ≤ j -2 < j ≤ n.

In fact, the property still holds when σ i is an homomorphism.

A cmap can be associated with any gmap: see[START_REF] Elter | Cellular complexes as structured semi-simplicial sets[END_REF], proof of Lemma 6 and Subsection 5.1.

We do not distinguish between the signed and the unsigned cases, since the proofs are quite similar.

Note that it is a generalized map

This definition is equivalent to the one given in[START_REF] Alayrangues | Border operator for generalized maps[END_REF].

Note that a similar phenomenon arose when studying the definition of cartesian product for cellular structures derived from the notion of combinatorial map[START_REF] Lienhardt | Cartesian product of simplicial and cellular structures[END_REF]. It was possible to optimize the definition for cmaps relatively to semi-simplicial sets, for gmaps relatively to cmaps, but the best way we found for defining the cartesian product of maps was to simulate the computation of the cartesian product of the associated gmaps.

Acknowledgements. The authors wish to thank the reviewers for many useful remarks and suggestions, Pol Vanhaecke and Francis Sergeraert for many informative discussions.

After identification, we get:

x = x Φ = (x 1 + x 2 + x 3 )Φ + (x" 1 + x" 2 + x" 3 + x" 4 )∂ S Φ = (x 1 + x 2 + x 3 )Φ + (x" 1 + x" 2 + x" 3 + x" 4 )Φ∂ S = x 1 + x 2 Φ + x 3 Φ + x" 1 ∂ S + x" 2 Φ∂ S + x" 3 Φ∂ S + x" 4 ∂ S

As Φ is a morphism, the simplices of x i Φ belong to the boundary of T (cel), for i = 1..3; the simplices of x" 1 belong to T (cel) and the simplices of x" j Φ belong to the boundary of T (cel), for j = 2..4, and the lemma is satisfied.

case 3:

x is not affected by the identification, and the lemma remains true for x .

Optimizations

Generalized Maps

Definition

Definitions of boundary operators have been proposed in [START_REF] Alayrangues | Border operator for generalized maps[END_REF] in order to optimize the computation of the homology groups for gmaps. We recall here these definitions, and we show that the so-defined homology of a gmap is equivalent to the simplicial homology of the associated quasi-manifold under conditions equivalent to C3. The proof of this equivalence is based upon the relations between a cmap corresponding to a quasi-manifold and the associated gmap, which can be explained in the following way.

An homogeneous (or pure) n-dimensional cmap C = ((G i ) i=0,...,n , (σ i ) i=1,...,n ) is such that any i-cell is incident to an n-cell, for 0 ≤ i ≤ n -1 [START_REF] Elter | Cellular complexes as structured semi-simplicial sets[END_REF] (in others words, the dimension of any main cell is n). We can then define an equivalent structure C = (G n , (R i ) i=0,...,n-1 ), where (R i ) i=0,...,n-1 are equivalence relations between the darts of G n , such that two darts d and d satisfy relation R i if and only if they have the same image dσ n . . . σ i+1 = d σ n . . . σ i+1 , for 0 ≤ i ≤ n -1. In fact, relations (R i ) i=0,...,n-1 implicitly represent the i-cells, and they satisfy properties which can be deduced from the definition of the cmaps.

When the cmap corresponds to a quasi-manifold, this structure can again be simplified: it is sufficient to explicitly represent n-cells and relation R n-1 , since n-cells are glued along (n -1)-cells; each equivalence class of R n-1 contains at most two darts, since at most two n-cells share an (n -1)-cell. R n-1 can thus be represented by an involution, namely αn, and we get the definition of gmaps.

Moreover, since we consider cmaps in which σ i+1 , for 0 ≤ i ≤ n-1, is an isomorphism between orbits α i+1 0 , . . . , α i+1 i-1 and orbits α i 0 , . . . , α i i-1 (cf. Definition 4), we get the subclass of gmaps without self-bending: note that it is easy, during the construction of a gmap, to control the fact that it is without self-bending [START_REF] Alayrangues | Equivalence between closed connected n-g-maps without multi-incidence and n-surfaces[END_REF][START_REF] Cardoze | Representing topological structures using cell-chains[END_REF]. A 2-gmap and a cmap encoding the same quasi-manifold are respectively displayed on Figure 15(a) and Figure 15(c).

Gmaps without self-bending satisfy Property 5 below.

Property 5 A gmap without self-bending G = (D, α 0 , . . . , αn), equivalent to a cmap as defined in Definition 4, satisfies, ∀d ∈ D, ∀i, 0 ≤ i ≤ n:

Algorithm

It is easy to propose an algorithm to compute the incidence matrix E i given a signed gmap. The only difference with the same algorithm for chains of maps (cf. Algorithm 1) is the way that we now consider cells. Indeed, contrary to cmaps, the darts of all the cells in relation by σ are now represented by only one dart in the gmap. Thus we use the same dart d to represent both the i-cell and the (i -1)-cell, ∀i : 0 ≤ i ≤ n. The second difference is that we iterate through all the darts of α 0 , . . . , α i-1 (d) instead of iterating through all the darts d ∈ c i (d) for cmaps. Indeed, when considering gmap G i in a cmap, we do not consider α j for

The complexity of the algorithm computing the incidence matrix E i given a signed gmap is linear in number of darts of the gmap.

Let us recall that such an algorithm requires that the gmap has all its cells oriented. Orienting an i-cell can be achieved locally, the complexity being linear in the number of darts of the cell. Thus, the algorithm which orients each cell for each dimension of the gmap is linear in number of darts of the gmap times its dimension.

The algorithm computing all the incidence matrices consists in first orienting all the cells for all dimensions, and second computing all the incidence matrices E i for 1 ≤ i ≤ n. Its overall complexity is thus also linear in the number of darts of the gmap times its dimension.

Maps

Maps are defined in order to represent orientable quasi-manifolds without boundaries (cf. [START_REF] Lienhardt | N-dimensional generalized combinatorial maps and cellular quasimanifolds[END_REF]).

Definition 13 (n-map) Let n ≥ 0, an n-map is defined by an (n + 1)-tuple M = (D, β 1 , • • • , βn) such that:

-D is a finite set of darts;

The link with gmaps is the following. Let G = (D, α 0 , • • • , αn) be a connected gmap without boundaries, i.e. such that α i is without fixed points for any 0 ≤ i ≤ n. Let O = (D, α 0 α 1 , • • • , α 0 αn) be the map of the orientations of G. O has at most two connected components; G is orientable if and only if O has exactly two connected components; in this case, each connected component is the inverse of the other one (cf. Fig. 16).

Conversely, let M = (D, β 1 , • • • , βn) be a connected map, and M = (D , β 1 , • • • , β n ) be a map isomorphic to M -1 by φ. Then we can define the corresponding gmap G = (D ∪ D , α 0 , • • • , αn) with:

for 1 ≤ i ≤ n, α i /D = φβ i , α i /D = φ -1 β i ; α 0 /D = φ, α 0 /D = φ -1 .


Katharina Haude

Motion in Movima

1

Motion in Movima

Katharina Haude, January 2015

There are languages which reflect the importance of motion, whether directed or undirected, in some way in their grammar. Aymara, for instance -my first language of study, at the time when I first met Mily in Leiden (2000) -, has a large inventory of direction suffixes indicating motion of something into, out of, against, etc. something else, and it is interesting to see how these suffixes interact with different types of verb roots. Movima, the lowland-Bolivian isolate I have been studying ever since the "Lexicon and syntax" project in Nijmegen, is not like that. But since motion is a universally perceptable phenomenon, perhaps it is even more interesting to look at a language that has less spectacular ways of expressing it. This is attempted below, and I will see how far I get.

Like other languages, Movima has motion verbs as well as grammatical elements expressing motion. I will start out with motion verbs.

Motion verbs

For the purpose of this paper, I classify as "motion verb" an intransitive verb that denotes motion of an entity (expressed as the argument) from one place to another without depending on the construction or context. Thus, a verb like Movima ascheɬ 'sit (down)' is not classed as a motion verb because its interpretation as either stative (sit) or dynamic (sit down) depends on the context. I assume that this is not the case for the following verbs:

(1) reflexives This list looks rather messy. With respect to meaning, there is no clear preference for the expression of either path or manner. The forms of the verbs do not seem to correspond to any particular semantic property. There is only one reflexive verb (1), although many Movima intransitive verb roots take the reflexive suffix in their most basic form. Similarly, middle reduplication, also very common with intransitives (indicating an "affected agent"), is only reflected marginally (2). There are a few monomorphemic verbs (3), but their exceptional status makes one suspect that these are lexicalized forms of earlier complex elements. In this group, the verb di:raɬ is particularly striking: it means that one travels from one's chaco or other settlement to Santa Ana, e.g. for a festivity. Classifier-like elements are common in motion verbs, as illustrated in (4); there are some that denote the moving entity, e.g. the canoe or body, but most denote the Ground with respect to which the Figure moves (some of these cases are lexicalized). Suffixes containing the phonemes -e and -ɬ are a complicated issue, since they seem to lose the e in some contexts, and it is hard to tell which suffix one is dealing with. There is an 'agentive' one (5), which, like reflexives and middles, marks many dynamic intransitive verbs, and which is compatible with another suffix of this type when a classifier is inserted (as in weleɬbaɬe). In verbs containing a classifier and ending in -(e)ɬ (6), the classifier seems to denote the Ground, but then, this is not consistent. The same analysis can be proposed for the verbs ending in -ɬe (7), a suffix that, elsewhere, is quite easily identified as one type of applicative ("co-participant") -but what is the difference with -ɬ here?

To sum up, while there is a number of motion verbs, neither the lexicon nor the derivational morphology treat them as a group or single them out in any particular way. In this domain, therefore, motion does not play a significant role in Movima.

Demonstratives

The system of demonstratives, which can be used as predicates and as pronouns, is highly elaborate in Movima. First of all, demonstratives distinguish sex and animacy (i.e. singular forms for female humans, masculine humans, non-humans vs. one plural for all these categories). Secondly, they distinguish proximity to speaker vs. hearer, absence, and ceased existence. Entities that are in sight, but not near to either speaker or hearer, are specified for their position as standing, not-standing, or elevated, and their relative distance. This category also contains sets for entities that are approaching or retreating, as shown in Table 1. The examples ( 8) and ( 9) illustrate the demonstratives for approaching and retreating entities, respectively. In (8), the demonstrative serves as the predicate. In ( 9), the demonstrative is used as a pronoun, i.e. it cooccurs with a predicate, occupying the same position that can otherwise be occupied by a free personal pronoun.

( Thus, in the system of demonstratives, motion has the same status as a standing or a nonstanding static position. One might wonder whether exophoric reference demands much more: one looks ahead for something standing, on the ground for something sitting or lying, and one may have a different way of searching for something that is moving.

Durative particles

The three Movima durative particles, which, like most Movima particles, cover the same positional categories as the demonstratives for visible entities: standing, nonstanding, and moving. Like most other particles, they can occur anywhere in the clause (even inside an NP).

(12) ena' 'standing' da(ya)' 'non-standing (sitting or lying)'

buka' 'moving'

The particle which is of interest here, buka', can cooccur with any verb, not only one expressing a motion event. In line with its aspectual, atelic meaning, it does not imply directed (i.e. telic) motion. Its main sense seems to be that the referent does not carry out an activity at one single place.

Example (13) illustrates the particle in combination with a motion verb (the --symbol indicates a particular kind of cliticization).

( In the current Movima corpus of about 26,000 sentences, there are over 500 occurrences of buka'. It would be interesting to make an inventory of all the verbs that the particle actually occurs with, in order to see if there are any preferences (e.g. for motion verbs), and how the particle is interpreted in combinations with different types of non-motion verbs or in different contexts.

Conclusion

Thus, in the verbal lexicon, motion does not play a particular role: there is nothing that sets apart motion verbs from other intransitive verbs. In the domain of exophoric reference, there are two distinct sets of demonstratives, which distinguish between approaching and retreating motion. Finally, there is an aspectual particle which simultaneously indicates duration and motion (or non-permanent location). The conclusion I draw from the data presented here is that even though different types of motion (such as direction or manner) are not strongly diversified, motion as such is a grammaticalized category in Movima.

Table 1

 1

	. Motion demonstratives (DEM)
		hum. male (M) hum. female (F) non-human (N) plural (PL)
	approaching (APPR) kula'wa	kila'niwa	kola'wa	kila'wa
	retreating (RTR)	kulro'	kilno'	kolro'	kilro'

che--iy'i joy-che--iy'i

  DEM.PL.AB(SENTIAL) stay_put ART.PL.AB DUR.MOVE name=3PL.AB here 'Their names are still here (i.e., in a book at the Cabildo).'

	(15)	kiro'			batukni kis	buka'	e:ɬa=is	ney
	When cooccurring with a demonstrative for visible entitites, the durative particles are in
	concordance with the categories expressed by the demonstratives, as shown by (16) and (17).
	(16)	kulro'	buka'		no-kos	bi:si=us
		DEM.RETR.M DUR.MOVE OBL-ART.N.AB bike=3M.AB
		'He is moving away on his bike.'
	(17)	kola'wa=s		mi:chi ɬat buka'a
		DEM.APPR.N=DET	cat	EVID DUR.MOVE
	13)	jayna joy-already DUR.MOVE buka' it 1INTR go-REFL--1PL	go-REFL--1PL
		'Then we were moving on, moving on.'
	In (14), buka' occurs with a non-motion activity verb ('chew'), indicating that the activity is
	carried out while moving. Example (15) contains a static verb (batukni 'stay put'), with the
	particle buka' indicating that the referents are located at different places.
	(14)	inɬa rey juyeni di'	loy rey jirampoj-wa=Ø
		I	pues person REL	not pues like-NMLZ=1SG
		n-as		buka'		dan-eɬ-wa=Ø	n-as	chora:da

OBL-ART.N DUR.MOVE chew-AGENTIVE-NMZ=1SG OBL-ART.N street 'I am a person who does not like to be walking around in the street chewing.' 'Look, there is a cat coming!'