<figure><img src="image_1.png" /></figure>

HAL
open science

# Structures simpliciales, simploïdales et cellulaires pour la modélisation géométrique à base topologique

Samuel Peltier

► To cite this version:

Samuel Peltier. Structures simpliciales, simploïdales et cellulaires pour la modélisation géométrique à base topologique. Informatique [cs]. Université de Poitiers, 2023. tel-04523303

HAL Id: tel-04523303

https://hal.science/tel-04523303

Submitted on 27 Mar 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
Habilitation à diriger des recherches
en informatique

présentée par

SAMUEL PELTIER

Structures simpliciales, simploïdales
et cellulaires pour la modélisation
géométrique à base topologique

Préparée au laboratoire XLIM, UMR CNRS 7252

Soutenue publiquement le 14 décembre 2023

Composition du jury :

<table><tr><td>DOMINIQUE BECHMANN, professeure, université de Strasbourg, ICUBE</td><td>Rapporteure</td></tr><tr><td>CHRISTIAN GENTIL, professeur, université de Bourgogne, LIB</td><td>Rapporteur</td></tr><tr><td>JEAN-LUC MARI, professeur, Aix-Marseille université, LIS</td><td>Rapporteur</td></tr><tr><td>GUILLAUME DAMIAND, directeur de recherche, CNRS, LIRIS</td><td>Examineur</td></tr><tr><td>STEFANIE HAHMANN, professeure, université de Grenoble, LJK</td><td>Examinatrice</td></tr><tr><td>PASCAL LIENHARDT, professeur, université de Poitiers, XLIM</td><td>Examineur</td></tr><tr><td>GÉRALDINE MORIN, professeure, université de Toulouse, IRIT</td><td>Examinatrice</td></tr></table>
<figure><img src="image_2.png" /></figure>
Remerciements

Je suis infiniment reconnaissant à toutes celles et ceux qui ont contribué, de près ou
de loin, à ce que cette aventure aboutisse.

Je remercie sincèrement l'ensemble des membres du jury DOMINIQUE BECHMANN,
CHRISTIAN GENTIL, JEAN-LUC MARI, GUILLAUME DAMIAND, STEFANIE HAHMANN,
PASCAL LIENHARDT et GÉRALDINE MORIN d'avoir accepté d'évaluer mon travail.

Je tiens à exprimer toute ma reconnaissance à PASCAL LIENHARDT pour nos
innombrables discussions plus passionnantes les unes que les autres, pour son regard
affuté sur l'ensemble des sujets traités dans ce manuscrit, et pour tout le savoir qu'il a pu
me transmettre durant la vingtaine d'années qui vient de s'écouler.

Les probabilités pour que j'oublie de nommer des personnes étant trop fortes, mes
remerciements suivants seront tout aussi sincères que concis. Merci donc aux collègues,
nombreux, pour tous nos échanges tellement enrichissants, et pour tous leurs encourage-
ments. Je remercie 10³ fois ma famille et tous mes potes, nombreux eux aussi, pour leur
soutien sans faille tout au long de cette aventure.

Je finalement déroger à la règle que je viens d'annoncer, et terminer par remercier
nommément les trois personnes les plus importantes de ma vie, mon triptyque, mes filles :
Lalie, Bertille et Rose.
<figure><img src="image_3.png" /></figure>
# Table des matières

<table><tr><td>1 Introduction</td><td>1</td></tr><tr><td>1.1 Contexte – Problématique</td><td>1</td></tr><tr><td>1.1.1 Caractérisation topologique</td><td>2</td></tr><tr><td>1.1.2 Combinatoire, algèbre et géométrie</td><td>4</td></tr><tr><td>1.2 Structure du document</td><td>7</td></tr><tr><td>2 Structures Combinatoires</td><td>9</td></tr><tr><td>2.1 Structures simpliciales</td><td>11</td></tr><tr><td>2.1.1 Ensembles semi-simpliciaux</td><td>11</td></tr><tr><td>2.1.2 Complexes simpliciaux abstraits</td><td>15</td></tr><tr><td>2.2 Structures simploïdales</td><td>18</td></tr><tr><td>2.2.1 Ensembles semi-cubiques</td><td>19</td></tr><tr><td>2.2.2 Ensembles semi-simploïdaux</td><td>19</td></tr><tr><td>2.2.3 Complexes simploïdaux abstraits</td><td>23</td></tr><tr><td>2.3 Structures cellulaires</td><td>27</td></tr><tr><td>2.3.1 Numérotation – Cellules</td><td>27</td></tr><tr><td>2.3.2 Graphes d'incidence</td><td>29</td></tr><tr><td>2.3.3 Variétés – Quasi-variétés</td><td>33</td></tr><tr><td>2.3.4 Cartes combinatoires</td><td>36</td></tr><tr><td>2.3.5 Équivalences de modèles</td><td>42</td></tr><tr><td>2.4 Structures celluloïdales</td><td>45</td></tr><tr><td>2.4.1 Numérotation – Celluloïdes</td><td>45</td></tr><tr><td>2.4.2 Quasi-variétés celluloïdales</td><td>47</td></tr><tr><td>2.4.3 Graphes d'incidences simploïdaux</td><td>52</td></tr><tr><td>2.5 Gestion de la dégénérescence</td><td>54</td></tr><tr><td>2.5.1 Ensembles simpliciaux</td><td>54</td></tr><tr><td>2.5.2 Ensembles simploïdaux</td><td>58</td></tr><tr><td>2.6 Conclusion</td><td>64</td></tr><tr><td>3 Calculs de groupes d'homologie</td><td>65</td></tr><tr><td>3.1 Notions de base</td><td>66</td></tr><tr><td>3.1.1 CW-complexes – Complexe de chaînes</td><td>66</td></tr><tr><td>3.1.2 Cycles, bords, homologie</td><td>67</td></tr><tr><td>3.2 Calcul global</td><td>68</td></tr><tr><td>3.2.1 Matrices d'incidence – Forme normale de SMITH</td><td>69</td></tr><tr><td>3.2.2 Calcul des générateurs – forme normale de SMITH-AGOSTON</td><td>70</td></tr><tr><td>3.2.3 Gestion des dégénérés</td><td>71</td></tr><tr><td>3.2.4 Calcul sur les ensembles simploïdaux</td><td>72</td></tr><tr><td>3.2.5 Calcul sur les structures cellulaires</td><td>72</td></tr><tr><td>3.2.6 Liens avec la caractéristique d'EULER-POINCARÉ</td><td>76</td></tr></table>
<table><tbody><tr><td>3.3</td><td>Calcul incrémental</td><td>77</td></tr><tr><td>3.3.1</td><td>Calcul incrémental des nombres de BETTI</td><td>77</td></tr><tr><td>3.3.2</td><td>Homologie persistante</td><td>77</td></tr><tr><td>3.3.3</td><td>Homologie effective</td><td>81</td></tr><tr><td>3.3.4</td><td>Calcul incrémental sur des structures simploïdales</td><td>92</td></tr><tr><td>3.3.5</td><td>Calcul incrémental sur des quasi-variétés cellulaires</td><td>96</td></tr><tr><td>3.4</td><td>Conclusion</td><td>100</td></tr><tr><td>4</td><td>Objets géométriques</td><td>103</td></tr><tr><td>4.1</td><td>Réalisation géométrique</td><td>104</td></tr><tr><td>4.1.1</td><td>Complexes simpliciaux</td><td>104</td></tr><tr><td>4.1.2</td><td>Complexes simploïdaux</td><td>105</td></tr><tr><td>4.1.3</td><td>Autres structures</td><td>106</td></tr><tr><td>4.2</td><td>Plongement linéaire</td><td>106</td></tr><tr><td>4.2.1</td><td>Complexes simpliciaux abstraits</td><td>106</td></tr><tr><td>4.2.2</td><td>Complexes simploïdaux abstraits</td><td>107</td></tr><tr><td>4.2.3</td><td>Structures cellulaires sans multi-incidence</td><td>107</td></tr><tr><td>4.2.4</td><td>Structures avec multi-incidence</td><td>108</td></tr><tr><td>4.3</td><td>Espaces de BÉZIER</td><td>108</td></tr><tr><td>4.3.1</td><td>Notions de base</td><td>108</td></tr><tr><td>4.3.2</td><td>Ensembles semi-simpliciaux</td><td>109</td></tr><tr><td>4.3.3</td><td>Ensembles semi-simploïdaux</td><td>113</td></tr><tr><td>4.3.4</td><td>Ensembles simpliciaux</td><td>116</td></tr><tr><td>4.3.5</td><td>Ensembles simploïdaux</td><td>119</td></tr><tr><td>4.3.6</td><td>Structures cellulaires</td><td>122</td></tr><tr><td>4.4</td><td>Application à la modélisation d'objets tubulaires</td><td>123</td></tr><tr><td>4.4.1</td><td>Contexte et objectifs</td><td>123</td></tr><tr><td>4.4.2</td><td>Branches - Jonctions</td><td>124</td></tr><tr><td>4.4.3</td><td>Pavage quad de la sphère</td><td>125</td></tr><tr><td>4.4.4</td><td>Géométrie des branches</td><td>128</td></tr><tr><td>4.4.5</td><td>Résultats</td><td>130</td></tr><tr><td>4.5</td><td>Conclusion</td><td>131</td></tr><tr><td>5</td><td>Conclusion - Perspectives</td><td>135</td></tr><tr><td>5.1</td><td>Bilan</td><td>135</td></tr><tr><td>5.1.1</td><td>Structures combinatoires</td><td>135</td></tr><tr><td>5.1.2</td><td>Calcul de l'homologie</td><td>136</td></tr><tr><td>5.1.3</td><td>Objets géométriques</td><td>136</td></tr><tr><td>5.2</td><td>Projet de recherche</td><td>137</td></tr><tr><td>5.2.1</td><td>Structures combinatoires</td><td>137</td></tr><tr><td>5.2.2</td><td>Calcul de l'homologie</td><td>138</td></tr><tr><td>5.2.3</td><td>Objets géométriques</td><td>139</td></tr><tr><td colspan="2">Bibliographie</td><td>143</td></tr></tbody></table>
# Introduction

## Sommaire

<table><tr><td>1.1 Contexte – Problématique</td><td>1</td></tr><tr><td>1.1.1 Caractérisation topologique</td><td>2</td></tr><tr><td>1.1.2 Combinatoire, algèbre et géométrie</td><td>4</td></tr><tr><td>1.2 Structure du document</td><td>7</td></tr></table>

## 1.1 Contexte – Problématique

La *modélisation géométrique à base topologique* vise à décrire des objets géométriques structurés en cellules de différentes dimensions : sommets, arêtes, faces, volumes... Cette description se retrouve dans divers domaines de l'informatique graphique : en conception assistée par ordinateur (CAO), en géométrie algorithmique, en simulation, en géometrie discrète, en animation, ou encore en analyse d'image.

Le terme *modélisation géométrique à base topologique* met en exergue deux adjectifs qui sont au coeur de cette discipline : *géométrique* et *topologique*. On s'intéresse ici à la *modélisation d'objets géométriques structurés* et à leur caractérisation topologique. Par exemple, considérons les dés représentés sur la figure 1.1a. Chaque dé est composé d'un nombre de faces différent et les faces de ces dés n'ont pas toutes la même structure : celles des dés rouge et bleu possèdent quatre cotés, celles des dés jaune, vert et blanc ont trois cotés, et celles du dé noir en ont cinq.

La structure de chaque dé peut être décrite par la structure de ses faces et par les relations d'adjacence entre celles-ci. Par ailleurs, le volume associé à chaque dé est entièrement décrit par son bord. Cette approche de représentation par les bords est classiquement utilisée en modélisation (B-Rep). Dans d'autres contextes, cette représentation par les bords ne suffit pas : une représentation des éléments volumiques est nécessaire. C'est le cas par exemple en fabrication additive lorsque l'on souhaite fabriquer un objet composé de différents matériaux, en géologie où un maillage peut être utilisé pour effectuer des simulations numériques, ou encore pour l'élaboration de jumeaux numériques pour la simulation d'actes chirurgicaux ou de réactions chimiques. La structure complète d'un dé peut être décrite à partir de cellules abstraites de dimension 0 (les sommets), 1 (les arêtes), 2 (les faces) et 3 (le volume), en décrivant les relations d'incidence entre les cellules de dimension $n$ et $n-1$ : les faces sont incidentes au volume, chaque arête est incidente à deux
<figure><img src="image_4.png" /><figcaption>FIGURE 1.1 – (a) Différents dés présentant différentes structures et différentes formes. (b) Différents joints de différentes formes.</figcaption></figure>

faces, et un coin (i. e. un sommet) d'un dé correspond à des extrémités d'arêtes adjacentes.

On peut noter que les faces du dé rouge et du dé bleu, qui ont la même structure, ont des formes différentes. Il est donc important de pouvoir associer une cellule géométrique à chaque cellule abstraite. Pour un dé, en associant un point de $\mathbb{R}^3$ à chaque sommet, la forme de chaque arête peut être définie par le segment reliant ses deux extrêmités, et la forme de chaque face, comme la partie du plan bordée par les arêtes de son bord. Dans d'autres contextes, il est important de pouvoir donner des formes courbes aux objets manipulés. C'est le cas notamment en CAO pour la modélisation de pièces mécaniques ou d'éléments de carosserie, où des modèles paramétriques surfaciques basés sur les espaces de BÉZIER, B-splines ou NURBS sont classiquement utilisés pour représenter des surfaces courbes. Lorsque l'on associe une forme géométrique à un objet abstrait, combinatoire, on le réalise géométriquement dans un espace topologique.

Enfin, on peut facilement imaginer que chacun de ces dés peut être obtenu à partir d'un bloc de plastique suffisamment grand en retirant de la matière, sans jamais percer le bloc. Considérons à présent les joints toriques représentés sur la figure 1.1b. Ils peuvent également être obtenus à partir d'un bloc de plastique en retirant de la matière, mais cette fois-ci, il faudra obligatoirement percer un tunnel afin d'obtenir la structure désirée. En conséquence, un dé et un joint torique n'ont pas la même caractérisation topologique.

### 1.1.1 Caractérisation topologique

Selon le contexte, la caractérisation topologique d'un objet prend des sens différents. Afin préciser de quoi l'on parle, considérons des variétés sans bord de dimension 2, ou surfaces fermées : la sphère, le tore à $n$ trous, la bouteille de KLEIN ou encore le plan projectif. De manière intuitive, tous ces objets peuvent être obtenus en cousant deux à
deux des pièces de tissu polygonales le long de leurs côtés<fnref n="1" />. En topologie générale, une variété sans bord de dimension 2 est définie par le voisinage de tout point qui doit être topologiquement équivalent, ou homéomorphe à une boule de dimension 2. C'est-à-dire qu'il existe une bijection continue permettant de passer du voisinage de tout point à un disque et telle que la bijection inverse soit également continue. Dit autrement, si on se donne un point quelconque sur l'assemblage, il est toujours possible de découper un petit disque de tissu autour. De plus deux points distincts admettent des voisinage disjoints, on dit alors que l'espace topologique est séparé ou HAUSDORFF.

En faisant abstraction de la géométrie d'un objet, on peut étudier sa topologie d'un point de vue combinatoire en ne considérant que sa structure, *i. e.* les relations d'incidence entre les cellules. Si dans un objet subdivisé de dimension 2, la propriété toute arête est incidente à exactement deux faces est satisfaite, alors il s'agit d'une variété combinatoire fermée de dimension 2. C'est-à-dire que si l'on se donne une représentation combinatoire d'un objet, alors on peut savoir s'il s'agit d'une surface fermée, et si la réponse est oui, alors on sait, à homéomorphisme près, à quelle variété topologique elle correspond. Malheureusement, cette caractérisation combinatoire des surfaces ne se généralise pas et ne permet pas de caractériser les variétés de dimension supérieure. Comme nous le verrons dans le chapitre 2, la classe d'objets caractérisée est plus large, il s'agit des quasi-variétés.

De manière générale, il n'est pas possible de caractériser à homéomorphisme près les objets géométriques que l'on manipule. En revanche, on peut caractériser leur structure, en calculant des propriétés qui sont préservées par homéomorphisme. On appelle ces propriétés des *invariants topologiques*. Par exemple, le nombre de composantes connexes, le nombre de tunnels, l'orientabilité, sont des invariants topologiques. Il est essentiel de savoir contrôler et caractériser la structure des objets que l'on manipule. Par exemple, lorsque l'on reconstruit un modèle volumique issu d'un système d'acquisition 3D, les propriétés topologiques peuvent guider cette reconstruction, e.g. le réseau racinaire d'une plante ou un arbre vasculaire est composé d'une seule composante connexe et ne contient pas de tunnels, une structure d'os trabéculaire contient des tunnels mais pas de cavité. En CAD-CAM, lorsque l'on modélise une pièce par des opérations de construction, il est important de pouvoir détecter des changements de structure, par exemple la déconnexion ou la création d'un tunnel ; *in fine*, la pièce ne pourra être usinée qu'à condition que son bord soit orientable.

L'homologie est un invariant topologique qui caractérise les "trous" d'un objet en toute dimension. En dimension 0, les trous correspondent aux composantes connexes, en dimension 1 aux tunnels, en dimension 2 aux cavités ; cette notion de trou se généralise en dimension supérieure. Bien sûr, deux objets ayant la même homologie ne sont pas nécessairement homéomorphes. Par exemple la figure 1.2 représente deux objets qui ont l'homologie du tore : une composante connexe, deux tunnels et une cavité. L'objet représenté en (a) est homéomorphe au tore, mais celui représenté en (b) ne l'est pas.

À l'inverse, si deux objets ont des invariants topologiques différents, alors ils ne sont

<footnote n="1">1. En réalité, on ne peut pas réaliser une bouteille de KLEIN ou un plan projectif dans $\mathbb{R}^3$; on peut en revanche le faire dans $\mathbb{R}^4$.</footnote>
<figure><img src="image_5.png" /><figcaption>FIGURE 1.2 – Deux objets ayant l'homologie du tore. (a) est homéomorphe au tore, (b) ne l'est pas.</figcaption></figure>

pas homéomorphes. Par exemple, considérons une balle de tennis de table et une bille de flipper. Ces deux objets ont une seule composante connexe, et aucun tunnel. Leurs groupes d'homologie de dimension 0 et 1 sont identiques (i. e. un trou de dimension 0 et aucun de dimension 1). En revanche, la balle de tennis de table est creuse, elle possède donc une cavité (i. e. un trou de dimension 2) alors que la bille de flipper est pleine et n'a donc pas de trou de dimension 2. Ces deux objets ne sont donc pas homéomorphes.

L'homologie est un invariant topologique puissant et incontournable :

— il est classiquement étudié en topologie algébrique, de nombreux résultats mathématiques sont établis et peuvent être utilisés;

— il contient d'autres invariants comme le nombre de composantes connexes, les nombres de BETTI, la caractéristique d'EULER ;

— il est directement lié à la structure de l'objet, c'est-à-dire qu'un objet de dimension $n$ ne contient aucun trou de dimension supérieure à $n$, ce qui n'est pas le cas par exemple des groupes d'homotopie ;

— sa définition est homogène : il se calcule de la même manière en toute dimension.

## 1.1.2 Combinatoire, algèbre et géométrie

### Un monde combinatoire

Au cours des dernières décennies, de nombreuses structures ont été définies afin de répondre à différents besoins en informatique graphique. Par exemple, en géométrie discrète ou en simulation, on travaille usuellement avec des structures à base de cubes, alors qu'en géométrie algorithmique ou en rendu, il est fréquent de travailler avec des structures à base de simplexes. Dans d'autres contextes, il peut s'avérer utile d'utiliser des structures permettant de manipuler des cellules plus générales, où par exemple, une face peut être bordée par un nombre quelconque d'arêtes.

Ainsi on peut distinguer ces différentes structures en fonction des types de cellules utilisées : certaines utilisent des cellules régulières simpliciales, cubiques ou simploïdales (un simploïde est un produit de simplexes quelconques), d'autres utilisent des cellules
"quelconques".

On peut également distinguer ces structures selon les contraintes imposées ou non sur
les assemblages de cellules. Par exemple, certaines structures contraignent les assemblages
dans le but de représenter des variétés. D'autres structures au contraire permettent
de modéliser des objets non-variétés, c'est-à-dire des assemblages "libres". Cela peut
par exemple être utile pour la représentation d'un objet volumique par son squelette
(axe médian), ou en géométrie discrète afin de considérer l'assemblage de deux voxels
partageant seulement un sommet ou une arête comme connexe.

Un monde géométrique

Lorsque l'on associe une forme à un objet combinatoire, on le réalise géométriquement dans un espace topologique : on associe une forme géométrique à chaque cellule abstraite. On se place ici généralement dans le cadre d'espaces CW-complexes 2, où les cellules sont des boules topologiques. Si on se place dans l'espace Rn, la boule de dimension n, centrée en c, et de rayon r est l'ensemble des points situés à une distance inférieure à r du point c 3. Un CW-complexe est défini de manière constructive comme suit : on se donne un ensemble discret X 0 de boules de dimension 0. En attachant des boules de dimension 1 à X 0 le long de leur bord S 0, on obtient X 1. Puis, en attachant des boules B 2 à X 1 le long de leur bord S 1 on obtient X 2 et ainsi de suite jusqu'à la dimension voulue. La figure 1.3 illustre une construction d'un CW-complexe décrivant le tore. L'ensemble X 0 ne contient qu'un sommet. Ensuite, deux arêtes sont attachées à ce sommet, on obtient X 1. Enfin un disque est attaché à X 1.

<figure><img src="image_6.png" /><figcaption>FIGURE 1.3 – Une construction d’un CW-complexe : le tore.</figcaption></figure>

Un monde algébrique

Les groupes d'homologie permettent de caractériser les CW-complexes en fonction de leurs
trous. Pour effectuer les calculs, on associe une structure algébrique à un CW-complexe :
un complexe de chaînes libre. Pour tout $k \in [0, n]$, on associe l'ensemble des boules $B^k$
à un groupe abélien ($C_k, +$). Les recollements des boules $B^k$ du CW-complexe sur son
$(k-1)$-squelette $X^{k-1}$ sont décrits dans le complexe de chaînes par des applications de
bord $\partial_k : C_k \to C_{k-1}$ qui correspondent à l'extension linéaire des relations d'incidence des

<footnote n="2">2. Les CW-complexes Closure finite complexes with Weak topology, ont été définis par J. H. C. Whitehead [Whitehead 1949].</footnote>

<footnote n="3">3. Le bord d'une boule $B^n$ est une sphère $S^{n-1}$.</footnote>
cellules. L'homologie du CW-complexe peut alors être calculée sur le complexe de chaînes associé.

Lorsque les CW-complexes sont triangulables, on associe directement un complexe de chaînes à une structure combinatoire. Une fois calculée, l'information homologique peut être restituée sur la structure combinatoire ou sur l'objet géométrique. On peut ainsi caractériser l'assemblage des cellules en fonction de ses trous, et selon le cas, localiser ces trous sur l'objet géométrique ou sur sa structure combinatoire.

## Activités de recherche

Le triptyque : *structures combinatoires, calcul de propriétés topologiques, formes géométriques* constitue la ligne directrice de nos travaux de recherche depuis le début des années 2000, où trois *mondes* interagissent : un monde combinatoire, un monde algébrique, et un monde géométrique. Ce triptyque représente donc notre vision de la modélisation géométrique, et notre approche de la recherche dans ce domaine qui vise à contribuer à chacun de ces trois *mondes*, tout en tenant compte des liens qui existent entre eux. La figure 1.4 décrit plus précisément ce triptyque, sur lequel s'appuie ce manuscrit.

<figure><img src="image_7.png" /><figcaption>FIGURE 1.4 – La structure des objets subdivisés est modélisée par une structure combinatoire. Ces objets sont réalisés géométriquement par un CW-complexe, respectant la structure. À tout objet subdivisé modélisé par une structure combinatoire, on peut associer des structures algébriques, à partir desquelles l'homologie de l'objet peut être calculée. Une fois le calcul effectué, l'information homologique peut être reportée sur l'objet combinatoire ou sur sa géométrie.</figcaption></figure>
Les travaux présentés dans ce manuscrit s’appuient sur des collaborations internationales avec ROCIO GONZALES DIAZ, YLL HAXHIMUSA et ADRIAN ION, WALTER G. KROPATSCH, nationales avec GUILLAUME DAMIAND, JACQUES-OLIVIER LACHAUD et GÉRALDINE MORIN, et locales avec SYLVIE ALAYRANGUES, ARTHUR CAVALIER, LAURENT FUCHS et PASCAL LIENHARDT. Y ont participé les doctorants et post-doctorants INÉS CASTILLA RIESO (doctorante XLIM), SOUKAYNA QARBOUA (post-doctorante XLIM), WASSIM RHARBAOUI (doctorant XLIM), ainsi que les stagiaires du Master informatique de l’université de Poitiers, et de l’ENSEEIHT DAMIEN AHOLOU, CLÉMENT CONTET, ANTOINE LAGRANGE et ALEXIS LOUAIL.

Ces collaborations ont donné lieu aux principales publications suivantes :

- concernant le calcul de groupes d'homologie et son optimisation : [Damiand 2006, Peltier 2007a, Peltier 2007b, Peltier 2009b, Damiand 2008, Alayrangues 2009b, Alayrangues 2009a, Damiand 2012, Alayrangues 2015b, Alayrangues 2015a, Lienhardt 2016, Rharbaoui 2020].

- concernant la définition et l'étude de structures combinatoires, en particulier simploïdales et cellulaires [Peltier 2009a, Alayrangues 2015c, Peltier 2018, Peltier 2023],

- concernant la modélisation d'objets tubulaires volumiques et paramétriques, à partir d'un squelette; qui est une activité de recherche plus récente [Peltier 2021].

## 1.2 Structure du document

Le chapitre 2 propose un tour d'horizon de structures combinatoires utilisées en modélisation géométrique à base topologique : simpliciales, simploïdales et cellulaires. En particulier, une classification est proposée, mettant en avant trois mécanismes : le produit cartésien, la numérotation cellulaire et la suppression de la multi-incidence.

La section 2.1 rappelle la définition des ensembles semi-simpliciaux et des complexes simpliciaux abstraits. La section 2.2 rappelle les définitions des ensembles semi-simploïdaux, une définition des complexes simploïdaux abstraits est proposée. La section 2.3 présente des exemples de structures issues de deux familles de structures cellulaires : les *CF*-ordres, les *n*-surfaces, et les chaînes de *n*-surfaces dont les définitions sont basées sur les ordres (ou graphes d'incidence) ; les *G* cartes et les chaînes de cartes dont les définitions sont basées sur les cartes combinatoires. En section 2.4, nous définissons la nouvelle notion de *celluloïde*, permettant de définir des structures *celluloïdales* complétant la classification proposée en faisant le pont entre les structures simploïdales et cellulaires. Enfin, la section 2.5 met en avant un autre mécanisme : la dégénérescence, permettant la définition du produit cartésien simplicial et du cône simploïdal. Les structures présentées dans cette partie sont les ensembles simpliciaux et les ensembles simploïdaux.

Le chapitre 3 est dédié au calcul de groupes d'homologie. La section 3.1 rappelle les notions de base de complexe de chaînes, de groupe des cycles, groupe des bords et groupes d'homologie. La section 3.2 rappelle les méthodes globales basées sur des réductions de matrices d'incidence, pour les structures simpliciales, simploïdales et cellulaires. En
particulier nous montrons comment étendre les calculs aux structures cellulaires. La section 3.3 est dédiée au calcul incrémental de l'homologie. Les notions liées à l'homologie persistante sont rappelées, l'homologie effective est présentée, ainsi qu'une mise en œuvre pour l'opération d'identification. Le calcul incrémental basé sur le produit cartésien est présenté, mettant en avant la formule de KÜNNETH. Ce résultat peut être directement utilisé dans le cadre simploïdal. Enfin, nous montrons comment les outils de l'homologie effective permettent de calculer l'homologie de cartes combinatoires.

Le chapitre 4 traite de la géométrie associées aux structures vues au chapitre 2. La section 4.1 présente la notion de réalisation géométrique. La définition des complexes simpliciaux réalisant les complexes simpliciaux abstraits est rappelée, et la réalisation des complexes simploïdaux abstraits est présentée. La réalisation géométrique des autres structures est discutée.

La section 4.2 présente les plongements linéaires, c'est-à-dire que la forme de chaque cellule est déduite des positions de l'ensemble des sommets de son bord. La section 4.3 est dédiée aux espaces paramétriques de Bézier, permettant de donner une forme courbe aux cellules. En particulier, nous avons établi les propriétés permettant de retrouver les structures d'ensembles simpliciaux et simploïdaux au sein même des espaces de Bézier. Enfin, la section 4.4 présente un champ d'application des ensembles semi-simploïdaux : la modélisation d'objets tubulaires volumiques paramétriques à partir de squelettes.

Pour conclure, le chapitre 5.1 présente un bilan, ainsi que des perspectives de recherche en lien avec l'ensemble des travaux présentés.
# Structures Combinatoires

## Sommaire

<table><tbody><tr><td><strong>2.1</strong></td><td><strong>Structures simpliciales</strong></td><td><strong>11</strong></td></tr><tr><td>2.1.1</td><td>Ensembles semi-simpiciaux</td><td>11</td></tr><tr><td>2.1.2</td><td>Complexes simpliciaux abstraits</td><td>15</td></tr><tr><td><strong>2.2</strong></td><td><strong>Structures simploïdales</strong></td><td><strong>18</strong></td></tr><tr><td>2.2.1</td><td>Ensembles semi-cubiques</td><td>19</td></tr><tr><td>2.2.2</td><td>Ensembles semi-simploïdaux</td><td>19</td></tr><tr><td>2.2.3</td><td>Complexes simploïdaux abstraits</td><td>23</td></tr><tr><td><strong>2.3</strong></td><td><strong>Structures cellulaires</strong></td><td><strong>27</strong></td></tr><tr><td>2.3.1</td><td>Numérotation – Cellules</td><td>27</td></tr><tr><td>2.3.2</td><td>Graphes d'incidence</td><td>29</td></tr><tr><td>2.3.3</td><td>Variétés – Quasi-variétés</td><td>33</td></tr><tr><td>2.3.4</td><td>Cartes combinatoires</td><td>36</td></tr><tr><td>2.3.5</td><td>Équivalences de modèles</td><td>42</td></tr><tr><td><strong>2.4</strong></td><td><strong>Structures celluloïdales</strong></td><td><strong>45</strong></td></tr><tr><td>2.4.1</td><td>Numérotation – Celluloïdes</td><td>45</td></tr><tr><td>2.4.2</td><td>Quasi-variétés celluloïdales</td><td>47</td></tr><tr><td>2.4.3</td><td>Graphes d'incidences simploïdaux</td><td>52</td></tr><tr><td><strong>2.5</strong></td><td><strong>Gestion de la dégénérescence</strong></td><td><strong>54</strong></td></tr><tr><td>2.5.1</td><td>Ensembles simpliciaux</td><td>54</td></tr><tr><td>2.5.2</td><td>Ensembles simploïdaux</td><td>58</td></tr><tr><td><strong>2.6</strong></td><td><strong>Conclusion</strong></td><td><strong>64</strong></td></tr></tbody></table>

Ce chapitre propose un tour d'horizon de structures combinatoires utlisées en modélisation géométrique à base topologique : simpliciales, simploïdales et cellulaires.

En particulier, nous étendons et complétons la classification présentée dans [Bechmann 2007, Lienhardt 2009]. La figure 2.1 illustre cette classification dans laquelle les structures se déduisent des ensembles semi-simpliciaux par trois mécanismes principaux : le produit cartésien, la numérotation cellulaire et la suppression de la multi-incidence. Dit autrement, toutes les structures ont un lien, plus ou moins direct avec les ensembles semi-simpliciaux. Plus précisément :

- un ensemble semi-simplicial est un ensemble de simplexes abstraits, les relations d'incidence entre ces simplexes est définie par des opérateurs de face;

- le produit cartésien permet de définir les structures simploïdales à partir des structures simpliciales : un simploïde abstrait correspond à un produit cartésien de simplexes abstraits;
— la numérotation cellulaire permet de définir les structures cellulaires : une cellule de dimension *n* est un cône sur une structure de dimension *n* − 1;

— la suppression de la multi-incidence permet de définir des structures dans lesquelles moins d’informations sont explicitement représentées. En particulier, le simplexe abstrait n’est plus l’élément de base pour de telles structures, contrairement à celles permettant de représenter des cellules incidentes plusieurs fois à d’autres cellules <fnref n="1" />.

<figure><img src="image_8.png" /><figcaption>FIGURE 2.1 – Classification complète des familles de structures combinatoires, basée sur les ensembles semi-simpliciaux. Trois mécanismes son mis en évidence dans cette classification : le produit cartésien permet de passer des structures simpliciales aux structures simploïdales, la numérotation cellulaire permet de structurer des cellules régulières en cellules plus générales, et la suppression de la multi-incidence permet de changer de formalisme.</figcaption></figure>

Dans cette classification, nous proposons :

— une définition de cellule simploïdale, ou celluloïde : une celluloïde est un produit cartésien de cellules quelconques. Nous posons ainsi le cadre permettant d’étendre les cartes combinatoires afin de représenter des assemblages de celluloïdes;

<footnote n="1">1. Sauf mention contraire, le terme *cellule* est utilisé dans ce manuscrit dans son sens le plus général, et désigne aussi bien un simplexe, un simploïde ou une cellule quelconque.</footnote>
— d’expliciter le mécanisme de suppression de la multi-incidence permettant d’aboutir aux notions classiques de complexes simpliciaux abstraits et de graphes d’incidence. Nous étendons ces structures aux simploïdes et proposons une première définition des complexes simploïdaux abstraits, qui correspondent aux ensembles semi-simploïdaux sans multi-incidence, et posons les bases pour la définition de graphes d’incidence simploïdaux, dont les cellules sont des assemblages de celluloïdes ne présentant pas de multi-incidence.

Un autre mécanisme n’est pas présenté sur la figure 2.1 : la dégénérescence. De manière informelle, il permet "d’écraser" une cellule sur une de ses faces. Par exemple, une arête d’un triangle peut être dégénérée en un sommet. Intuitivement, l’arête géométrique correspondante est écrasée en un point ; le bord du triangle résultant ne comporte alors plus que deux arêtes. Ce mécanisme permet en particulier de définir le produit cartésien simplicial, et le cône simploïdal.

Pour des raisons de clarté, le choix a été fait de présenter en dernier lieu les structures permettant la représentation de la dégénérescence : les ensembles simpliciaux et simploïdaux. Comme nous le verrons en conclusion de ce chapitre, la définition de structures cellulaires permettant la représentation de cellules dégénérées ne nous a pas semblé utile.

La Section 2.1 rappelle les notions d'ensembles semi-simpliciaux et de complexes simpliciaux abstraits. La Section 2.2 rappelle la notion d'ensemble semi-simploïdal, et présente les complexes simploïdaux abstraits. La Section 2.3 rappelle les notions de cartes combina-toires et de graphes d'incidence. La Section 2.4 présente la notion de celluloïde permettant d'étendre les structures de cartes combinatoires au cadre simploïdal. Enfin, la Section 2.5 rappelle les notions d'ensembles simpliciaux et simploïdaux. Nous rappelons ou définis-sons également les opérations permettant manipuler ces structures, en mettant en avant les différents mécanismes établissant les liens existants entre ces structures.

## 2.1 Structures simpliciales

Comme indiqué en introduction, toutes les structures décrites dans ce manuscrit ont un lien avec les ensembles semi-simpliciaux. Dans la littérature, lorsque l'on présente les structures simpliciales, il est courant de commencer par donner la définition des complexes simpliciaux abstraits, qui permettent de décrire des objets simpliciaux de manière ensem-bliste, donc sans multi-incidence. Nous avons fait le choix de commencer par présenter la structure qui est à l'origine de cette classification : les ensembles semi-simpliciaux.

### 2.1.1 Ensembles semi-simpliciaux

Les ensembles semi-simpliciaux permettant de décrire des assemblages quelconques de simplexes. Leur définition se base sur un ensemble de simplexes abstraits, sur lesquels agissent des opérateurs de face, permettant de décrire les relations d'incidence entre un simplexe et les simplexes de son bord.
### 2.1.1.1 Structure combinatoire

**Définition 1** Un ensemble semi-simplicial (ou ESS) de dimension $n$, $S = (K, (d_i))$ est une famille d'ensembles $K = (K^p)_{p \in [0,n]}$ munis d'applications $d_i : K^p \to K^{p-1}$ pour $p > 0$ et $i \in [0, p]$, qui vérifient :

$$ \forall p > 1, \forall \sigma \in K^p, \sigma d_i d_j = \sigma d_j d_{i-1} \text{ avec } j < i. $$

Les éléments de $K^p$ sont les **simplexes de dimension $p$ ou $p$-simplexes**. Comme on s'intéresse aux ensembles semi-simpliciaux finis, tous les ensembles $K^p$ sont finis et le nombre $n$ d'ensembles de $K$ est lui aussi fini.

Les applications $d_i$ sont les **opérateurs de face** des simplexes. En toute rigueur, il faudrait nommer les opérateurs de face d'un $p$-simplexe $d_i^p$ afin de distinguer par exemple l'opérateur de face $d_0$ d'une arête, de celui d'un triangle ou d'un tétraèdre. Bien souvent, il n'y a pas d'ambiguïté, ce qui permet d'omettre l'exposant $p$ des opérateurs de face, et ainsi simplifier la notation.

Notons que le choix a été fait ici d'utiliser la notation post-fixée pour les opérateurs de face. Ainsi, $\sigma d_i d_j$ correspond à $d_j(d_i(\sigma))$. L'intérêt de cette notation est qu'elle permet de "lire" directement de gauche à droite en utilisant le même sens de lecture que celui utilisé pour lire ce document.

La figure 2.2 illustre des exemples et un contre-exemple d'ensembles semi-simpliciaux, ainsi que des notions qui suivent.

<figure><img src="image_9.png" /><figcaption>FIGURE 2.2 – (a)–(c) Trois ensembles semi-simpliciaux de dimension 2. Tous les simplexes de (a) et (b) sont complets. En (b), deux arêtes ont même bord. (c) contient de la multi-incidence. On peut vérifier que tout triangle $\sigma$ vérifie $\sigma d_2 d_1 = \sigma d_1 d_1$, $\sigma d_2 d_0 = \sigma d_0 d_1$ et $\sigma d_1 d_0 = \sigma d_0 d_0$. (d) n'est pas un ensemble semi-simplicial : $\sigma d_2 d_0 \neq \sigma d_0 d_1$.</figcaption></figure>

Si $\sigma d_j = \mu$, alors $\mu$ est la $j$-face de $\sigma$. Si dans un ensemble semi-simplicial $S$, un simplexe $\sigma$ est incident plusieurs fois à une de ses faces $i$. e. $\exists i \neq j$ tel que $\sigma d_j = \sigma d_i$, on dit que $S$ contient de la **multi-incidence**.
Le **bord** d'un $p$-simplexe $\sigma$ est l'ensemble des simplexes $\mu = \sigma d_{i_1} \dots d_{i_k}, k \in [1, p]$. Une conséquence directe de la propriété de commutation des opérateurs de face est que tout simplexe du bord de $\sigma$ peut être désigné de manière unique par une suite d'opérateurs de face d'indices strictement décroissants.

Deux simplexes sont incidents si l'un est dans le bord de l'autre. L'ensemble des simplexes qui ont $\sigma$ dans leurs bords est l'étoile de $\sigma$. Un simplexe est dit principal si son étoile est vide. Un $p$-simplexe est complet s'il possède $p+1$ sommets distincts dans son bord. Un sous-ensemble de $S$ qui est aussi un ensemble semi-simplicial est un sous-ensemble semi-simplicial de $S$.

Les relations sur les opérateurs de face garantissent la cohérence du bord des simplexes. Par exemple, sans ces relations, un $p$-simplexe pourrait avoir jusqu'à $(p+1)!$ sommets distincts dans son bord, alors qu'il ne peut pas en posséder plus de $(p+1)$.

### 2.1.1.2 Opérations de construction

L'opération de **cône** permet en particulier de construire les simplexes et leurs bords, l'opération d'**identification** permet d'assembler les simplexes. Les définitions sont rappelées ici, des précisions et des algorithmes figurent dans [Peltier 2009a].

#### Cône

L'opération de cône sur un ensemble semi-simplicial $S$ consiste à ajouter un nouveau $0$-simplexe $v$ à $S$, et à créer un nouveau $(p+1)$-simplexe $\bar{\sigma}$ incident à $\sigma$ et à $v$ pour chaque $p$-simplexe $\sigma$ de $S$. La dimension de tout nouveau simplexe $\bar{\sigma}$ est donc par définition supérieure ou égale à 1. Les opérateurs de face sont définis par :

- $\forall \bar{\sigma}$ de dimension $p+1$, $\bar{\sigma}d_{p+1} = \sigma$;

- Si $p=0$, alors $\bar{\sigma}d_0 = v$, sinon, pour tout $i \in [0, p]$, $\bar{\sigma}d_i = \overline{\sigma d_i}$.

Notons qu'en partant d'un ensemble semi-simplicial réduit à un seul sommet, l'appli- cation successive de $p$ opérations de cône permet de créer un ensemble semi-simplicial correspondant à un $p$-simplexe et son bord. La figure 2.3 illustre une opération de cône effectuée sur un ensemble semi-simplicial de dimension 1.

#### Identification

L'opération d'identification de base est définie pour deux $p$-simplexes $\sigma$ et $\tau$ ayant même bord, c'est-à-dire que, pour tout $i \in [0, p]$, $\sigma d_i = \tau d_i$. L'opération consiste à fu- sionner $\sigma$ et $\tau$ en un nouveau $p$-simplexe $\mu$ ayant même bord que $\sigma$ et $\tau$, et telle que son étoile corresponde à l'union des étoiles de $\sigma$ et $\tau$, i. e. pour tout $(p+1)$-simplexe $\nu$ tel que $\nu d_i = \sigma$ ou $\nu d_i = \tau$ avant l'identification de $\sigma$ et $\tau$, alors $\nu d_i = \mu$ après l'opération. Par définition, le bord d'un $0$-simplexe est nul, deux sommets ont donc toujours même bord et peuvent toujours être identifiés. La figure 2.4 illustre des opérations d'identification.

Des opérations de plus haut niveau ont été définies : par exemple, deux $p$-simplexes n'ayant pas même bord peuvent être identifiés par une opération d'identification plus générale consistant à identifier de manière récursive les faces deux à deux afin de se ramener au cas atomique de l'identification de deux simplexes ayant même bord.

Dans ce cas, il faut être vigilant car il peut arriver que ces identifications changent la
<figure><img src="image_10.png" /><figcaption>FIGURE 2.3 – (a) Un ensemble semi-simplicial $S$ de dimension 1 (en noir) et un nouveau sommet $v$ (en rouge). (b) Résultat de l'opération de cône de $S$ par $v$.</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>FIGURE 2.4 – (a) Un ensemble semi-simplicial de dimension 2. (b) Peut être obtenu à partir de (a) par trois opérations d'identification des sommets. (c) Peut être obtenu à partir de (b) en identifiant les deux arêtes qui ont même bord.</figcaption></figure>

structure du bord des simplexes à identifier. Par exemple, sur la figure 2.5, l'identification des deux arêtes rouges produit une boucle. En effet, soient $\sigma$ et $\mu$ ces deux arêtes. Elles partagent les deux sommets de leur bord, mais pas avec les mêmes opérateurs de face : $\sigma d_0 = \mu d_1$ et $\sigma d_1 = \mu d_0$. L'identification de $\sigma$ et $\mu$ entraîne l'identification de leurs faces.

Tous les ensembles semi-simpliciaux peuvent être construits uniquement à partir des opérations de cône et d'identification. D'autres opérations ont également été définies, comme par exemple l'identification de sous-ensembles de simplexes, des opérations de **split**, de **flip**, etc. [Bechmann 2007].

Comme vu en introduction, la notion de variété se caractérise de manière combinatoire jusqu'à la dimension 2. Si l'on souhaite représenter de telles structures, on peut optimiser la représentation et se contenter de représenter les 2-simplexes principaux, et remplacer les opérateurs de face des $n$-simplexes par des opérateurs d'adjacence entre $n$-simplexes,
<figure><img src="image_12.png" /><figcaption>FIGURE 2.5 – (a) L’identification des deux arêtes (en rouge) induit l’identification de leurs sommets (en rouge). (b) L’identification des faces des deux arêtes a créé deux boucles, les deux arêtes ont à présent même bord. (c) Résultat de l’identification des deux arêtes.</figcaption></figure>

comme illustré sur la figure 2.6.

### 2.1.2 Complexes simpliciaux abstraits

Le mécanisme de suppression de la multi-incidence sur les ensembles semi-simpliciaux conduit à la définition des complexes simpliciaux abstraits (ou CSA) [Agoston 1976]. Cette structure simpliciale est basée sur une description ensembliste.

#### 2.1.2.1 Structure combinatoire

**Définition 2** *Un complexe simplicial abstrait K est un ensemble de sous-ensembles non vides d'un ensemble fini V tel que :*

$$ (1) \{v\} \in K \text{ pour tout } v \in V, $$

$$ (2) \text{ Si } \sigma \in K, \text{ alors tout sous-ensemble non vide de } \sigma \text{ appartient à } K $$

Les éléments de $V$ sont appelés **sommets**, ceux de $K$ sont les **simplexes abstraits**. La **dimension** d'un élément $\{v_0, \dots, v_p\}$ de $K$ est $p$. En particulier, tout sommet $v$ de $V$ est associé au 0-simplexe $\{v\}$ de $K$. La **dimension de K** est celle d'un simplexe de dimension maximale de $K$. On note $|V|$ le nombre de sommets de $V$.

Les notions de sous-complexe, de face, de bord, d'étoile, de simplexe principal et d'incidence, s'étendent directement pour les complexes simpliciaux abstraits.

Notons en particulier que, de par la définition ensembliste des complexes simpliciaux abstraits, deux simplexes ne peuvent pas avoir même bord, et un simplexe ne peut pas
<figure><img src="image_13.png" /><figcaption>FIGURE 2.6 – (a) Une quasi-variété simpliciale de dimension 2. (b) représentation optimisée de (a) où seuls les 2-simplexes sont explicités, leurs opérateurs de face (en bleu) sont remplacés par des opérateurs d'adjacence (en rouge).</figcaption></figure>

être incident plusieurs fois à une de ses faces. Enfin, tout $p$-simplexe est complet, i. e. possède exactement $p + 1$ sommets dans son bord.

Par exemple, la figure 2.7 représente les CSA $K^1, K^2, K^3$ et $K^4$ suivants :

$$K^1 = \{ \{v_0\}, \{v_2\}, \{v_3\}, \{v_4\}, \\ \{v_3, v_0\}, \{v_3, v_2\}, \{v_3, v_4\} \}$$

$$K^2 = \{ \{v_0\}, \{v_1\}, \{v_2\}, \{v_3\}, \{v_4\}, \{v_5\}, \\ \{v_0, v_1\}, \{v_0, v_3\}, \{v_1, v_3\}, \{v_1, v_2\}, \{v_2, v_5\}, \{v_1, v_5\}, \{v_3, v_4\}, \\ \{v_0, v_1, v_3\}, \{v_1, v_2, v_5\} \}$$

$$K^3 = \{ \{v_0\}, \{v_1\}, \{v_2\}, \{v_3\}, \{v_4\}, \\ \{v_0, v_1\}, \{v_0, v_3\}, \{v_1, v_3\}, \{v_1, v_2\}, \{v_2, v_3\}, \{v_3, v_4\}, \\ \{v_0, v_1, v_3\}, \{v_1, v_2, v_3\} \}$$

$$K^4 = \{ \{v_0\}, \{v_1\}, \{v_2\}, \{v_3\}, \{v_4\}, \{v_5\}, \\ \{v_0, v_1\}, \{v_0, v_2\}, \{v_0, v_3\}, \{v_1, v_3\}, \{v_1, v_4\}, \\ \{v_1, v_2\}, \{v_2, v_3\}, \{v_2, v_4\}, \{v_2, v_5\}, \\ \{v_0, v_1, v_3\}, \{v_0, v_1, v_2\}, \{v_0, v_2, v_3\}, \{v_1, v_2, v_3\}, \{v_1, v_2, v_4\}, \\ \{v_0, v_1, v_2, v_3\} \}$$

Le CSA $K^1$ est de dimension 1, $K^2$ et $K^3$ sont de dimension 2 et $K^4$ est de dimension 3. $K^1$ est un sous-complexe de $K^3$.
<figure><img src="image_14.png" /><figcaption>FIGURE 2.7 – (a) – (d) représentation des complexes simpliciaux abstraits $K^1, K^2, K^3$ et $K^4$.</figcaption></figure>

### 2.1.2.2 Opérations de construction

Les opérations de construction de base sont les mêmes que pour les ensembles semi-simpliciaux : le **cône** permet en particulier de construire les simplexes, et l'**identification** permet de les assembler.

#### Cône

Soit $K$ un CSA sur $V$ et $v \notin V$ un nouveau sommet. Le résultat de l'opération de cône définie par $K$ et $v$ est le CSA $K'$ contenant :

- tous les simplexes de $K$,

- le 0-simplexe $\{v\}$,

- tous les simplexes $\sigma \cup \{v\}$, pour tout $\sigma \in K$.

Par exemple, $K^3$ peut être obtenu à partir de $K^1$ en effectuant une opération de cône sur le sous-complexe $\{{\{v_0\}, \{v_2\}, \{v_3\}, \{v_3, v_0\}, \{v_3, v_2\}\}}$ avec le sommet $v_1$.

Comme pour les ensembles semi-simpliciaux, en partant d'un CSA réduit à un seul 0-simplexe, l'application successive de $p$ opérations de cône permet de créer un CSA correspondant à un $p$-simplexe abstrait et son bord.

#### Identification

L'opération d'identification élémentaire consiste à "fusionner" deux sommets distincts. Cette opération est toujours définie, quels que soient les deux sommets choisis. Le CSA résultant peut toutefois être fortement impacté par l'identification de deux sommets. En effet, l'identification de deux sommets peut entraîner :

- l'identification de simplexes de dimensions supérieures. Par exemple, le CSA $K^3$ peut être obtenu à partir de $K^2$ en identifiant $v_3$ et $v_5$, ce qui entraîne l'identification des arêtes $\{v_1, v_5\}$ et $\{v_1, v_3\}$;

- la dégénérescence de simplexes de dimensions supérieures, c'est-à-dire leur suppression. Par exemple, $K^1$ peut être obtenu à partir de $K^3$ en identifiant $v_1$ et $v_3$. Cette identification entraîne l'identification des arêtes $\{v_0, v_3\}$ et $\{v_0, v_1\}$, l'identi-
fication des arêtes {$v_2, v_3$} et {$v_1, v_2$}, la dégénérescence de l'arête {$v_1, v_3$}, et la dégénérescence des deux triangles.

D'un point de vue pratique, on peut décrire un CSA en explicitant uniquement les simplexes principaux, tous les autres simplexes peuvent être déduits de ces simplexes : ce sont des sous-ensembles non vides des simplexes principaux.

Notons que le nombre de simplexes nécessaires pour représenter un objet sans multi-incidence est en général bien plus élevé que le nombre de simplexes nécessaires pour représenter le même objet en autorisant la multi-incidence. Par exemple, la subdivision d'un tore avec un CSA nécessite au minimum 14 triangles, 21 arêtes et 7 sommets, alors qu'avec un ESS, seulement 2 triangles, 3 arêtes et 1 seul sommet sont nécessaires, comme le montre la figure 2.8.

<figure><img src="image_15.png" /><figcaption>FIGURE 2.8 – (a) Une subdivision simpliciale minimale du tore décrite par un complexe simplicial abstrait. (b) Une subdivision simpliciale minimale du tore décrite par un ensemble semi-simplicial.</figcaption></figure>

## 2.2 Structures simploïdales

Nous mettons à présent en avant le mécanisme de produit cartésien, permettant de définir des structures simploïdales. Les cellules des structures simploïdales sont des produits de simplexes, aussi appelés **simploïdes**. À l'instar d'un cube de dimension $p$ qui peut être obtenu par le produit cartésien de $p$ arêtes (i. e. de 1-simplexes), les simploïdes sont des produits de simplexes de dimensions quelconques. La notion de simploïde a été introduite par [Dahmen 1982].
Afin de présenter les ensembles semi-simploïdaux de manière progressive, nous commençons par présenter les ensembles semi-cubiques, qui sont un cas particulier d'ensembles semi-simploïdaux. On retrouve des structures cubiques dans divers domaines : en géométrie discrète où les objets discrets sont décrits par des pixels en 2D ou des voxels en 3D, en imagerie 3D où les données d'acquisition sont structurées en grilles régulières, ou encore en simulation numérique dont les calculs sont effectués sur des maillages héxaédriques.

### 2.2.1 Ensembles semi-cubiques

Les ensembles semi-cubiques [Serre 1951, Brown 1981] permettent de manipuler des assemblages de cubes. Leur définition est analogue à celle des ESS, i. e. elle est basée sur un ensemble de cubes abstraits, sur lesquels agissent des opérateurs de face satisfaisant des relations de cohérence.

**Définition 3** *Un ensemble semi-cubique S = (K, (d_j^i)), de dimension n, est une famille d'ensembles K = (K^p)_{p \in [0,n]} de p-cubes abstraits munis d'opérateurs de face d_j^i : K^p \to K^{p-1}, pour 1 \le p \le n, i \in [1, p] et j \in [0, 1]. Pour tout p-cube, p > 1, on a :*

$$ \sigma d_j^i d_l^k = \sigma d_l^k d_j^{i-1}, \forall k < i $$

Chaque p-cube est donc muni de $2p$ opérateurs de face : $d_0^1, d_1^1, \dots, d_0^p, d_1^p$. Par exemple, une arête est munie de deux opérateurs de face $d_0^1$ et $d_1^1$, un carré est muni des quatre opérateurs $d_0^1, d_1^1, d_0^2$ et $d_1^2$ : cf. figure 2.9. De manière intuitive, chaque p-cube correspond au produit cartésien de p arêtes, les deux opérateurs de face $d_0^i$ et $d_1^i$ correspondent intuitivement aux opérateurs de face de la $i^{\text{e}}$ arête intervenant dans le produit. Les relations définies sur les opérateurs de face jouent le même rôle que pour les ensembles semi-simpliciaux : elles garantissent la cohérence du modèle. De manière intuitive, soit $\mu = \sigma_1 \times \dots \times \sigma_p$ un p-cube issu du produit des arêtes $\sigma_1, \dots, \sigma_p$, la face $\mu d_j^i$ correspond au $(p-1)$-cube $\sigma_1 \times \dots \times \sigma_i d_j \times \dots \times \sigma_p$.

### 2.2.2 Ensembles semi-simploïdaux

Les ensembles semi-simploïdaux [Fuchs 1997, Peltier 2009a] généralisent les ensembles semi-simpliciaux et semi-cubiques. En effet dans cette structure, les cellules, appelées simploïdes, correspondent à des produits de simplexes quelconques.

Comme nous le verrons en Section 2.5, l'opération de produit cartésien est également définie sur les structures simpliciales. Dans les structures simploïdales, les cellules sont plus générales que des simplexes ou les cubes. Par exemple, le produit cartésien simploïdal d'un 2-simplexe par un 1-simplexe est un prisme, alors que le produit cartésien simplicial des deux mêmes simplexes correspond à la triangulation du prisme : cf. figure 2.10.

#### 2.2.2.1 Structure combinatoire

Pour les simplexes et les cubes, il n'existe qu'un type de cellule pour chaque dimension ; c'est pourquoi les simplexes et les cubes sont caractérisés par leur dimension. On peut en
<figure><img src="image_16.png" /><figcaption>FIGURE 2.9 – Le 2-cube représenté en (b) correspond intuitivement au produit cartésien de l’arête verticale et de l’arête horizontale représentées en (a). Les opérateurs de face $d_j^1$ (resp. $d_j^2$) du 2-cube correspondent aux opérateurs de face de la première (resp. de la seconde) arête.</figcaption></figure>

revanche construire différents simploïdes pour une dimension donnée : cf. figure 2.11. Ainsi, un simploïde $\mu$ est caractérisé par son **type** $(a_1, \dots, a_n)$ défini par un $n$-uplet d'entiers strictement positifs. Intuitivement, $\mu$ correspond au produit cartésien $\sigma_1 \times \dots \times \sigma_n$ où $\sigma_i$ est un simplexe de dimension $a_i$. Le simploïde $\mu$ est de **dimension** $\sum_{j=1}^n a_j$ et de **longueur** $n$.

Le fait de ne pas faire apparaître de 0 dans le type d'un simploïde correspond intuitivement au fait que le produit d'un simploïde par un sommet est l'identité. On notera que les $p$-simplexes, $p > 0$, sont des simploïdes de type ($p$) de longueur 1, un $0$-simplexe est de type (), les $p$-cubes sont des simploïdes de type $(1, \dots, 1)$ de longueur $p$.

**Définition 4** Un ensemble semi-simploïdal $S = (K, (d_j^i))$ est un ensemble de simploïdes muni d'un opérateur de type $\mathcal{T}: K \mapsto \bigcup_{i \ge 0} \mathbb{N}^{*i}$ et d'opérateurs de face $d_j^i$.

<figure><img src="image_17.png" /><figcaption>FIGURE 2.10 – Produit cartésien simplicial et produit cartésien simploïdal.</figcaption></figure>
<figure><img src="image_18.png" /><figcaption>FIGURE 2.11 – simploïdes et leurs types, jusqu'à la dimension 3.</figcaption></figure>

Soit $\sigma \in K$; $\sigma T$ est le type de $\sigma$. Soit $\sigma T = (a_1, \dots, a_n) : \sigma d_j^i$ est défini si $1 \le i \le n, 0 \le j \le a_i$. Les opérateurs vérifient les propriétés suivantes :

### (I) Action sur le type

$$1) \sigma d_j^i T = \begin{cases} (a_1, \dots, a_i - 1, \dots, a_n) & \text{si } a_i > 1 \\ (a_1, \dots, a_{i-1}, a_{i+1}, \dots, a_n) & \text{si } a_i = 1 \end{cases}$$

### (II) Commutation des opérateurs de face

$$1) d_j^i d_l^i = d_l^i d_{j-1}^i \quad l < j, a_i > 1$$

$$2) d_j^i d_l^k = \begin{cases} d_l^k d_j^i & \text{si } a_k > 1 \\ d_l^k d_j^{i-1} & \text{sinon} \end{cases} \quad k < i$$

□

Notons que le cas (II.1) avec $a_i = 1$ n'est pas explicité car il s'agit du cas particulier de (II.2) où $a_k = 1$, avec $k = i - 1$.

La figure 2.12 illustre un prisme $\sigma$ de type (2,1) et une partie de son bord. On peut vérifier par exemple que $\sigma d_2^1 d_1^1 = \sigma d_1^1 d_1^1$ et $\sigma d_0^2 d_2^1 = \sigma d_2^1 d_0^2$.

On peut noter qu'un simploïde de type (2,1) et un simploïde de type (1,2) n'ont pas la même structure, i. e. ils n'ont pas les mêmes opérateurs de face. Cela s'explique par le fait que le produit cartésien n'est pas commutatif.

### 2.2.2.2 Opérations de construction

Tout ensemble semi-simploïdal peut être construit à partir de deux opérations de base : l'opération de **produit cartésien** qui permet en particulier de construire des simploïdes et leurs bords à partir de simplexes et leurs bords, et l'opération d'**identification** permettant de les assembler.

#### Produit cartésien

La définition du produit cartésien sur les ensembles simploïdaux se déduit directement du fait que le produit de deux simploïdes $\sigma$ et $\mu$ de types respectifs $(a_1, \dots, a_n)$ et $(b_1, \dots, b_m)$ est un simploïde $\tau = \sigma \times \mu$ de type $(a_1, \dots, a_n, b_1, \dots, b_m)$. De plus, les opérateurs de face sont définis de manière à respecter le produit : $\tau d_j^i = \sigma d_j^i \times \mu$ pour tout
<figure><img src="image_19.png" /><figcaption>FIGURE 2.12 – (a) – (b) Correspondance entre le produit cartésien de deux simplexes (et leur bord) et un simploïde de type (2, 1). Par souci de clarté, seulement une partie du bord du prisme est représentée. Les opérateurs de face $d_j^1$ du prisme (en rouge) viennent de sa première composante (i. e. un triangle), les opérateurs de face $d_j^2$ du prisme (en bleu) viennent de la seconde composante (i. e. une arête).</figcaption></figure>

i compris entre 1 et n, et $\tau d_j^{i+n} = \sigma \times \mu d_j^i$ pour tout i compris entre 1 et m. L'opération de produit cartésien peut être défini sur les ensembles semi-simploïdaux de la manière suivante [Peltier 2006a] :

**Définition 5** Soient $S = (K, (d_j^i))$ et $S' = (K', (d_j'^i))$ deux ensembles semi-simploïdaux. Le produit cartésien $S \times S'$ est l'ensemble semi-simploïdal $S'' = (K'', (d_j''^i))$ tel que :

$$— K'' = K \times K'$$

$$— \forall \sigma'' = \sigma \times \sigma', \text{ tel que } \sigma T = (a_1, \dots, a_n) \text{ et } \sigma' T = (b_1, \dots, b_m), \text{ on a :}$$
$$— \sigma'' T = (a_1, \dots, a_n, b_1, \dots, b_m)$$

$$— \sigma'' d_j''^i = \begin{cases} \sigma d_j^i \times \sigma' & \text{si } 1 \le i \le n, \\ \sigma \times \sigma' d_j'^{i-n} & \text{si } n+1 \le i \le n+m \end{cases}$$

Ainsi, le produit cartésien de deux ensembles semi-simploïdaux $S$ et $S'$ de dimensions respectives $d$ et $d'$, est un ensemble semi-simploïdal $S''$ de dimension $d + d'$.

## Identification

Le principe est exactement le même que pour les ensembles semi-simpliciaux, l'opération atomique consiste à fusionner deux simploïdes ayant même bord (et donc même type), ce qui implique en particulier de mettre à jour leurs étoiles. Ici encore, des opérations de plus haut niveau peuvent être définies, par exemple l'identification de deux simploïdes (de même type) n'ayant pas même bord, comme illustré sur la figure 2.13. Enfin, lorsque deux simploïdes partagent les mêmes faces mais via des opérateurs différents, les mêmes phénomènes de *twist* présentés dans le cadre simplicial peuvent se produire.

**Théorème 1** Un ensemble semi-simploïdal peut être associé de manière canonique à tout ensemble semi-simplicial et réciproquement.
<figure><img src="image_20.png" /><figcaption>FIGURE 2.13 – L’opération d’identification de deux simploïdes n’ayant pas même bord est définie de manière récursive en identifiant d’abord leurs faces. Les opérateurs de face ne sont pas représentés.</figcaption></figure>

La preuve est immédiate : cela provient du fait que tout simplexe est un simploïde, et tout simploïde correspond à un produit cartésien de simplexes.

### 2.2.3 Complexes simploïdaux abstraits

Nous proposons à présent une première approche permettant d'étendre au cadre simploïdal le mécanisme de suppression de la multi-incidence défini dans le cadre simplicial. Pour celà, nous définissions un simploïde abstrait comme un ensemble de simplexes abstraits. Nous proposons ensuite une définition des complexes simploïdaux abstraits qui n'ont, à notre connaissance, pas été définis ni étudiés auparavant.

#### 2.2.3.1 Structure combinatoire

**Définition 6** *Soit $V = (V^i)_{i \in [1,n]}$, $n \ge 1$ une partition d'un ensemble fini de sommets. Un simploïde abstrait sur $V$ est un ensemble non vide de simplexes abstraits $\sigma = \{\sigma_{j_1}, \dots, \sigma_{j_p}\}$ où $1 \le j_1 < \dots < j_p \le n$ tel que $\sigma_{j_k} \subseteq V^{j_k}$ pour tout $k \in [1, p]$.*

*Pour tout $k \in [1, p]$, pour toute face $\mu_{j_k}$ de $\sigma_{j_k}$, le simploïde abstrait $\mu = \{\sigma_{j_1}, \dots, \mu_{j_k}, \dots, \sigma_{j_p}\}$ est une face de $\sigma$.*

Comme $V$ est une partition, tous les $V^i$ sont non vides. Notons qu’un simploïde abstrait peut contenir des simplexes abstraits de dimension 0. Cela permet :

- d'étendre directement la notion de face,

- de définir simplement l'opération d'identification,

- de faire un lien direct avec les complexes simploïdaux géométriques. Ce dernier point est discuté au Chapitre 4.
Contrairement à la définition des ensembles semi-simploïdaux, le type d'un simploïde abstrait peut donc contenir des valeurs nulles. Le type d'un simploïde abstrait est défini par un multi-ensemble d'entiers positifs ou nuls, et sa longueur est le nombre d'éléments de son type. Dit autrement, on ne distingue pas, par exemple, un simploïde de type (1, 2) d'un simploïde de type (2, 1); en revanche, on explicite la produit cartésien par un 0-simplexe, ce qui différencie la structure d'un simploïde de type {0, 1, 2} de celle d'un simploïde de type {1, 2}, qui n'ont ni même type, ni même longueur.

En particulier, un simploïde abstrait composé uniquement de 0-simplexes abstraits est un sommet simploïdal. Il existe donc des sommets simploïdaux de différents types : {0}, {0, 0}, etc. Nous pouvons à présent définir les complexes simploïdaux abstraits :

**Définition 7** Soit $V = (V^i)_{i \in [1,n]}$, $n \ge 1$ une partition d'un ensemble fini de sommets. Un complexe simploïdal abstrait $K^\square$ est un ensemble de simploïdes abstraits définis sur $V$, tel que pour tout simploïde abstrait $\sigma \in K^\square$, toutes les faces de $\sigma$ appartiennent à $K^\square$.

Soient $\sigma = \{\sigma_{j_1}, \dots, \sigma_{j_p}\}$ et $\mu = \{\mu_{j_1}, \dots, \mu_{j_p}\}$ deux simploïdes de $K^\square$. Si pour tout $k \in [1, p]$, $\sigma_{j_k} \subseteq V^{j_k}$ et $\mu_{j_k} \subseteq V^{j_k}$, alors $\sigma$ et $\mu$ ont même structure.

Notons que pour tout $i \in [1, n]$, l'ensemble des simplexes de $V^i$ qui composent l'ensemble des simploïdes de $K^\square$ est un complexe simplicial abstrait $K^i$.

La figure 2.14 représente un complexe simploïdal abstrait. On peut noter que tous les sommets simploïdaux d'une composante connexe ont même structure : ceux de la composante connexe contenant le cube sont construits à partir de $V^1$, $V^2$ et $V^3$, ceux de l'autre composante connexe sont construits à partir de $V^1$ et $V^2$ seulement.

Un complexe simploïdal abstrait peut être décrit par l'ensemble des simploïdes principaux qu'il contient, l'ensembles des faces appartiennent implicitement au complexe et peuvent être explicitées en calculant les sous-ensembles non vides de chaque simplexe abstrait.

Par exemple, soit $\sigma = \{\{a, b, c\}, \{x, y\}\}$ un simploïde abstrait de type $\{2, 1\}$. Les simploïdes suivants sont des faces de $\sigma$ :

type{1, 1} : {{a, b}, {x, y}}, {{a, c}, {x, y}}, {{b, c}, {x, y}};

type{2, 0} : {{a, b, c}, {x}}, {{a, b, c}, {y}};

type{0, 1} : {{a, b}, {x}}, {{a, b}, {y}}, {{b, c}, {x}}, {{b, c}, {y}}, {{a, c}, {x}},
{{a, c}, {y}}, {{a}, {x, y}}, {{b}, {x, y}}, {{c}, {x, y}};

type{0, 0} : {{a}, {x}}, {{a}, {y}}, {{b}, {x}}, {{b}, {y}}, {{c}, {x}}, {{c}, {y}}.

### 2.2.3.2 Opérations de construction

Les deux opérations de base sont : le produit cartésien permettant de créer en particulier les simploïdes abstraits, et l'opération d'identification de sommets simploïdaux.
<figure><img src="image_21.png" /><figcaption>FIGURE 2.14 – Représentation d'un complexe simploïdal abstrait, défini à partir de la partition de sommets : $V^1 = \{a, b, c, d, e\}$, $V^2 = \{x, y, z\}$ et $V^3 = \{u, v\}$. Par souci de clarté, un sommet simploïdal $\{\{v_{i_1}\}, \dots, \{v_{i_p}\}\}$ est noté $v_{i_1} \dots v_{i_p}$. Par exemple, le sommet simploïdal $\{\{b\}, \{x\}, \{u\}\}$ est noté $bxu$. Les simploïdes principaux sont $\{\{a, b\}, \{x, y\}, \{u, v\}\}$ de type $\{1, 1, 1\}$, $\{\{a, b, c\}, \{x\}, \{u\}\}$ de type $\{2, 0, 0\}$, $\{\{b, c\}, \{x\}, \{v\}\}$ de type $\{1, 0, 0\}$ pour la composante connexe de gauche ; $\{\{d, e\}, \{x, y\}\}$ de type $\{1, 1\}$ et $\{\{e\}, \{y, z\}\}$ de type $\{0, 1\}$ pour celle de droite.</figcaption></figure>

### Produit cartésien

Soient $\sigma = \{\sigma_{i_1}, \dots, \sigma_{i_p}\}$ et $\mu = \{\mu_{j_1}, \dots, \mu_{j_q}\}$ deux simploïdes abstraits. Le produit cartésien $\sigma \times \mu$ est défini si et seulement si $\sigma$ et $\mu$ sont définis à partir d'ensembles de sommets disjoints, i. e. pour tout $k \in [1, p]$ et pour tout $l \in [1, q]$, $V^{i_k} \cap V^{j_l} = \emptyset$. Le simploïde $\sigma \times \mu$ est défini par $\sigma \cup \mu$. Le produit cartésien de deux complexes simploïdaux abstraits $K^{\square1} \times K^{\square2}$ est défini par l'ensemble des simploïdes abstraits $\sigma \times \mu$, pour tout $\sigma \in K^{\square1}$ et pour tout $\mu \in K^{\square2}$.

Par exemple, la figure 2.15 illustre une opération de produit cartésien appliqué à deux complexes simploïdaux abstraits.

L'opération de produit cartésien permet en particulier de créer les simploïdes abstraits et leurs bords.

### Identification de sommets

Soit $K^{\square}$ un complexe simploïdal abstrait. L'opération d'identification de deux sommets simploïdaux $\sigma$ et $\mu$ est définie si et seulement si $\sigma = \{\sigma_{i_1}, \dots, \sigma_{i_p}\}$ et $\mu = \{\mu_{j_1}, \dots, \mu_{j_q}\}$ ont même structure. L'opération consiste à identifier deux à deux les sommets $\sigma_{i_k}$ et $\mu_{i_k}$ dans chaque complexe simplicial $K^{i_k}$, pour tout $k \in [1, p]$.

Par exemple, sur la figure 2.14, il n'est pas possible d'identifier $bxu$ et $dy$, car ils n'ont pas même structure. Pour pouvoir identifier ces deux sommets simploïdaux, il faut intuitivement faire passer la composante connexe de droite dans le même espace de sommets que la composante de gauche. Cela est possible par exemple en effectuant un produit cartésien par un sommet quelconque de $V^3$.
<figure><img src="image_22.png" /><figcaption>FIGURE 2.15 – Produit cartésien de deux complexes simploïdaux abstraits $K^{\square 1}$ et $K^{\square 2}$. Tous les simploïdes $K^{\square 1}$ sont définis à partir de $V^1$ et $V^2$, ceux de $K^{\square 2}$ à partir de $V^3$. La structure de tous les simploïdes du complexe résultant du produit est construite à partir de $V^1$, $V^2$ et $V^3$.</figcaption></figure>

La figure 2.16 illustre des opérations d'identification de sommets simploïdaux. Notons que, comme pour les complexes simpliciaux abstraits, l'identification de deux sommets simploïdaux peut entrainer l'identification de simploïdes de dimensions supérieures, ainsi que la dégénérescence de simploïdes sur un simploïde de leur bord. Les dégénérescences correspondent à des dégénérescences simpliciales, répercutées sur le produit cartésien. Par exemple sur la figure 2.16, lors de la dernière identification, les sommets simpliciaux $\{u\}$ et $\{v\}$ sont identifiés, entraînant la dégénérescence de l'arête $\{u, v\}$ et donc la dégénérescence du cube $\{\{a, b\}, \{x, y\}, \{u, v\}\}$ sur sa face $\{\{a, b\}, \{x, y\}, \{u\}\}$.

**Notes** : Cette première approche pour la définition des ensembles simploïdaux abstraits est basée sur une partition d'un ensemble de sommets. Un complexe simploïdal abstrait est défini à partir de simploïdes abstraits issus de produits cartésiens de complexes simpliciaux abstraits $K^1, \dots, K^n$ définis respectivement sur chaque partie $V^1, \dots, V^n$ d'une partition de sommets. Cette approche est restrictive, en particulier :

- on ne peut pas représenter explicitement la dégénérescence : lorsqu'un simploïde est dégénéré, cela est uniquement dû au fait qu'un des simplexes $\sigma^i \in K^i$ qui le comporte est dégénéré. On observe le même phénomène pour les complexes simpliciaux abstraits : lorsqu'un simplexe est dégénéré, il n'apparaît plus dans le complexe. Par exemple sur la figure 2.17, la définition proposée ne permet pas d'identifier les quatre sommets rouges du cube représenté en (a) afin d'obtenir le cube dégénéré représenté en (b);

- certains assemblages de simploïdes non dégénérés ne correspondent pas à des sousensembles de produits cartésiens de complexes simpliciaux abstraits. Par exemple, l'assemblage de carrés représentés sur la figure 2.17c<fnref n="2" /> ne peut pas être représenté par un complexe simploïdal abstrait tel que nous les avons définis.

<footnote n="2">2. Merci à POL VANHAECKE du laboratoire de Mathématiques et Applications de l'université de Poitiers, qui a mis au jour cet exemple.</footnote>
<figure><img src="image_23.png" /><figcaption>FIGURE 2.16 – Trois opérations d'identification successives de sommets simploïdaux. La première identification consiste à identifier les 0-simplexes $\{a\}$ et $\{d\}$, $\{x\}$ et $\{z\}$, et $\{u\}$ et $\{w\}$. La deuxième opération entraîne l'identification de deux arêtes. La troisième identification entraîne la dégénérescence du cube sur une de ses faces.</figcaption></figure>

## 2.3 Structures cellulaires

Jusqu'à présent, nous avons présenté différentes structures régulières basées sur la notion de cellule abstraite (simplexes, cubes, simploïdes) sur lesquelles agissent des opérateurs de face.

Dans cette partie, nous présentons le mécanisme de numérotation permettant de définir la notion de cellule "quelconque" à partir d'ensembles semi-simpliciaux.

De manière intuitive, l'ensemble des simplexes correspondant à une cellule correspond à la triangulation barycentrique de cette cellule. Les structures cellulaires peuvent donc être vues comme des structures simpliciales structurées en cellules.

### 2.3.1 Numérotation – Cellules

Nous commençons par rappeler la notion d'ensemble semi-simplicial numéroté [Lienhardt 1994], qui permet de définir la notion de cellules.
<figure><img src="image_24.png" /><figcaption>FIGURE 2.17 – Illustration des restrictions inhérentes à la définition des complexes simploïdaux abstraits proposée. (a) – (b) Identification des sommets rouges dégénère le cube. (c) Assemblage de carrés. (b) et (c) ne peuvent pas être représentés par des complexes simploïdaux abstraits, tels que nous les avons définis.</figcaption></figure>

**Définition 8** Un ensemble semi-simplicial numéroté $(S, \nu)$ est un ensemble semi-simplicial $S = (K, (d_i))$ de dimension $n$ muni d'une application $\nu : K^0 \to \{0, \dots, n\}$, tel que pour tout simplexe principal $\sigma$ de $K$ :

- si $\sigma \in K^0$, alors $\nu(\sigma) = 0$,

- si $\sigma \in K^p$, $p \in [1, n]$, l'ensemble des entiers associés par $\nu$ à l'ensemble des 0-simplexes incidents à $\sigma$ est $\{0, \dots, p\}$.

Soit $\mu$, un $p$-simplexe dont l'ensemble des sommets associés est $\{v_0, \dots, v_p\}$ : on dit que $\mu$ est **numéroté** $(\nu(v_0), \dots, \nu(v_p))$, avec $\nu(v_0) < \dots < \nu(v_p)$.

Par exemple, la figure 2.18a représente un ensemble semi-simplicial numéroté de dimension 3. Les sommets de chaque $p$-simplexe principal sont numérotés $(0, \dots, p)$.

On peut noter que la numérotation d'un ensemble semi-simplicial nous assure que tous les simplexes sont complets, i. e. un $p$-simplexe possède ($p+1$) sommets distincts dans son bord. Ceci n'empêche pas plusieurs simplexes de partager un même bord. On peut enfin noter que l'on ne peut pas associer de numérotation à tout ensemble semi-simplicial, même si tous les simplexes sont complets comme le montre les figures 2.18b et 2.18c.

Dès lors que l'on sait associer une numérotation à un ensemble semi-simplicial, on peut partitionner celui-ci en cellules.

**Définition 9** Soit $(S, \nu)$ un ensemble semi-simplicial numéroté. Une cellule de dimension $p$, ou $p$-cellule, est identifiée par un 0-simplexe $\sigma$ numéroté ($p$) et contient $\sigma$ ainsi que tous les $j$-simplexes numérotés $(\nu(v_0), \dots, \nu(v_{j-1}), p)$ qui lui sont incidents, où $1 \le j \le p$, et les $v_k, k \in [0, j-1]$ sont des 0-simplexes de $S$.

Par exemple, dans un ensemble semi-simplicial numéroté de dimension supérieure ou égale à 2, toutes les 2-cellules sont composées d'un sommet $v$ numéroté (2), d'arêtes numérotées (0, 2) et (1, 2) incidentes $v$ et de triangles numérotés (0, 1, 2) incidents à $v$.
<figure><img src="image_25.png" /><figcaption>FIGURE 2.18 – (a) Un ensemble semi-simplicial numéroté de dimension 3. Les opérateurs de faces ne sont pas représentés ; ils peuvent être directement déduits de la numérotation : la face $d_j$ d'un simplexe principal est la face opposée au sommet numéroté $j$. (b) – (c) Deux exemples d'ensembles semi-simpliciaux non numérotables. (b) On ne peut pas trouver de numérotation telle que chaque triangle soit numéroté (0, 1, 2). (c) Les deux 1-simplexes principaux doivent être numérotés (0, 1) ; ils sont incidents aux trois sommets d'un triangle principal qui doit être numéroté (0, 1, 2), la numérotation est donc impossible. L'arête principale rouge n'est pas numérotée (0, 1).</figcaption></figure>

Dans un ensemble semi-simplicial numéroté, il y a donc autant de *p*-cellules que de sommets numérotés (*p*) : cf. figure 2.19.

Nous présentons maintenant les deux grandes familles de structures cellulaires : les modèles basés sur les **graphes d'incidence** (ou ordres) et ceux basés sur les **cartes combinatoires**. Le lecteur intéressé pourra consulter l'ouvrage de référence [Damiand 2014] pour une étude approfondie.

### 2.3.2 Graphes d'incidence

Comme son nom l'indique, un graphe d'incidence est un graphe, permettant de décrire les relations d'incidence entre les différentes cellules d'un objet subdivisé. Chaque noeud du graphe correspond à une cellule, et deux cellules sont liées par un arc si l'une est face de l'autre.

La relation d'incidence définit une relation d'ordre partiel entre les cellules. Plusieurs structures basées sur les ordres ont été définies et adaptées à différents types d'applications, par exemple [Edelsbrunner 1987, Rossignac 1989, Sobhanpanah 1989]. Les différences sont soit liées à la définition (par exemple les dimensions des cellules sont explicitées ou non), ou au type de subdivisions visé. En particulier, il est possible d'ajouter des contraintes sur la manière dont les cellules sont assemblées ; ce point est discuté en Section 2.3.5.

La définition proposée ici pour illustrer les graphes d'incidence est basée sur la notion d'ordre [Bertrand 1999a].
<figure><img src="image_26.png" /><figcaption>FIGURE 2.19 – (a) Un ensemble semi-simplicial numéroté. (b) Mise en évidence de la structuration cellulaire de (a). (c) Subdivision cellulaire correspondant à (b).</figcaption></figure>

**Définition 10** Un ordre est un couple $|X| = (X, \alpha)$, où $X$ est un ensemble et $\alpha$ est une relation d'ordre (binaire, réflexive, antisymétrique, et transitive). Soient $\beta$ l'inverse de $\alpha$, et soit $\theta$ l'union de $\alpha$ et $\beta$.

Les CF-ordres <fnref n="3" /> sont des ordres dénombrables et localement finis, c'est-à-dire que $X$ est dénombrable et pour tout $x$ appartenant à $X$, $\theta(x)$ est fini.

Voici quelques rappels sur le vocabulaire et les notions associées aux ordres [Daragon 2003, Daragon 2005]. La figure 2.20 illustre les différentes notions qui suivent.

L'ensemble $\alpha(x)$ est l'**α-adhérence** de $x$, ou la **fermeture** de la cellule $x$. L'ensemble $\beta(x)$ est la **β-adhérence** de $x$, ou l'**étoile** de la cellule $x$. La **θ-adherence** de $x$ est l'union de la fermeture et de l'étoile de $x$.

Les **α-, β- et θ-adhérences strictes**, respectivement notées $\alpha^\square$, $\beta^\square$ et $\theta^\square$ contiennent tous les éléments de l'adhérence correspondante, excepté $x$. Par exemple, le bord de $x$ est défini par $\alpha^\square(x)$. Les cellules **principales** sont les cellules dont l'étoile stricte est vide, c'est-à dire que $\beta^\square(x)$ est vide.

La notion de **α-voisin** de $x$, notée $\alpha^\bullet(x)$ est définie par l'ensemble $\{y \in \alpha^\square(x), \alpha^\square(x) \cap \beta^\square(y) = \emptyset\}$, qui contient les éléments du bord de $x$ les plus proches via $\alpha$: cela correspond à la notion de face présentée pour les structures régulières. Les notions de $\beta$- et $\theta$-voisins sont définies de manière similaire, et notées $\beta^\bullet$ et $\theta^\bullet$.

Une suite $x_0, x_1, \dots, x_n$ telle que $x_i$ appartient à $\theta^\square(x_{i+1})$ est une **θ-chaîne** de longueur $n$. Un ordre est **connexe** si tout couple d'élément est relié par une **θ-chaîne**. Les notions de $\alpha-$, $\alpha^\bullet-$, $\beta-$ et $\beta^\bullet$-chaînes sont définies de manière similaire. Le **rang** d'un élément, noté $\rho(x, |X|)$ est la longueur de la plus longue $\alpha^\bullet$-chaîne qui part de $x$.

Les CF-ordres permettent de représenter une classe très large d'objets cellulaires. On ne considère ici que les **CF-ordres fermés**, c'est-à-dire ne présentant pas de saut

<footnote n="3">3. CF signifie *Countable and locally Finite*.</footnote>
<figure><img src="image_27.png" /><figcaption>FIGURE 2.20 – (a) Le CF-ordre fermé correspondant à la subdivision cellulaire de la figure 2.19c. (b) Le CF-ordre $|\alpha(f_1)|$. (c) Le CF-ordre $|\theta(e_2)|$. (d) Le CF-ordre $|\alpha^{\bullet}(f_1)|$. (e) Le CF-ordre $|\beta(v_5)|$. (f) Le CF-ordre $|\alpha^{\square}(f_1)|$. (g) Un ordre qui n’est pas fermé car il y a un saut de dimension entre $V_1$ et $e_2$.</figcaption></figure>

de dimension entre deux cellules. En particulier, cela permet d'interpréter le rang d'une cellule comme sa dimension. Un CF-ordre est dit **pur** si toutes les cellules principales sont de même rang.

**Définition 11** *Soit $|X|$ Un CF-ordre. $|X|$ est dit fermé si pour tout $x \in X$ et $y \in \alpha^{\square}(x)$ :* 
$$ \forall i \in ]\rho(y, |X|), \rho(x, |X|)[, \exists z \in \alpha^{\square}(x) \cap \beta^{\square}(y), \rho(z, |X|) = i $$

On peut imaginer plusieurs manières de représenter un ordre. En utilisant des graphes orientés acycliques (DAG), la relation d'ordre est explicitée par des arcs orientés, la transitivity est encodée de manière implicite. La dimension d'une cellule correspond au nombre d'arcs qui la sépare d'un noeud qui n'a pas de face. Les diagrammes de HASSE permettent également de représenter des ordres en explicitant uniquement les relations entre les deux éléments de rangs successifs, la transitivity est aussi encodée de manière implicite. Les arcs ne sont en revanche pas orientés, la dimension des cellules est déduite de l'axe vertical : si une cellule est représentée au dessus d'une autre, alors sa dimension est supérieure.

La représentation choisie ici utilise les arcs orientés des DAG, ainsi que l'axe vertical pour représenter la relation d'ordre. Les noeuds du graphe d'incidence correspondent aux
éléments de $X$, et un arc est représenté de $x$ vers $y$ si $y$ est un élément de $\alpha^{\bullet}(x)$, donc une de ses faces.

Bien que cette description structurelle d'un objet cellulaire par un CF-ordre soit à première vue "naturelle" et "intuitive", elle comporte certaines limitations. Par exemple, considérons les trois subdivisions cellulaires représentées sur la figure 2.21 : un disque (à bord), une sphère pincée (orientable) et un plan projectif (non orientable). Le CF-ordre représenté en (d) décrit les relations d'incidence entre les cellules de ces trois objets, qui ne sont clairement pas les mêmes. La question qui se pose alors est : étant donné un CF-ordre, quel objet cellulaire décrit-il ? Comme nous allons le voir dans ce qui suit, dans le cas présent la réponse est : aucun de ces trois objets...

<figure><img src="image_28.png" /><figcaption>FIGURE 2.21 – (a) Un disque, (b) une sphère pincée et (c) un plan projectif. (d) Un CF-ordre décrivant les relations d'incidence des trois subdivisions cellulaires (a), (b), et (c).</figcaption></figure>

Afin de répondre à cette question, la clé est l'interprétation simpliciale. En effet, on peut associer un ensemble semi-simplicial numéroté à tout CF-ordre fermé. Plus précisément il s'agit d'un complexe simplicial abstrait numéroté : un 0-simplexe numéroté $p$ est associé à toute $p$-cellule. On obtient ainsi une numérotation et à toute suite de cellules $(c_i, \dots, c_j)$, telle que $c_k$ est une face de $c_{k+1}$, avec $k \in [i, j - 1]$, correspond un $(j-i)$-simplexe.

En particulier, toute suite de longueur maximale $n$ correspond à un simplexe principal numéroté $(0, \dots, n)$. On retrouve donc la notion de cellule au sens des ensembles semi-simpliciaux numérotés. Ainsi, le complexe cellulaire associé au CF-ordre représenté sur la figure 2.21 est représenté sur la figure 2.22.

### 2.3.2.1 Opérations de construction

Les opérations de construction sont le **cône cellulaire** et l'**identification** de cellules.

#### Cône cellulaire

L'opération de cône cellulaire consiste à ajouter une nouvelle cellule et à la relier à l'ordre par $\alpha$. Notons toutefois qu'afin de garantir que le CF-ordre résultant soit fermé, l'opération de cône doit être effectué sur un sous-ordre pur. La figure 2.23 illustre l'opération de cône cellulaire sur un CF-ordre.
<figure><img src="image_29.png" /><figcaption>FIGURE 2.22 – (a) Ensemble semi-simplicial numéroté correspondant au CF-ordre représenté sur la figure 2.21d, avec mise en évidence des cellules. (b) subdivision cellulaire associée à (a).</figcaption></figure>

### Identification

L'opération d'identification consiste à fusionner deux cellules. Il faut pour cela s'assurer que les sous-graphes correspondant à leur fermeture soient identiques.

### 2.3.2.2 Cellules

Le problème illustré par la figure 2.21 est lié à la multi-incidence. Différentes approches ont été menées pour décrire des assemblages de cellules via des graphes d'incidence, aucune ne permet, à notre connaissance, de décrire des structures cellulaires présentant de la multi-incidence. Si cela peut sembler évident que l'on ne peut pas représenter de la multi-incidence entre une *k*-cellule et une (*k* − 1)-cellule, cela est moins évident lorqu'il y a plus d'une dimension d'écart, mais cette limitation est toujours vraie [Damiand 2014] Section 8.2.3.

Concernant les cellules, on sait seulement qu'elles sont obtenues par opération de cône. Même s'ils sont purs et fermés, les cellules des CF-ordres ne correspondent pas nécessairement à des boules. Par exemple, figure 2.24 illustre un CF-ordre pur et fermé contenant de telles cellules : l'arête $e_2$ possède trois sommets dans son bord, et le bord de la face $f_2$ n'est pas connexe.

### 2.3.3 Variétés – Quasi-variétés

Idéalement, il serait intéressant de garantir que la réalisation géométrique des cellules soient homéomorphes à des boules, comme c'est la cas pour les simplexes les cubes et plus généralement les simploïdes. Cela permettait de représenter des CW-complexes, et pouvoir utiliser tous les résultats existants sur ces espaces topologiques. Malheureusement, la caractérisation d'un boule n'est pas combinatoire.

La caractérisation combinatoire utilisée pour définir les cellules des objets construits à partir de *n*-cellules assemblées le long de (*n* − 1)–cellules est basée sur la notion de variété : une condition combinatoire nécessaire est la suivante : toute (*n* − 1)–cellule est incidente à au plus 2 *n*-cellules. En dimension 0, 1 et 2, cette condition est suffisante. Par exemple,
<figure><img src="image_30.png" /><figcaption>FIGURE 2.23 – (a) Un CF-ordre fermé mais non pur : deux cellules principales sont de dimension 2 et une est de dimension 1. (b) le CF-ordre résultant de l'opération de cône sur (a) n'est plus fermé : il y a un saut de dimension (flèche rouge). (c) – (d) Le résultat d'une opération de cône effectuée sur un sous-ordre pur et fermé reste fermé.</figcaption></figure>

la figure 2.25 illustre des exemples de variétés simpliciales obtenues en assemblant deux triangles, le voisinage de tout point est homéomorphe à un disque 4.

Pour $n > 2$, cette condition n'est pas suffisante pour caractériser les variétés. En effet, la classe d'objets vérifiant cette propriété correspond à une classe plus large : les **quasi-variétés**. À notre connaissance, les quasi-variétés consituent la classe d'objets pouvant être caractérisés de manière combinatoire la plus proche des variétés. Par exemple, les cellules $f_2$ et $e_2$ (et leurs bords) de la figure 2.24 ne sont pas des quasi-variétés.

**Définition 12** Une quasi-variété simpliciale numérotée de dimension $n$ est un ensemble semi-simplicial numéroté ($S, \nu$) de dimension $n$ qui peut être construit, à partir d'un ensemble semi-simplicial vide, de la manière suivante :

— ajout des $n$-simplexes isolés (et leurs bords),

— identification des $(n-1)$-simplexes (et leurs bords) de manière à ce que tout $(n-1)$-simplexe soit incident à au plus deux $n$-simplexes.

<footnote n="4">4. Ou bien à un demi-disque sur le bord, dans le cas de variétés à bord.</footnote>
<figure><img src="image_31.png" /><figcaption>FIGURE 2.24 – (a) Un CF-ordre. (b) le complexe simplicial abstrait numéroté correspondant avec mise en évidence des cellules. (c) Une représentation de la subdivision cellulaire, certaines cellules sont clairement pathologiques au sens où leur topologie est très différente de celle d'une boule.</figcaption></figure>

L'objet représenté sur la figure 2.26b est une quasi-variété simpliciale numérotée qui ne correspond pas à une variété. Cet objet peut être obtenu à partir d'un cône sur une cellule carrée (cf. figure 2.26a) en identifiant deux à deux les triangles bleus de deux cotés opposées. Chaque triangle est bien incident à au plus deux tétraèdres, mais le voisinage du sommet numéroté 3 n'est pas homéomorphe à une boule.

Finalement, les **quasi-variétés cellulaires** ou QVC, constituent la sous-classe des quasi-variétés simpliciales numérotées telle que chaque cellule (et son bord) soit également une quasi-variété simpliciale numérotée.

### 2.3.3.1 Quasi-variétés cellulaires

**Définition 13** Une quasi-variété cellulaire $S$ de dimension $n$ est une quasi-variété simpliciale numérotée telle que :

- si $n = 0$, alors $S$ est un ensemble de 0-simplexes numérotés 0, partitionné en composantes connexes de un ou deux 0-simplexes.

- si $n > 0$, alors $S$ peut être construite à partir des deux opérations suivantes :

1. **cône cellulaire** sur une $(n-1)$-quasi-variété cellulaire $S'$ : cette opération consiste à effectuer un cône simplicial sur chaque composante connexe de $S'$, en numérotant $n$ le nouveau sommet du cône de chaque composante,

2. **identification** de deux $(n-1)$-cellules. Soient $c_1$ et $c_2$ deux $(n-1)$-cellules de $S$, telles que chaque $(n-1)$-simplexe de $c_1$ et de $c_2$ appartient au bord d'un seul $n$-simplexe de $S$ et qu'il existe un isomorphisme $\phi$ entre $c_1$ et $c_2$ : cette opération consiste à identifier chaque simplexe de $c_1$ avec le simplexe de $c_2$ correspondant par $\phi$.

Notons que dans la définition, $c_1$ et $c_2$ ne sont pas nécessairement deux cellules différentes. Dans ce cas, il est possible de "replier" la cellule sur elle-même, on parle alors
<figure><img src="image_32.png" /><figcaption>FIGURE 2.25 – (a) Deux triangles peuvent être assemblés de différentes manières afin d'obtenir différentes variétés simpliciales : un anneau en (b), un tore en (c), une bouteille de KLEIN en (d).</figcaption></figure>

de **repliement**. La figure 2.27 présente des exemples et contre-exemples de quasi-variétés cellulaires.

Par définition, dans une quasi-variété cellulaire de dimension $n$, tous les simplexes principaux sont de dimension $n$. De plus, leur définition constructive par cônes et identifications de cellules garantit que tout $(n-1)$-simplexe $\mu$ est face d'exactement un ou deux $n$-simplexes. Si $\mu$ est face de deux simplexes $\sigma$ et $\sigma'$, la numérotation garantit que $\sigma$ et $\sigma'$ partagent $\mu$ via un même opérateur de face $d_i$. Par exemple, sur la figure 2.27b, les opérateurs de face $d_j$ de chaque triangle correspondent aux faces opposées à son sommet numéroté $j$. On peut constater que toute arête partagée par deux triangles est partagée via un même opérateur de face. En particulier, si $\mu = \sigma d_n = \sigma' d_n$, alors $\mu$ appartient à une $(n-1)$-cellule, sinon $\mu$ appartient à une $n$-cellule. La figure 2.28 illustre la construction d'une quasi-variété cellulaire.

### 2.3.4 Cartes combinatoires

Nous présentons dans cette partie des structures cellulaires qui intègrent dans leur définition les contraintes permettant de garantir que les cellules sont des quasi-variétés. Nous présentons deux structures :

- les **Gcartes** qui permettent de représenter des quasi-variétés cellulaires. Les cellules (et leur bord) ainsi que l'assemblage lui-même sont des quasi-variétés;

- les **chaînes de cartes** qui permettent de représenter des assemblages quelconques de quasi-variétés cellulaires.

Différents modèles cellulaires ont été définis dans le but de décrire des variétés combinatoires. Historiquement, les premiers travaux sur les cartes combinatoires ont été effectués par Edmonds [Edmonds 1960] pour représenter des subdivisions de surfaces orientables sans bord. La structure de **demi-arête** a été définie dans le cadre de la modélisation de volumes par leurs bords (solid modeling) [Weiler 1985, Mäntylä 1988]. Ces structures ont été étendues aux surfaces orientables ou non [Guibas 1985], à la dimension 3 par
<figure><img src="image_33.png" /><figcaption>FIGURE 2.26 – (a) Une variété simpliciale de dimension 3 obtenue par une opération de cône sur une cellule carrée. En identifiant deux à deux les quatre faces triangulaires opposées représentées en bleu, on obtient la quasi-variété simpliciale représentée en (b). Par souci de clarté, seules les arêtes des triangles bleues et celles incidentes au sommet numéroté 3 sont représentées. La réalisation topologique de (b) n’est pas une variété : le voisinage du sommet numéroté 3 n’est pas une homéomorphe à une boule de dimension 3.</figcaption></figure>

[Dobkin 1987], et en dimension quelconque par [Vince 1983, Lienhardt 1989]. Des équivalences entre ces structures ont été montrées dans [Lienhardt 1991].

Il existe donc différentes structures basées sur la notion de carte combinatoire. Les cartes généralisées (ou Gcartes) permettent de décrire les quasi-variétés cellulaires en toute dimension, à bord ou sans bord, orientables ou non.

Les Gcartes optimisent la représentation des quasi-variétés cellulaires en tirant parti du fait que tous les simplexes principaux ont même dimension, et que si deux simplexes principaux $\sigma$ et $\mu$ sont adjacents, alors il existe $j$ tel que $\sigma d_j = \mu d_j$. Les cellules ne sont donc pas explicitées au sein de cette structure, mais sont décrites à partir d'un élément plus élémentaire correspondant à chaque simplexe principal : le brin.

Dans la suite de ce chapitre, le terme **cellule** désigne une quasi-variété cellulaire obtenue par application d'une opération de cône sur une quasi-variété cellulaire de dimension inférieure.

### 2.3.4.1 Cartes généralisées

**Définition 14** Une carte généralisée de dimension $n$, ou $n$-Gcarte, où $n \ge 0$, est un $(n+2)$-uplet $G = (B, \alpha_0, \dots, \alpha_n)$ tel que :

- $B$ est un ensemble fini d'éléments, appelés **brins**,

- $\forall i \in [0, n], \alpha_i$ est une involution sur $B$,

- $\forall i \in [0, n-2], \forall j \in [i+2, n], \alpha_i \alpha_j$ est une involution.

Une involution $\alpha_i$ est une permutation telle que $\alpha_i = \alpha_i^{-1}$. Une $n$-Gcarte n'explicite
<figure><img src="image_34.png" /><figcaption>FIGURE 2.27 – (a) Une quasi-variété simpliciale numérotée qui n’est pas une quasi-variété cellulaire, car les deux 2-cellules n’ont pas été assemblées le long d’une 1-cellule complète (en rouge). (b) Une quasi-variété cellulaire. (c) Une quasi-variété cellulaire qui peut être obtenue à partir de (b) en identifiant la 1-cellule (en bleu) avec elle-même, créant un repliement.</figcaption></figure>

que les simplexes de dimension $n$ (i. e. les brins), et les relations d'adjacence entre ces simplexes (i. e. les involutions). Les cellules ne sont pas explicitées, mais peuvent être retrouvées en utilisant la notion d'orbite. Comme les sommets des simplexes principaux sont numérotés de 0 à $n$, tout $n$-simplexe est incident à exactement une $p$-cellule, pour tout $p \in [0, n]$. Une cellule de dimension $p$ peut donc être définie à partir des simplexes principaux, c'est-à-dire des brins.

**Définition 15** Soit $\Phi = \{\pi_0, \dots, \pi_n\}$ un ensemble de permutations définies sur un ensemble $B$. On note $\langle \Phi \rangle = \{\pi_0, \dots, \pi_n\}$ le groupe des permutations de $B$ engendré par $\Phi$. L'orbite d'un élément $b \in B$ relative au groupe $\langle \Phi \rangle$, notée $\langle \Phi \rangle$ (b) est l'ensemble $\{\phi(b) \mid \phi \in \langle \Phi \rangle\}$.

De manière informelle, l'orbite $\langle \alpha_{i_1}, \dots, \alpha_{i_n} \rangle$ (b) d'un brin $b$ d'une Gcarte $G$ est l'ensemble des brins de $G$ qu'il est possible d'atteindre à partir de $b$, par application de n'importe quelle composition d' involutions $\alpha_{i_1}, \dots, \alpha_{i_n}$.

**Définition 16** Soit $G$ une $n$-Gcarte, $b$ un brin de $G$ et $i \in \{0, \dots, n\}$. La $i$-cellule incidente à $b$ est $\langle \alpha_0, \dots, \alpha_{i-1}, \alpha_{i+1}, \dots, \alpha_n \rangle$ (b).

La figure 2.29 illustre les notions d'orbite et de cellules sur une Gcarte de dimension 2. Une $n-G$carte $G = (B, \alpha_0, \dots, \alpha_n)$ est dite **fermée** ou **sans point fixe** si, pour tout $i \in \{0, \dots, n\}$, et pour tout $b \in B$ $b\alpha_i \neq b$. Par exemple, la Gcarte représentée sur la figure 2.29a contient des points fixes par $\alpha_2$.
<figure><img src="image_35.png" /><figcaption>FIGURE 2.28 – Construction d'une quasi-variété cellulaire de dimension 2.</figcaption></figure>

Concernant les opérations de construction, comme les Gcartes correspondent à des quasi-variétés cellulaires, elles peuvent être construites de manière similaire à la définition 13.

### Extention

Soit $G = (B, \alpha_0, \dots, \alpha_n)$ une $n-G$carte, et soit $Q$ la quasi-variété cellulaire de dimension $n$ correspondante. La $(n+1)-G$carte $(B, \alpha_0, \dots, \alpha_n, \alpha_{n+1} = Id)$, appelée l'**extension** de $G$, correspond à l'application d'une opération de cône cellulaire sur chaque composante connexe de $Q$.

### Couture

L'opération de **couture** permet d'assembler les cellules à chaque étape de la construction de la Gcarte. Cette opération correspond à l'identification de cellules et leur bord dans la quasi-variété cellulaire associée. La figure 2.30 illustre la construction de la Gcarte correspondant à la quasi-variété cellulaire représentée sur la figure 2.28.

### Produit cartésien

Le produit cartésien d'une $k$-Gcarte par une $l$-Gcarte est une $(k+l)$-Gcarte. Cette opération n'est pas développée ici, une étude complète détaillant les définitions et les algorithmes de calcul du produit cartésien sur différentes structures cellulaires, notamment les Gcartes et les chaînes de cartes est disponible dans [Lienhardt 2004].

**Notes** : Une attention particulière doit être portée sur l'interprétation cellulaire des Gcartes, afin de bien comprendre ce que l'on manipule. Lorsque l'on passe d'une $n$-Gcarte à une $(n+1)$-Gcarte via une extention, on ajoute, pour chaque composante connexe, une $(n+1)$-cellule, dont le bord est une quasi-variété cellulaire de dimension $n$. Par exemple,
<figure><img src="image_36.png" /><figcaption>FIGURE 2.29 – (a) La 2-Gcarte correspondant à la quasi-variété cellulaire représentée sur la figure 2.27b. (b) Chaque orbite < $\alpha_1, \alpha_2$ > correspond à une cellule de dimension 0. (c) Chaque orbite < $\alpha_0, \alpha_2$ > correspond à une cellule de dimension 1. (d) Chaque orbite < $\alpha_0, \alpha_1$ > correspond à une cellule de dimension 2.</figcaption></figure>

lorsque l'on passe d'une 2-Gcarte représentant une sphère à une 3-Gcarte en ajoutant
$\alpha_3 = Id$, on crée une 3-Gcarte dont le bord correspond à une sphère, la 3-cellule "rem-
plit" la sphère. Considérons à présent une 2-Gcarte représentant un tore; en ajoutant
$\alpha_3 = Id$, on crée une cellule de dimension 3 dont le bord est un tore, mais on n'a pas
"rempli" le tore. Dit autrement, la cellule de dimension 3 ne correspond pas à un tore
"plein" mais bien à un cône sur un tore. Un autre exemple illustre cela : la figure 2.26b
représente une quasi-variété cellulaire qui peut être obtenue par un cône cellulaire (avec
le sommet numéroté 3) sur la surface décrivant un cylindre vertical. On voit bien ici que
la 3-cellule est un cône sur le cylindre et non pas un cylindre "plein".

Bien sûr, cela n'empêche pas de décrire une subdivision d'un tore plein, ou d'un cylindre plein, en construisant par exemple un cube de dimension 3, c'est-à-dire un cylindre plein, et en recollant deux faces opposées pour obtenir un tore "plein".

2.3.4.2 Chaînes de cartes

Comme nous venons de le voir, la notion de quasi-variété cellulaire permet de manipuler
des cellules et des assemblages de cellules proches des variétés.

La modélisation d'objets géométriques non-variétés a également été étudiée par
exemple dans [De Floriani 2003], conduisant à la définition de structures permettant de
relâcher les contraintes portant sur les assemblages de cellules. Nous présentons ici la struc-
ture des **chaînes de cartes** [Elter 1994] qui permet de représenter de tels assemblages,
dont les cellules sont représentées par des Gcartes (cf. figure 2.31).

**Définition 17** *Une chaîne de cartes de dimension n, est un n-uplet :*

$C = ((G^i)_{i=0,...,n}, (\sigma^i)_{i=1,...,n})$ tel que :

1. $\forall i, 0 \le i \le n, G^i = (B^i, \alpha_0^i, \dots, \alpha_{i-1}^i, \alpha_i^i = \omega)$ est une $i-G$ carte telle que $\omega$ n'est pas définie sur $B^i$;

2. $\forall i, 1 \le i \le n, \sigma^i : B^i \to B^{i-1}$;
<figure><img src="image_37.png" /><figcaption>FIGURE 2.30 – En haut : construction d’une Gcarte à partir des opérations d’extension et de couture. L’extension permet de construire une $(n+1)$-Gcarte à partir d’une $n$-Gcarte, l’opération de couture identifie des cellules en respectant les contraintes des quasi-variétés cellulaires. En bas : subdivision cellulaire correspondante.</figcaption></figure>

pour $i \ge 2$, $\sigma^i$ vérifie, pour tout brin $b$ de $B^i$ :

(a) $\sigma^i$ est un isomorphisme$^5$ entre une orbite $< \alpha_0^i, \dots, \alpha_{i-2}^i >$ de $G^i$ et une orbite $< \alpha_0^{i-1}, \dots, \alpha_{i-2}^{i-1} >$ de $G^{i-1}$,

(b) $b\alpha_{i-1}^i\sigma^i\sigma^{i-1} = b\sigma^i\sigma^{i-1}$.

Dans une chaîne de cartes de dimension $n$, toutes les cellules sont explicitement représentées. Les relations d’incidence entre une $i$-cellule et une $(i-1)$-cellule de son bord sont explicitées via les opérateurs de face $\sigma^i$. C’est la raison pour laquelle, pour chaque Gcarte de dimension $i$, l’involution $\alpha_i^i = \omega$ n’est pas définie. On appelle de telles Gcartes des $\omega$-Gcartes.

Une $j$-cellule $c_j$ est incidente à une $i$-cellule $c_i$ s’il existe un brin $b_i$ de $c_i$, un brin $b_j$ de $c_j$, et une suite d’opérateurs de face tels que $b_i\sigma^i \cdots \sigma^{j+1} = b_j$.

<footnote n="5">5. Cette condition 2.(a) est plus restrictive que celle donnée dans [Elter 1994], mais suffisante ici.</footnote>
<figure><img src="image_38.png" /><figcaption>FIGURE 2.31 – (a) Un complexe cellulaire, qui n’est pas une quasi-variété, les cellules sont des quasi-variétés cellulaires. (b) La chaîne de cartes correspondant à la subdivision cellulaire représentée en (a). (c) La légende utilisée pour représenter la chaîne de cartes représentée en (b).</figcaption></figure>

Bien sûr, une chaîne de cartes peut être associée à toute Gcarte. Il suffit pour cela d'expliciter toutes les cellules sous forme de Gcartes. Lorsque l'objet lui même est une quasi-variété cellulaire, il est plus intéressant, au regard de la complexité de la représentation, de le représenter par une seule Gcarte.

### 2.3.5 Équivalences de modèles

Nous avons présenté deux familles de structures cellulaires, présentant deux approches distinctes : pour les graphes d'incidence, les cellules et les relations d'incidence sont explicitées. Les cellules sont quelconques ; on sait seulement que ce sont des cônes. L'assemblage des cellules ne permet pas de représenter de multi-incidence.

La définition des cartes combinatoires est basée sur la notion de quasi-variété cellulaire ; leurs définitions intègrent des contraintes sur les cellules : ce sont des quasi-variétés cellulaires, et les assemblages autorisent la multi-incidence. Les simplexes principaux composant les cellules (i. e. les brins) et leurs relations d'adjacence sont explicitées, mais les cellules en revanche ne le sont pas.

Se pose alors la question du lien entre ces structures, et en particulier : est-il possible d'ajouter des contraintes sur les CF-ordres afin de garantir que les cellules et les assemblages soient des quasi-variétés cellulaires ? La réponse est oui, et la sous-classe des CF-ordres répondant à cela est celle des *n*-surfaces. Les *n*-surfaces ont été initialement définies par [Evako 1996] et introduites dans le domaine de l'analyse d'images par [Bertrand 1999b].
Les $n$-surfaces sont des CF-ordres purs et fermés définis récursivement de la manière suivante :

**Définition 18** *Soit $|X| = (X, \alpha)$ un CF-ordre non vide.*

— L'ordre $|X|$ est une 0-surface si $X$ contient exactement deux éléments $x$ et $y$ tels que $y \notin \alpha(x)$ and $x \notin \alpha(y)$;

— L'ordre $|X|$ est une $n$-surface, $n > 0$, si $|X|$ est connexe, et si, pour tout $x \in X$, l'ordre $|\theta^{\square}(x)|$ est une $(n-1)$-surface.

Les $n$-surfaces sont des CF-ordres permettant de représenter les quasi-variétés cellulaires fermées sans multi-incidence. L'équivalence entre les $n$-surfaces et les $n$-Gcartes fermées sans multi-incidence a été établie dans [Alayrangues 2008].

La figure 2.32 illustre une $n$-surface, la quasi-variété cellulaire correspondante, et la Gcarte associée.

<figure><img src="image_39.png" /><figcaption>FIGURE 2.32 – (a) Une $n$-surface de dimension 2 décrivant une sphère. (b) Le CF-ordre $| \theta^{\square}(e_1) | = | \theta^{\square}(e_2) |$ est une 1-surface. (c) Subdivision cellulaire décrite par (a). (d) La quasi-variété cellulaire correspondant à (a) est fermée et sans multi-incidence. (e) La Gcarte correspondant à la $n$-surface représentée en (a).</figcaption></figure>

Pour résumer, le mécanisme de suppression de la multi-incidence permet de faire le lien dans le cellulaire entre les Gcartes fermées sans multi-incidence et les $n$-surfaces.

L'idée de base permettant de prouver l'équivalence entre ces deux modèles est la notion de **cell-tuple** introduite par Brisson [Brisson 1993] et la **propriété de switch** que doivent respecter les graphes d'incidence. Cette propriété garantit qu'à toute suite de cellules incidentes $(c_0, \dots, c_i, \dots, c_n)$ correspond une unique suite $(c_0, \dots, c'_i, \dots, c_n)$, pour tout $i \in [0, n]$ et $c_i \neq c'_i$. L'opérateur *switch*$_i$ associe à tout triplet $(c_{i-1}, c_i, c_{i+1})$ de cellules incidentes de dimension consécutives, l'unique triplet $(c_{i-1}, c'_i, c_{i+1})$ où $c_i \neq c'_i$. Afin d'homogénéiser la définition de l'opérateur *switch* sur les cellules de dimension 0 et $n$, une cellule fictive de dimension $-1$ et une cellule fictive de dimension $n+1$ sont ajoutées au graphe d'incidence. La figure 2.33 illustre l'opérateur *switch* : étant données trois cellules incidentes, une seule configuration *en diamant* (représentée en rouge) passe par ces 3 cellules.
L'opérateur $switch_i$ correspond dans le modèle des Gcartes aux involutions $\alpha_i$. Une conséquence directe de la propriété de switch est que, pour toute suite $(c_0, \cdots, c_n)$, on a : $(switch_i switch_j)^2 = \text{Id}$ pour tout $j \neq i \pm 1$. Ceci correspond, dans le modèle des Gcartes, à la propriété : $\alpha_i \alpha_j$ est une involution pour tout $j \in [i+2, n]$.

<figure><img src="image_40.png" /><figcaption>FIGURE 2.33 – (a) Une subdivision cellulaire du tore correspondant à une 2-surface. (b) La propriété $switch_0$ associe $(x^{-1}, v_2, e_5)$ et $(x^{-1}, v_3, e_5)$. (c) La propriété $switch_1$ associe $(v_1, e_2, f_2)$ et $(v_1, e_4, f_2)$. (d) La propriété $switch_2$ associe $(e_4, f_2, x^3)$ et $(e_4, f_3, x^3)$. Les cellules fictives $x^3$ et $x^{-1}$ (en vert) sont ajoutées afin d'homogénéiser la propriété de switch pour les rangs 0 et 2.</figcaption></figure>

### 2.3.5.1 Chaînes de surfaces

Comme nous l'avons vu précédemment, les Gcartes permettent de manipuler des quasi-variétés cellulaires, dont les cellules (et leurs bords) sont également des quasi-variétés cellulaires. Les chaînes de cartes permettent de représenter des assemblages quelconques de quasi-variétés cellulaires. De manière analogue, nous avons étendu les *n*-surfaces aux **chaînes de n-surfaces** [Alayrangues 2015c] qui permettent de représenter des assemblages
blages quelconques de quasi-variétés cellulaires sans multi-incidence.

**Définition 19** *Soit $|X| = (X, \alpha)$ un CF-ordre connexe non vide. $|X|$ est une chaîne de surfaces de dimension $k$ si, $\forall i, 1 \le i \le k, \forall x^i$ cellule principale de rang $i$ de $|X|$, $|\alpha^{\square}(x^i)|$ est une $(i-1)$-surface.*

Les chaînes de surfaces généralisent les *n*-surfaces : le bord de chaque *i*-cellule principale est une $(i-1)$-surface, mais la subdivision globale n’est pas nécessairement une *n*-surface. Dit autrement, chaque cellule est contrainte, mais le mode d’assemblage lui-même ne l’est plus.

Nous avons montré l'équivalence entre les chaînes de *n*-surfaces et les chaînes de cartes sans multi-incidence. La figure 2.34 illustre une subdivision cellulaire, sa description par une chaîne de surfaces, et la chaîne de cartes correspondante. Pour montrer cette équivalence, nous avons étendu la propriété *switch* aux chaînes de *n*-surfaces. Afin d'obtenir une définition homogène, nous considérons également une cellule fictive $x^{-1}$ qui appartient à l'-$\alpha$-adhérence de tout élément de X.

**Propriété 1** *Soit $|X|$ une $k$-chaîne de surfaces. $\forall (x, y) \in (X \cup \{x^{-1}\}) \times (X \cup \{y^{-1}\})$, $\beta^\bullet(x) \cap \alpha^\bullet(y)$ est soit vide, soit contient exactement 2 éléments.*

À notre connaissance, les chaînes de *n*-surfaces constituent la structure combinatoire basée sur des graphes d'incidence la plus large pour laquelle une équivalence ait été établie avec une carte combinatoire.

## 2.4 Structures celluloïdales

Nous avons présenté les trois mécanismes à la base de la classification présentée en introduction de ce chapitre sur la figure 2.1 : le produit cartésien, la suppression de la multi-incidence, et la numérotation cellulaire. Afin de compléter la classification présentée en introduction, nous combinons les mécanismes de produit cartésien et de numérotation cellulaire. À notre connaissance, cette étude n’a jamais été menée auparavant.

L'objectif est donc d'étendre à la fois :

- le mécanisme de numérotation cellulaire aux structures simploïdales,

- le mécanisme de produit cartésien aux structures cellulaire,

- le mécanisme de suppression de la multi-incidence aux structures *cellulaires simploïdales*, ou *celluloïdales*.

### 2.4.1 Numérotation – Celluloïdes

Pour rappel, la numérotation des ensembles semi-simpliciaux induit une structuration cellulaire ; le produit cartésien permet quant à lui de structurer des produits de simplexes en simploïdes. Nous combinons ces deux mécanismes en considérant des produits de cellules, ou **celluloïdes**.
<figure><img src="image_41.png" /><figcaption>FIGURE 2.34 – (a) Une chaîne de surfaces correspondant à la subdivision cellulaire (b). En (c), la chaîne de cartes sans multi-incidence correspondante.</figcaption></figure>

Ensuite, nous définissons la notion de **quasi-variété celluloïdale** intégrant les constraintes de quasi-variétés pour les celluloïdes. Ces celluloïdes étant définies, nous donnons les éléments permettant de définir des structures celluloïdales basées sur les graphes d'incidence et sur les cartes combinatoires.

Une celluloïde correspond à un produit de cellules : chaque sommet de l'ensemble semi-simploïdal résultant est numéroté par le *n*-uplet correspondant aux numéros des sommets des ensembles semi-simpliciaux numérotés dont il est issu, comme illustré sur la figure 2.35.

Chaque sommet numéroté *n* d'un ensemble semi-simplicial numéroté correspond à une cellule de dimension *n*. On peut étendre directement la notion de cellule à celle de celluloïde en associant à chaque sommet numéroté (*n*₁, ..., *n*ₚ) une celluloïde de type correspondant. Un type étant un *n*-uplet ne contenant que des valeurs strictement positives, on prendra soin "d'oublier" les sommets numérotés 0. Par exemple, un sommet numéroté (0,0) correspond à une celluloïde de type (); un sommet numéroté (1,0) ou (0,1) correspond à une celluloïde de type (1), etc.
La figure 2.35 illustre la construction d'un ensemble semi-simploïdal numéroté à partir de deux ensembles semi-simpliciaux numérotés, ainsi que les types associés à chaque sommet. Chaque produit de cellules correspond à une celluloïde.

<figure><img src="image_42.png" /><figcaption>FIGURE 2.35 – (a) Deux ensembles semi-simpliciaux numérotés avec mise en évidence des cellules. (b) L'ensemble semi-simploïdal numéroté résultant de (a), avec mise en évidence des celluloïdes. Chaque celluloïde correspond à un produit de cellules.</figcaption></figure>

### 2.4.2 Quasi-variétés celluloïdales

Par construction, tous les simploïdes principaux d'une celluloïde ont même type. Notons que sans contrainte supplémentaire, on observe le même phénomène que dans le simplicial : le produit de cellules qui ne correspondent pas à des quasi-variétés construit une celluloïde qui ne correspond pas non plus à une quasi-variété, comme sur la figure 2.35.

Nous suivons ici l'approche suivante afin de définir les structures basées sur des assemblages de quasi-variétés celluloïdales :

1. création des celluloïdes quasi-variétés (et leurs bords), ou **celluloïdes élémentaires**,

2. assemblage des celluloïdes élémentaires :

- préservant la notion de quasi-variété : Gcartes simploïdales,

- libre : chaînes de cartes simploïdales.

#### 2.4.2.1 Celluloïdes élémentaires

Les briques de base, ou **celluloïdes élémentaires** sont définies comme des produits de quasi-variétés cellulaires, chacune résultant d'une opération de cône cellulaire.

**Définition 20** Une celluloïde élémentaire de type $(a_1, \dots, a_p)$ et de dimension $n = \sum_{i=1}^p a_i$, où $a_i > 0$ pour tout $i$, est le produit de quasi-variétés cellulaires $Q^1, \dots, Q^p$
de dimensions respectives $a_1, \dots, a_p$, telles que, pour tout $i$, $Q^i$ est un cône sur une quasi-variété cellulaire de dimension $a_i - 1$.

Notons que chaque quasi-variété cellulaire $Q^i$ est connexe, contient exactement une $a_i$-cellule, et toutes ses $(a_i - 1)$-cellules sont au bord. Par construction, une celluloïde élémentaire contient donc une seule celluloïde principale (et son bord) de type $(a_1, \dots, a_p)$ et de dimension $n$. Notons également que chaque quasi-variété cellulaire de dimension $a_i$ est un cône cellulaire : aucune identification de $(a_i - 1)$-cellules n'a été effectuée. Par exemple, la figure 2.36 illustre la construction d'une celluloïde élémentaire de type (2, 1) (en haut) et la construction d'une celluloïde élémentaire de type (1, 1, 1) (en bas).

<figure><img src="image_43.png" /><figcaption>FIGURE 2.36 – (a) Deux cellules (et leurs bords) de dimensions 2 et 1 avec mise en évidence des cellules. (b) La celluloïde élémentaire de type (2, 1) issue de (a), avec mise en évidence des celluloïdes. (c) Trois cellules (et leurs bords) de dimension 1 avec mise en évidence des cellules. (d) La celluloïde élémentaire de type (1, 1, 1) issue de (c), avec mise en évidence des celluloïdes.</figcaption></figure>

Dans la suite de cette partie, toutes les **celluloïdes** considérées sont issues de celluloïdes élémentaires. Dit autrement, chaque celluloïde correspond à l'intérieur d'une quasi-variété.
### 2.4.2.2 Assemblages de celluloïdes

Dans cette partie, nous posons les bases permettant d'étendre les Gcartes et les chaînes de cartes pour manipuler des assemblages de celluloïdes : les Gcartes simploïdales et les chaînes de cartes simploïdales. Pour rappel, nous avons vu en section 2.3.4 que les Gcartes et les chaînes de cartes permettent de représenter des assemblages de cellules où pour chaque *n*-cellule, seuls les *n*-simplexes sont explicités : chacun étant représenté par un brin. Pour ces deux structures, les involutions $\alpha_i$, $i < n$, représentent des relations d'adjacence via un même opérateur de face au sein d'une cellule de dimension *n*. Concernant les assemblages de cellules :

- pour les chaînes de cartes, les opérateurs $\sigma_i$ décrivent les relations de face entre cellules,

- pour les Gcartes, seules les *n*-cellules sont représentées et les opérateurs de face sont remplacés par des opérateurs d'adjacence entre *n*-cellules : les opérateurs $\sigma_n$ sont remplacés par les involutions $\alpha_n$.

De manière analogue, chaque simploïde principal d'une celluloïde peut être représenté par un brin, caractérisé par son type. La définition des celluloïdes garantit que tous les simploïdes de dimension $n-1$ faisant partie d'une celluloïde de dimension *n* sont incidents à exactement 2 simploïdes principaux, qui le partagent via un même opérateur de face $d_j^i$. La définition 21 traduit la notion de celluloïde élémentaire dans le formalisme des cartes combinatoires.

**Définition 21** Une Gcarte simploïdale élémentaire de type $(a_1, \dots, a_p)$ est un *n*-uplet $G = (B, (\alpha_j^i)_{j \in [0, a_i]})$, munie d'un opérateur de type $\mathcal{T}: B \mapsto \bigcup_{i \ge 0} \mathbb{N}^{*i}$ tel que :

1. pour tout $b \in B$, $b\mathcal{T} = (a_1, \dots, a_p)$,

2. pour tout $i \in [1, p]$, $\alpha_{a_i}^i = \omega$ n'est pas définie sur B,

3. $\forall i \in [1, p], (B, (\alpha_j^i)_{j \in [0, a_i]})$ est une $\omega$-Gcarte,

4. $\forall i \neq k, \forall j \in [0, a_i - 1], \forall l \in [0, a_k - 1], \alpha_j^i \alpha_l^k$ est une involution.

Les cartes combinatoires simploïdales peuvent être définies à partir des Gcartes simploïdales élémentaires :

- pour les **chaînes de cartes simploïdales**, qui décrivent des assemblages libres de celluloïdes, il faut ajouter des opérateurs de face,

- pour les **Gcartes simploïdales**, qui décrivent des quasi-variétés celluloïdales, les opérateurs de face sont remplacés par des opérateurs d'adjacence entre celluloïdes élémentaires de même dimension, dont les types sont compatibles, c'est-à-dire qui peuvent être assemblées le long d'une celluloïde de leur bord.

#### Chaînes de cartes simploïdales

Il est à présent possible de définir les **chaînes de cartes simploïdales**, afin de décrire des assemblages quelconques de Gcartes simploïdales élémentaires. L'idée est la suivante : toutes les celluloïdes étant explicitées, on ajoute les opérateurs de face $\sigma_{a_i}^i$, qui décrivent les relations de face entre celluloïdes; voici dans les grandes lignes l'idée de la définition :
— soit $b$ un brin d'une Gcarte simploïdale élémentaire $C$, tel que $b\tau = (a_1, \dots, a_p)$ :

— les opérateurs de face $\sigma_{a_i}^i$ sont définis sur $C$ pour $i \in [1, p]$,

$$ - b\sigma_{a_i}^i \tau = \begin{cases} (a_1, \dots, a_{i-1}, a_i - 1, a_{i+1}, \dots, a_p) & \text{si } a_i > 1, \\ (a_1, \dots, a_{i-1}, a_{i+1}, \dots, a_p) & \text{si } a_i = 1, \end{cases} $$

— les opérateurs de face $\sigma_{a_i}^i$ sont des isomorphismes sur les faces.

— chaque $\sigma_{a_i}^i$ vérifie à la fois :

— la propriété décrite pour les chaînes de cartes simpliciales sur chaque composante du brin cf. 2.(b) de la définition 17,

— les propriétés de commutation des ensembles semi-simploïdaux.

Par exemple, la figure 2.37 représente un assemblage de celluloïdes élémentaires et la chaîne de cartes simploïdale correspondante.

<figure><img src="image_44.png" /><figcaption>FIGURE 2.37 – (a) Un assemblage de celluloïdes élémentaires avec mise en évidence des celluloïdes. (b) Ensemble des Gcartes simploïdales élémentaires. (c) Convention utilisée. (d) Chaîne de cartes simploïdale associée à (a).</figcaption></figure>

## Gcartes simploïdales
Pour définir les **Gcartes simploïdales**, seules les celluloïdes principales sont expli-
citées, ainsi que les relations d'adjacence. Les celluloïdes principales ont toutes la même
dimension *n*, mais peuvent avoir des types différents.

Pour cela, nous adaptons la définition des Gcartes simploïdales élémentaires : les in-
volutions $\alpha_{a_i}^i$ sont à présent définies et décrivent les relations d'adjacence entre celluloïdes
compatibles, c'est-à-dire qui peuvent être assemblées le long de faces isomorphes. Atten-
tion : les opérateurs d'adjacence $\alpha_{a_i}^i$ ne sont pas des involutions car rien ne garantit que
deux celluloïdes sont assemblées via un même opérateur $\alpha_{a_i}^i$. Par exemple, une celluloïde
de type (1, 1, 1) pourra être assemblée à une celluloïde de type (2, 1) le long d'une cel-
luloïde de type (1, 1) de trois manières différentes : par $\alpha_1^1$, $\alpha_1^2$ ou $\alpha_1^3$. Les propriétés de
commutation définies sur ces opérateurs d'adjacence dépendent donc de la composante
utilisée pour assembler les celluloïdes. Par exemple, la figure 2.38 reprend l'exemple de la
figure 2.37 en tirant partie du fait que l'assemblage des celluloïdes est une quasi-variété.
Les celluloïdes élémentaires de types (2) et (1, 1) sont assemblées le long de celluloïdes de
type (1).

<figure><img src="image_45.png" /></figure>

<figure><img src="image_46.png" /><figcaption>FIGURE 2.38 – a) Quasi-variété celluloïdale correspondant à l'exemple de la figure 2.37, seules les celluloïdes principales sont explicitées. (b) Gcarte simploïdale correspondant à (a), les opérateurs de face $\sigma_j^i$ des celluloïdes principales sont remplacées par des opérateurs d'adjacence $\alpha_j^i$ entre celluloïdes principales.</figcaption></figure>

La figure 2.39 illustre un exemple en dimension 3 : les brins verts sont de type (2, 1), les brins roses sont de type (1, 1, 1). Toutes les involutions sont représentées par des *liaisons* non orientées, les opérateurs d'adjacence sont représentés par des *liaisons* orientées. Chaque couleur correspond aux opérateurs $\alpha_j^i$ pour $i$ fixé : en rouge $\alpha_1^1$, en bleu $\alpha_2^2$ et en vert $\alpha_3^3$. Par souci de clarté, seuls les opérateurs d'adjacence différents de l'identité sont représentés.

On peut vérifier que pour tout brin vert *b* de type (2, 1) relié à un brin rose *b'* de type (1, 1, 1), $b\alpha_2^1 = b'$ et $b'\alpha_1^2 = b$. Les deux celluloïdes sont assemblées le long d'une celluloïde de type (1, 1). De manière intuitive, $b'\alpha_1^2 = b$ signifie que c'est la seconde arête composant
$b'$ qui est supprimée pour obtenir la face de type (1, 1). Donc $b\alpha_2^1\alpha_0^1$ commute avec $b\alpha_0^1\alpha_2^1$ et $b\alpha_2^1\alpha_0^3$ commute avec $b\alpha_0^2\alpha_2^1$.

<figure><img src="image_47.png" /><figcaption>FIGURE 2.39 – *a*) Un ensemble de quasi-variétés celluloïdales élémentaires de dimension 3. Seuls les simploïdes principaux sont représentés. (*c*) La Gcarte simploïdale correspondante, les opérateurs d'adjacence ne sont pas représentés, ils sont tous égaux à l'identité. (*b*) Une quasi-variété celluloïdale obtenue à partir des quasi-variétés celluloïdales élémentaires de (*a*). (*d*) La Gcarte simploïdale correspondante ; seuls les opérateurs d'adjacence différents de l'identité sont représentés : $\alpha_2^1$ (en rouge) et $\alpha_1^2$ (en bleu).</figcaption></figure>

Bien sûr, les Gcartes simploïdales autorisent la multi-incidence. On peut tout à fait recoller une Gcarte simploïdale élémentaire sur elle-même : soit sur deux de ses faces, à la seule condition qu'elles soient isomorphes, soit en recollant une face automorphe sur elle-même en créant ainsi un repliement.

### 2.4.3 Graphes d'incidences simploïdaux

On s'intéresse enfin au mécanisme de suppression de la multi-incidence pour les structures celluloïdales. Nous donnons dans cette partie les éléments de base pour la définition graphes d'incidence simploïdaux à partir de la notion de *CF*-ordre vue en Section 2.3.2 pour les structures cellulaires.

Nous suivons ici la même approche que pour les structures quasi-variétés celluloïdales,
nous définissons :

- la notion de CF-celluloïde dans le formalisme des CF-ordres,

- l'opération d'identification permettant d'assembler des celluloïdes.

Comme vu précédemment, chaque cellule est un cône, et une celluloïde est produit de cellules. Rappelons que nous avons défini les complexes simploïdaux abstraits à partir d'ensembles de sommets disjoints $V^1, \dots, V^n$; et deux simploïdes peuvent être identifiés s'ils ont même structure, c'est-à dire s'ils sont définis à partir des mêmes ensembles de sommets. Nous gardons ici la même approche en étendant la définition des ensembles simploïdaux abstraits aux celluloïdes.

**Définition 22** Une CF-celluloïde de type $(a_1, \dots, a_n)$ est un ensemble de CF-ordres $(X^1, \alpha^1), \dots, (X^n, \alpha^n)$ tel que pour tout $i \in [1..n]$ :

- $(X^i, \alpha^i)$ est de dimension $a_i$,

- $(X^i, \alpha^i)$ est un cône sur un CF-ordre pur et fermé,

- tous les ensembles $X^i$ sont disjoints.

Par exemple, la figure 2.40 représente la CF-celluloïde de type (2, 1) correspondant à l'ensemble semi-simploïdal numéroté illustrée sur la figure 2.35.

<figure><img src="image_48.png" /><figcaption>FIGURE 2.40 – La CF-celluloïde correspondant à la figure 2.35 est définie par l'ensemble des deux CF-ordres décrivant des cônes sur des CF-ordres purs et fermés.</figcaption></figure>

On peut reconstruire le complexe simploïdal abstrait numéroté correspondant en considérant tous les ensembles de chemins (un chemin par composante) de la celluloïde, cf. figure 2.41.

### Assemblages de celluloïdes

Afin de décrire des assemblages de celluloïdes, il faut définir l'opération d'identification. Soit $C = \{(X^1, \alpha^1), \dots, (X^n, \alpha^n)\}$ une CF-celluloïde de type $(a_1, \dots, a_n)$. Toutes les celluloïdes du bord de $C$ sont identifiées par des ensembles de sous-ordres de $\{(X^1, \alpha^1), \dots, (X^n, \alpha^n)\}$. Par exemple, la figure 2.42 représente une CF-celluloïde du bord de la celluloïde principale représentée sur la figure 2.40.

Les identifications sont donc définies au niveau des cellules du bord, et consistent donc à fusionner des sous-ordres, composante par composante. Pour cela, il faut que les CF-celluloïdes aient même structure, i. e. définies à partir d'un même ensemble d'ordres,
<figure><img src="image_49.png" /><figcaption>FIGURE 2.41 – (a) Une CF-celluloïde principale de type {2, 1} et son bord. (b) Complexe simploïdal abstrait correspondant à (a). Le simploïde de type {2, 1} représenté en bleu correspond au produit du chemin bleu de longueur 2 de la première composante, par le chemin bleu de longueur 1 de la seconde composante.</figcaption></figure>

comme expliqué pour les complexes simploïdaux abstraits. Afin que les types correspondent, il sera donc éventuellement nécessaire d'effectuer le produit d'une CF-celluloïde par un CF-celluloïde correspondant à un sommet.

## 2.5 Gestion de la dégénérescence

Cette partie présente le dernier mécanisme évoqué en introduction : la dégénérescence. Nous présentons deux structures permettant de gérer ce mécanisme : les ensembles simpliciaux et simploïdaux. Ces structures sont munies, en plus des opérateurs de face, d'une seconde famille d'opérateurs appelés **opérateurs de dégénérescence**. Les opérateurs de dégénérescence permettent en particulier de définir :

- l'opération de produit cartésien sur les ensembles simpliciaux. Une définition directe sur les ensembles semi-simpliciaux peut en être déduite [Lienhardt 2004];

- l'opération de cône simploïdal. Cette définition ne s'étend pas aux ensembles semi-simploïdaux.

Cette partie s'appuie en particulier sur les références [May 1967, Lang 1996, Peltier 2018].

### 2.5.1 Ensembles simpliciaux

Les ensembles simpliciaux sont classiquement étudiés en topologie. Un ensemble simplicial est un ensemble semi-simplicial muni d'une seconde famille d'opérateurs : les opérateurs de dégénérescence.
<figure><img src="image_50.png" /><figcaption>FIGURE 2.42 – (a) La celluloïde de type (1,1) et son bord, face de la celluloïde principale principale de type {2,1}, est définie par l'ensemble des deux sous-ordres représentés en bleu. (b) La celluloïde correspondante à (a) est représentée en bleu.</figcaption></figure>

### 2.5.1.1 Structure combinatoire

**Définition 23** *Un ensemble simplicial $S = S = (K, (d_i), (s_i))$ est une famille d'ensembles $K = (K^p)_{i \in \mathbb{N}}$, munie de deux familles d'applications : $\forall p > 0, \forall i, 0 \le i \le p, d_i : K^p \to K^{p-1}; \forall p \ge 0, \forall i, 0 \le i \le p, s_i : K^i \to K^{i+1}$, vérifiant :*

$$d_i d_j = d_j d_{i-1} \quad \text{si } j < i$$

$$s_i s_j = s_j s_{i+1} \quad \text{si } j \le i$$

$$s_i d_j = d_j s_{i-1} \quad \text{si } j < i$$

$$s_i d_j = d_{j-1} s_i \quad \text{si } j > i + 1$$

$$s_i d_i = s_i d_{i+1} = \text{Id}$$

*Un $(p+1)$-simplexe $\mu$ est dit **dégénéré** s'il existe un $p$-simplexe $\sigma$ et un opérateur de dégénérescence $s_i$ tel que $\mu = \sigma s_i$.*

De manière intuitive, un $p$-simplexe $\sigma$ peut être associé à la suite de ses sommets $(v_0, \dots, v_j, \dots, v_p)$. Le $(p-1)$-simplexe $\sigma d_j$ correspond à la suite de sommets $(v_0, \dots, v_{j-1}, v_{j+1}, \dots, v_p)$ et le $(p+1)$-simplexe dégénéré $\sigma s_j$ correspond à la suite de sommets $(v_0, \dots, v_j, v_{j+1}, \dots, v_p)$.

D'un point de vue théorique, tous les ensembles simpliciaux contiennent un nombre infini de simplexes : en effet, à tout $i$-simplexe correspond au moins un $(i+1)$-simplexe dégénéré. En pratique, seuls les simplexes non dégénérés et leurs bords (dégénérés ou non) sont utiles pour représenter des objets géométriques correspondants.

### 2.5.1.2 Opérations de construction

Les opérations de construction de base sont ici encore le cône et l'identification.
<figure><img src="image_51.png" /><figcaption>FIGURE 2.43 – a) Un ensemble semi-simplicial. (b) Un ensemble simplicial : l’arête rouge $\mu$ est dégénérée sur le sommet rouge $\sigma$ (i. e. $\mu = \sigma s_0$). (c) Une représentation intuitive de la structuration simpliciale correspondant à (b) : d’un point de vue topologique, l’arête dégénérée n’intervient plus dans le bord du triangle. (d) Un ensemble simplicial représentant une arête et son bord et tous ses simplexes dégénérés jusqu’à la dimension 2.</figcaption></figure>

## Cône

L’opération de cône s’étend directement sur les ensemble simpliciaux. Pour chaque $p$-simplexe $\sigma$ (dégénéré ou non) de l’ensemble simplicial sur lequel on souhaite effectuer une opération de cône, un $(p+1)$-simplexe $\bar{\sigma}$ est créé. Les opérateurs de face sont établis comme décrit pour les ensembles semi-simpliciaux, et les opérateurs de dégénérescence sont établis de la même manière : $\bar{\sigma}s_j = \sigma s_j$ pour tout $0 \le j \le p$.

## Identification

L’opération d’identification de deux $p$-simplexes $\sigma$ et $\mu$ ayant même bord implique l’identification deux à deux de tous les simplexes dégénérés issus de $\sigma$ et $\mu$ par une même suite d’opérateurs de dégénérescence, comme illustré sur la figure 2.44. Plus précisément, soit $K$ l’ensemble des simplexes de $S$ avant l’identification de $\sigma$ et $\mu$. $K$ peut être partitionné en $K = C_0 \cup \dots \cup C_n \cup K'$ tel que pour tout $i$, tous les simplexes de $C_i$ doivent être identifiés$^6$; les simplexes de $K'$ ne sont pas impactés par l’identification. Après l’identification de $\sigma$ et $\mu$, l’ensemble simplicial résultant contient donc un seul simplexe $\gamma_i$ pour chaque classe d’équivalence $C_i$, ainsi que tous les simplexes de $K'$.

Les opérateurs de face et de dégénérescence de chaque simplexe $\gamma_i$ sont définis en respectant les classes d’équivalence. Il faut ensuite mettre à jour les opérateurs de face des simplexes de $K'$ qui avaient une face dans une classe d’équivalence, ainsi que les opérateurs de dégénérescence des simplexes de $K'$ qui dégénéraient un simplexe d’une classe d’équivalence. Le détail de l’algorithme est disponible dans [Peltier 2018].

<footnote n="6">6. L’indice *i* est simplement un numéro de classe d’équivalence, et n’a rien à voir avec la dimension des simplexes de la classe.</footnote>
<figure><img src="image_52.png" /><figcaption>FIGURE 2.44 – L'identification de l'arête non dégénérée (en noir) et de l'arête dégénérée (en rose) représentées en (a) induit l'identification de leurs dégénérés. Le résultat de l'identification de ces deux arêtes est représenté en (b).</figcaption></figure>

### Produit cartésien

Comme indiqué en préambule, le **produit cartésien** $S \times S'$ de deux ensembles simpliciaux $S$ et $S'$ peut être défini de manière directe : tout $p$-simplexe $\mu \in S \times S' = (\sigma, \sigma')$, où $\sigma$ et $\sigma'$ sont deux $p$-simplexes est tel que pour tout $j$, $\mu d_j = (\sigma d_j, \sigma' d_j)$ et $\mu s_j = (\sigma s_j, \sigma' s_j)$. Par exemple, sur la Figure 2.45, on peut vérifier que $(\beta s_1, \beta' s_0)d_0 = (\beta s_1 d_0, \beta' s_0 d_0) = (\beta d_0 s_0, \beta') = (\gamma s_0, \beta')$.

L'opération de produit cartésien peut être étendue sur les ensembles semi-simpliciaux en considérant un ensemble semi-simplicial comme un ensemble simplicial, en manipulant ses simplexes dégénérés et ses opérateurs de dégénérescence de manière implicite.

**Théorème 2** [*Lienhardt 2004*] On peut associer un ensemble semi-simplicial à tout ensemble simplicial, dont tous les simplexes dégénérés sont faces de simplexes dégénérés et réciproquement.

L'ensemble semi-simplicial et l'ensemble simplicial associé sont dits **équivalents**. Par exemple, l'ensemble simplicial représenté sur la figure 2.45b est équivalent à un ensemble semi-simplicial.

Il est montré dans [Lang 1997], qu'un $p$-simplexe $\nu = (\sigma I, \mu J)$ résultant du produit cartésien de deux simplexes $p$-simplexes $\sigma I$ et $\mu J$, avec $I = s_{i_1} \cdots s_{i_k}$ et $J = s_{j_1} \cdots s_{j_l}$, est dégénéré si et seulement si un même opérateur de dégénérescence est à la fois dans $I$ et dans $J$. Inversement, un $p$-simplexe $\nu$ n'est pas dégénéré si et seulement si aucun opérateur apparaît à la fois dans $I$ et dans $J$. Autrement dit, tous les simplexes, d'un ensemble simplicial $S$ équivalent à un ensemble semi-simplicial peuvent être définis par un simplexe $\sigma$ non dégénéré de $S$ et une suite d'opérateurs de dégénérescence. On peut ainsi montrer que le produit cartésien de deux ensembles simpliciaux équivalents à des ensembles semi-simpliciaux est lui aussi équivalent à un ensemble semi-simplicial.

Finalement, l'opération de produit cartésien se définit sur les ensembles semi-simpliciaux [Lienhardt 2004] en manipulant les opérateurs de dégénérescence de manière implicite, via des suites d'indices.
<figure><img src="image_53.png" /><figcaption>FIGURE 2.45 – Le produit cartésien de deux ensembles simpliciaux s’exprime directement à l’aide des indices des opérateurs de dégénérescence. (a) Deux arêtes non dégénérées et leur bord. (b) Le résultat du produit cartésien. Seuls les simplexes non dégénérés sont nommés.</figcaption></figure>

## 2.5.2 Ensembles simploïdaux

Les ensembles semi-simploïdaux permettent de manipuler au sein d'un même formalisme des assemblages de simplexes, de cubes et plus généralement de simploïdes, mais l'opération de cône n'est pas définie sur les ensembles semi-simploïdaux : cf. figure 2.46.

Les ensembles simploïdaux généralisent à la fois les ensembles simpliciaux et les ensembles cubiques qui peuvent être définis de la manière suivante [Serre 1951, Brown 1981].

**Définition 24** Un ensemble cubique $S = (K, (d_j^i), (s^i))$ est une famille $K = (K^p)_{p \in \mathbb{N}}$ de cubes abstraits munis de deux familles d'applications, tel que $(K, (d_j^i))$ est un ensemble semi-cubique, les $(s^i)$ sont les opérateurs de dégénérescence : $\forall p \ge 0, \forall i, 0 \le i \le p, s^i : K^p \to K^{p+1}$, tels que :

$$- s^i s^k = s^k s^{i+1} \quad \text{si } k \le i,$$

$$- s^i d_j^k = d_j^k s^{i-1} \quad \text{si } k \le i,$$

$$- s^i d_j^k = d_j^{k-1} s^i \quad \text{si } k > i + 1,$$

$$- s^i d_j^{i+1} = \text{Id}.$$

Par exemple, si $c$ est un 2-cube, donc de type $(1, 1)$, $cs^i$ est le 3-cube dégénéré de type $(1, 1, 1)$ où $i$ correspond à la position de la nouvelle arête dégénérée dans le type.

### 2.5.2.1 Structure combinatoire

Comme vu pour les ensembles simpliciaux et cubiques, les opérateurs de dégénérescence sont des applications qui montent en dimension.
<figure><img src="image_54.png" /><figcaption>FIGURE 2.46 – L’opération de cône n’est pas définie sur les ensembles semi-simploïdaux. (a) Un ensemble semi-simploïdal. (b) Le cône sur un simploïde de type (1, 1) produit une cellule de dimension 3 qui n’est pas un simploïde (en rouge).</figcaption></figure>

Un simploïde peut être dégénéré de deux manières différentes : soit sur un simploïde de même longueur, ce qui correspond intuitivement à dégénérer un de ses simplexes générateurs; soit en augmentant la longueur de 1, ce qui correspond intuitivement à la dégénérescence vue pour les cubes, c’est-à-dire au produit cartésien par une arête dégénérée.

Par exemple, à partir d'un simploïde de type (2,3), ses opérateurs de dégénérescence permettent d'obtenir des simploïdes dégénérés :

- de type (3,3) et (2,4) : intuitivement, on dégénère chacun de ses simplexes générateurs ;

- de type (1,2,3), (2,1,3) et (2,3,1) : intuitivement, on effectue le produit du simploïde par une arête dégénérée.

Bien entendu, des relations de cohérence doivent être respectées entre les opérateurs de face et les opérateurs de dégénérescence. La définition 25 est une version corrigée de celle publiée dans [Peltier 2018], qui intègre des cas particuliers liés aux opérateurs de dégénérescence $s_{-1}^i$.

**Définition 25** Un ensemble simploïdal $S = (K, (d_j^i), (s_l^k))$ est un ensemble de simploïdes muni d'un opérateur de type $\mathcal{T}: K \mapsto \bigcup_{i \ge 0} \mathbb{N}^{*i}$, d'opérateurs de face $d_j^i$ et d'opérateurs de dégénérescence $s_l^k$.

Soit $\sigma \in K$ ; $\sigma \mathcal{T} = (a_1, \cdots, a_n)$ est le type de $\sigma$ ; $\sigma d_j^i$ (resp. $\sigma s_l^k$) est défini si $1 \le i \le n, 0 \le j \le a_i$ (resp. $0 \le k \le n$ et $l = -1$, ou $1 \le k \le n$ et $0 \le l \le a_k$). Les opérateurs de face vérifient les propriétés suivantes :

(I) Action sur le type
$$
1) \sigma d_j^i \mathcal{T} = \begin{cases} (a_1, \dots, a_i - 1, \dots, a_n) & \text{si } a_i > 1 \\ (a_1, \dots, a_{i-1}, a_{i+1}, \dots, a_n) & \text{sinon} \end{cases}
$$

$$
2) \sigma s_j^i \mathcal{T} = \begin{cases} (a_1, \dots, a_i + 1, \dots, a_n) & 1 \le i \le n, 0 \le j \le a_i \\ (a_1, \dots, a_i, 1, a_{i+1}, \dots, a_n) & 0 \le i \le n, j = -1 \end{cases}
$$

(II) Commutation des opérateurs de face

1) $d_j^i d_l^i = d_l^i d_{j-1}^i \quad l < j, a_i > 1$

$$
2) d_j^i d_l^k = \begin{cases} d_l^k d_j^i & \text{si } a_k > 1 \\ d_l^k d_j^{i-1} & \text{sinon} \end{cases} \quad k < i
$$

(III) Commutation des opérateurs de dégénérescence

$$
1) s_{-1}^{i} s_{-1}^{k} = s_{-1}^{k} s_{-1}^{i+1} \quad k \le i
$$

$$
2) si l \neq -1, s_{-1}^{i} s_{l}^{k} = \begin{cases} s_{l}^{k} s_{-1}^{i} s_{l}^{i} & k \le i \\ s_{l}^{k-1} s_{-1}^{i} s_{l}^{i} & i < k-1 \end{cases} \\
s_{-1}^{i} s_{0}^{i+1} = s_{-1}^{i} s_{1}^{i+1}
$$

$$
3) si j, l \neq -1, s_j^i s_l^k = \begin{cases} s_l^k s_j^i s_i & i \neq k \\ s_l^k s_{j+1}^i s_i & i = k, l \le j \end{cases}
$$

(IV) Commutation des opérateurs de face/dégénérescence

$$
1) si l \neq -1, s_l^i d_l^i = s_l^i d_{l+1}^i = Id
$$

$$
s_l^i d_j^i = \begin{cases} d_j^i s_{l-1}^i & \text{si } j < l \\ d_{j-1}^i s_l^i & \text{si } j > l+1 \end{cases} \quad \text{si } a_i > 1
$$

$$
\begin{align*}
s_1^i d_0^i &= d_0^i s_{-1}^{i-1} & \text{si } a_i = 1 \\
s_0^i d_2^i &= d_1^i s_{-1}^{i-1}
\end{align*}
$$

$$
2) si l = -1, s_l^{i-1} d_j^i = Id, j = 0, 1
$$

Dans les autres cas :

$$
3) si k \le i - 1, s_l^k d_j^i = \begin{cases} d_j^i s_l^k & si l \ne -1 \\ d_{j-1}^{i-1} s_l^k & sinon \end{cases}
$$

$$
4) \text{ sinon (i. e. } k > i), s_l^k d_j^i = \begin{cases} d_j^i s_l^k & \text{si } a_i > 1 \\ d_j^i s_{l-1}^{k-1} & \text{sinon} \end{cases}
$$

□

Pour rappel, aucun "0" n'apparaît dans le type d'un simploïde, car le produit
cartésien d'un simplexe par un sommet est l'identité d'un point de vue structurel. Cela
explique pourquoi différents cas doivent être distingués dans la définition, même si ces
différents cas sont intuitivement similaires. Plus généralement, la définition 25 peut être
entièrement retrouvée à partir des propriétés de commutation sur les opérateurs de face et
de dégénérescence des ensembles simpliciaux, et du fait que, intuitivement, l'application
de deux opérateurs sur deux simplexes générateurs différents sont indépendants.

La partie (I) décrit l'action d'un opérateur de face (resp. dégénérescence) sur le type d'un simploïde (I-1) (resp. (I-2)). Comme vu pour le simplicial, un opérateur de face (resp. dégénérescence) diminue (resp. augmente) la dimension du simploïde sur lequel il agit. En particulier, si $a_i = 1$, alors l'application d'un opérateur $d_j^i$ diminue la longueur du simploïde (car il n'y a aucun 0 dans le type d'un simploïde). De manière similaire, lorsque l'on applique un opérateur de dégénérescence $s_{-1}^k$, la longueur du simploïde augmente. Intuitivement, cela revient à ajouter une arête dégénérée comme simplexe générateur du simploïde.

Les parties (II) (resp. (III), (IV)) sont les relations de cohérence liées aux opérateurs de face (resp. dégénérescence, face et dégénérescence).

On peut noter que différents cas correspondent aux propriétés de commutation des ensembles simpliciaux, *i. e.* lorsque les opérateurs sont appliqués sur un même simplexe générateur : cf. équation (II-1), le dernier cas de (III-3), et (IV-1).

Le cas (IV-2) correspond au cas où un opérateur de face est appliqué à 1-simplexe générateur dégénéré (au final, rien n'est modifié).

Les autres cas garantissent l'indépendance des opérateurs appliqués sur des simplexes générateurs distincts :

- (II-2) : deux cas distincts car un 1-simplexe générateur peut disparaitre suite à l'application d'un opérateur de face ;

- (III-1), (III-2) et le premier cas de (III-3) : correspondent aux différents cas de dégénérescence, qui prennent en compte l'ajout de nouveaux simplexes générateurs créés par des opérateurs $s_{-1}$. Notons que (III-2) n'a pas de propriété de com-mutation lorsque $k = i + 1$, car $\sigma s_{-1}^{k-1} s_l^k \mathcal{T} = (a_1, \dots, a_{k-1}, 2, \dots, a_n)$ (le premier opérateur de dégénérescence créé un nouveau 1-simplexe générateur, sur lequel le second opérateur de dégénérescence agit). Il doit néanmoins vérifier les contraintes des ensembles simpliciaux, c'est pourquoi on avoir la propriété $s_{-1}^i s_0^{i+1} = s_{-1}^i s_1^{i+1}$.

- (IV-3) et (IV-4) : deux cas distincts en fonction de la création ou la suppression d'un 1-simplexe générateur.

Notons qu'une conséquence directe de la définition des ensembles simploïdaux est que l'on peut associer un unique ensemble simploïdal à tout ensemble simplicial ainsi qu'à tout ensemble cubique. Par exemple, tout *p*-simplexe d'un ensemble simplicial correspond à un simploïde de type (*p*) et tout opérateur de face (resp. dégénérescence) simplicial $d_i$ (resp. $s_j$) correspond à un opérateur de face (resp. dégénérescence) simploïdal $d_i^1$ (resp. $s_j^1$). L'idée est similaire pour les ensembles cubiques en associant un simploïde de type (1, ..., 1) de longueur *p* à tout *p*-cube.

Comme pour les ensembles simpliciaux, d'un point de vue théorique, tous les simploïdes dégénérés existent et tout ensemble simploïdal est donc par définition de taille infinie. Ici encore, seuls les simploïdes non dégénérés et leurs bords (dégénérés ou non) sont utiles pour représenter des objets géométriques corespondants : cf. chapitre 4.
### 2.5.2.2 Opérations de construction

Les opérateurs de dégénérescence permettent de définir l'opération de cône sur les ensembles simploïdaux. Ainsi, les ensembles simploïdaux généralisent et homogénéisent les ensembles simpliciaux et cubiques, à la fois au regard des cellules, mais également des opérations.

#### Produit cartésien

Comme pour les ensembles semi-simploïdaux, l'opération de **produit cartésien** permet de construire en particulier les simploïdes. La définition du produit cartésien de deux ensembles simploïdaux $S^1$ et $S^2$ est directement déduite de la propriété suivante : le produit cartésien de $\sigma^1$ de type $(a_1, ..., a_k)$, et $\sigma^2$ de type $(b_1, ..., b_l)$ est un simploïde $\sigma^1 \times \sigma^2$ de type $(a_1, ..., a_k, b_1, ..., b_l)$.

Les opérateurs de face sont établis comme décrit pour l'opération de produit cartésien des ensembles semi-simploïdaux. Les opérateurs de dégénérescence sont établis selon la propriété suivante : $\sigma s_j^i = \sigma^1 s_j^i \times \sigma^2$ pour $0 \le i \le k$, $\sigma s_j^{i+k} = \sigma \times \sigma^2 s_j^i$ pour $0 \le i \le l$.

Attention, les simploïdes $\tau^1 = \sigma^1 s_{-1}^k \times \sigma^2$ et $\tau^2 = \sigma^1 \times \sigma^2 s_{-1}^0$ correspondent à un même simploïde ; on a donc $\tau^1 = \tau^2$.

#### Identification

Comme pour les ensembles semi-simploïdaux, deux simploïdes $\sigma$ et $\mu$ peuvent être identifiés s'ils ont même type et même bord. De manière analogue à ce qui a été décrit pour les ensembles simpliciaux, l'identification de $\sigma$ et $\mu$ induit les identifications de leurs simplexes dégénérés.

D'un point de vue théorique, il n'est pas nécessaire de définir une opération de **dégénérescence** ; pour dégénérer un simploïde $\mu$ sur une de ses faces $\sigma$, il suffit de l'identifier avec un simploïde $\sigma s_j^i$ de même type, ayant même bord que $\mu$. En pratique, si $\sigma s_j^i$ n'est pas explicité, il suffit de l'expliciter en indiquant que $\sigma s_j^i = \mu$.

Notons que si $\mu$ est un simploïde principal, alors il peut simplement être supprimé car après dégénérescence, il ne sera pas une face d'un simplexe non dégénéré.

#### Cône simploïdal

Nous avons défini l'opération de **cône simploïdal** à partir d'un ensemble simploïdal $S$ et un nouveau sommet $v$, comme une composition de deux opérations :

1. produit cartésien de $S$ par une arête $(v', v)$, ou extrusion,

2. dégénérescence de $S' = S \times v$ en $v$.

L'opération de dégénérescence d'un ensemble simploïdal $S'$ en un sommet consiste à identifier tous ses sommets en un seul, puis toutes ses arêtes en une seule arête dégénérée, et à répéter ce processus sur tous les simploïdes de dimension supérieure. Au final, l'ensemble simploïdal résultant ne contient qu'un seul sommet, et un simploïde dégénéré de chaque type contenu dans $S$. Par exemple, la figure 2.47 illustre l'opération de cône correspondant à la figure 2.46, la 3-cellule correspondant à une pyramide à base carrée
est en fait un cube dont une face entière est dégénérée.

En pratique, cette opération peut être simplifiée en créant directement $S'$ dégénéré en un point : un simploïde de chaque type contenu dans $S$ est créé, tous ses opérateurs de face et de dégénérescence sont définis en fonction de leurs types.

<figure><img src="image_55.png" /><figcaption>FIGURE 2.47 – Représentation géométrique de l'opération de cône correspond à la figure 2.46. (a) L'opération de cône effectuée sur un carré (et son bord) a pour résultat une pyramide à base carrée (d). L'opération de cône consiste en une extrusion (a) – (b) suivie de la dégénérescence (c) de la copie du carré original (représenté en orange).</figcaption></figure>

Notons enfin que dans le cas particulier où tous les simploïdes d'un ensemble semi-simploïdal sont de longueur 1, c'est à dire qu'ils correspondent tous à des simplexes, alors l'opération de cône simplicial peut également être effectuée.

### 2.5.2.3 Lien avec les supercomplexes

Les **supercomplexes** ont été définis en 1957 par [Gugenheim 1957]. En se basant sur notre définition des ensembles simploïdaux, la structure des supercomplexes peut se définir de la manière suivante :

**Définition 26** *Un supercomplexe $S = (K, (d_j^i), (s_j^i))$ est un ensemble de simploïdes absunts, muni d'un opérateur de type $\mathcal{T}: K \mapsto \bigcup_{i \ge 1} \mathbb{N}^i$, d'opérateurs de face $d_j^i$ et d'opérateurs de dégénérescence $s_l^k$.*

*Soit $\sigma\mathcal{T} = (a_1, \dots, a_n) : \sigma d_j^i$ (resp. $\sigma s_l^k$) est défini si $1 \le i \le n, a_i > 0, 0 \le j \le a_i$ (resp. $1 \le k \le n$ et $0 \le l \le a_k$). Les opérateurs vérifient les conditions suivantes :*

$$ 
\begin{aligned}
- \sigma d_j^i \mathcal{T} &= (a_1, \dots, a_i - 1, \dots, a_n), \\
\sigma s_j^i \mathcal{T} &= (a_1, \dots, a_i + 1, a_{i+1}, \dots, a_n);
\end{aligned}
$$

- les opérateurs de face et de dégénérescence ayant le même exposant satisfont les propriétés de commutation des opérateurs de face et de dégénérescence des ensembles simpliciaux;

- les opérateurs de face et de dégénérescence n'ayant pas le même exposant commutent.

□
On peut montrer que notre définition est équivalente à celle des supercomplexes [Peltier 2018]. Si la définition des supercomplexes est clairement plus compacte que la notre, elle est moins adaptée à une implantation directe car il faut gérer la relation d'équivalence entre les types car dans un supercomplexe, le type d'un simploïde peut contenir un nombre quelconque de valeurs nulles.

## 2.6 Conclusion

Dans ce chapitre, nous avons présenté une classification mettant en avant différentes structures combinatoires, toutes basées sur les ensembles semi-simpliciaux : les structures simpliciales, simploïdales, et cellulaires. Nous avons mis en évidence trois mécanismes permettant de faire des ponts entre ces structures :

- le produit cartésien permettant de structurer des produits de simplexes en simploïdes,

- la numérotation cellulaire permettant de définir la notion de cellule, qui peut être créée par l'opération de cône,

- la suppression de la multi-incidence, qui permet d'utiliser un formalisme dans lequel le simplexe abstrait n'est plus l'élément de base de la représentation.

Afin de présenter une classification complète, nous avons défini la notion de celluloïde correspondant au produit cartésien de cellules. Trois nouvelles structures ont été présentées :

- les complexes simploïdaux abstraits, qui étendent la notion de complexe simplicial abstrait,

- les graphes d'incidence simploïdaux, qui intègrent le mécanisme de suppression de la multi-incidence,

- les cartes simploïdales, qui intègrent dans leur définition des contraintes portant sur les cellules : ce sont des quasi-variétés.

Le mécanisme de dégénérescence a également été présenté pour les structures simpliciales et simploïdales. Les opérateurs de dégénérescence des ensembles simpliciaux permettent de définir l'opération de produit cartésien, qui peut être traduite pour les ensembles semi-simpliciaux.

Les opérateurs de dégénérescence des ensembles simploïdaux permettent de définir l'opération de cône simploïdal ; cette opération ne peut pas être définie pour les ensembles semi-simploïdaux.

La définition de nouvelles structures cellulaires intégrant des opérateurs de dégénérescence ne nous semble pas pertinente. En effet, les structures cellulaires permettent déjà de manipuler des cellules quelconques : le fait de pouvoir dégénérer une cellule ne semble pas permettre d'obtenir de nouvelles structures de cellules que l'on ne puisse déjà obtenir. De plus les opérations de construction de base (cône cellulaire, produit cartésien, identification) sont déjà définies pour ces structures.
# Calculs de groupes d'homologie

## Sommaire

<table><tbody><tr><td><strong>3.1 Notions de base</strong></td><td><strong>66</strong></td></tr><tr><td>3.1.1 CW-complexes – Complexe de chaînes</td><td>66</td></tr><tr><td>3.1.2 Cycles, bords, homologie</td><td>67</td></tr><tr><td><strong>3.2 Calcul global</strong></td><td><strong>68</strong></td></tr><tr><td>3.2.1 Matrices d'incidence – Forme normale de SMITH</td><td>69</td></tr><tr><td>3.2.2 Calcul des générateurs – forme normale de SMITH-AGOSTON</td><td>70</td></tr><tr><td>3.2.3 Gestion des dégénérés</td><td>71</td></tr><tr><td>3.2.4 Calcul sur les ensembles simploïdaux</td><td>72</td></tr><tr><td>3.2.5 Calcul sur les structures cellulaires</td><td>72</td></tr><tr><td>3.2.6 Liens avec la caractéristique d'EULER-POINCARÉ</td><td>76</td></tr><tr><td><strong>3.3 Calcul incrémental</strong></td><td><strong>77</strong></td></tr><tr><td>3.3.1 Calcul incrémental des nombres de BETTI</td><td>77</td></tr><tr><td>3.3.2 Homologie persistante</td><td>77</td></tr><tr><td>3.3.3 Homologie effective</td><td>81</td></tr><tr><td>3.3.4 Calcul incrémental sur des structures simploïdales</td><td>92</td></tr><tr><td>3.3.5 Calcul incrémental sur des quasi-variétés cellulaires</td><td>96</td></tr><tr><td><strong>3.4 Conclusion</strong></td><td><strong>100</strong></td></tr></tbody></table>

Dans le chapitre 2, différentes structures combinatoires ont été présentées, permettant de construire et manipuler des objets subdivisés. On peut les distinguer selon le type de cellules utilisées et selon les contraintes sur les assemblages. Des liens entre ces différentes structures ont été mis en avant.

Quelle que soit la structure utilisée, il est important de savoir caractériser topologiquement l'objet que l'on considère. Par exemple, plusieurs subdivisions du tore ont été présentées, certaines simpliciales, d'autres cellulaires. Mais dans tous les cas, l'espace topologique associé est un tore. Réciproquement, si on se donne une subdivision, *est-on capable de caractériser à homéomorphisme près l'objet que l'on manipule* ? De manière générale, la réponse est *non*.

Comme mentionné en introduction, on s'intéresse ici au calcul des groupes d'homologie, qui peuvent être définis de manière informelle comme l'étude de l'attachement des cellules le long de leur bord. Ils caractérisent les trous d'un objet subdivisé en chaque dimension.

Nous commençons par rappeler les notions de bases algébriques liées à l'homologie. Nous rappelons ensuite les méthodes de calcul globales pour les structures régulières, *i. e.*
basées sur l'étude de l'attachement de toutes les cellules, et donnons le cadre permettant d'appliquer ces méthodes pour les structures cellulaires.

Enfin, nous présentons des méthodes incrémentales permettant de calculer l'homologie d'un objet résultant d'une opération de construction. Le calcul incrémental de l'homologie de structures simpliciales, simploïdales et cellulaires est présenté sous le prisme des opérations de base présentées au chapitre 2 : l'identification, le cône, le produit cartésien et la dégénérescence.

## 3.1 Notions de base

### 3.1.1 CW-complexes – Complexe de chaînes

L'homologie permet en particulier d'étudier les espaces topologiques CW-complexes. Afin de pouvoir effectuer des calculs, un CW-complexe $C$ de dimension $n$ est étudié sur une structure algébrique : un **complexe de chaînes**. Pour tout $k \in [0, n]$, on associe l'ensemble des boules $B^k$ de $C$ à un groupe abélien $(C_k, +)$. Les recollements des boules $B^k$ du CW-complexes sur son $(k-1)$ squelette sont décrits dans le complexe de chaînes par des applications de bord $\partial_k : C_k \to C_{k-1}$.

Un CW-complexe est dit **régulier** si les fonctions d'attachement sont des homéomorphismes. Cela implique en particulier qu'il n'y a pas de multi-incidence, ni de repliements de cellules. Par exemple, la réalisation géométrique d'un complexe simplicial abstrait est un CW-complexe régulier : cf. chapitre 4. En revanche, le CW-complexe associé à une arête incidente deux fois à un même sommet n'est pas régulier. Pour plus de précisions, voir [Munkres 1984] p.214.

Notons que dans la littérature mathématique, le terme *cellule* est synonyme de *boule topologique*. Ceci n'est pas le cas dans ce manuscrit : la notion de cellule fait bien référence aux *briques de base* de la structure combinatoire dont on parle, *i. e.* des simplexes, des simploïdes, ou des cellules au sens des ensembles semi-simpliciaux numérotés. En particulier, comme nous l'avons vu au chapitre précédent, les cellules des structures cellulaires sont des quasi-variétés, elles ne sont donc pas nécessairement homéomorphes à des boules.

Enfin, notons qu'en toute généralité, il existe des CW-complexes qui ne sont pas triangulables ; ils ne peuvent donc pas être associés à une structure simpliciale, ils sortent donc du cadre de cette étude.

**Définition 27** *Un complexe de chaînes libre* $(C, \partial)$ *est une suite :*

$$C_n \xrightarrow{\partial_n} C_{n-1} \xrightarrow{\partial_{n-1}} \dots \xrightarrow{\partial_1} C_0 \xrightarrow{\partial_0} 0.$$

où pour tout $0 \le p \le n$, $C_p$ est le **groupe abélien des p-chaînes** et les applications $\partial_p : C_p \to C_{p-1}$ sont des **homomorphismes de bord tels que pour tout $i, 1 \le i \le n$ :**

$$\partial_i \partial_{i-1} = 0.$$
Lorsqu'il n'y a pas d'ambiguïté sur la dimension *i* considérée, l'indice *i* des homomorphismes $\partial_i$ n'est pas indiqué.

Nous présentons à présent la manière d'associer un complexe de chaînes à une
structure combinatoire en se basant sur l'exemple des ensembles semi-simpliciaux; les
notions présentées s'étendent directement sur les autres structures régulières. Comme
nous le verrons, cela est moins direct pour les structures cellulaires, car les cellules ne
correspondent pas nécessairement à des boules.

Une *p*-chaîne est une somme formelle de *p*-cellules à coefficients dans un groupe donné, généralement $\mathbb{Z}$ ou $\mathbb{Z}/2\mathbb{Z}$. Le théorème des coefficients universels [Munkres 1984] garantit que toute l'information homologique est obtenue en travaillant avec des coefficients dans $\mathbb{Z}$. Sauf mention contraire, on se place dans ce cadre général. Pour des raisons d'optimisation, il peut s'avérer utile de travailler avec d'autres coefficients. En particulier, si l'homologie sur $\mathbb{Z}$ n'a pas de torsion (cf. théorème 3 page 68), alors les groupes d'homologie calculés sur $\mathbb{Z}/2\mathbb{Z}$ contiennent toute l'information homologique.

L'ensemble des *p*-chaînes muni de l'addition + forme le groupe $C_p$ des *p*-chaînes. Ce groupe est généré par l'ensemble des *p*-simplexes qui forme une base de $C_p$. Par exemple sur la figure 3.1, toute 2-chaîne s'écrit $\alpha_1 f_1 + \alpha_2 f_2$, où $\alpha_1, \alpha_2 \in \mathbb{Z}$.

Le calcul de l'homologie sur $\mathbb{Z}$ nécessite une orientation des cellules. Intuitivement, le simplexe $-\sigma$ correspond au simplexe $\sigma$ considéré avec son orientation opposée. Le **bord** d'un $p$-simplexe $\sigma$ est la $(p-1)$-chaîne définie par la somme alternée de ses faces : $\sigma\partial_p = \sum_{i=0}^{p} (-1)^i \sigma d_i$. Les homomorphismes de bord $\partial_p$ sont définis comme l'extention linéaire du bord d'un simplexe sur les chaînes. Par exemple, $(3f_1 - 2f_2)\partial = 3f_1\partial - 2f_2\partial = 3(e_1 - e_2 + e_3) - 2(e_5 - e_4 + e_2) = 3e_1 - 5e_2 + 3e_3 - 2e_5 + 2e_4$. On peut facilement vérifier que pour toute $p$-chaîne $c$, $p > 0$, on a bien $c\partial_p\partial_{p-1} = 0$. Cela provient du fait que pour tout $p$-simplexe $\sigma$, $\sigma\partial_p\partial_{p-1} = 0$.

3.1.2 Cycles, bords, homologie

Certaines *p*-chaînes ont la particularité d'avoir un bord nul. On appelle ces *p*-chaînes des *p*-cycles : *z* est un *p*-cycle si et seulement si $z\partial_p = 0$. Parmi les *p*-cycles, certains ont en plus la particularité d'être le bord d'un (*p* + 1)-chaîne, on appelle ces *p*-cycles des *p*-bords : *b* est un *p*-bord si et seulement s'il existe une (*p* + 1)-chaîne *c* tel que $c\partial_{p+1} = b$.

Le groupe des *p*-cycles est noté $Z_p$ et celui des *p*-bords, $B_p$. La propriété $\partial\partial = 0$ des homomorphismes de bord nous assure que tout *p*-bord est un *p*-cycle et le groupe $B_p$ est un sous-groupe de $Z_p$.

**Définition 28** Le *p*-groupe d'homologie d'un complexe de chaînes libre (*C*, ∂) est défini par le groupe quotient :

$$
H_p = Z_p / B_p
$$

où $Z_p = \text{Ker } \partial_p \text{ et } B_p = \text{Im } \partial_{p+1}$.
Le $p^e$ groupe d'homologie $H_p$ d'un complexe de chaînes libre est donc défini comme le groupe des $p$-cycles quotienté par le groupe des $p$-bords. Dit autrement, les éléments des groupes d'homologie sont des classes d'équivalence. Deux cycles $z_1$ et $z_2$ font partie d'une même classe d'équivalence si et seulement s'il existe un bord $b$ de $B_p$ tel que $z_1 = z_2 + b$. Les deux cycles $z_1$ et $z_2$ sont dits **homologues**.

Par exemple sur la figure 3.1, $b = e_5 + e_2 - e_4$ est un 1-bord, $z_1 = e_7 - e_5 + e_6$ et $z_2 = e_7 + e_2 - e_4 + e_6$ sont des cycles homologues car $z_2 = z_1 + b$. On peut constater qu'il entourent le même tunnel. Dans le cadre de cette étude, les objets considérés sont finis. Ainsi, pour chaque dimension $p$, le groupe $H_p$ est de type fini, c'est-à-dire que tout élément de $H_p$ peut être obtenu à partir d'un nombre fini d'éléments. Les groupes d'homologie vérifient donc le théorème des groupes abéliens de type fini [Munkres 1984].

**Théorème 3 (Théorème fondamental des groupes abéliens de type fini).**

Tout groupe abélien de type fini $G$ est isomorphe à une somme directe de groupes monogènes :

$$ \underbrace{\mathbb{Z} \oplus \dots \oplus \mathbb{Z}}_{\beta} \oplus \mathbb{Z} / t_1 \mathbb{Z} \oplus \dots \oplus \mathbb{Z} / t_k \mathbb{Z} $$

où $1 < t_i \in \mathbb{Z}$ et $t_i$ divise $t_{i+1}$. Le rang de $G$, noté $\beta$, est appelé le **nombre de BETTI de G**. Les entiers $t_i$ sont les **coefficients de torsion de G**. Le nombre de BETTI et les coefficients de torsion de G sont déterminés de manière unique par $G$.

Chaque groupe d'homologie $H_p$ est donc caractérisé par son nombre de BETTI et ses coefficients de torsion. Pour chaque dimension $p$, le $p^e$ nombre de BETTI $\beta_p$ d'un objet correspond au nombre de "trous" de dimension $p$ qu'il possède. Par exemple pour le tore, qui possède une composante connexe, deux tunnels et une cavité, ses nombres de BETTI sont : $\beta_0 = 1$, $\beta_1 = 2$ et $\beta_2 = 1$.

Les entiers $t_i$ caractérisent la partie dite de torsion : un tel élément de torsion est une classe d'équivalence regroupant des cycles qui ne sont pas des bords, mais tels que si on les considère $t_i$ fois, ce sont des bords. Par exemple, la bouteille de KLEIN contient un élément de torsion en dimension 1 : $\beta_0 = 1$, $\beta_1 = 1$ et $t_1 = 2$, $\beta_2 = 0$. Le plan projectif contient également un élément de torsion en dimension 1 : $\beta_0 = 1$, $\beta_1 = 0$ et $t_1 = 2$, $\beta_2 = 0$.

## 3.2 Calcul global

Cette section traite du calcul global des groupes d'homologie, c'est-à-dire basé sur l'analyse globale des relations d'incidence. Différents algorithmes ont été établis pour calculer les nombres de BETTI, les coefficients de torsion ou encore les générateurs des groupes d'homologie, c'est à dire un représentant de chaque classe d'équivalence engendrant le groupe. L'approche classique consiste à réduire les matrices d'incidence décrivant les homomorphismes de bord $\partial_p$ en leur forme normale de SMITH. Les notions classiques présentées dans cette partie sont détaillées en particulier dans [Cairns 1961, Agoston 1976, Munkres 1984, Kannan 1979, Peltier 2006b].
### 3.2.1 Matrices d'incidence – Forme normale de SMITH

Les matrices d'incidence décrivent les homomorphismes de bord. L'homologie peut se
calculer sur la forme normale de SMITH des matrices d'incidence.

#### 3.2.1.1 Matrices d'incidence

On peut associer à tout ensemble semi-simplicial $(K, (d_i))$ un complexe de chaînes libre $(C, \partial)$, où chaque $C_p$ est engendré par $K^p$. Chaque homomorphisme de bord $\partial_p$ peut être représenté par la matrice d'incidence $E^p$, exprimée dans les bases des $p$ et $(p-1)$-simplexes, comme représenté sur la figure 3.1.

<figure><img src="image_56.png" /><figcaption>FIGURE 3.1 – (a) Un ensemble semi-simplicial ; (b) les matrices d'incidence correspondant à (a), décrites dans les bases des simplexes.</figcaption></figure>

Notons, que l'on utilise ici une notation transposée comparé à ce que l'on trouve
usuellement dans la littérature. Comme pour la notation des opérateurs de face, cela
permet de lire les produits de matrice de gauche à droite dans le sens de lecture. Par
exemple, on pourra vérifier la propriété $\partial_p \partial_{p-1} = 0$ en effectuant le produit $E^p \cdot E^{p-1}$.

#### 3.2.1.2 Forme normale de SMITH

La forme normale de SMITH $N^p$ d'un matrice d'incidence $E^p$ décrit le même homomorphisme de bord $\partial_p$ mais dans d'autres bases des $p$-chaînes et ($p-1$)-chaînes, de manière à mettre au jour une base des $p$-cycles et une base des ($p-1$)-bords. Cette transformation est appelée **réduction** de $N^p$ en sa forme normale de SMITH.
$$
N^p = \left( \begin{array}{c|c} \begin{array}{cc} \lambda_1 & 0 \\ \vdots & \vdots \\ 0 & \lambda_k \end{array} & 0 \\ \hline 0 & 0 \end{array} \right)
$$

où tous les entiers $\lambda_i$ sont supérieurs ou égaux à 1 et $\forall i \in [0, k - 1]$, $\lambda_i$ divise $\lambda_{i+1}$.
Cette matrice est dite en forme normale de SMITH.

Le nombre de lignes nulles de chaque matrice $N^p$ donne donc le rang du groupe $Z_p$ ;
le nombre de colonnes non nulles donne le rang du groupe $B_{p-1}$. Le $p^e$ nombre de BETTI
est égal au rang de $Z_p$ moins le rang de $B_p$. Les entiers $\lambda_j > 1$ sont les coefficients de torsion.

3.2.2 Calcul des générateurs – forme normale de SMITH-AGOSTON

En mémorisant les changements de base effectués pour réduire une matrice $E^p$ en $N^p$, on obtient une description de la base de $Z_p$ en terme de chaînes de $p$-simplexes : correspondant aux lignes nulles. En faisant la même chose sur la matrice $N^{p+1}$, on obtient une base de $B_p$ : correspondant aux colonnes non nulles. Pour obtenir un ensemble minimal de générateurs du $p^e$ groupe d'homologie $H_p$, il faut donc pouvoir effectuer le quotient de ces deux groupes. Une manière simple est de s'assurer que la base des bords est un sous-ensemble de la base des cycles (aux coefficients $t_i$ près). C'est ce que permet la forme normale de SMITH-AGOSTON.

$$
N_{*}^{p} = \left( \begin{array}{c|c} 0 & 0 \\ \hline \lambda_{k} & 0 \\ \vdots & \vdots \\ 0 & \lambda_{1} \end{array} \right)
$$

Dit autrement, la forme normale de SMITH-AGOSTON $N_*^p$ d'une matrice d'incidence $E^p$ permet de s'assurer que la base des $p$-chaînes utilisée pour décrire $\partial_p$ est bien la même que celle utilisée pour décrire $\partial_{p+1}$. Plus précisément, à chaque $p$-chaîne correspondant à une ligne $i$ de $N_*^p$ correspond bien la même $p$-chaîne pour la colonne $i$ de $N_*^{p+1}$ : pour plus de détails, voir [Agoston 1976], ainsi que nos travaux de thèse [Peltier 2006a] qui décrivent les algorithmes de mise en forme normale de Smith-Agoston.
Pour le lecteur intéressé, notons que différents travaux ont pour objectif d'optimiser le processus de réduction d'une matrice en sa forme normale de SMITH [Dumas 2001, Giesbrecht 1996, Storjohann 1996]. D'autres s'attachent à réduire le nombre de cellules de l'objet subdivisé tout en préservant son homologie afin de pouvoir effectuer le calcul sur un objet plus petit [Dlotko 2010, González-Díaz 2009, Kaczynski 1998, Kaczynski 2004, Damiand 2012]. En particulier, dans [Damiand 2008], nous avons proposé un algorithme permettant de calculer de manière efficace les générateurs des groupes d'homologie sur des Gcartes de dimension 3 orientables, contenant des tunnels et des cavités. En partant d'une subdivision initiale où toutes les cellules sont des boules, la Gcarte est simplifiée, tout en préservant son homologie, jusqu'à obtenir une représentation minimale, permettant d'en déduire directement un ensemble de générateurs.

Des travaux ont été menés afin d'obtenir de "jolis" générateurs, i. e. des représentants "collant" au mieux aux tunnels, notamment pour des variétés de dimension 2 [Dey 2008]. Le calcul d'une base minimale du premier groupe d'homologie à coefficients sur $Z/2Z$ d'un complexe simplicial a été proposée dans [Dey 2018]. Le terme minimal fait référence au fait que chaque cycle de la base est de longueur minimale (chaque arête étant pondérée). Une base minimale est donc un ensemble de cycles minimaux. [Gonzalez-Lorenzo 2022] proposent une heuristique pour le calcul d'une base minimale des groupes d'homologie en toute dimension, à coefficients sur $Z/2Z$, pour des objets discrets représentés par des structures cubiques.

De manière générale, peu de travaux traitent du calcul des générateurs des groupes d'homologie. La grande majorité des travaux concerne le calcul des nombres de BETTI des groupes, généralement calculés à coefficients $Z/2Z$. Ceci répond à la grande majorité des cadres applicatifs, où les données correspondent en général à des objets de $\mathbb{R}^3$ sans torsion.

### 3.2.3 Gestion des dégénérés

On peut associer directement un complexe de chaînes libre à un ensemble simplicial ou simploïdal. Un simplexe dégénéré n'est dans ce cas simplement pas pris en compte dans le complexe de chaînes. Soit $S = (K, (d_i), (s_j))$ un ensemble simplicial, le complexe de chaînes libre associé à $S$ est construit de la manière suivante : $C_p$ est engendré par l'ensemble des $p$-simplexes non dégénérés.

Pour tout $p$-simplexe de $S$, $\sigma\partial_p = \sum_{i=0}^p r_i(-1)^i \sigma d_i$, où $r_i = 0$ si $\sigma d_i$ est dégénéré, $r_i = 1$ sinon. Cette définition vérifie bien $\partial\partial = 0$ : en particulier, le bord de tout simplexe dégénéré $\sigma = \mu s_i$ est nul. En effet, soit $\sigma$ un $p$-simplexe dégénéré, il existe donc $\mu$ tel que $\mu s_i = \sigma$. D'après la définition 23, pour tout $j < i$, on a $\mu s_i d_j = \mu d_j s_{i-1}$ et pour tout $j > i + 1$, on a $\mu s_i d_j = \mu d_{j-1} s_i$. Dit autrement, toutes les faces de $\sigma$, exceptées $\sigma d_i$ et $\sigma d_{i+1}$, sont dégénérées. Elles comptent donc pour 0 dans le bord de $\sigma$. De plus, on a $\sigma d_i = \sigma d_{i+1}$. Le bord de $\sigma$ vaut donc $\mu - \mu = 0$. On notera qu'un simplexe dégénéré $\sigma$ possède au plus un seul simplexe non dégénéré dans son bord : s'il en possède un, il s'agit de $\mu$.
La gestion des simplexes dégénérés pour le calcul des matrices d'incidence est donc direct. Les méthodes de réduction de matrices décrites dans les parties précédentes peuvent donc directement être appliquées pour des structures présentant de la dégénérescence.

### 3.2.4 Calcul sur les ensembles simploïdaux

On peut associer directement un complexe de chaînes à un ensemble semi-simploïdal en utilisant comme pour les ensembles semi-simpliciaux, l'ensemble des simploïdes de dimension $p$ comme base des $p$-chaînes. Les homomorphismes de bord $\partial_p$ sont définis en utilisant la formule générale du bord d'un produit de cellules [Hatcher 2002] :

$$ (a \times b)\partial = a\partial \times b + (-1)^{\dim(a)}a \times b\partial $$

Les homophismes de bord $\partial^\square$ des ensembles semi-simploïdaux sont définis à partir de cette formule générale, à partir des opérateurs de face [Peltier 2006a]. Soit $\sigma$ un simploïde de type $(a_1, \dots, a_p)$, son bord tient à la fois compte de l'indice des opérateurs de face, et de son type.

**Définition 29** Soit $\sigma$ un simploïde de type $(a_1, \dots, a_p)$ de dimension $n > 0$. Le bord de $\sigma$ est la $(n-1)$-chaîne :

$$ \sigma \partial^\square = \sum_{i=1}^{p} \sum_{j=0}^{a_i} (-1)^{j + \sum_{k=1}^{i-1} a_k} \sigma d_j^i $$

Si $\sigma$ est un sommet, alors son bord est nul.

Par exemple, considérons un simploïdes $\sigma$ de type $(2, 1)$ et un simploïde $\mu$ de type $(1, 2)$. On a :

$$ \sigma \partial^\square = (\sigma d_0^1 - \sigma d_1^1 + \sigma d_2^1) + (\sigma d_0^2 - \sigma d_1^2), $$

$$ \mu \partial^\square = (\mu d_0^1 - \sigma d_1^1) - (\sigma d_0^2 - \sigma d_1^2 + \sigma d_2^2). $$

Les méthodes classiques de réduction de matrices d'incidence peuvent être appliquées directement à tout ensemble semi-simploïdal. L'homologie calculée sur ce complexe de chaînes est équivalente à l'homologie calculée sur l'ensemble semi-simplicial associé [Peltier 2006a].

Les résultats présentés pour les ensembles simpliciaux et la prise en compte des dégénérés s'étend de manière directe sur les ensembles simploïdaux : les simploïdes dégénérés ne sont pas pris en compte dans le calcul du bord d'un simploïde non dégénéré.

### 3.2.5 Calcul sur les structures cellulaires

Comme indiqué en introduction de ce chapitre, l'homologie d'un CW-complexe peut être calculée à partir du complexe de chaînes qui lui est associé. Or les cellules des structures cellulaires sont des cônes sur des quasi-variétés, elles ne correspondent donc pas nécessairement à des boules. On ne peut donc pas associer directement un CW-complexe à une structure cellulaire.
Bien sûr, comme on sait associer un ensemble semi-simplicial à toute structure cellulaire, on peut donc calculer l'homologie d'un objet cellulaire à partir de cet ensemble semi-simplicial. Mais en procédant ainsi, on perd l'intérêt de la structuration cellulaire qui optimise la représentation de l'ensemble semi-simplicial (cf. figure 3.2 et Table 3.1 extraits de [Alayrangues 2015a]).

<figure><img src="image_57.png" /><figcaption>FIGURE 3.2 – Objets cellulaires. (a) Un tore à deux trous. (b) Une bouteille de KLEIN. (c) Un pignon. (d) Une tour volumique. (e) Une éponge de Menger volumique.</figcaption></figure>

<table><caption>TABLE 3.1 – Nombre de cellules des objets représentés sur la figure 3.2.</caption><thead><tr><th rowspan="2">Objet<br>dimension des cellules</th><th colspan="4">subdivision cellulaire</th><th colspan="4">Analogue simplicial</th></tr><tr><th>0</th><th>1</th><th>2</th><th>3</th><th>0</th><th>1</th><th>2</th><th>3</th></tr></thead><tbody><tr><td>2-tore</td><td>151</td><td>294</td><td>142</td><td>-</td><td>588</td><td>1.770</td><td>1.180</td><td>-</td></tr><tr><td>bouteille de KLEIN</td><td>324</td><td>648</td><td>324</td><td>-</td><td>1.296</td><td>3.888</td><td>2.592</td><td>-</td></tr><tr><td>Pignon</td><td>470</td><td>701</td><td>231</td><td>-</td><td>1.402</td><td>4.206</td><td>2.804</td><td>-</td></tr><tr><td>Tour</td><td>228</td><td>452</td><td>226</td><td>4</td><td>910</td><td>3.824</td><td>4.928</td><td>2.016</td></tr><tr><td>Éponge de Menger</td><td>64</td><td>144</td><td>96</td><td>20</td><td>324</td><td>1.576</td><td>2.208</td><td>960</td></tr></tbody></table>

Les résultats qui suivent sont issus de nos travaux [Alayrangues 2015a, Alayrangues 2011], où nous avons défini un opérateur de bord cellulaire pour les chaînes de cartes et les Gcartes. Nous avons prouvé que l'homologie définie sur une chaîne de cartes C par cet opérateur de bord est bien équivalente à l'homologie calculée sur l'analogue simplicial sous les conditions suivantes :

1. toutes les involutions de C sont sans point fixe, i. e. pour tout i, pour tout brin b, on a $b\alpha_i \neq b$: cf. figure 3.3;

2. toutes les *i*-cellules sont orientables;

3. le **bord canonique** que chaque *i*-cellule a l'homologie d'une ($i-1$)-sphère, i. e. $H_0 \simeq \mathbb{Z}$, $H_{i-1} \simeq \mathbb{Z}$ et $H_j \simeq 0$ pour tout $j \notin \{0, i-1\}$. De manière intuitive, le bord canonique d'une *i*-cellule revient à la considérer sans tenir compte des recollements sur les ($i-1$)-cellules de son bord, comme représenté sur la figure 3.4.
<figure><img src="image_58.png" /><figcaption>FIGURE 3.3 – (a) Une chaîne de cartes contenant des points fixes. (b) La représentation de la subdivision cellulaire de (a).</figcaption></figure>

### 3.2.5.1 Complexe de chaînes, nombre d'incidence, homomorphismes de bord

Comme décrit pour les structures régulières, on construit le groupe des *p*-chaînes à partir de l'ensemble des *p*-cellules.

**Définition 30** Soit $C = ((G^i)_{i=0,...,n}, (\sigma^i)_{i=1,...,n})$ une chaîne de carte. $C_* = \{C_i\}_{i=0,...,n}$ est la famille de groupes de chaînes associée à $C$, telle que chaque $C_i$ est le groupe engendré par l'ensemble des composantes connexes de $G^i$, c'est-à-dire par les $i$-cellules.

Afin d'obtenir un complexe de chaînes libre, nous définissons les homomorphismes de bord $\partial_i^{cell} : C_i \to C_{i-1}$ directement sur les cellules.

Pour cela, on définit le **nombre d'incidence** entre une $i$-cellule et une $(i-1)$-cellule. On utilise pour cela la notion de **bord canonique** d'une $i$-cellule.

Le **nombre d'incidence** est basé sur l'orientation des cellules. Une condition nécessaire pour définir ce nombre d'incidence est donc que toutes les cellules soient **orientables**.

**Définition 31** Soit $C$ une chaîne de cartes. Une $i$-cellule $c = (B, \alpha_0^i, \dots, \alpha_{i-1}^i, \alpha_i^i = \omega)$ de $C$ est orientable si et seulement si son bord canonique $(B, \alpha_0^i, \dots, \alpha_{i-1}^i)$ est orientable, i. e. si $c$ contient exactement deux orbites $< \alpha_0^i \alpha_1^i, \dots, \alpha_0^i \alpha_{i-1}^i >$.

On peut ainsi partitionner l'ensemble des brins de chaque cellule en deux parties et affecter un signe $sg(b)$ à tout brin $b$ d'une cellule, tel que $sg(b) = -sg(b\alpha_0)$.

Notons que le fait d'avoir uniquement des cellules orientables n'empêche pas que l'objet lui-même ne le soit pas. Par exemple, une bouteille de KLEIN est une surface non orientable qui peut être obtenue à partir d'une cellule orientable carrée en recollant deux à deux les arêtes de son bord canonique, comme sur la figure 3.4. Si on considère un cône cellulaire sur une bouteille de KLEIN, on obtient en revanche une 3-cellule non orientable, car son bord canonique n'est pas orientable puisque c'est une bouteille de KLEIN.
<figure><img src="image_59.png" /><figcaption>FIGURE 3.4 – Un tore, une sphère, une bouteille de KLEIN, et un anneau peuvent être construits avec une seule 2-cellule, dont le bord canonique correspond à un cycle de quatre arêtes (en rouge).</figcaption></figure>

Soit $C$ une chaîne de cartes, et soit $i \in \{1, \dots, n\}$. Soit $c^i(b^i)$ et $c^{i-1}(b^{i-1})$ deux cellules de $C$. Le **nombre d'incidence**, $(c^i(b^i) : c^{i-1}(b^{i-1})) = n_+ - n_-$, où $n_+$ (resp. $n_-$) est le nombre de préimages (relativement à $\sigma^i$) de $b^{i-1}$ dans $c^i$ ayant un signe égal (resp. différent) de celui de $b^{i-1}$. Intuitivement, le fait d'assigner le signe + ou - à l'une des deux orbites d'une cellule détermine son orientation. Ce choix n'a aucun impact sur le calcul de l'homologie. Une fois l'orientation de chaque cellule établi, le choix des brins $b^i$ et $b^{i-1}$ n'impacte pas le nombre d'incidence entre ces cellules. Ainsi, on notera plus simplement $(c^i : c^{i-1})$ le nombre d'incidence entre deux cellules. On peut à présent définir les opérateurs de bord :

**Définition 32** Soit $C = ((G^i)_{i=0,...,n}, (\sigma^i)_{i=1,...,n})$ une chaîne de cartes. Soit $C_* = \{C_i\}_{i=0,...,n}$ la famille des groupes des chaînes associé à $C$. L'opérateur de bord $\partial_i^{cell}$ est l'extension linéaire de l'opérateur de bord défini sur chaque $i$-cellule de $G^i$ par :

$$c^i \partial_i^{cell} = \sum_{c^{i-1} \in G^{i-1}} (c^i : c^{i-1}) c^{i-1}$$

La figure 3.5 illustre cette notion de préimage des opérateurs de face tenant compte de l'orientation de chaque cellule.

Nous avons prouvé dans [Alayrangues 2015a] que les opérateurs $\partial^{cell}$ sont bien des homomorphismes de bord, i. e. $\partial^{cell} \partial^{cell} = 0$, et que l'homologie définie par ce complexe de chaînes est équivalente à l'homologie calculée sur l'ensemble semi-simplicial associé. Nous avons enfin proposé des optimisations permettant de relâcher certaines contraintes lorsque l'on souhaite calculer l'homologie sur $\mathbb{Z}/2\mathbb{Z}$ et adapté la définition du nombre d'incidence aux Gcartes.
<figure><img src="image_60.png" /><figcaption>FIGURE 3.5 – (a) Une chaîne de cartes décrivant la subdivision d'un anneau. Chaque cellule est orientable, l'ensemble des brins de chaque cellule est partitionné en deux ensembles de brins (bleus et verts) correspondant à ses deux orientations. (b) Subdivision cellulaire correspondant à (a). Les flèches bleues (resp. rouges) correspondent à des opérateurs de face entre deux cellules ayant même (resp. différent) signe. (c) les matrices d'incidence décrivant les homomorphismes de bord $\partial_2^{cell}$ et $\partial_1^{cell}$.</figcaption></figure>

### 3.2.6 Liens avec la caractéristique d'EULER-POINCARÉ

Il existe un lien fort entre les groupes d'homologie et un autre invariant bien connu en topologie combinatoire : la caractéristique d'Euler-Poincaré, notée $\chi$. Cet invariant topologique, initialement défini sur les polyèdres comme la somme alternée du nombre de sommets, arêtes et faces, a été généralisé aux CW-complexes de dimension $n$ : $\chi = \sum_{i=0}^{n} (-1)^i |c_i|$, où $|c_i|$ désigne le nombre de $i$-cellules du CW-complexe.

Une autre définition de la caractéristique d'Euler-Poincaré est basée sur les nombres de BETTI : $\chi = \sum_{i=0}^{n} (-1)^i \beta_i$.

Cette définition double de la caractéristique d'Euler-Poincaré permet dans certains cas, de calculer les nombres de BETTI efficacement. C'est ce que nous avons utilisé dans le cadre du projet Région *Mimosa* afin d'effectuer la caractérisation et la correction topologique de modèles volumiques d'os trabéculaires, issus d'acquisitions tomographiques. Ce travail s'est effectué au cours du stage post-doctoral de SOUKAYNA QARBOUA. Le modèle utilisé est celui des Gcartes. Une première acquisition produit un modèle où chaque cellule volumique est un cube. Une première étape de simplifications consiste à fusionner des cellules distinctes afin de préserver des cellules correspondant à des boules [Damiand 2008].

Nous savons qu'un modèle réel d'os trabéculaire est sans torsion, composé d'une seule composante connexe, et ne présente pas de cavité. Lors de la reconstruction du modèle volumique, plusieurs composantes connexes peuvent apparaître. Pour chacune d'elles, nous pouvons calculer le nombre de trous en chaque dimension, sans passer par des réductions de matrices d'incidence :

— $\beta_0$, le nombre de composantes connexes est égal à 1,
- le nombre de cavités $β_2$ est égal au nombre de bords du volume moins un (la surface externe ne compte pas comme une cavité),

- $β_3$ est nul car les données proviennent de $\mathbb{R}^3$,

- le nombre de tunnels $β_1$ peut est déduit de l'égalité $\sum_{i=0}^{3} (-1)^i |c_i| = 1 - β_1 + β_2$.

L'étape de simplification topologique consiste à :

- supprimer les petites composantes connexes,

- supprimer les petites cavités,

- fusionner les composantes connexes restantes en créant des *ponts de matière* entre elles,

- *percer* les cavités en creusant la matière depuis chacune d'elles jusqu'au bord extérieur du volume.

## 3.3 Calcul incrémental

De nombreux travaux sont dédiés au calcul de l'homologie d'objets subdivisés. Généralement, on s'intéresse au calcul de l'homologie d'un objet donné (cf. calcul global). Le calcul incrémental de l'homologie d'un objet s'attache à effectuer le calcul étape après étape en analysant la construction de l'objet.

### 3.3.1 Calcul incrémental des nombres de BETTI

Une première approche concerne le calcul incrémental des nombres de BETTI pour des complexes simpliciaux abstraits dont la dimension maximale est 3 [Delfinado 1995]. Cette approche a l'intérêt d'être intuitive, et se base sur la notion de **filtration**, que l'on retrouve dans d'autres approches incrémentales présentées dans ce document.

Une filtration est une suite de complexes : $K^0 \subseteq K^1 \subseteq \dots \subseteq K^n = K$.

De manière informelle, une filtration peut être vue comme les différentes étapes de construction d'un complexe, obtenu par ajouts successifs de simplexes.

L'algorithme s'exprime très simplement : à chaque ajout d'un $p$-simplexe $\sigma$, soit l'ajout de $\sigma$ créé un $p$-cycle, auquel cas $β_p$ augmente de 1, soit l'ajout de $\sigma$ "bouche" un ($p-1$)-cycle, et dans ce cas, $β_{p-1}$ diminue de 1. La Table 3.2 illustre cet algorithme incrémental.

### 3.3.2 Homologie persistante

La notion de filtration est à la base de la théorie de l'homologie persistante, ou persistance homologique, qui permet de décrire l'homologie d'un objet d'un point de vue dynamique. La persistance homologique est actuellement très largement étudiée et utilisée, dans de nombreux domaines qui dépassent le cadre de la modélisation géométrique à base topologique. Par exemple en cosmologie [Pranav 2016] pour la caractérisation de la toile cosmique, en géosciences pour la détection de fractures dans des roches [Suzuki 2020], en médecine pour la caractérisation d'échantillons cancéreux [Masoomy 2021], ou encore en
<table><caption>TABLE 3.2 – Une filtration d'un complexe simplicial représentant le bord d'un tétraèdre à la dernière étape. À chaque étape le nouveau simplexe ajouté et les nombres de BETTI sont indiqués.</caption><thead><tr><th></th><th>•<sub>v<sub>0</sub></sub></th><th>•<sub>v<sub>0</sub></sub> •<sup>v<sub>1</sub></sup></th><th>•<sub>v<sub>0</sub></sub> •<sup>v<sub>1</sub></sup></th><th>•<sub>v<sub>0</sub></sub> •<sup>v<sub>1</sub></sup></th></tr></thead><tbody><tr><td>K<sub>0</sub></td><td>K<sub>1</sub></td><td>K<sub>2</sub></td><td>K<sub>3</sub></td><td>K<sub>4</sub></td></tr><tr><td>β<sub>0</sub> = 0</td><td>β<sub>0</sub> = 1</td><td>β<sub>0</sub> = 2</td><td>β<sub>0</sub> = 1</td><td>β<sub>0</sub> = 2</td></tr><tr><td>β<sub>1</sub> = 0</td><td>β<sub>1</sub> = 0</td><td>β<sub>1</sub> = 0</td><td>β<sub>1</sub> = 0</td><td>β<sub>1</sub> = 0</td></tr><tr><td>β<sub>2</sub> = 0</td><td>β<sub>2</sub> = 0</td><td>β<sub>2</sub> = 0</td><td>β<sub>2</sub> = 0</td><td>β<sub>2</sub> = 0</td></tr><tr><td>∅</td><td>v<sub>0</sub></td><td>v<sub>1</sub></td><td>v<sub>0</sub>v<sub>1</sub></td><td>v<sub>2</sub></td></tr><tr><td>K<sub>5</sub></td><td>K<sub>6</sub></td><td>K<sub>7</sub></td><td>K<sub>8</sub></td><td>K<sub>9</sub></td></tr><tr><td>β<sub>0</sub> = 1</td><td>β<sub>0</sub> = 1</td><td>β<sub>0</sub> = 2</td><td>β<sub>0</sub> = 1</td><td>β<sub>0</sub> = 1</td></tr><tr><td>β<sub>1</sub> = 0</td><td>β<sub>1</sub> = 1</td><td>β<sub>1</sub> = 1</td><td>β<sub>1</sub> = 1</td><td>β<sub>1</sub> = 0</td></tr><tr><td>β<sub>2</sub> = 0</td><td>β<sub>2</sub> = 0</td><td>β<sub>2</sub> = 0</td><td>β<sub>2</sub> = 0</td><td>β<sub>2</sub> = 0</td></tr><tr><td>v<sub>0</sub>v<sub>2</sub></td><td>v<sub>1</sub>v<sub>2</sub></td><td>v<sub>3</sub></td><td>v<sub>1</sub>v<sub>3</sub></td><td>v<sub>0</sub>v<sub>1</sub>v<sub>2</sub></td></tr><tr><td>K<sub>10</sub></td><td>K<sub>11</sub></td><td>K<sub>12</sub></td><td>K<sub>13</sub></td><td>K<sub>14</sub></td></tr><tr><td>β<sub>0</sub> = 1</td><td>β<sub>0</sub> = 1</td><td>β<sub>0</sub> = 1</td><td>β<sub>0</sub> = 1</td><td>β<sub>0</sub> = 1</td></tr><tr><td>β<sub>1</sub> = 1</td><td>β<sub>1</sub> = 2</td><td>β<sub>1</sub> = 1</td><td>β<sub>1</sub> = 0</td><td>β<sub>1</sub> = 0</td></tr><tr><td>β<sub>2</sub> = 0</td><td>β<sub>2</sub> = 0</td><td>β<sub>2</sub> = 0</td><td>β<sub>2</sub> = 0</td><td>β<sub>2</sub> = 1</td></tr><tr><td>v<sub>2</sub>v<sub>3</sub></td><td>v<sub>0</sub>v<sub>3</sub></td><td>v<sub>0</sub>v<sub>2</sub>v<sub>3</sub></td><td>v<sub>0</sub>v<sub>1</sub>v<sub>3</sub></td><td>v<sub>1</sub>v<sub>2</sub>v<sub>3</sub></td></tr></tbody></table>
biophysique pour la caractérisation de protéines [Ichinomiya 2020].

Intuitivement, l'homologie persistante permet d'avoir une vision de l'évolution des groupes d'homologie d'un objet relativement à sa filtration. Par exemple, une filtration peut être construite en utilisant des alpha-complexes [Edelsbrunner 2010], des complexes de Čech [Dantchev 2012] ou des complexes de Vietoris-Rips [Zomorodian 2010]. Pour ces structures, à partir d'un nuage de points, en considérant des boules de rayons croissants, des simplexes de dimensions supérieurs sont ajoutés au fur et à mesure que les boules grossissent et s'intersectent. La différence entre ces modèles concerne les conditions d'intersection pour créer un nouveau simplexe. Par exemple, la figure 3.6 illustre plusieurs étapes d'une filtration obtenue sur ce principe.

<figure><img src="image_61.png" /><figcaption>FIGURE 3.6 – (a) – (d) À partir d'un nuage de points, une filtration d'un complexe simplicial de dimension 2 est obtenu en considérant des intersections de disques de rayon croissant.</figcaption></figure>

Dans la théorie de l'homologie persistante, les éléments des groupes d'homologie ont une durée de vie : lorsqu'un *p*-cycle est créé à une certaine étape de la filtration, le groupe d'homologie $H_p$ est modifié. Dans la suite de la filtration, ce cycle sera éventuellement "bouché", c'est-à-dire qu'il deviendra un bord par l'ajout de ($p+1$)-simplexes. La durée de vie d'un cycle correspond au nombre d'étapes entre sa date de naissance (lorsqu'il est créé) et sa date de mort (lorsqu'il est bouché). Plus la durée de vie est grande, plus l'information topologique est significative. À l'inverse, si la durée de vie d'un cycle est courte, alors celui-ci n'est pas significatif dans l'analyse globale du nuage de points. Une des propriétés intéressantes de l'homologie persistante est qu'elle est insensible aux perturbations géométriques.

L'homologie persistante d'une filtration peut être représentée par un **diagramme de persistance**, qui permet de représenter graphiquement les durées de vie de chaque cycle : chaque cycle est représenté par un point dont l'abscisse représente la date de naissance et l'ordonnée la date de mort. Plus le point est proche de la diagonale, plus sa durée de vie est courte. Par exemple, sur la figure 3.7, (a) et (c) représentent deux nuages de points de $\mathbb{R}^2$ répartis dans un anneau. Sur les diagrammes de persistance correspondants (b) et (d), les points rouges représentent des cycles de dimension 0. Ils sont tous alignés verticalement car l'ensemble des points sont présents dès la première étape de la filtration.
Les points bleus représentent les cycles de dimension 1. Sur ces deux exemples, on peut remarquer qu'une seule composante connexe et un 1-cycle persistent (les points en haut du graphique), et caractérisent bien l'homologie de l'anneau (une composante connexe et un tunnel).

<figure><img src="image_62.png" /><figcaption>FIGURE 3.7 – Deux nuages de points répartis aléatoirement dans un anneau de $\mathbb{R}^2$ ont des diagrammes de persistance similaires. (b) Diagramme de persistance associé à l'ensemble de points (a). (d) Diagramme de persistance associé à l'ensemble de points (c). Images réalisées avec la bibliothèque Gudhi.</figcaption></figure>

En pratique, l'homologie persistante est largement utilisée pour des complexes simpliciaux abstraits, et l'homologie est calculée à coefficients dans un corps, le plus souvent $\mathbb{Z}/2\mathbb{Z}$. Des travaux récents s'attachent à calculer les coefficients de torsion [Boissonnat 2019] en utilisant plusieurs corps pour les coefficients.

Il est possible de mesurer une distance entre deux diagrammes de persistance, notamment via la notion de **bottleneck distance**. Par exemple, [Damiand 2020] propose un algorithme permettant de simplifier la filtration associée à une variété combinatoire 2D orientable représentée par une carte combinatoire, tout en garantissant la stabilité du diagramme de persistance.

L'homologie persistante a également été étendue dans le cas de **filtration zigzag**.
donnant lieu à la notion de **persistance zigzag** [Carlsson 2010, Milosavljević 2011], où entre deux complexes simpliciaux successifs de la filtration, on peut avoir $K_i \subseteq K_{i+1}$ ou bien $K_i \supseteq K_{i+1}$.

Récemment, [Dey 2022] propose d'utiliser une version simplifiée des $\Delta$-complexes<fnref n="1" /> i. e. autorisant que deux simplexes aient même bord, mais pas de multi-incidence, afin de transformer une filtration zigzag de complexes simpliciaux abstraits en une filtration classique sur les $\Delta$-complexes. L'objectif est de calculer l'homologie persistante de manière efficace. Ils font l'hypothèse qu'entre deux complexes consécutifs de la filtration, un unique simplexe est ajouté ou supprimé.

#### 3.3.3 Homologie effective

En parallèle de l'émergence de l'homologie persistante, nous avons travaillé sur la théorie de l'homologie effective et sa mise en oeuvre dans le cadre de la modélisation géométrique.

Les notions relatives à l'homologie effective utilisées dans cette partie sont basées sur le document de référence de J. RUBIO et F. SERGERAERT [Rubio 2006]. Le terme "effective" fait référence au fait que, plutôt que de prouver l'existence d'un isomorphisme par exemple, cette théorie de l'homologie s'attache à le construire. Par exemple, savoir que le groupe d'homologie $H_3(X)$ est isomorphe à $\mathbb{Z} \oplus \mathbb{Z}$ est une chose, construire l'isomorphisme en est une autre.

Nous utilisons ici les notions de **réduction**, d'équivalence homologique, et de **cône d'un morphisme**, qui permettent de mettre en oeuvre le **théorème des suites exactes courtes effectives** (théorème SECE).

Cette partie se base en particulier sur nos travaux [Alayrangues 2015b], ainsi que les travaux effectués dans le cadre de la thèse de W. RHBARBAOUI [Rharbaoui 2022, Rharbaoui 2020].

##### 3.3.3.1 Outils de base pour l'homologie effective

**Définition 33** Une réduction associe un complexe de chaînes avec un second, homologiquement équivalent, et généralement plus petit en terme de nombre de générateurs.

Une réduction $\rho = ((C^0, \partial^0), (C^1, \partial^1), h, f, g)$, notée $\rho : (C^0, \partial^0) \rightsquigarrow (C^1, \partial^1)$, est un diagramme :

$$ \rho = \text{h} \underset{\leftarrow}{\overset{g}{\rightleftharpoons}} (C^0, \partial^0) \xrightarrow{f} (C^1, \partial^1) $$

où $(C^0, \partial^0)$ et $(C^1, \partial^1)$ sont deux complexes de chaînes, $f$ et $g$ sont des morphismes de complexes de chaînes, et $h$ est un morphisme gradué de degré 1, tels que :

<footnote n="1">1. Les $\Delta$-complexes correspondent à des ensembles semi-simpliciaux géométriques.</footnote>
(a) $gf = id_{C^1}$

(b) $fg + h\partial^0 + \partial^0 h = id_{C^0}$

(c) $hf = gh = hh = 0$

Le morphisme gradué $h : C_i^0 \to C_{i+1}^0$ est aussi appelé **opérateur d'homotopie**.

**Notes :**

- $f$ est un morphisme de complexe de chaînes : $\forall c_i \in C_i^0, c_i \partial_i^0 f = c_i f \partial_i^1$

- $g$ est un morphisme de complexe de chaînes : $\forall c_i \in C_i^1, c_i \partial_i^1 g = c_i g \partial_i^0$

- $h$ est un morphisme gradué de degré 1 : $\forall c_i \in C_i^0, c_i h \in C_{i+1}^0$

**Propriété 2** Si une réduction existe entre deux complexes de chaînes ($C^0, \partial^0$) et ($C^1, \partial^1$), alors leurs groupes d'homologie sont isomorphes.

La figure 3.8, représente la réduction suivante :

- $f : C^0 \to C^1$

$$v_0 f = v_1 f = v_2 f = v_0; v_3 f = v_4 f = v_5 f = v_3$$

$$e_0 f = e_1 f = e_2 f = e_3 f = 0; e_4 f = e_4; e_5 f = -e_4; e_6 f = e_6$$

$$f_0 f = 0$$

- $g : C^1 \to C^0$

$$v_0 g = v_0; v_3 g = v_3$$

$$e_4 g = e_4; e_6 g = e_6 + e_3 + e_2 - e_1 - e_0$$

- $h : C^0 \to C^0$

$$v_0 h = v_3 h = 0; v_1 h = -e_0; v_2 h = -e_1 - e_0; v_4 h = -e_2; v_5 h = -e_3 - e_2$$

$$e_0 h = e_1 h = e_2 h = e_3 h = e_4 h = 0; e_5 h = -f_0; e_6 h = 0$$

<figure><img src="image_63.png" /><figcaption>FIGURE 3.8 – Représentation d'une réduction entre deux complexes de chaînes. Leurs groupes d'homologie sont isomorphes : $H_0 \simeq \mathbb{Z}$ et $H_1 \simeq \mathbb{Z}$. Les flèches représentent l'orientation positive des cellules.</figcaption></figure>

On peut noter qu'il existe une réduction triviale entre deux complexes de chaînes identiques où $f$ et $g$ sont des morphismes identité, et $h$ est le morphisme gradué nul.

Deux complexes de chaînes peuvent être homologiquement équivalents sans qu'une réduction puisse directement être définie entre les deux. L'association se fait via un
troisième complexe, plus "gros" en terme de nombre de générateurs, tel qu'une réduction existe entre ce complexe et chacun des deux autres.

**Définition 34** Soient trois complexes de chaînes $(C, \partial)$, $(C^S, \partial^S)$ et $(C^B, \partial^B)$. Une équivalence homologique $\Upsilon$ est une paire de deux réductions $\rho$ et $\rho^S$ telle que :

$$ \Upsilon : (C, \partial) \stackrel{\rho}{\rightleftharpoons} (C^B, \partial^B) \stackrel{\rho^S}{\Longrightarrow} (C^S, \partial^S) $$

En pratique, on utilise les équivalences homologiques afin d'associer un "petit" complexe de chaînes $(C^S, \partial^S)$ à un autre complexe $(C, \partial)$ en passant par un "gros" complexe $(C^B, \partial^B)$. La propriété 2 sous assure que ces trois complexes de chaînes ont des groupes d'homologie isomorphes. L'objectif est donc d'utiliser le petit $(C^S, \partial^S)$, qui contient généralement moins de générateurs que $(C, \partial)$, pour calculer l'homologie de l'objet manipulé. Par exemple, la figure 3.9 représente une équivalence homologique pour laquelle il n'existe pas de réduction entre les complexes $(C, \partial)$ et $(C^S, \partial^S)$.

<figure><img src="image_64.png" /><figcaption>FIGURE 3.9 – Représentation d'une équivalence homologique. Les trois complexes de chaînes ont des groupes d'homologie isomorphes. Il n'existe pas de réduction entre les deux complexes de chaînes $(C, \partial)$ et $(C^S, \partial^S)$.</figcaption></figure>

Le cône d'un morphisme permet de représenter un morphisme sous la forme d'un complexe de chaînes.

**Définition 35** Le cône d'un morphisme de complexe de chaînes $\phi : (C^0, \partial^0) \to (C^1, \partial^1)$, noté $\text{Cone}(\phi)$, est le complexe de chaînes $(C^\phi, \partial^\phi)$ défini de la manière suivante :

$$ \forall i, C_i^\phi = C_{i-1}^0 \oplus C_i^1 \text{ et } \partial_i^\phi = \begin{pmatrix} -\partial_{i-1}^0 & \phi_{i-1} \\ 0 & \partial_i^1 \end{pmatrix} $$

$C_i^\phi$ est donc défini comme la somme directe de $C_{i-1}^0$ et de $C_i^1$, pour tout $i$. Toute $i$-chaîne $c_i = c_{i-1}^0 + c_i^1$ de $C_i^\phi$ est notée $c_i = (c_{i-1}^0 \ c_i^1)$, où $c_{i-1}^0 \in C_{i-1}^0$ et $c_i^1 \in C_i^1$, et

$$ c_i \partial_i^\phi = (c_{i-1}^0 \ c_i^1) \begin{pmatrix} -\partial_{i-1}^0 & \phi_{i-1} \\ 0 & \partial_i^1 \end{pmatrix} = (-c_{i-1}^0 \ \partial_{i-1}^0 \ c_{i-1}^0 \phi_{i-1} + c_i^1 \partial_i^1) $$

### 3.3.3.2 Théorème des suites exactes courtes effectives

**Définition 36** Une suite exacte courte effective est un diagramme :
$$0 \xrightarrow{\partial^0} (C^0, \partial^0) \xrightarrow{r} (C^1, \partial^1) \xrightarrow{s} (C^2, \partial^2) \xrightarrow{\partial^0} 0$$

où

- $(C^0, \partial^0)$, $(C^1, \partial^1)$, $(C^2, \partial^2)$ sont des complexes de chaînes,

- $i, j$ sont des morphismes de complexes de chaînes,

- $r, s$ sont des morphismes gradués

qui vérifient :

1. $ir = id_{C^0}$

2. $ri + js = id_{C^1}$

3. $sj = id_{C^2}$

On notera que seuls $i$ et $j$ sont des morphismes de complexe de chaînes, c'est-à-dire que la notion de bord est préservée. Les morphismes $r$ et $s$ préservent uniquement la notion de chaîne.

<figure><img src="image_65.png" /><figcaption>FIGURE 3.10 – Représentation d'une suite exacte courte effective impliquant trois complexes de chaînes.</figcaption></figure>

L'exemple de la figure 3.10 illustre une suite exacte courte, dont les morphismes sont définis de la manière suivante :

— $i : C^0 \to C^1$

$$v_3 i = v_1 - v_3; v_4 i = v_2 - v_4;$$

$$e_4 i = e_1 - e_4.$$

— $r : C^1 \to C^0$

$$v_0 r = v_1 r = v_2 r = v_5 r = 0; v_3 r = -v_3; v_4 r = -v_4;$$

$$e_0 r = e_1 r = e_2 r = e_3 r = e_5 r = 0; e_4 r = -e_4;$$

$$f_0 r = f_1 r = 0.$$

— $j : C^1 \to C^2$

$$v_0 j = v_0; v_1 j = v_3 j = v_1; v_2 j = v_4 j = v_2; v_5 j = v_5;$$

$$e_0 j = e_0; e_1 j = e_4 j = e_1; e_2 j = e_2; e_3 j = e_3; e_5 j = e_5;$$
$$f_0 j = f_0; f_1 j = f_1.$$

$$— s : C^2 \to C^1$$

$$v_0 s = v_0; v_1 s = v_1; v_2 s = v_2; v_5 s = v_5;$$

$$e_0 s = e_0; e_1 s = e_1; e_2 s = e_2; e_3 s = e_3; e_5 s = e_5;$$

$$f_0 s = f_0; f_1 s = f_1.$$

On peut remarquer que l'exemple de la figure 3.10 correspond à une opération d'identification : ($C^0$, $\partial^0$) représente la partie identifiée, ($C^1$, $\partial^1$) représente l'objet avant l'opération, et ($C^2$, $\partial^2$) représente le résultat de l'opération.

Étant donnée une suite exacte courte effective, une équivalence homologique pour ($C^0$, $\partial^0$) et une autre pour ($C^1$, $\partial^1$), le théorème 4 [Rubio 2006] permet de déduire une équivalence homologique pour ($C^2$, $\partial^2$). Dit autrement, si on sait décrire une opération de construction par une suite exacte courte effective, alors connaissant l'homologie d'un objet avant l'opération, l'homologie correspondant à la partie impactée par l'opération, alors on peut en déduire l'homologie de l'objet après l'opération.

**Théorème 4** Soit

$$0 \xrightarrow{\qquad} (C^0, \partial^0) \underset{i}{\stackrel{r}{\rightleftharpoons}} (C^1, \partial^1) \underset{j}{\stackrel{s}{\rightleftharpoons}} (C^2, \partial^2) \xrightarrow{\qquad} 0$$

une suite exacte courte effective, et deux équivalences homologiques :

$$(C^0, \partial^0) \underset{\sim}{\overset{\rho^0}{\rightleftharpoons}} (C^{B0}, \partial^{B0}) \underset{\sim}{\overset{\rho^{S0}}{\rightleftharpoons}} (C^{S0}, \partial^{S0})$$

$$(C^1, \partial^1) \underset{\sim}{\overset{\rho^1}{\rightleftharpoons}} (C^{B1}, \partial^{B1}) \underset{\sim}{\overset{\rho^{S1}}{\rightleftharpoons}} (C^{S1}, \partial^{S1})$$

Il est possible de construire une équivalence homologique :

$$(C^2, \partial^2) \underset{\sim}{\overset{\rho^2}{\rightleftharpoons}} (C^{B2}, \partial^{B2}) \underset{\sim}{\overset{\rho^{S2}}{\rightleftharpoons}} (C^{S2}, \partial^{S2})$$

$$où i^B = f^0 i g^1, i^S = g^{S0} i^B f^{S1}, (C^{B2}, \partial^{B2}) = \text{Cone}(i^B) \text{ et } (C^{S2}, \partial^{S2}) = \text{Cone}(i^S).$$

Il s'agit ici uniquement de la partie du théorème utilisée dans la suite. Le théorème complet permet également de calculer notamment ($C^1$, $\partial^1$) à partir d'une suite exacte courte effectives et deux équivalences homologiques liées à ($C^0$, $\partial^0$) et ($C^2$, $\partial^2$). Cette seconde partie du théorème est notamment utilisée pour calculer l'homologie d'un objet après application d'une opération correspondant à l'inverse d'une opération d'identification [Rharbaoui 2022]. La figure 3.11 illustre le principe du théorème SECE.

#### 3.3.3.3 Application du théorème SECE à l'opération d'identification

Nous avons utilisé l'homologie effective dans un contexte du suivi de l'homologie d'un objet au cours d'un processus de construction, comme illustré en figure 3.12.