<figure><img src="image_66.png" /><figcaption>FIGURE 3.11 – Illustration du théorème 4 : étant donnée une suite exacte courte (en haut), et deux équivalences homologiques (à gauche et au centre), on peut déduire la troisième équivalence homologique (à droite en mauve).</figcaption></figure>

<figure><img src="image_67.png" /><figcaption>FIGURE 3.12 – Processus de construction d'un objet. Chaque étape de construction est obtenue à partir de la précédente en appliquant une opération d'identification [Rharbaoui 2022].</figcaption></figure>

D'un point de vue théorique, nous avons montré comment utiliser le théorème 4 pour calculer l'homologie d'un objet résultant d'une opération d'identification [Rharbaoui 2020].

Pour cela, nous avons montré comment :

- associer une suite exacte courte à toute opération d'identification,

- associer une équivalence homologique à un objet initial,

- associer une équivalence homologique à la partie de l'objet concernée par l'identification.

Le principe, expliqué ici pour les ensembles semi-simpliciaux est le suivant : pour chaque dimension *k*, on partitionne l'ensemble des *k*-simplexes de ($C^1, \partial^1$) selon les identifications à réaliser. On note $I_k = (I_{k,q})$ la partition des *k*-simplexes, où chaque ensemble $I_{k,q}$ contient tous les simplexes correspondant à un simplexe résultant de l'opération d'identifi-
cation. L'ensemble des partitions doit respecter la contrainte suivante : si deux $k$-simplexes $\sigma_q^x$ et $\sigma_q^y$ appartiennent au même ensemble $I_{k,q}$, alors pour tout $i \in [0, k]$, $\sigma_q^x d_i$ et $\sigma_q^y d_i$ appartiennent à un même ensemble de $I_{k-1}$. Ceci qui correspond au fait que deux simplexes peuvent être identifiés seulement si leur bord est identifié.

Soit $I_{k,q} = \{\sigma_q^0, \dots, \sigma_q^p\}$ un élément de $I_k$. Après identification, par convention, tous les simplexes sont remplacés par $\sigma_q^0$. Si $I_{k,q}$ ne contient qu'un seul élément, alors ce simplexe n'est pas impacté par l'opération d'identification. Le simplexe $\sigma_q^0$ est un **simplexe survivant**, les autres simplexes de $I_{k,q}$ sont des **simplexes supprimés**.

La suite exacte courte associée à une identification est définie de la manière suivante :

$$— \forall \sigma_q^x \in C^1, \sigma_q^x j = \sigma_q^0,$$

$$— \forall \sigma_q^0 \in C^2, \sigma_q^0 s = \sigma_q^0,$$

— les générateurs de $C^0$ sont les cellules supprimées,

$$— \forall \sigma_q^x \in C^0, \sigma_q^x i = \sigma_q^0 - \sigma_q^x,$$

$$— \forall \sigma_q^x \in C^1, \sigma_q^0 r = 0, \sigma_q^x r = -\sigma_q^x \text{ si } x > 0,$$

$$— \partial^0 = i \partial^1 r.$$

En pratique, lorsqu'une opération d'identification est effectuée, il est possible de simplifier l'équivalence homologique de l'objet résultant à deux moments (cf. figure 3.13) :

— lorsque l'équivalence homologique de la partie identifiée est calculée, en simplifiant $(C^{S0}, \partial^{S0})$, ce qui, par définition, aura pour effet de simplifier $(C^{S2}, \partial^{S2})$. Pour cela il est nécessaire d'identifier dans une même étape des simplexes et des simplexes de leurs bords. Ces simplifications ne sont pas exemple pas possibles si toutes les identifications sont effectuées par dimensions croissantes.

— une fois que l'équivalence homologique liée à l'objet résultant est calculée, il est possible de simplifier $(C^{S2}, \partial^{S2})$.

Bien entendu, ces simplifications induisent des calculs supplémentaires; il est donc important de pouvoir mesurer l'impact de ces simplifications sur l'ensemble des calculs effectuées lors des étapes suivantes.

Les résultats présentés sur le calcul incrémental de l'homologie d'un objet au cours de sa construction s'étendent directement à toute structure pour laquelle on sait définir un opérateur de bord permettant de construire un complexe de chaînes. Ils s'étendent donc directement aux structures cubiques et simploïdales. Pour les structures cellulaires il faut bien entendu respecter les contraintes définies pour la définition d'un opérateur de bord.

La figure 3.14 illustre une application du théorème 4 sur un exemple d'identification. La suite exacte courte effective est celle décrite pour la figure 3.10. On peut remarquer que le "gros" complexe de l'équivalence homologique de l'objet manipulé est identique au complexe associé à l'objet manipulé. Il s'agit de l'initialisation du processus de construction. Si on souhaite effectuer d'autres identifications ensuite, on part de l'équivalence homologique que l'on vient d'obtenir (à droite) : le "gros" complexe contient effectivement plus de générateurs que l'objet manipulé. À chaque identification, la taille du "gros" complexe croît proportionnellement à la partie identifiée. Intuitivement, le "gros" complexe mémorise la réduction initiale ainsi que l'ensemble des opérations effectuées depuis la première étape.

Le cas de la désidentification a également été traité dans [Rharbaoui 2022]. Une dési-
<figure><img src="image_68.png" /><figcaption>FIGURE 3.13 – Deux types de simplifications permettant de réduire la taille du "petit" complexe associé à l'objet résultant de l'opération d'identification. Dans cet exemple, deux arêtes et leurs bords sont identifiées lors d'une étape, une simplification peut être effectuée lors du calcul de ($C^{S0}$, $\partial^{S0}$), et une autre après le calcul de ($C^{S2}$, $\partial^{S2}$).</figcaption></figure>

dentification peut être vue comme le processus inverse d'une identification et entre également dans le cadre de l'homologie effective. Nous ne donnons pas le détail dans ce manuscrit, l'approche est similaire, seuls des aspects techniques changent. Les définitions de tous les morphismes ne sont pas rappelés ici; le lecteur intéressé pourra les trouver dans [Alayrangues 2015b].

D'un point de vue pratique, il est important de noter que tous les morphismes mis en jeu dans la nouvelle équivalence homologique (représentés en mauve sur la figure 3.14) sont définis sous forme matricielle.

Considérons par exemple la définition de $\partial^{B2}$. D'après la définition 35 et le théorème 4, on a : $\partial_i^{B2} = \begin{pmatrix} -\partial_{i-1}^{B0} & f^0 ig^1 \\ 0 & \partial_i^{B1} \end{pmatrix}$

La définition de l'homomorphisme de bord $\partial^{B2}$ nécessite donc :

- de composer les morpshismes $f^0, i$ et $g^1$, ce qui se traduit en pratique par les multiplications des matrices correspondantes.

- d'effectuer des sommes directes de (composition de) morphismes, ce qui se traduit en pratique par la fusion des matrices correspondant à $-\partial_{i-1}^B, f^0ig^1$ et $\partial^{B1}$ et une matrice nulle.

Dans les travaux de thèse de W. RHARBAOUI, une implantation de matrices creuses spécifiquement dédiée au calcul de l'homologie effective est proposée. Elle permet d'optimiser le calcul des différents morphismes.

En particulier, la structure de donnée proposée permet de fusionner 4 matrices par modification d'une des matrices. Dans l'exemple $\partial^{B2}$, il est essentiel de ne pas avoir à parcourir la matrice $\partial_i^{B1}$ dont la taille est liée à celle de l'objet ainsi que du nombre total
<figure><img src="image_69.png" /><figcaption>FIGURE 3.14 – Illustration du théorème SECE, appliqué à une opération d'identification. À gauche, l'équivalence homologique relative à la partie identifiée, au centre l'équivalence homologique relative à l'objet avant identification, à droite l'équivalence homologique du résultat de l'opération d'identification, est déduite du théorème SECE.</figcaption></figure>

de cellules qui ont été supprimées lors des identifications passées.

On peut également remarquer que certaines matrices ne diffèrent que très peu de
la matrice identité. Par exemple, le morphisme $j$ est différent de l'identité uniquement
pour les seules cellules supprimées. L'implantation proposée permet de manipuler impli-
citement la matrice identité et d'expliciter uniquement les modifications de telles ma-
trices. D'autres types d'optimisation sont prises en compte dans l'implémentation propo-
sée, comme l'aspect *creux* des matrices. Le détail complet de la structure est disponible
dans [Rharbaoui 2022]. En particulier, nous avons montré et observé expérimentalement
que :

- lorsque l'information homologique calculée sur le "petit" complexe n'a pas besoin d'être reportée sur l'objet manipulé, alors la complexité du calcul à chaque étape ne dépend que de la partie identifiée à l'étape correspondante,

- lorsque l'information homologique est reportée sur l'objet manipulé : un ensemble de générateurs est calculé, la complexité croît au fur et à mesure des identifications.
<figure><img src="image_70.png" /><figcaption>FIGURE 3.15 – Exemple d'une matrice obtenue par fusion de 4 matrices. En rouge, la partie modifiée. Les maillons en noir ne sont pas parcourus [Rharbaoui 2022].</figcaption></figure>

À chaque étape, la complexité des calculs dépend de la complexité de la réduction initiale et du nombre total des cellules impactées par l'identification de l'étape courante ainsi que de toutes les étapes précédentes.

### 3.3.3.4 Liens avec d'autres méthodes

#### Suites de MAYER-VIETORIS

Il existe des liens évidents avec les suites de MAYER-VIETORIS : [Boltcheva 2010] montrent que les résultats sur les suites de MAYER-VIETORIS entrent dans le cadre de l'homologie effective. De manière intuitive, si $A$ et $B$ sont deux complexes simpliciaux, une telle suite met en relation les groupes d'homologie de $A \cap B$ (partie identifiée), $A \oplus B$ (objet avant application de l'opération d'identification), et $A \cup B$ (résultat de l'identification). L'exemple présenté sur la figure 3.10 correspond à un tel cas, mais en toute généralité, les suites de MAYER-VIETORIS correspondent à des cas particuliers d'identification, où la partie identifiée correspond à l'intersection de deux complexes simpliciaux. Par exemple
l'identification représentée sur la figure 3.16 ne peut pas être décrite ainsi.

<figure><img src="image_71.png" /><figcaption>FIGURE 3.16 – Représentation d'une suite exacte courte effective correspondant à une opération d'identification ne pouvant pas être décrite par une suite de MAYER-VIETORIS.</figcaption></figure>

Homologie persistante de tours

Nous avons mis en évidence des liens avec l'homologie persistante, en particulier l'homologie persistante de tours [Dey 2014, Kerber 2019], dans laquelle la notion de filtration est étendue : les complexes simpliciaux abstraits ne sont plus reliés uniquement par des inclusions mais, plus généralement, par des applications simpliciales. Il est montré en particulier qu'une application simpliciale se décompose en :

— *inclusions élémentaires*, qui correspondent des ajouts de simplexes,

— *effondrements élémentaires*, qui correspondent à l'identification de deux sommets, entraînant éventuellement l'identification ou la dégénérescence de simplexes de dimensions supérieures.

Une tour est donc définie par une suite de complexes $K_0 \xrightarrow{\phi_0} K_1 \xrightarrow{\phi_1} \dots \xrightarrow{\phi_{n-1}} K_n$, où chaque $\phi_j$ est soit une inclusion élémentaire, soit un effondrement élémentaire.

On sait associer un ensemble simplicial à tout complexe simplicial abstrait via un mécanisme de numérotation [Damiand 2014]. Nous avons montré l'on peut traduire chaque opération élémentaire d'un complexe simplicial abstrait dans l'ensemble simplicial correspondant :

— l'inclusion élémentaire dans $K$ correspond dans $S$ à ajouter d'un $p$-simplexe et son bord, et à identifier son bord avec des simplexes de $S$. Notons que l'équivalence homologique correspondant à l'ajout d'un simplexe et son bord dans $S$ est simplement la somme directe de l'équivalence homologique associée à $S$ et de celle associée au simplexe et son bord (qui se réduit sur un sommet),

— un effondrement élémentaire dans $K$ correspond dans $S$ à des opérations d'identification et de dégénérescence : cf. figure 3.17.

Nous avons montré que l'opération de dégénérescence peut être décrite par une suite exacte courte effective, le Théorème SECE peut donc être appliqué : cf. figure 3.18. Les détails des fonctions ne sont pas données ici, ils sont disponibles dans [Rharbaoui 2022].

Au final, toutes les opérations utilisées pour définir l'homologie persistante de tours entrent dans le cadre de l'homologie effective.
<figure><img src="image_72.png" /><figcaption>FIGURE 3.17 – L’effondrement élémentaire sur un complexe simplicial abstrait se traduit pas des identifications et des dégénérescences dans l’ensemble simplicial associé (en bas). (a)–(b) Une opération d’effondrement élémentaire (des deux sommets rouges) sur un complexe simplicial abstrait. (c) Un ensemble simplicial correspondant à (a), les opérateurs de dégénérescence ne sont pas représentés. (b) identifications de simplexes. (c) dégénérescences de simplexes.</figcaption></figure>

### 3.3.4 Calcul incrémental sur des structures simploïdales

L'étude de l'homologie sur les structures simploïdales nous a naturellement conduit à étudier l'opération de produit cartésien. À notre connaissance, il n'est pas possible de décrire une opération de produit cartésien sous la forme d'une suite exacte courte effective comme nous l'avons présenté pour l'opération d'identification. La question qui se pose alors est la suivante : soient $S^1$ et $S^2$ deux ensembles semi-simploïdaux ; connaissant les groupes d'homologie de $S^1$ et ceux de $S^2$, peut-on en déduire l'homologie de $S^1 \times S^2$ ?

La formule de KÜNNETH du théorème 5 nous indique que cela est bien possible sous certaines conditions, et comment effectuer le calcul.

**Théorème 5** Soient $C$ et $C'$ des complexes de chaînes, Si $R$ est un anneau principal, et les $R$-modules $C_i$ sont libres, alors pour chaque $n$, il existe une suite exacte courte

$$0 \to \bigoplus_i (H_i(C) \otimes_R H_{n-i}(C')) \to H_n(C \otimes_R C') \to \bigoplus_i \operatorname{Tor}_R(H_i(C), H_{n-i-1}(C')) \to 0$$

et cette suite scinde.

Dans notre contexte, les $R$-modules $C_i$ sont des groupes abéliens, ou $\mathbb{Z}$-modules libres, $\mathbb{Z}$ est bien un anneau principal, et la suite exacte scinde. On peut donc appliquer le Théorème 5.
<figure><img src="image_73.png" /><figcaption>FIGURE 3.18 – Représentation d'une suite exacte courte effective correspondant à une opération de dégénérescence. À partir de l'équivalence homologique correspondant à un ensemble simplicial (au centre) et l'équivalence homologique correspondant à un simplexe dégénéré (à gauche), l'équivalence homologique résultant de la dégénérescence (à droite) peut être déduite.</figcaption></figure>

L'objectif n'est pas ici d'en expliquer tous les détails, dans laquelle l'homologie de deux complexes de chaînes et l'homologie du complexe résultant de leur produit interviennent. En particulier, ce théorème met en jeu une suite exacte courte, dont la forme générale est :

$$0 \to A \to B \to C \to 0$$

En particulier, lorsque une telle suite scinde, comme c'est le cas ici, alors un résultat classique d'algèbre nous assure que le groupe $B$ est isomorphe à $A \oplus C$ [Munkres 1984]. Par exemple, sur la figure 3.10, on observe visuellement ce résultat où l'ensemble des $p$-simplexes de l'objet avant opération correspond à l'union des $p$-simplexes caractérisant l'opération (à gauche) et des $p$-simplexes de l'objet résultant. Dit autrement, le groupe des $p$-chaînes $C_p^1$ est bien isomorphe à $C_p^0 \oplus C_p^2$.

La formule de KÜNNETH nous garantit donc si l'on connaît l'homologie de deux complexes $C$ et $C'$, et si l'on sait calculer la partie $Tor$, alors on peut en déduire l'homologie de $C \otimes C'$.
L'opérateur $\otimes$ est appelé **produit tensoriel**. De manière simplifiée, soient $A$ et $B$ deux groupes abéliens de type fini; $A \otimes B$ est un groupe abélien de type fini, défini comme le groupe quotient $F(A \times B)/R(A, B)$, où $F(A \times B)$ est le groupe abélien engendré par l'ensemble des couples $(a, b)$ avec $a \in A$ et $b \in B$, et $R(A, B)$ est le sous-groupe de $F(A \times B)$ engendré par tous les éléments de la forme $(a + a', b) - (a, b) - (a', b)$ ou $(a, b + b') - (a, b) - (a, b')$. Dit autrement, les éléments de $A \otimes B$ vérifient $(a, b) + (a', b) = (a+a', b)$ et $(a, b) + (a, b') = (a, b+b')$. Notons qu'en toute rigueur, deux produits tensoriels distincts apparaissent dans la formule de KÜNNETH : un produit tensoriel de groupes et un produit tensoriel de complexes de chaînes. De manière résumée, si $(C, \partial)$ et $(C', \partial')$ sont deux complexes de chaînes, alors le produit tensoriel de ces deux complexes est un complexe de chaînes $(C^{\square}, \partial^{\square})$ défini par :

$$— C_n^{\square} = (C \otimes C')_n = \bigoplus_{p+q=n} C_p \otimes C_q,$$

$$— (c_p \otimes c'_q) \partial^{\square} = c_p \partial \otimes c'_q + (-1)^p c_p \otimes c'_q \partial'$$

Cette définition correspond à celle du complexe de chaînes associé au résultat d'un produit cartésien simploïdal. Notons que la formule est également définie directement pour les espaces topologiques. Ainsi, on notera $C \times C'$ un produit d'espaces topologiques et $C \otimes C'$ le produit tensoriel des complexes de chaînes associé. On utilisera les résultats classiques suivants sur le produit tensoriel de groupes abéliens :

$$— A \otimes B \simeq B \otimes A,$$

$$— A \otimes \mathbb{Z} \simeq A,$$

$$— \mathbb{Z}/p\mathbb{Z} \otimes \mathbb{Z}/q\mathbb{Z} \simeq \mathbb{Z}/\text{pgcd}(p, q)\mathbb{Z}.$$

L'opérateur *Tor*, aussi appelé **produit de torsion**, indique comment influe le produit tensoriel d'éléments de torsion de $A$ et $B$ dans l'homologie de $A \otimes B$. On utilisera les propriétés suivantes de l'opérateur *Tor* :

$$— \operatorname{Tor}(A, B) \simeq \operatorname{Tor}(B, A),$$

$$— \operatorname{Tor}(\mathbb{Z}, \mathbb{Z}) \simeq 0,$$

$$— \operatorname{Tor}(\mathbb{Z}, \mathbb{Z}/p\mathbb{Z}) \simeq 0,$$

$$— \operatorname{Tor}(\mathbb{Z}/p\mathbb{Z}, \mathbb{Z}/q\mathbb{Z}) \simeq \mathbb{Z}/\text{pgcd}(p, q)\mathbb{Z}.$$

En particulier, on peut remarquer que si l'homologie de $C$ ou l'homologie de $C'$ ne contient pas de torsion, alors la partie *Tor* est triviale. Dans ce cas, l'homologie du produit $C \otimes C'$ est isomorphe au produit des homologies de $C$ et $C'$. Notons que c'est toujours le cas lorsque l'on calcule l'homologie à coefficients dans $\mathbb{Z}/2\mathbb{Z}$.

Par exemple, la figure 3.19 illustre la formule dans un cas "simple" où $C$ ne contient pas de torsion. On cherche à calculer l'homologie d'un complexe de chaînes résultant du produit de deux cercles. Soit $C$ le complexe de chaînes de dimension 1 associé à un cercle. L'homologie de $C$ est $H_0(C) \simeq \mathbb{Z}$, et $H_1(C) \simeq \mathbb{Z}$. L'homologie du produit de deux cercles peut être calculée directement avec la formule de KÜNNETH : on est ici dans le cas où l'homologie de $C \times C$ est égale au produit des homologies. Comme on peut s'y attendre, on obtient bien l'homologie d'un tore :

$$— H_0(C \times C) \simeq H_0(C) \otimes H_0(C) \simeq \mathbb{Z} \otimes \mathbb{Z} \simeq \mathbb{Z}$$

$$— H_1(C \times C) \simeq H_0(C) \otimes H_1(C) \oplus H_1(C) \otimes H_0(C) \simeq \mathbb{Z} \otimes \mathbb{Z} \oplus \mathbb{Z} \otimes \mathbb{Z} \simeq \mathbb{Z} \oplus \mathbb{Z}$$

$$— H_2(C \times C) \simeq H_1(C) \otimes H_1(C) \simeq \mathbb{Z} \otimes \mathbb{Z} \simeq \mathbb{Z}$$
<figure><img src="image_74.png" /><figcaption>FIGURE 3.19 – Illustration de la formule de KÜNNETH : le tore peut être défini comme produit cartésien de deux cercles. L'homologie du tore (b) se déduit du produit des homologies des cercles (a).</figcaption></figure>

Considérons à présent le plan projectif P, dont l'homologie est $H_0(P) \simeq \mathbb{Z}$ et $H_1(P) \simeq \mathbb{Z}/2\mathbb{Z}$. La formule de KÜNNETH nous donne l'homologie du produit de deux plans projectifs :

$$
\begin{align*}
H_0(P \times P) &\simeq H_0(P) \otimes H_0(P) \\
&\simeq \mathbb{Z} \otimes \mathbb{Z} \\
&\simeq \mathbb{Z}
\end{align*}
\begin{align*}
H_1(P \times P) &\simeq H_0(P) \otimes H_1(P) \oplus H_1(C) \otimes H_0(C) \\
&\simeq \mathbb{Z} \otimes \mathbb{Z}/2\mathbb{Z} \oplus \mathbb{Z}/2\mathbb{Z} \otimes \mathbb{Z} \\
&\simeq \mathbb{Z}/2\mathbb{Z} \oplus \mathbb{Z}/2\mathbb{Z}
\end{align*}
\begin{align*}
H_2(P \times P) &\simeq H_1(P) \otimes H_1(P) \\
&\simeq \mathbb{Z}/2\mathbb{Z} \otimes \mathbb{Z}/2\mathbb{Z} = \mathbb{Z}/2\mathbb{Z}
\end{align*}
\begin{align*}
H_3(P \times P) &\simeq \operatorname{Tor}(H_1(P), H_1(P)) \\
&\simeq \operatorname{Tor}(\mathbb{Z}/2\mathbb{Z}, \mathbb{Z}/2\mathbb{Z}) \\
&\simeq \mathbb{Z}/2\mathbb{Z}
\end{align*}
$$

On peut noter qu'il y a un "saut de dimension" pour la torsion. Comme on peut
peut-être s'y attendre, dans le produit de deux plans projectifs, de la torsion apparaît
dans les groupes d'homologie de dimension 1 et 2. De manière peut être moins évidente,
de la torsion apparaît également en dimension 3, alors que les groupes d'homologie de
dimension 2 et plus du plan projectif sont triviaux.

La formule de KÜNNETH peut donc être directement utilisée pour le calcul de l'homo-
logie d'ensembles semi-simploïdaux, pour lesquels le produit cartésien est une opération
de base. Ce résultat s'étend directement aux ensembles simploïdaux, seule la définition
des homomorphismes de bord change afin de tenir compte des simploïdes dégénérés.

Si ces résultats permettent de calculer l'homologie résultant d'un produit cartésien,
ils ne sont pas adaptés pour une approche incrémentale où différentes opérations peuvent
s'enchaîner. Pour cela, il faut maintenir une équivalence homologique à chaque étape. Ce
point reste encore à étudier pour l'opération de produit cartésien.

3.3.5 Calcul incrémental sur des quasi-variétés cellulaires

Jusqu'à présent nous avons présenté deux approches globales qui peuvent être utilisées
pour calculer l'homologie de structures cellulaires :

— dans tous les cas, le calcul peut être effectué directement sur l'ensemble semi-simplicial associé, sans tenir compte de la structuration cellulaire. On perd alors l'optimisation de la représentation cellulaire,

- pour la sous-classe pour laquelle on sait définir un opérateur de bord (cf. section 3.2.5), le calcul peut être effectué en tenant compte de la structuration en cellules.

On montre dans cette partie comment les outils de l'homologie effective peuvent être
utilisés afin de définir incrémentalement l'homologie de structures cellulaires dont les cel-
lules sont des quasi-variétés cellulaires. L'idée est de tirer partie de leur définition construc-
tive, basée sur les opérations de cône cellulaire et d'identification de cellules. Les résultats
qui suivent s'appliquent directement pour le calcul incrémental de l'homologie des Gcartes
ou des chaînes de cartes. Les détails techniques et les preuves ne sont pas donnés ici, ils
sont disponibles dans [Alayrangues 2015b].

Le principe de cette approche est de maintenir une équivalence homologique :

— pour chaque composante connexe,

— pour chaque cellule.

Ainsi, lorsqu'une opération d'identification cellulaire est appliquée, les équivalences
homologiques associées aux cellules identifiées sont utilisées afin de calculer de manière
efficace l'homologie de la Gcarte ou chaîne de cartes résultante.

Pour effectuer ces calculs de manière efficace, on utilise d'autres outils de l'homologie ef-
fective : la notion de **perturbation**, ainsi que les **lemmes de perturbation** [Rubio 2006]
associés. Une perturbation d'un complexe de chaînes consiste à modifier ses homomor-
phismes de bord, les lemmes permettent de répercuter la perturbation sur une réduction
impliquant le complexe de chaînes.

**Définition 37** *Soit $(C, \partial)$ un complexe de chaînes. Soit $\delta : C \to C$ un morphisme gradué tel que $(\partial + \delta)^2 = 0$. $\delta$ est une perturbation de $\partial$.*

Par exemple, si (C, ∂) est un complexe de chaînes, comme (C, 0) est un complexe de
chaînes, ∂ est une perturbation de l'opérateur de bord nul.

Étant donnée une réduction de (C⁰, ∂⁰) dans (C¹, ∂¹), le **lemme de perturbation Easy** permet, étant donnée une perturbation de ∂¹, de répercuter cette modification sur ∂⁰ afin d'obtenir une nouvelle réduction tenant compte de la perturbation. Le **lemme de perturbation Basic** est défini similairement dans l'autre sens : il permet, à partir d'une perturbation de ∂⁰, de répercuter cette modification dans ∂¹ afin d'obtenir une nouvelle
réduction tenant compte de la perturbation. La figure 3.20 illustre les deux lemmes de perturbation.

**Propriété 3** *Lemme de perturbation Easy*

Soit $\rho = ((C^0, \partial^0), (C^1, \partial^1), h, f, g)$ une réduction, soit $\delta^1$ une perturbation de $\partial^1$, alors
$\rho^\delta = ((C^0, \partial^0 + \delta^0), (C^1, \partial^1 + \delta^1), h, f, g)$ est une réduction, où $\delta^0 = f\delta^1 g$.

**Propriété 4** *Lemme de perturbation Basic*

Soit $\rho = ((C^0, \partial^0), (C^1, \partial^1), h, f, g)$ une réduction, soit $\delta^0$ une perturbation de $\partial^0$ qui
satisfait l'hypothèse de nilpotence, i. e. :

$$
\forall c \in C^0, \exists i \in \mathbb{N} \mid c(\delta^0 h)^i = 0
$$

Alors $\rho^\delta = ((C^0, \partial^0 + \delta^0), (C^1, \partial^1 + \delta^1), h^\delta, f^\delta, g^\delta)$ est une reduction, où :

$$
- \delta^1 = g\Phi\delta^0 f = g\delta^0 \Psi f.
$$

$$
- f^{\delta} = \Psi f
$$

$$
- g^{\delta} = g\Phi
$$

$$
- h^{\delta} = h\Phi = \Psi h
$$

$$
avec^2 \Phi = \sum_{i=0}^{i=\infty} (-1)^i (\delta^0 h)^i \text{ et } \Psi = \sum_{i=0}^{i=\infty} (-1)^i (h \delta^0)^i.
$$

Notons que le lemme *Easy* est toujours applicable, alors que le lemme *Basic* est appli-
cable sous les conditions de nilpotence.

<figure><img src="image_75.png" /><figcaption>FIGURE 3.20 – Illustration des lemmes de perturbation *Easy* et *Basic*</figcaption></figure>

**3.3.5.1 Équivalence homologique – cône cellulaire**

On note $\mathcal{C}$ une quasi-variété cellulaire connexe, et $\mathcal{C}\mathcal{C}^{\text{ext}}$ la quasi-variété cellulaire obtenue par une opération de cône cellulaire sur $\mathcal{C}$. Le théorème 6 [Giblin 1977] nous dit que l'opération de cône sur un objet annule tous ses groupes d'homologie, excepté pour $H_0$ qui est isomorphe à $\mathbb{Z}$.

<footnote n="2">2. D'après l'hypothèse de nilpotence, chaque somme contient un nombre fini de termes non nuls.</footnote>
**Théorème 6 (Homologie d'un cône)** Soit $X$ un objet résultant d'une opération de cône, alors :

$$H_0(X) \simeq \mathbb{Z}$$

$$H_p(X) = 0 \text{ pour tout } p > 0$$

## Équivalence homologique d'une composante connexe

L'équivalence homologique associée à chaque composante connexe après l'application d'un cône cellulaire est obtenue de manière immédiate en utilisant le Théorème 6 : on peut prendre comme "gros" complexe une copie du complexe associé à l'objet manipulé, et comme "petit" complexe, un complexe réduit à un seul générateur de dimension 0. La réduction $((C^B, \partial^B), (C, \partial), f, g, h)$ est définie de la manière suivante :

- l'opérateur $h$ est nul,

- $f$ et $g$ sont des isomorphismes.

La réduction $((C^B, \partial^B), (C^S, \partial^S), f^S, g^S, h^S)$ est définie de la manière suivante :

- $h^S$ associe à chaque $k$-simplexe $\sigma \in CC^{ext}$, le $(k+1)$-simplexe $\tau$ qu'il génère par l'opération de cône, tel que $\sigma h^S = (-1)^{k+1}\tau$, $h^S$ est nul ailleurs,

- $f^S$ est nul partout excepté pour les sommets (celui du cône et ceux de $CC$), qui sont associés avec le sommet de $C^S$,

- L'application $g^S$ associe le sommet de $C^S$ avec le sommet du cône de $C^B$.

<figure><img src="image_76.png" /><figcaption>FIGURE 3.21 – (a) une équivalence homologique associée à une composante connexe d'une quasi-variété cellulaire de dimension 1. Après extention de la composante connexe, l'équivalence homologique de la 2-cellule peut être déduite de (a) : à partir d'une équivalence isomorphe (les cellules sont simplement montées en dimension) et d'une équivalence homologique associée à la 0-cellule du cône, les lemmes de perturbation permettent d'en déduire une équivalence homologique de la cellule.</figcaption></figure>
### Équivalence homologique d'une cellule

Les lemmes de perturbation *Easy* et *Basic* permettent de déduire l'équivalence homologique associée à chaque cellule, à partir de l'équivalence homologique de son bord (i. e. de la quasi-variété cellulaire de dimension inférieure sur laquelle s'appuie le cône), cf. figure 3.21.

### 3.3.5.2 Équivalence homologique – identification cellulaire

#### Équivalence homologique d'une cellule

Que la cellule soit impactée ou non par l'identification, son équivalence homologique n'est pas modifiée. En pratique, pour chaque ensemble de cellules identifiées, il suffit de conserver une équivalence homologique.

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

FIGURE 3.22 – Exemple d'identification cellulaire. Seules les cellules identifiées et leurs bords sont mises en évidence. (a) avant identification. (b) après identification. Les cellules représentées en gris, qui apparaissent dans le bord de cellules identifiées, ne sont pas impactées par l'opération d'identification

#### Équivalence homologique d'une composante connexe

Afin de pouvoir utiliser le théorème SECE, il faut construire la suite exacte courte associée à une opération d'identification, ainsi que l'équivalence homologique correspondant à la partie identifiée. La figure 3.22 illustre une opération d'identification cellulaire mettant en évidence l'ensemble des cellules impactées. Le principe de l'utilisation des lemmes de perturbation pour le calcul de l'équivalence homologique associée à la partie identifiée est illustré sur la figure 3.23.

Pour obtenir l'équivalence homologique correspondant à la partie identifiée, on utilise les équivalences homologiques des cellules impactées. Le principe est de reconstituer le complexe de chaînes correspondant à l'ensemble des cellules identifiées en perturbant le bord de ces cellules. Ensuite, on répercute la perturbation sur le "gros" complexe en utilisant le lemme de perturbation *Easy*, puis du "petit" en utilisant le lemme de perturbation *Basic*.

L'équivalence homologique de la partie identifiée est obtenue directement à partir de cette équivalence homologique en considérant la somme directe de n copies de cette équi-
<figure><img src="image_78.png" /><figcaption>FIGURE 3.23 – Illustration de l'utilisation des lemmes de perturbation pour calculer l'équivalence homologique associée à la partie identifiée de l'identification illustrée sur la figure 3.22.</figcaption></figure>

valence homologique, *n* étant le nombre de cellules identifiées diminué d'une unité.

La suite exacte courte effective est obtenue à partir de la définition de la perturbation et du choix des cellules qui "survivent" à l'opération d'identification.

## 3.4 Conclusion

Nous avons présenté différentes méthodes de calcul des groupes d'homologie de structures combinatoires.

L'approche globale consiste à réduire les matrices de bord décrivant les relations d'incidence entre toutes les cellules. Cette approche s'applique directement sur toute structure dont les cellules correspondent à des boules.

C'est le cas pour les structures régulières dont les cellules sont des simplexes, des cubes ou des simploïdes, mais ce n'est pas le cas des cellules des structures cellulaires en général. Nous avons présenté la sous-classe de Gcartes et des chaînes de cartes pour lesquelles on peut calculer l'homologie de manière directe : le bord des cellules doit avoir l'homologie d'une sphère, les cellules doivent être orientables, et sans point fixe. Ceci correspond à de nombreux cas en pratique.

L'approche incrémentale consiste à s'affranchir d'un calcul basé sur l'étude globale de la structure. L'étude d'approches incrémentales pour les structures simpliciales, simploïdales et cellulaires, nous a amené à étudier comment l'homologie est impactée par l'application de différentes opérations :

— il est bien connu que l'homologie d'un cône annule tous les groupes d'homologie,
excepté $H_0$ qui est isomorphe à $\mathbb{Z}$;

— l'homologie effective permet de calculer incrémentalement l'homologie d'un objet construit par une suite d'identifications et de dégénérescence. Elle permet également de calculer l'homologie d'une structure cellulaire de manière incrémentale. Le calcul est basé sur les opérations de cône cellulaire et d'identification cellulaire, et tire partie de la structuration cellulaire;

— la formule de KÜNNETH permet de calculer l'homologie d'un objet résultant d'une opération de produit cartésien, particulièrement adapté aux structures simploïdales,

— Enfin, nous avons montré que l'homologie persistante de tours entre dans le cadre de l'homologie effective.
<figure><img src="image_79.png" /></figure>
# Objets géométriques

## Sommaire

<table><tr><td>4.1 Réalisation géométrique</td><td>104</td></tr><tr><td>4.1.1 Complexes simpliciaux</td><td>104</td></tr><tr><td>4.1.2 Complexes simploïdaux</td><td>105</td></tr><tr><td>4.1.3 Autres structures</td><td>106</td></tr><tr><td>4.2 Plongement linéaire</td><td>106</td></tr><tr><td>4.2.1 Complexes simpliciaux abstraits</td><td>106</td></tr><tr><td>4.2.2 Complexes simploïdaux abstraits</td><td>107</td></tr><tr><td>4.2.3 Structures cellulaires sans multi-incidence</td><td>107</td></tr><tr><td>4.2.4 Structures avec multi-incidence</td><td>108</td></tr><tr><td>4.3 Espaces de BÉZIER</td><td>108</td></tr><tr><td>4.3.1 Notions de base</td><td>108</td></tr><tr><td>4.3.2 Ensembles semi-simpliciaux</td><td>109</td></tr><tr><td>4.3.3 Ensembles semi-simploïdaux</td><td>113</td></tr><tr><td>4.3.4 Ensembles simpliciaux</td><td>116</td></tr><tr><td>4.3.5 Ensembles simploïdaux</td><td>119</td></tr><tr><td>4.3.6 Structures cellulaires</td><td>122</td></tr><tr><td>4.4 Application à la modélisation d'objets tubulaires</td><td>123</td></tr><tr><td>4.4.1 Contexte et objectifs</td><td>123</td></tr><tr><td>4.4.2 Branches – Jonctions</td><td>124</td></tr><tr><td>4.4.3 Pavage quad de la sphère</td><td>125</td></tr><tr><td>4.4.4 Géométrie des branches</td><td>128</td></tr><tr><td>4.4.5 Résultats</td><td>130</td></tr><tr><td>4.5 Conclusion</td><td>131</td></tr></table>

Comme nous l'avons vu dans les chapitres précédents, il existe différentes structures permettant de manipuler des assemblages de simplexes, de simploïdes, de cellules ou encore de celluloïdes. Nous avons en particulier présenté les opérations de construction de base, ainsi que la caractérisation topologique des objets manipulés via le calcul de groupes d'homologie.

En modélisation géométrique, il est également important de pouvoir donner une forme aux objets combinatoires que l'on manipule. D'ailleurs, dans les chapitres 2 et 3, nous avons illustré différents objets combinatoires par des représentation géométriques.
Dans un premier temps, nous présentons la notion de **réalisation géométrique** de différentes structures dans $\mathbb{R}^n$. De manière simplifiée, une réalisation géométrique est un isomorphisme entre une structure combinatoire et un espace topologique. c'est-à-dire qu'à chaque cellule abstraite est associée une cellule géométrique, et la topologie induite dans l'espace géométrique respecte la structure.

Nous présentons ensuite deux approches permettant d'associer plus généralement une
forme à un objet combinatoire :

- plongement linéaire : qui consiste à associer une forme géométrique à un objet en donnant uniquement une position à ses sommets. La forme de chaque cellule de dimension supérieure à 0 est définie par l'ensemble de positions de ses sommets.

- plongement non inéaire : une forme est associée à chaque cellule. Nous présentons les espaces de BÉZIER, définis de manière paramétrique, qui permettent de représenter des cellules de forme courbe. Les espaces de BÉZIER font partie de la famille des modèles dits à pôles, c'est-à-dire que la forme de chaque cellule est définie de manière exacte par un ensemble de points appelés points de contrôle. Nous montrons en particulier que l'on retrouve, dans les espaces de BÉZIER, les structures d'ensembles simpliciaux et simploïdaux.

**Note :**

Dans la littérature mathématique, une application $f : X \to Y$ entre deux espaces topologiques $X$ et $Y$ est un *plongement* si elle induit un homéomorphisme de $X$ dans $f(X)$, où $f(X)$ est muni de la topologie induite (comme sous-ensemble de l'espace topologique $Y$). Nous utilisons le terme *plongement* pour désigner l'association d'une forme géométrique à une structure combinatoire.

4.1 Réalisation géométrique

4.1.1 Complexes simpliciaux

La réalisation géométrique d'un complexe simplicial abstrait $K$ est un complexe simplicial $\mathcal{K}$, dont la définition est basée sur la notion de simplexe géométrique.

**Définition 38** *Soit $\{a_0, \dots, a_p\}$ un ensemble de points de $\mathbb{R}^n$ affinement indépendants. Le p-simplexe géométrique $\sigma$ de sommets $a_0, \dots, a_p$ est l'enveloppe convexe de ces points. Un simplexe décrit par un sous-ensemble non vide de $\{a_0, \dots, a_p\}$ est une **face de** $\sigma$. Les faces de $\sigma$ différentes de $\sigma$ lui-même sont les **faces propres** de $\sigma$, leur union est le **bord** de $\sigma$ et $\sigma$ est la **face principale**.*

**Définition 39** *Un complexe simplicial $K$ de $\mathbb{R}^n$ est une famille finie de simplexes géométriques de $\mathbb{R}^n$ telle que :*

- toute face d'un simplexe de K est dans K,

- l'intersection de deux simplexes $\sigma_1, \sigma_2$ de $K$ est soit vide, soit une face commune à $\sigma_1$ et $\sigma_2$.

Un simplexe de K est dit **principal** s'il n'est face propre d'aucun simplexe.
À tout complexe simplicial abstrait $K$ contenant $n$ sommets $\{v_1, \dots, v_n\}$, on peut associer un complexe simplicial $\mathcal{K}$ de $\mathbb{R}^n$ de manière canonique : on associe à chaque sommet $v_i$ le point $e_i$, où l'ensemble des $e_i$, $i \in [1, n]$ désigne la base canonique de $\mathbb{R}^n$. À chaque simplexe abstrait $\{v_{i_1}, \dots, v_{i_p}\}$ de $K$, on associe l'enveloppe convexe des points $\{e_{i_1}, \dots, e_{i_p}\}$. Cette construction est la réalisation géométrique canonique de $K$ dans $\mathbb{R}^n$.

Bien souvent, cette construction canonique est réalisée dans un espace "trop grand". Par exemple, tout graphe peut être réalisé géométriquement dans $\mathbb{R}^3$, quel que soit le nombre de sommets. De manière générale, tout complexe simplicial abstrait de dimension $n$ peut être réalisé géométriquement dans $\mathbb{R}^{2n+1}$.

Par exemple, considérons le complexe simplicial abstrait suivant :

$$K = \left\{ \begin{array}{l} \{\{v_0\}, \{v_1\}, \{v_2\}, \{v_3\}, \{v_4\}, \{v_5\} \\ \{v_1, v_2\}, \{v_2, v_5\}, \{v_1, v_5\}, \\ \{v_0, v_1\}, \{v_1, v_3\}, \{v_0, v_3\}, \{v_3, v_4\}, \\ \{v_0, v_1, v_3\}, \{v_1, v_2, v_5\} \end{array} \right\}$$

La réalisation géométrique canonique de $K$ est définie dans $\mathbb{R}^6$. La figure 4.1 illustre trois exemples de complexes simpliciaux qui correspondent à des réalisations géométriques de $K$ dans $\mathbb{R}^2$.

<figure><img src="image_80.png" /><figcaption>FIGURE 4.1 – (a) – (c) Trois complexes simpliciaux qui correspondent à des réalisations géométriques d'un même complexe simplicial abstrait.</figcaption></figure>

### 4.1.2 Complexes simploïdaux

La définition des complexes simploïdaux abstraits que nous avons proposée permet d'étendre directement la définition de la réalisation géométrique des complexes simpliciaux abstraits. Pour rappel, un complexe simploïdal abstrait $K^\square$ est défini à partir d'une partition de sommets $V = (V^i)_{i \in [1, n]}$ et pour tout $i \in [1, n]$, l'ensemble des simplexes de $V^i$ composant les simploïdes $K^\square$ est un complexe simplicial abstrait $K^i$.

On peut associer à tout $V^i$, l'espace vectoriel $\mathbb{R}^{|V^i|}$. Comme tous les $V^i$ sont disjoints, on peut définir l'espace ambiant produit $\mathbb{R}^{|V^1|} \times \dots \times \mathbb{R}^{|V^n|}$, qui est isomorphe à $\mathbb{R}^{\sum_{i=1}^n |V^i|}$. Dit autrement, on peut mettre en bijection l'ensemble des sommets de $V$ avec la base canonique de $\mathbb{R}^{\sum_{i=1}^n |V^i|}$. Une manière de procéder est de se donner une numérotation globale sur la partition $V$ telle que chaque sommet $v_j \in V$ est associé à $e_j$.
Soit $\sigma = \{\sigma_{i_1}, \dots, \sigma_{i_p}\}$ un simploïde abstrait de $K^{\square}$; comme tous les espaces vectoriels associés aux ensembles $V^i$ sont indépendants, on peut directement définir le **simploïde géométrique** associé à $\sigma$ comme le produit des simplexes géométriques qui le compose. En associant à tout simploïde abstrait de $K^{\square}$ le simploïde géométrique correspondant, on construit la réalisation géométrique canonique de $K^{\square}$ dans $\mathbb{R}^{\sum_{i=1}^n |V^i|}$.

Dit autrement, à chaque sommet simploïdal $\{\{v_{i_1}\}, \dots, \{v_{i_p}\}\}$ de $K^{\square}$, on associe le point $e_{i_1} + \dots + e_{i_p}$, et à tout simploïde abstrait $\sigma = \{\sigma_1, \dots, \sigma_n\}$, on associe l'enveloppe convexe de ses sommets simploïdaux. Comme indiqué pour les complexes simpliciaux, l'espace $\mathbb{R}^{\sum_{i=1}^n |V^i|}$ est en général "trop grand".

### 4.1.3 Autres structures

De manière générale, la réalisation géométrique d'un ensemble simplicial ou simploïdal est un CW-complexe : à chaque cellule abstraite est associée une boule de même dimension, les fonctions d'attachement du CW-complexe correspondent aux opérateurs de face.

Pour les structures cellulaires, il est possible de procéder de la même manière en passant par l'interprétation simpliciale. En considérant uniquement les cellules, cela n'est en revanche pas possible en toute généralité car il n'est pas possible d'associer une boule à chaque cellule.

La construction d'un CW-complexe nécessite en particulier de contrôler que l'intersection de deux cellules géométriques correspond bien à une cellule de dimension inférieure de leur bord. De manière générale, on associe une forme géométrique à chaque cellule en respectant les relations d'incidence de la structure. Il est également possible d'ajouter des contraintes, afin de garantir par exemple que l'intersection entre deux cellules géométriques quelconques est soit vide, soit correspond à une cellule géométrique de leurs bords, ou encore qu'une cellule ne s'auto-intersecte pas. Ces contraintes géométriques ne sont pas traitées dans ce document.

## 4.2 Plongement linéaire

### 4.2.1 Complexes simpliciaux abstraits

De manière intuitive, les réalisations géométriques des complexes simpliciaux abstraits peuvent être vues comme des plongements aux sommets particuliers. Cette construction garantit la cohérence entre la structure combinatoire et l'espace topologique associé : en particulier, l'intersection de deux simplexes est soit vide, soit un simplexe de dimension inférieure du complexe.

Comme indiqué précédemment, tout complexe simplicial abstrait de dimension $n$ peut être réalisé géométriquement dans $\mathbb{R}^{2n+1}$. Si l'on souhaite conserver la cohérence entre l'espace topologique et la structure, il est nécessaire de vérifier que toutes les intersections de simplexes correspondent bien à des simplexes de dimension inférieure de l'objet géométrique.
### 4.2.2 Complexes simploïdaux abstraits

Le plongement aux sommets d'un complexe simploïdal abstrait nécessite les mêmes vérifications d'intersection que celles évoquées pour les complexes simpliciaux abstraits.

Plus généralement, notons que le produit cartésien d'un complexe simploïdal abstrait par un sommet ne change pas sa structure, mais cela change l'objet géométrique associé. Par exemple, considérons un complexe simploïdal abstrait $K^\square$ défini sur $V = (V^i)_{i\in[1,n]}$, et $K'^\square$ un sous-complexe de $K^\square$, où tous les simploïdes de $K'^\square$ sont de la forme $\{\sigma_{i_1}, \dots, \sigma_{i_p}\}$, avec $\sigma_{i_k} \in V^{i_k}$ pour $k \in [1, p]$. En effectuant le produit cartésien de $K^\square$ par un simploïde correspondant à un sommet de $V^{i_q}$ où $q \notin \{i_1, \dots, i_p\}$, on augmente intuitivement la dimension de l'espace géométrique dans lequel $K^\square$ est réalisé, mais la structure du complexe abstrait reste identique. Cela revient intuitivement à ajouter un 0 dans le type du simploïde abstrait.

Inversement, si on considère un sous-complexe $K'^\square$ dont tous les simploïdes sont de la forme $\{\sigma_{i_1}, \dots, \sigma_{i_p}, \{v\}\}$, avec $v \in V^{i_{p+1}}$, alors le sous-complexe peut être projeté de $\mathbb{R}^{\sum_{k=1}^{p+1}|V^{i_k}|}$ dans $\mathbb{R}^{\sum_{k=1}^{p}|V^k|}$ en supprimant la composante $\{v\}$ de chaque simploïde.

Notons que le fait d'expliciter les sommets intervenant dans la définition de chaque simploïde se retrouve également dans la définition des **supercomplexes**, comme présenté en section 2.5.2.3.

### 4.2.3 Structures cellulaires sans multi-incidence

Concernant les structures à base de graphes d'incidence, comme les *n*-surfaces ou les chaînes de *n*-surfaces, qui ne permettent pas de représenter des objets présentant de la multi-incidence, on peut associer une forme à un objet en donnant seulement des coordonnées aux sommets. Cela dit, si cette méthode permet d'associer une géométrie précise à tout simplexe ou simploïde en toute dimension, cela est moins évident pour les structures cellulaires. En effet, si les cellules de dimension 0 et 1 sont définies sans ambiguïté, dès la dimension 2, la définition de la forme d'une 2-cellule par la position de l'ensemble de ses sommets et des arêtes de son bord peut poser certains problèmes. Si l'ensemble des sommets de la cellule n'est pas coplanaire : comment la cellule surfacique est-elle définie ? Avec ces seules informations, il n'est pas possible d'effectuer des calculs de base liés à la géométrie de ces cellules, comme par exemple l'intersection avec une droite ou une autre cellule.

On peut bien entendu résoudre ce problème en utilisant la structure simpliciale associée. La géométrie de chaque *p*-cellule est alors définie comme l'union des *p*-simplexes géométriques associés. Cette solution a bien entendu l'inconvénient de perdre l'optimisation de la représentation cellulaire. On peut appliquer le même type de plongement pour des structures de type cartes combinatoires ne présentant pas de multi-incidence avec bien sûr les mêmes inconvénients.
### 4.2.4 Structures avec multi-incidence

De manière évidente, les plongements linéaires ne sont pas adaptés aux structures permettant la multi-incidence, comme les ensembles simpliciaux ou simploïdaux, ou les cartes combinatoires, dès lors que :

- deux cellules partagent un même ensemble de sommets,

- une cellule est incidente plusieurs fois à l'une de ses faces.

Par exemple, si l'on se contente de donner une position à chaque sommet de l'ensemble semi-simplicial représenté sur la figure 4.12a, la forme géométrique du triangle sera définie par le segment reliant les deux sommets de son bord.

## 4.3 Espaces de BÉZIER

Nous présentons dans cette partie les espaces de BÉZIER, qui permettent de donner des formes courbes aux simplexes et aux simploïdes. Plus précisément, les espaces de BÉZIER permettent de donner une forme géométrique à chaque cellule, tout en préservant les relations d'incidence de la structure associée. Un espace **espace triangulaire de BÉZIER**, ou espace de BÉZIER simplicial, est un ensemble de simplexes de BÉZIER satisfaisant certaines contraintes de continuité (cf. [Farin 2002]).

Les espaces de BÉZIER simpliciaux ont naturellement une structure d'ensemble simplicial, et les **espaces simploïdaux de BÉZIER**, ou produits d'espaces de BÉZIER triangulaires, ont naturellement une structure d'ensemble simploïdal.

### 4.3.1 Notions de base

En préambule, il est utile de rappeler les définitions et notations qui suivent. En particulier, la structuration des espaces simpliciaux et simploïdaux de BÉZIER est mise en évidence via la numérotation des points de contrôle par des **multi-indices**.

L'ensemble $\Gamma_d^i$ des multi-indices de dimension $i$ et degré $d$ est défini de la manière suivante : $\Gamma_d^i = \{\alpha = (\alpha_0, \dots, \alpha_i) \in \mathbb{N}^{i+1} \mid |\alpha| = \alpha_0 + \dots + \alpha_i = d\}$. Par souci de lisibilité, un multi-indice $(\alpha_0, \dots, \alpha_i)$ sera plus simplement noté $\alpha_0 \cdots \alpha_i$. Par exemple, $\Gamma_3^1 = \{03, 12, 21, 30\}$, et $\Gamma_3^2 = \{003, 012, 021, 030, 102, 111, 120, 201, 210, 300\}$. Le nombre d'éléments de $\Gamma_d^i$, noté $|\Gamma_d^i|$, est égal à $\binom{i+d}{i}$.

Les **polynômes de BERNSTEIN multivariés de degré $d$ et multi-indice $\alpha$** sont définis par $B_\alpha^d(u) = \binom{d}{\alpha} u_0^{\alpha_0} \cdots u_i^{\alpha_i}$, où $\alpha = (\alpha_0, \dots, \alpha_i)$, et $\binom{d}{\alpha} = \frac{d!}{\alpha_0! \cdots \alpha_i!}$ sont les **coefficients multinomiaux**, et les $\{u_j\}$ sont les coordonnées barycentriques de $u$, un point du $i$-simplexe standard, $i$. e. les $\{u_j\}$ vérifient : $\forall j, 0 \le j \le i, 0 \le u_j \le 1 \text{ et } \sum_{j=0}^i u_j = 1$.

L'ensemble des polynômes de BERNSTEIN $B_\alpha^d(u)$ forme une base des polynômes multivariés, c'est-à-dire que tout polynôme multivarié peut s'écrire de manière unique comme combinaison linéaire de ces polynômes.
On pourra également noter que la formule du multinôme de Newton nous indique que la somme des polynômes de BERNSTEIN vaut toujours 1 :

$$ (u_0 + \cdots + u_i)^d = 1^d = 1 = \sum_{|\alpha|=d} \binom{d}{\alpha} u_0^{\alpha_0} \cdots u_i^{\alpha_i} = \sum_{|\alpha|=d} B_{\alpha}^d(u). $$

Cela signifie que les points des simplexes et des simploïdes de Bézier sont bien définis comme combinaisons affines des points de contrôle.

### 4.3.2 Ensembles semi-simpliciaux

Un *i*-simplexe de BÉZIER de degré *d* est défini par $P(u) = \sum_{\alpha \in \Gamma_d^i} P_\alpha B_\alpha^d(u)$, où $\{P_\alpha, \alpha \in \Gamma_d^i\}$ est l'ensemble de ses points de contrôle (cf. figure 4.4). Ainsi, à chaque point *u* du *i*-simplexe standard correspond un point du simplexe de BÉZIER $P(u)$, entièrement défini par ses points de contrôle, comme illustré sur la figure 4.2.

<figure><img src="image_81.png" /><figcaption>FIGURE 4.2 – À tout point *u* de l'espace de paramètre correspond un point $P(u)$ du simplexe de BÉZIER défini par ses points de contrôle.</figcaption></figure>

En utilisant les polynômes de BERNSTEIN, on peut donc calculer un ensemble de points d'un *i*-simplexe de BÉZIER en échantillonnant l'ensemble des points du *i*-simplexe standard. En pratique, on peut utiliser l'algorithme récursif de DE CASTELJAU de complexité équivalente.

L'algorithme de DE CASTELJAU permet de calculer les points d'un *i*-simplexe de BÉZIER de degré *d* par une suite d'interpolations linéaires, ce qui revient à reconstruire les polynômes de BERNSTEIN, comme illustré sur la figure 4.3. Pour tout point $u = (u_0, \cdots, u_i)$ du *i*-simplexe standard, le point $P(u)$ du *i*-simplexe de Bézier de degré *d* peut être défini à partir de l'ensemble de points de contrôle $\{P_\alpha | \alpha \in \Gamma_d^i\}$ de la manière suivante : pour tout $u$, $P_\alpha^0(u) = P_\alpha$ sont les points de contrôle. Le point $P_{0 \cdots 0}^d(u) = P(u)$ est un point du *i*-simplexe de BÉZIER défini récursivement par la relation suivante :

$$ P_{\alpha_0 \cdots \alpha_i}^k(u) = \sum_{j=0}^{i} u_j P_{\alpha_0 \cdots \alpha_{j-1}(\alpha_j+1)\alpha_{j+1} \cdots \alpha_i}^{k-1}(u), \text{ avec } 0 < k \le d. $$
De manière intuitive, sur la figure 4.3(a), à partir du point de contrôle $P_{12}$, il existe 3 chemins permettant de remonter jusqu'au point $P_{00}^3 : u_0u_1u_1, u_1u_0u_1$ et $u_1u_1u_0$, soit $3u_0u_1^2$ correspondant au polynôme de Berstein $B_{12}^3(u_0, u_1)$.

<figure><img src="image_82.png" /><figcaption>FIGURE 4.3 – Principe de l’algorithme de DE CASTELJAU. En (a), pour une courbe de degré 3, en (b) pour un triangle de degré 3.</figcaption></figure>

Notons que tout point $u = (u_0, \dots, u_i)$ du *i*-simplexe standard peut toujours s'écrire $(u_0, \dots, u_{i-1}, 1-(u_0+\dots+u_{i-1}))$ ; ainsi, on trouve souvent dans la littérature la définition des courbes de BÉZIER utilisant un unique paramètre $t$ et les polynômes de BERNSTEIN décrits dans la base $t$, $(1-t)$, avec $t$ compris entre 0 et 1.

### 4.3.2.1 Représentation d'un espace simplicial de BÉZIER

On peut représenter un espace triangulaire de BÉZIER par l'ensemble de ses simplexes principaux, où chaque simplexe principal stocke l'ensemble de ses points de contrôle. Le degré peut être fixé pour tous les simplexes d'un ensemble semi-simplicial afin de simplifier les opérations de construction. Cela étant, il est également possible de manipuler des simplexes principaux de degrés différents en utilisant des résultats bien connus d'élévation de degré [Farin 2002]. Cette approche basée sur le stockage des points de contrôle sur les simplexes principaux pose deux problèmes, cf. figure 4.4a :

- la structure n'est pas explicitée : les relations d'incidence ne sont donc pas directes. Or ce sont des informations essentielles dès que l'on souhaite étudier la structure un objet;

- si deux simplexes sont assemblés le long d'une face, leurs points de contrôle sont dupliqués, ce qui est bien entendu une source potentielle d'incohérences.
<figure><img src="image_83.png" /><figcaption>FIGURE 4.4 – (a) Simplexes principaux et leurs points de contrôle. (b) Répartition des points de contrôle sur l'ensemble de la structure. Chaque simplexe ne stocke que ses points de contrôle propres. (c) Un espace triangulaire de BÉZIER dont la structure correspond à l'ensemble semi-simplicial représenté en (b).</figcaption></figure>

On peut utiliser d'autres structures de données qui permettent de résoudre ces deux problèmes en utilisant les propriétés des espaces de BÉZIER. En effet, il est bien connu que le bord d'un *i*-simplexe de BÉZIER est composé de simplexes de BÉZIER de dimensions inférieures : tout simplexe de BÉZIER contient son bord. Par exemple, le bord d'un triangle de BÉZIER est composé de courbes de BÉZIER. La numérotation des points de contrôle des simplexes de BÉZIER basée sur les multi-indices permettent répartir l'ensemble des points de contrôle d'un simplexe principal sur le simplexe et son bord.

Plus précisément, l'ensemble des points de contrôle $P_{\alpha_0 \cdots \alpha_{j-1} 0 \alpha_{j+1} \cdots \alpha_i}$ d'un *i*-simplexe de BÉZIER sont les points de contrôle d'un $(i-1)$-simplexe de BÉZIER correspondant à sa $j$-e face. Par exemple, sur la figure 4.4a, l'ensemble des points de contrôle $\{P_{300}, P_{210}, P_{120}, P_{030}\}$ d'un des deux triangles de degré 3 sont les points de contrôle de la courbe de BÉZIER de degré 3 correspondant à sa face obtenue par application de l'opérateur $d_2$.

Chaque *i*-simplexe peut donc stocker uniquement ses points de contrôle propres, c'est-à-dire les points de contrôle qui n'appartiennent pas à son bord. Les points de contrôle propres d'un *i*-simplexe sont donc de la forme $P_{\alpha_0 \cdots \alpha_i}$ avec, pour tout $0 \le j \le i$, $\alpha_j > 0$. L'ensemble des points de contrôle d'un espace triangulaire de BÉZIER peuvent être répartis sur la structure d'un ensemble semi-simplicial [Lang 1996, Fuchs 1997]. Cela permet de résoudre les deux problèmes présentés lorsque chaque simplexe principal stocke tous ses points de contrôle :

- les relations d'incidence sont explicitées par l'ensemble semi-simplicial,

- aucun point de contrôle n'est dupliqué.

Lorsque l'on souhaite calculer l'espace triangulaire de BÉZIER associé à un ensemble semi-simplicial, on peut reconstituer l'ensemble des points de contrôle de chaque simplexe
principal via les indices des opérateurs de face qui permettent d'accéder aux points de contrôle de leurs bords. Par exemple, sur la figure 4.4b, l'arête commune aux deux triangles contient uniquement ses points de contrôle propres numérotés 12 et 21. Pour le triangle du haut (resp. du bas), cette arête est sa face $d_0$ (resp. $d_1$), ces points sont donc numérotés 012 et 021 (resp. 102 et 201) pour le triangle, comme indiqué sur la figure 4.4a.

D'un point de vue pratique, les points de contrôle d'un simplexe de BÉZIER peuvent être stockés dans un *tableau simplicial*, selon l'ordre lexicographique de leur multiindice [DeRose 1993] comme illustré sur la figure 4.5.

<figure><img src="image_84.png" /><figcaption>FIGURE 4.5 – Les points de contrôle d'un simplexe de BÉZIER peuvent être stockés dans un tableau simplicial en utilisant l'ordre lexicographique des multi-indices.</figcaption></figure>

L'indice d'un point de contrôle $P_\alpha$ peut être simplement retrouvé en utilisant l'algorithme décrit dans [Peltier 2018]. L'idée est la suivante : soit $\alpha = \alpha_0 \dots \alpha_i$ le multi-indice d'un point de contrôle. Si $i = 1$, alors le point de contrôle est stocké dans la case $\alpha_0$ du tableau simplicial. Si $i > 1$, alors il faut d'abord stocker tous les multi-indices de même degré commençant par 0, puis $1, \dots$ jusqu'à tous ceux commençant par $\alpha_0 - 1$. On reconnue en considérant à présent $\alpha_1$ et ainsi de suite jusqu'à considérer le dernier indice $\alpha_i$.

Dans le cas où l'ensemble des points de contrôle est réparti sur un ensemble semi-simplicial, chaque simplexe stocke uniquement ses points de contrôles propres.

### 4.3.2.2 Opérations de construction

Comme nous l'avons vu au chapitre 2, les opérations de construction de base pour les ensembles semi-simpliciaux sont le cône et l'identification. Pour chacune de ces opérations, les positions des points de contrôle des simplexes impactés par les opérations doivent être calculées.

#### Cône

Pour l'opération de cône, les points de contrôle propres des nouveaux simplexes créés par l'opération peuvent être calculés par exemple par interpolation entre les points du simplexe dont il est issu est le nouveau sommet : cf. figure 4.6.

#### Identification

Les points de contrôle du simplexe $\tau$ résultant de l'identification de deux simplexes $\sigma$ et $\mu$ peuvent définir de différentes manières : par exemple, on peut leur associer les points $\sigma$ ou ceux de $\mu$, on encore les définir par interpolation des points de $\sigma$ et $\mu$ comme représenté sur la figure 4.7.
<figure><img src="image_85.png" /></figure>

FIGURE 4.6 – Espace triangulaire de BÉZIER issu d'une opération de cône. Les points de contrôle des deux triangles sont obtenus par interpolation des points de contrôle de la boucle et de l'arête en bas et du point de contrôle du nouveau sommet (en rouge).

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

FIGURE 4.7 – (a) Un espace triangulaire de BÉZIER. (b) Résultat de l'opération d'identification des deux arêtes en orange de (a). Les points de contrôle de l'arête résultante peuvent être calculés par interpolation linéaire des points de contrôle des deux arêtes.

Produit cartésien

L'opération de produit cartésien est présentée en Section 4.3.4, les résultats présentés peuvent être directement adaptés aux ensembles semi-simpliciaux en manipulant les simplexes dégénérés nécessaires à la définition du produit cartésien de manière implicite.

4.3.3 Ensembles semi-simploïdaux

Les simploïdes de BÉZIER [Dahmen 1982] généralisent la notion bien connue de
carreaux de BÉZIER, définis par des produits tensoriels de courbes de BÉZIER. La
structure d'ensemble semi-simploïdal se retrouve grâce aux multi-indices des points de
contrôle. Plus précisément, chaque point de contrôle est ici numéroté par un *n*-uplet de
multi-indices, correspondant à la structure du simploïde.
Un simploïde de BÉZIER de type $(a_1, \dots, a_n)$ et de degré $(d_1, \dots, d_n)$ est défini par :
$$P(u^1, \dots, u^n) = \sum_{\alpha^1 \in \Gamma_{d_1}^{a_1}} \dots \sum_{\alpha^n \in \Gamma_{d_n}^{a_n}} P_{(\alpha^1, \dots, \alpha^n)} B_{\alpha^1}^{d_1}(u^1) \times \dots \times B_{\alpha^n}^{d_n}(u^n)$$
où chaque $u^i$ est un point du $a_i$-simplexe standard, et $\{P_{(\alpha^1, \dots, \alpha^n)}\}$ est l'ensemble de ses points de contrôle.
Par souci de clarté, $P_{(\alpha^1, \dots, \alpha^n)}$ est également noté $P_{\alpha^1, \dots, \alpha^n}$.

<figure><img src="image_87.png" /><figcaption>FIGURE 4.8 – Les points de contrôle du prisme et son bord, représentés en (b) sont numérotés par des couples de multi-indices correspondant aux simplexes et leurs bords représentés en (a).</figcaption></figure>

La figure 4.9 représente des simploïdes de BÉZIER et leurs types jusqu'à la dimension 3. Les points de contrôle ne sont pas représentés.

<figure><img src="image_88.png" /><figcaption>FIGURE 4.9 – Simploïdes de BÉZIER et leurs types jusqu'à la dimension 3.</figcaption></figure>

Les espaces simploïdaux de BÉZIER généralisent les espaces cubiques de BÉZIER, définis comme des assemblages de cubes de BÉZIER. Le principe est exactement le même, mais on ne se restreint pas ici à des produits tensoriels d'arêtes : cf. figure 4.10.

Un espace simploïdal de BÉZIER est un ensemble *S* de simploïdes de BÉZIER respectant certaines contraintes, comme présenté pour les espaces simpliciaux de BÉZIER.

Dans les espaces simploïdaux de BÉZIER, l'espace paramétrique d'un simploïde de type $(a_1, \dots, a_n)$ correspond à des produits tensoriels d'espaces triangulaires de BÉZIER. La figure 4.11 illustre l'espace paramétrique d'un prisme défini comme produit de deux espaces paramétriques.
<figure><img src="image_89.png" /><figcaption>FIGURE 4.10 – (a) Un espace cubique de BÉZIER. (b) Un espace simploïdal de BÉZIER dans lequel un simploïde de type (2,1) est assemblé à un tétraèdre le long d'une de ses faces triangulaires, et à un cube le long d'une de ses faces carrées.</figcaption></figure>

<figure><img src="image_90.png" /><figcaption>FIGURE 4.11 – Le domaine de l'espace paramétrique du prisme est le produit de deux domaines indépendants correspondant à la structure du prisme. À chaque point $(u^1, u^2)$ de l'espace des paramètres correspond un point du simploïde de BÉZIER.</figcaption></figure>

### 4.3.3.1 Représentation d'un espace simploïdal de BÉZIER

Comme décrit pour les espaces simpliciaux de BÉZIER, il est possible de décrire un espace simploïdal de BÉZIER par l'ensemble des simploïdes principaux où chacun stocke l'ensemble de ses points de contrôle. Cette approche présente les mêmes inconvénients.

Il est également possible ici de répartir l'ensemble des points de contrôle d'un simploïde de BÉZIER sur lui-même et son bord. Plus généralement, les espaces simploïdaux de BÉZIER ont une structure d'ensemble semi-simploïdal. On retrouve ici encore cette struc-turation au niveau des *n*-uplets de multi-indices qui numérotent les points de contrôle des simploïdes de BÉZIER. Cette correspondance illustrée sur la figure 4.8) permet en particulier d'associer à chaque simploïde de BÉZIER ses points de contrôle propres (*i*. *e*. qui ne contiennent aucun 0 dans tout le *n*-uplet) et de reconstruire l'ensemble de ses points de contrôle en utilisant les indices des opérateurs de face, en procédant de la même manière que pour les ensembles semi-simpliciaux sur chaque composante du *n*-uplet de
multi-indices.

Par exemple, soit $\sigma$ un simploïde de BÉZIER de type $(a_1, \dots, a_n)$ et $\{P_{\alpha^1, \dots, \alpha^n}\}$ l'ensemble de ses points de contrôle. L'ensemble des points de contrôle de $\sigma$ tels que $\alpha_j^i = 0$ définit le simploïde de BÉZIER correspondant à sa face $d_j^i$. Par exemple sur la figure 4.8b, si $\sigma$ désigne le prisme, alors l'ensemble des points de contrôle $P_{\alpha^1, 04}$ définit sa face triangulaire $d_0^2$ située au premier plan.

D'un point de vue pratique, de manière analogue à ce qui a été vu pour les ensembles semi-simpliciaux, l'ensemble des points de contrôles propres de chaque simploïde peut être stocké dans un **tableau simploïdal** selon l'ordre lexicographique des *n*-uplets de multi-indices [DeRose 1993]. Par exemple, soit $P = \{P_{(\alpha^1, \dots, \alpha^n)}\}$ l'ensemble des points de contrôle d'un simploïde de BÉZIER de type $(a_1, \dots, a_n)$ et de degré $(d_1, \dots, d_n)$. Si $n=1$, alors le simploïde correspond à un simplexe, et $P$ est stocké dans un tableau simplicial. Si $n > 1$, il faut commencer par stocker tous les points de contrôle d'un simploïde de type $(a_2, \dots, a_n)$ de degré $(d_2, \dots, d_n)$ pour chaque multi-indice de $\Gamma_{d_1}^{a_1}$ précédant $\alpha^1$. Ensuite, le point $P$ peut être stocké comme s'il s'agissait d'un simploïde de BÉZIER de type $(a_2, \dots, a_n)$ et $(d_2, \dots, d_n)$, indicé par le *n*-uplet de multi-indices $(\alpha^2, \dots, \alpha^n)$.

### 4.3.3.2 Opérations de construction

Comme nous l'avons vu au chapitre 2, les opérations de construction de base pour les ensembles semi-simploïdaux sont le produit cartésien et l'identification. Pour chacune de ces opérations, les positions des points de contrôle des simploïdes impactés par les opérations doivent être calculées. Notons que l'opération de cône simploïdal n'est pas définie sur les ensembles semi-simploïdaux

**produit cartésien** Chaque point de contrôle $P_{\alpha^1, \dots, \alpha^p, \alpha^{p+1}, \dots, \alpha^{p+q}}$ d'un simploïde de BÉZIER $\tau$ résultant du produit cartésien de deux simploïdes $\sigma$ et $\mu$ de types respectifs $(a_1, \dots, a_p)$ et $(b_1, \dots, b_q)$ est obtenu à partir du point $P_{\alpha^1, \dots, \alpha^p}$ de $\sigma$ et du point $P_{\alpha^1, \dots, \alpha^q}$ de $\mu$. On peut par exemple utiliser une somme de MINKOWSKI. Par exemple sur la figure 4.8, le point de contrôle $P_{111,22}$ du prisme est obtenu à partir du point $P_{111}$ du triangle et du point $P_{22}$ de l'arête.

**identification**

### 4.3.4 Ensembles simpliciaux

Nous avons vu que d'un point de vue structurel, si un *p*-simplexe $\mu = \tau d_j$ est dégénéré, i. e. $\mu = \sigma s_i$, alors $\mu$ n'intervient pas dans le bord de $\tau$. Par exemple la figure 4.12 illustre la différence entre un ensemble semi-simplicial contenant une boucle, et un ensemble simplicial où la boucle est dégénérée. Ces deux objets n'ont pas la même homologie $H_1$ : celle de l'ensemble semi-simplicial est isomorphe à $\mathbb{Z}$ et celle de l'ensemble simplicial est triviale.

Pour que la forme géométrique associée à un ensemble simplicial $S$ corresponde bien à la structure de $S$, la forme géométrique associée de $\mu$ doit être égale à celle de $\sigma$. D'un
point de vue pratique, seuls les simplexes non dégénérés et leurs faces, dégénérées ou non, sont utiles pour définir la forme d'un ensemble simplicial. On peut donc explicitier uniquement ces simplexes ; les autres simplexes dégénérés peuvent être gérés de manière implicite et peuvent être obtenus, si nécessaire, en appliquant une suite d'opérateurs de dégénérescence à partir d'un simplexe non dégénéré.

<figure><img src="image_91.png" /><figcaption>FIGURE 4.12 – a) Un ensemble semi-simplicial, (b) un espace triangulaire de BÉZIER associé à (a). (c) 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$), (d) Un espace triangulaire de BÉZIER associé à (c) : la forme de l'arête dégénérée est définie par celle du sommet de son bord. L'arête $\mu$ est le seul simplexe dégénéré qui apparaît dans le bord d'un simplexe non dégénéré.</figcaption></figure>

On peut également associer un simplexe de BÉZIER à tout *i*-simplexe $\sigma$ d'un ensemble simplicial et plus généralement un espace triangulaire de BÉZIER à tout ensemble simpli- cial [Peltier 2018]. Les relations entre les points contrôle de $\sigma$ et ceux de $\sigma d_j$ sont celles décrites pour les ensembles semi-simpliciaux, *i. e.* l'ensemble des points de contrôle $P_\alpha$ de $\sigma$ tels que $\alpha_j = 0$ sont les points de contrôle de $\sigma d_j$. Si $\mu$ est dégénéré, *i. e.* $\mu = \sigma s_j$ alors la Propriété 5 [Peltier 2018] doit être satisfaite afin de garantir que la forme de $\mu$ soit bien celle de $\sigma$ : cf. Figure 4.13.

**Propriété 5** Soient $\sigma$ un *i*-simplexe, et $B_\sigma$ le simplexe de BÉZIER qui lui est associé, défini par les points de contrôle $\{P_\alpha\}$. Soient $\mu = \sigma s_j$, $0 \le j \le i$, et $B_\mu$ le simplexe de BÉZIER qui lui est associé, défini par les points de contrôle $\{P_{\alpha'}\}$. Si tous les points de contrôle $P_{\alpha'_0 \cdots \alpha'_j \alpha'_{j+1} \cdots \alpha'_{i+1}}$ tels que :

- $\alpha'_k = \alpha_k$, pour $0 \le k \le j-1$,

- $\alpha'_j + \alpha'_{j+1} = \alpha_j$,

- $\alpha'_k = \alpha_{k-1}$, pour $j+2 \le k \le i+1$

sont égaux à $P_{\alpha_0 \cdots \alpha_i}$, alors $B_\sigma = B_\mu$. $\square$

On peut montrer de manière directe que si la propriété est vérifiée, alors à tout point $P(u'_0, \dots, u'_{i+1})$ de $B_\mu$ correspond le point $P(u_0, \dots, u_i)$ de $B_\sigma$, où $u'_k = u_k$ pour tout $0 \le k \le j-1$, $u'_j + u'_{j+1} = u_j$ et $u'_k = u_{k-1}$ pour tout $j+2 \le k \le i+1$. Pour cela il suffit de montrer que pour tout $P_\alpha$, on a :
$$ \binom{d}{\alpha} u_0^{\alpha_0} \cdots u_j^{\alpha_j} \cdots u_i^{\alpha_i} = \sum_{\alpha'_j + \alpha'_{j+1} = \alpha_j} \binom{d}{\alpha'} u_0^{\prime \alpha'_0} \cdots u_j^{\prime \alpha'_j} u_{j+1}^{\prime \alpha'_{j+1}} \cdots u_{i+1}^{\prime \alpha'_{i+1}} $$

Ce qui revient à montrer que l'on a bien l'égalité suivante, qui se montre directement en appliquant la formule du binôme de NEWTON :

$$ \binom{d}{\alpha} u_0^{\alpha_0} \cdots (u'_j + u'_{j+1})^{\alpha_j} \cdots u_i^{\alpha_i} = \sum_{\alpha'_j + \alpha'_{j+1} = \alpha_j} \binom{d}{\alpha_0 \cdots \alpha'_j \alpha'_{j+1} \cdots \alpha_i} u_0^{\alpha_0} \cdots u_j^{\alpha'_j} u_{j+1}^{\alpha'_{j+1}} \cdots u_i^{\alpha_i} $$

<figure><img src="image_92.png" /><figcaption>FIGURE 4.13 – Illustration de la Propriété 5. (a) Si tous les points de contrôle de l’arête dégénérée sont égaux à celui du sommet, alors les deux simplexes de BÉZIER correspondants sont égaux. (b) Une arête et ses deux triangles dégénérés. Si tous les points de contrôle d’un triangle alignés verticalement correspondent au point de contrôle de l’arête dans l’alignement vertical, alors les simplexes de BÉZIER correspondant sont égaux.</figcaption></figure>

D'un point de vue pratique, seuls les points de contrôle des simplexes non dégénérés sont donc nécessaires pour associer un espace triangulaire de BÉZIER à un ensemble simplicial. L'ensemble des points de contrôle de tout simplexe, qu'il soit dégénéré ou non, peut être retrouvé à partir de ses points de contrôle propres et des relations correspondant à ses opérateurs de face et de dégénérescence. En particulier, si un simplexe est dégénéré, alors ses points de contrôle peuvent être déduits du simplexe non dégénéré de plus grande dimension de son bord, en utilisant la Propriété 5.

On notera qu'ici encore, on suppose que tous les simplexes de l'ensemble simplicial sont de même degré, mais il est tout à fait possible d'assembler des simplexes de BÉZIER de degrés différents en utilisant des techniques d'élévation de degré.
4.3.4.1 Produit cartésien

La figure 4.14 reprend l'exemple de la figure 2.45) en représentant les points de contrôle des différents simplexes mis en jeu. Comme toutes les faces de tous les simplexes non dégénérés sont également non dégénérés, cet exemple illustre également un produit cartésien d'ensemble semi-simpliciaux.

<figure><img src="image_93.png" /><figcaption>FIGURE 4.14 – Produit cartésien de deux espaces triangulaires de BÉZIER. Les simplexes dégénérés et leurs points de contrôle sont explicités sur la figure, mais peuvent être manipulés de manière implicite. (b) L'espace triangulaire de BÉZIER résultant de (a) correspond à un ensemble semi-simplicial.</figcaption></figure>

[Lang 1997] proposent de calculer la position des points de contrôle d'un simplexe $\sigma \times \mu$ par combinaisons linéaires de ses sommets. Cette méthode dégénère la géométrie d'un simplexe qui serait plusieurs fois incident à son bord.

Par définition, $\sigma$, $\mu$ et $\sigma \times \mu$ ont même dimension. La propriété 5 permet d'associer chaque point de contrôle d'un simplexe dégénéré à un point de contrôle d'un simplexe de son bord. On peut donc calculer les points de chaque simplexe $\sigma \times \mu$ en utilisant par exemple une somme de MINKOWSKI : chaque point $P_\alpha$ de $\sigma \times \mu$ correspond à la somme du point $P_\alpha$ de $\sigma$ et du point $P_\alpha$ de $\mu$.

4.3.5 Ensembles simploïdaux

Concernant les ensembles simploïdaux, l'approche est similaire : on sait associer un simploïde de BÉZIER à tout simploïde. Pour associer un espace simploïdal de BÉZIER à tout ensemble simploïdal $S$ et garantir que la structure de $S$ soit bien respectée, la propriété suivante doit être vérifiée [Peltier 2018] :

**Propriété 6** Soit $S = (K, (d_j^i), (s_l^k))$ un ensemble simploïdal, soit $\sigma$ un simploïde de type $(a_1, ..., a_n)$ de $K$, soit $P^{\sigma} = \{P_{(\alpha^1, ..., \alpha^n)}, \alpha^i \in \Gamma_{d_i}^{a_i}, 1 \le i \le n\}$ l'ensemble de ses points de contrôle, et $B_{\sigma}$ le simploïde de BÉZIER qui lui est associé.
(1) Soit $\mu = \sigma d_j^i$, soit $P^\mu$ son ensemble de points de contrôle, et soit $B_\mu$ le simploïde de BÉZIER associé à $\mu$.

Si tout point de contrôle $P_{(\alpha^1, \dots, \alpha^i, \dots, \alpha^n)}^\sigma$ est égal à :

- $P_{(\alpha^1, \dots, \alpha^{i-1}, \alpha'^i, \alpha^{i+1}, \dots, \alpha^n)}^\mu$, où $\alpha'^i = \alpha_0^i \cdots \alpha_{j-1}^i \alpha_{j+1}^i \cdots \alpha_{a_i}^i$ si $a_i > 1$ et $\alpha_j^i = 0$,

- $P_{(\alpha^1, \dots, \alpha^{i-1}, \alpha^{i+1}, \dots, \alpha^n)}^\mu$, si $a_i = 1$,

alors $B_\sigma(u) = B_\mu(u')$ où :

- $u = (u^1, \dots, u^n)$,

- $u' = (u^1, \dots, u^{i-1}, u'^i, u^{i+1}, \dots, u^n)$,

où $u'^i = (u_0^i, \dots, u_{j-1}^i, u_{j+1}^i, \dots, u_{a_i}^i)$, si $a_i > 1$ et $u_j^i = 0$,

- $u' = (u^1, \dots, u^{i-1}, u^{i+1}, \dots, u^n)$ si $a_i = 1$.

(2) Soit $\mu = \sigma s_j^i$, soit $P^\mu$ l'ensemble de ses points de contrôle, et soit $B_\mu$ le simploïde de BÉZIER associé à $\mu$ :

- si $j \ge 0$: tous les points de contrôle $P_{(\alpha^1, \dots, \alpha'^i, \dots, \alpha^n)}^\mu$ sont égaux au point de contrôle $P_{(\alpha^1, \dots, \alpha^i, \dots, \alpha^n)}^\sigma$, où $\alpha_k'^i = \alpha_k^i$ pour $k < j$, $\alpha_j'^i + \alpha_{j+1}^i = \alpha_j^i$, et $\alpha_k'^i = \alpha_{k-1}^i$ pour $k > j + 1$,

- si $j = -1$: tous les points de contrôle $P_{(\alpha^1, \dots, \alpha^i, \alpha'^{i+1}, \alpha^{i+1}, \dots, \alpha^n)}^\mu$ de $\sigma s_{-1}^i$ sont égaux au point de contrôle $P_{(\alpha^1, \dots, \alpha^n)}^\sigma$, où $\alpha'^{i+1} \in \Gamma_{d_{i+1}'}^1$,

alors $B_\sigma = B_\mu$

□

Par exemple, la figure 4.15 représente des simploïdes de BÉZIER de type (2,1) dont certaines faces sont dégénérées (en rouge). La figure 4.16 illustre un ensemble simploïdal de BÉZIER, certains simploïdes sont dégénérés (en rouge).

<figure><img src="image_94.png" /><figcaption>FIGURE 4.15 – (a) – (c) Un prisme dont une partie du bord, représentée en rouge, est dégénérée. (a) Une face carrée est dégénérée en une arête. (b) Une arête est dégénérée en un sommet. (c) Une face carrée est dégénérée en un sommet.</figcaption></figure>

Une conséquence directe de la Propriété 6, est qu'en pratique, il suffit que chaque simploïde non dégénéré d'un ensemble simploïdal connaisse ses points de contrôles propres pour pouvoir reconstruire l'espace simploïdal de BÉZIER entièrement. L'ensemble des points de contrôle de tout simploïde $\sigma$ peut être reconstitué en utilisant la Propriété 6 et les indices des opérateurs de face :

- si $\sigma$ est un sommet, le point de l'espace correspondant à son point de contrôle lui est associé ;
— sinon :

— si $\sigma$ est non dégénéré, l'ensemble de ses points de contrôles peut être reconstruit à partir de ses points de contrôles propres et ceux des simploïdes de son bord, en utilisant les indices de ses opérateurs de face;

— si $\sigma$ est dégénéré, il est nécessaire de reconstituer l'ensemble des points du simplexe non dégénéré dont il est issu, en utilisant les indices des opérateurs de dégénérescence ainsi que la Propriété 6, qui lie les points de contrôle de $\sigma$ et ceux de $\sigma s_j^i$.

<figure><img src="image_95.png" /><figcaption>FIGURE 4.16 – Un ensemble simploïdal plongé dans un espace simploïdal de BÉZIER.</figcaption></figure>

Comme pour les ensembles simpliciaux, la forme géométrique associée à un ensemble simploïdal est entièrement définie par l'ensemble des simploïdes non dégénérés comme le montrent les figures 4.15 et 4.16.

Notons que deux simploïdes $\sigma$ et $\mu$ peuvent avoir des formes similaires, mais des types différents et dans ce cas, ils ne pourront pas être identifiés. Cela se produit en particulier lorsque :

— le type de $\sigma$ est une permutation du type de $\mu$. Par exemple, un simploïde de type (1, 2) et un simploïde de type (2, 1) ont des formes de prisme, mais leurs types sont différents ; ils n'ont pas les mêmes opérateurs de face (le produit cartésien n'est pas commutatif) ;

— un simploïde possède une face dégénérée. Par exemple, sur la figure 4.17a, les deux faces ont bien une forme triangulaire, mais correspondent à un simploïde de type (1, 1) dont une arête est dégénérée pour l'une, et à un simploïde de type (2) pour l'autre. Comme le montrent les Figures 4.17b et 4.17c, les structures de leurs points de contrôle sont différentes.
<figure><img src="image_96.png" /><figcaption>FIGURE 4.17 – (a) Deux faces de forme triangulaire, leur structure n’est pas la même. La structure des points de contrôle d’un carreau de BÉZIER dont une arête est dégénérée (b) est différente de celle d’un triangle de BÉZIER (c).</figcaption></figure>

### 4.3.5.1 Cône simploïdal

Par définition, le résultat d'une opération de cône simploïdal contient des simploïdes dégénérés (cf. section 2.5.2.2 page 62). Par exemple, la pyramide à base carrée représentée sur la figure 4.17a est obtenue par une opération de cône sur un simploïde de type (1, 1). Il s'agit d'un cube dont une face carrée est dégénérée en un sommet. Tous les points de contrôle de cette face sont dont égaux à l'unique sommet de son bord, représenté en rouge. Les autres points de contrôle peuvent être obtenus par interpolation à partir du point correspondant à ce sommet, et des points du simploïde de type (1, 1) sur lequel l'opération a été appliquée.

### 4.3.6 Structures cellulaires

Concernant les cartes combinatoires, qui permettent la multi-incidence, il est intéressant de pouvoir associer une géométrie courbe à chaque cellule. Il n'existe pas de lien aussi fort que ceux présentés pour les structures simpliciales et simploïdales avec les espaces de BÉZIER. De plus à notre connaissance, la plupart des modeleurs cellulaires visent à générer des maillages, et sont basés sur des plongements linéaires.

Dans [Bechmann 1997], des liens structurels ont été mis en avant entre les chaînes de cartes et les carreaux de GREGORY-BÉZIER cubiques et triangulaires de degré 3. De manière informelle, les carreaux de GREGORY-BÉZIER de degré 3 sont définis par 4 courbes de BÉZIER ayant chacune leurs points de contrôle. Comparé aux carreaux de BÉZIER classiques, certains points sont "dupliqués" afin de mieux contrôler les assemblages au niveau des coins des carreaux. Un carreau de GREGORY-BÉZIER de dimension 2 et degré 3 possède 20 points de contrôle, soit exactement le nombre de brins d'une chaîne de cartes représentant une face carrée et son bord. Les auteurs proposent d'associer un point de contrôle à chaque brin. La géométrie de chaque cellule principale de la chaîne de carte est ainsi définie de manière paramétrique. Si cette solution semble s'étendre de manière directe en dimension supérieurs pour des cellules cubiques et triangulaires de degré 3,
l'extension à des cellules quelconques ou à d'autres degrés ne semble pas immédiate.

En CAO, une technique classique consiste à utiliser des morceaux de surfaces découpées, ou *trimmées* dans des espaces paramétriques de simplexes ou des carreaux de BÉZIER. Par exemple, en découpant un pentagone dans l'espace paramétrique d'un triangle de BÉZIER, on obtient un morceau de surface *trimmé*, que l'on peut associer à une 2-cellule. Un des problèmes majeurs est le maintien de la structure au sein de l'objet géométrique. En effet, si dans la structure combinatoire, deux cellules partagent une arête, alors on souhaite que l'intersection des deux cellules *trimmées* correspondantes s'intersectent en une courbe. Généralement, ce problème est traité par approximation d'une courbe. Il serait bien évidemment plus intéressant de maintenir la structure dans le modèle géométrique, comme dans les espaces de BÉZIER.

## 4.4 Application à la modélisation d'objets tubulaires

Cette section se base sur nos travaux [Peltier 2021] effectués en collaboration avec GÉRALDINE MORIN, et concerne la modélisation d'objets tubulaires volumiques paramétriques à partir d'un squelette, que l'on appelle aussi *dessin en bâtons*. Ces travaux montrent un cas d'application des ensembles semi-simploïdaux, tirant parti à la fois de la structure combinatoire et de leur plongement "naturel" dans des espaces de BÉZIER.

### 4.4.1 Contexte et objectifs

Les modèles paramétriques surfaciques basés sur les espaces de BÉZIER, ou d'autres espaces comme les B-splines ou les NURBS, sont les modèles standards utilisés dans le noyau des systèmes CAO [Farin 2002]. Ils offrent la possibilité d'étudier et d'assurer une continuité lisse pour les surfaces géométriques 3D, tout en offrant un contrôle intuitif et un échantillonnage à la carte. La version linéaire par morceaux de ces modèles, ou maillages, est la représentation la plus usuelle des objets volumiques, et sont l'entrée naturelle des pipelines de rendu et le support du plaquage de texture. Ils sont utilisés dans des applications qui ne requièrent pas de surfaces lisses, comme par exemple dans les jeux. Plus récemment, l'analyse isogéométrique (IGA) [Cottrell 2009, Hughes 2005] propose d'utiliser directement le modèle géométrique pour effectuer des calculs physiques dans le cadre de la Fabrication Assistée par Ordinateur.

Lorsque les propriétés physiques d'un objet volumique doivent être contrôlées et analysées, comme pour l'impression 3D, la représentation d'un volume par son bord ne suffit pas et une subdivision volumique explicite doit être utilisée [Livesu 2017]. Des méthodes discrètes générant des maillages volumiques ont été proposées. Par exemple [Lyon 2016] propose d'extraire un maillage volumique à partir de sa surface. [Massarwi 2016] propose une représentation volumique paramétrique continue et lisse basée sur des B-splines; ils considèrent le volume issu de produits tensoriels et se basent sur des techniques de trimming. Ces modèles volumiques différentiables peuvent être utilisés comme support pour des calculs mécaniques [Massarwi 2019]).
Les squelettes offrent une représentation intuitive, simplifiée et de dimension réduite d'un objet 3D [Tagliasacchi 2016]. Ils sont donc intéressants pour la reconstruction de formes (e.g. [Sundar 2003]), la conception de formes, comme ébauche, et pour l'animation (e.g. [Raptis 2011]). Combler le fossé entre les squelettes et les modèles de surfaces correspondants a été traité par différents travaux [Bærentzen 2012, Usai 2016, Panotopoulou 2018, Fuentes Suárez 2018]. [Livesu 2016] et [Viville 2021] généralisent ces approches pour calculer un maillage volumique d'hexaèdres à partir d'un squelette.

La figure 4.18 illustre les différentes étapes du processus.

<figure><img src="image_97.png" /><figcaption>FIGURE 4.18 – Un objet tubulaire volumique paramétrique construit à partir d'un squelette. (a) En entrée : un dessin en bâtons modélisé par un ensemble semi-simplicial de dimension 1, dont la forme est décrite par un assemblage de courbes de BÉZIER. (b) Construction des jonctions en chaque sommet du graphe. (c) Construction et assemblage des branches volumiques sur les jonctions. (d) Résultat du processus : un objet tubulaire volumique paramétrique lisse par morceaux.</figcaption></figure>

Par rapport aux travaux de [Livesu 2017] ou [Viville 2021] qui proposent de calculer un modèle linéaire par morceaux (maillage volumique) à partir d'un squelette, nous calculons un modèle lisse basé sur des éléments polynomiaux. De plus, alors que [Massarwi 2019] utilise des techniques de trimming pour calculer un modèle de volume lisse, nous utilisons les ensembles semi-simploïdaux afin d'assurer la cohérence topologique du domaine paramétrique des volumes de BÉZIER. Notre travail généralise et étend aux volumes paramétriques lisses les résultats présentés dans [Panotopoulou 2018], où des maillages de carreaux de surfaces sont calculés.

### 4.4.2 Branches – Jonctions

Intuitivement, la création de l'objet volumique consiste à "épaissir" le squelette 1D en un assemblage de volumes. On associe à chaque arête A du squelette, une **branche volumique** qui "suit" la courbe associée à A, et on associe une **jonction** à chaque sommet
<figure><img src="image_98.png" /><figcaption>FIGURE 4.19 – (a) Chaque branche volumique est un assemblage symétrique de quatre prismes de BÉZIER ; le bord de chaque branche est composé de quatre carreaux de BÉZIER (on ne considère pas les extrémités). (b) Mise en évidence de la structuration symétrique des prismes, qui se retrouve sur les kites. Les opérateurs de face se déduisent de la couleur des sommets.</figcaption></figure>

du squelette. L'objet volumique tubulaire est alors défini par un ensemble de branches qui sont assemblées de manière continue au niveau des jonctions. Dans [Panotopoulou 2018], toutes les branches ont la même structure régulière : la surface d'une branche est constituée de quatre faces carrées, ou **quads**. Une régularité similaire est fournie par le modèle de volume proposé : chaque branche est un assemblage de quatre prismes, collés le long de faces carrées : les quatre prismes sont disposés symétriquement autour de l'axe de la branche, correspondant au squelette. La même structure composée de quatre triangles se retrouve aux extrémités des branches et au niveau des jonctions. On appelle cet assemblage de quatre triangles un **kite** : cf. figure 4.19b. Une jonction est définie comme un assemblage de kites, ou **kite folio**.

Cette symétrie permet d'assembler les branches entre elles au niveau des jonctions en respectant les couleurs des sommets, *i.* *e*. les opérateurs de face des triangles. En effet, au niveau d'un **kite**, les couleurs des sommets sont déduits des indices des opérateurs de face. Une branche peut être adjacente à quatre autres branches au maximum (via les quatre triangles du **kite**), et une jonction peut supporter autant de branches que l'on souhaite : cf. figure 4.20.

### 4.4.3 Pavage quad de la sphère

Un des principaux enjeux dans le processus est la création des jonctions. Sur le squelette, on considère une sphère unitaire autour de chaque sommet *v* de degré *n* ≥ 2 : chaque arête incidente à *v* est associée à une courbe de BÉZIER, et sa tangente en *v* définit un point sur la sphère. On appelle ces points les **points verts**. Nous construisons
<figure><img src="image_99.png" /><figcaption>FIGURE 4.20 – (a) Chaque jonction est un assemblage de kites, chaque kite est le support d'une branche. (b) Six branches sont assemblées au niveau d'une jonction. Chaque branche partage un quart de kite avec quatre branches voisines distinctes. Toutes les branches ont comme sommet commun le point vert de la jonction.</figcaption></figure>

une quadrangulation où chaque quad correspond à un point vert, en considérant chaque branche de manière incrémentale. Une fois la quadrangulation établie, le kite folio est créé et les branches sont assemblée, chacune sur son kite. La figure 4.21 illustre le processus de création d'une jonction.

Les quadrangulations que nous considérons sont des **quadrangulations simples** sur la sphère correspondant à une classe de graphes simples planaires, c'est-à-dire sans boucle, et tel que deux arêtes distinctes ne peuvent pas avoir les mêmes sommets extrémités. Les quadrangulations simples sur des surfaces ont été étudiées dans [Nakamoto 1996].

[Batagelj 1989] étudie les classes de quadrangulation calculées de manière inductive, i. e. en partant d'une configuration initiale en ajoutant des quads. Une approche similaire est menée dans [Brinkmann 2005], où des opérations d'**expansion** et leurs inverses, les **réductions de face** mettent en jeu des sommets de degré minimal 2 ou 3, correspondant à un cas particulier de **contraction de face** définies dans [Nakamoto 1996]. De manière simplifiée, ces opérations consistent à ajouter ou supprimer des quads en préservant une quadrangulation.

L'approche suivie dans [Panotopoulou 2018] est basée sur la division, ou *split* d'un quad en deux, correspondant à une opération d'expansion de [Brinkmann 2005]. Dans la quadrangulation résultante, au moins deux quads partagent 2 arêtes adjacentes. Cette approche ne permet donc pas d'obtenir des configurations où chaque branche est adjacente à quatre branches distinctes comme représenté sur la figure 4.20b. L'approche incrémentale suivie dans [Viville 2021] est basée sur l'utilisation de la triangulation de Delaunay calculée à partir de l'enveloppe convexe des points verts répartis sur la sphère. Le graphe corres-
<figure><img src="image_100.png" /><figcaption>FIGURE 4.21 – (a) – (c) Illustration de l’algorithme incrémental de quadrangulation de la sphère. À chaque étape, un point vert est ajouté, entraînant l’ajout d’un quad dans le pavage de la sphère. (d) La jonction est finalement créée en effectuant une opération de cône sur le graphe correspondant au pavage quad, avec comme nouveau sommet le centre de la sphère. Cette jonction correspond à la configuration représentée sur la figure 4.20b.</figcaption></figure>

pondant est ensuite modifié par des opérations de suppression et d'ajouts d'arêtes jusqu'à ce que chaque sommet soit de degré 4, obtenant ainsi le graphe dual de la quadrangulation.

Dans notre contexte, les opération d'expansion et de réduction de *quads* correspondent à ajouter ou supprimer une branche au niveau de la jonction. Nous avons défini des opérations d'ouverture et de fermeture correspondant à l'ajout et à la suppression d'un quad. Nos résultats sont similaires à ceux de [Brinkmann 2005], mais ils sont plus adaptés à des considérations géométriques. En particulier, nous avons établi et prouvé le Théorème 7 qui garantit que toute quadrangulation est atteignable en utilisant une suite d'opérations d'ouvertures. L'idée de la preuve est de partir d'une configuration quelconque, et de montrer qu'il existe toujours une suite de fermetures permettant d'obtenir la quadrangulation canonique de la sphère à deux quads. Les détails de la preuve sont disponibles dans [Peltier 2021].

**Théorème 7** *Toute quadrangulation simple de la sphère, contenant $n \ge 2$ quads, peut être obtenue à partir de la quadrangulation simple canonique composée de 2 quads, par application d'une suite de $n - 2$ opérations d'ouvertures.*

L'algorithme que nous proposons est incrémental : il considère les points verts un par un (cf. figure 4.21). En pratique, nous travaillons sur le graphe dual de la quadrangulation, où chaque sommet correspond à un point vert ; nous maintenons le graphe dual où chaque sommet est de degré 4.

Le graphe dual est représenté par une carte combinatoire de dimension 2, ce qui permet de savoir, à chaque étape, dans quelle face se trouve le nouveau point vert à traiter.

À partir de ce graphe dual, les positions géométriques des points rouges et bleus de chaque quad sont calculés via une heuristique, définissant ainsi la quadrangulation, que nous modélisons par un ensemble semi-simplicial de dimension 1 où les opérateurs de face de chaque arête sont déduits de la couleur rouge ou bleue des sommets. La jonction est
finalement créée en effectuant une opération de cône sur la quadrangulation, avec comme
nouveau sommet le centre de la sphère : cf. figure 4.21d.

Comme chaque arête de la quadrangulation est partagée par exactement deux quads,
chaque triangle d'une jonction est commun à exactement deux kites, correspondant à deux
branches adjacentes. Notons que la géométrie de chaque arête de la quadrangulation est
une géodésique, c'est-à-dire un arc de **grand cercle** (i. e. dont le plan support contient le
centre de la sphère). Plus précisément, les deux sommets d'un arc passent par un unique
grand cercle<fnref n="1" />, définissant ainsi deux arcs possibles. Dans certaines configurations, comme
par exemple lorsque toutes les branches ont des directions proches (cf. figure 4.22), certains
arcs ont une longueur supérieure à π. Le choix de l'arc associé à chaque arête est traitée
dans notre algorithme au moment de l'ajout de chaque point vert.

<figure><img src="image_101.png" /><figcaption>FIGURE 4.22 – (a) – (c) Une jonction composée de quatre branches ayant des directions proches. La quadrangulation de la sphère est donc composée de quatre quads. (d) – (f) En changeant les directions des arêtes du squelette, la jonction obtenue est lissée.</figcaption></figure>

4.4.4 Géométrie des branches

Une fois l'ensemble des jonctions créé, il reste à définir la géométrie des branches et
à les assembler au niveau des jonctions sur les kites correspondants, en respectant les

<footnote n="1">1. Sauf cas particulier de deux points antipodaux qui appartiennent à une infinité de grands cercles.</footnote>
couleurs des sommets.

Les points de contrôle de chaque kite de branche sont placés sur les plans correspondants aux quatre triangles de chaque kite de jonction. Il reste alors à positionner les points de contrôle internes de chaque branche afin de contrôler les volumes de BÉZIER. La courbe centrale de chaque branche correspond à celle du squelette. Nous prenons deux critères en considération pour définir la géométrie des branches :

- *minimisation des twists*: des twists peuvent se produire lorsque la section d'une branche tourne autour de la courbe centrale,

- *préservation de la section*: le long d'une branche, la surface correspondant à sa section dépend des points de contrôle intermédiaires. L'objectif est garantir une épaisseur régulière sur toute la longueur de la branche.

La première étape est la mise en correspondance des points rouges et bleus des kites des branches avec les points rouges et bleus des kites des jonctions correspondantes. Afin de minimiser les twists le long de chaque branche, nous nous sommes basés sur la méthode utilisée dans [Panotopoulou 2018] utilisant l'algorithme de *minimisation de rotation des frames* (*rotation minimizing frames*, ou RMF) proposé par [Wang 2008]. Au niveau de chaque jonction, nous choisissons l'appariement entre le kite de la branche et le kite correspondant de la jonction minimisant l'angle de rotation entre les deux kites. La figure 4.23 illustre deux appariements possibles entre un kite d'une branche et celui de sa jonction. L'appariement représenté en (a) minimise le twist de la branche. Dans la configuration (c) aucun appariement n'est significativement meilleur que l'autre (cas d'un twist à 90°). Dans ce cas, on permute les couleurs rouges et bleues de toute la jonction. Bien entendu, cette permutation des couleurs n'est parfois plus possible lorsque l'objet tubulaire présente des cycles de branches.

<figure><img src="image_102.png" /><figcaption>FIGURE 4.23 – Appariement du kite d'une branche avec le kite d'une jonction. L'appariement (a) minimise le twist comparé à l'appariement (b). Lorsque la configuration (c) se présente, on échange les couleurs rouge/bleu de la jonction lorsque cela est possible, afin de se retrouver dans la configuration (a).</figcaption></figure>

À ce stade, les points de contrôle des extrémités des branches sont positionnés selon les kites, et les points de contrôle de la courbe de BÉZIER centrale *c* d'une branche sont ceux de la courbe correspondant dans le squelette.
Afin d'éviter des aplatissements de la branche et préserver son épaisseur, les points de contrôle internes des volumes doivent être placés sur des plans orthogonaux à la courbe. Notons que l'algorithme de RMF est a priori défini sur la courbe elle-même et non pas pour ses points de contrôle. Néanmoins, l'algorithme de double réflection [Wang 2008] nécessite en entrée uniquement la tangente en un point afin de calculer la *frame* locale basée sur un plan orthogonal à ce point. Nous avons donc besoin d'obtenir une tangente en chaque point de contrôle interne. Pour cela, nous utilisons le polygone de contrôle de la courbe *c*. Plus précisément, le polygone de contrôle d'une courbe de BÉZIER *c* de degré *d* définie à partir de *d* + 1 points de contrôles converge de manière lisse vers la courbe [Morin 2001], mais seulement *d* tangentes de contrôle sont définies par le polygone de contrôle. Ces *d* tangentes définissent les points de contrôle de l'hodographe de la courbe, *i. e.* la dérivée première de *c* qui est une courbe de BÉZIER de degré *d* − 1. Afin d'obtenir une tangente par point de contrôle de *c*, nous effectuons donc une élévation de degré de l'hodographe. Ainsi on peut déduire *d* + 1 tangentes de contrôle, et donc une *frame* par point de contrôle : cf. figure 4.24.

<figure><img src="image_103.png" /><figcaption>FIGURE 4.24 – (a) Le polygone de contrôle d'une courbe de BÉZIER de degré 3 définit trois vecteurs correspondant aux 3 points de contrôle de l'hodographe défini par une courbe de degré 2. (b) Élevation du degré de l'hodographe : 4 vecteurs définissent une courbe de degré 3. Le nouveau polygône de contrôle définit les tangentes (en rouge) en chaque point de contrôle de la courbe initiale (a).</figcaption></figure>

Les points de contrôle internes des branches sont ainsi interpolés entre les deux kites extrémités dans chaque *frame* locale au niveau de chaque point de contrôle de la courbe. En pratique, cela est fait pour chaque triangle de chaque kite. Au final, l'utilisation de ces frames locales permet de garantir une épaisseur globalement constante tout au long de la branche, cf : figure 4.25.

Les contraintes géométriques liées aux éventuelles intersections entre les branches ou auto-intersections ne sont pas traitées.

4.4.5 Résultats

La figure 4.26 montre des modèles d'objets tubulaires volumiques polynomiaux, obte-
nus avec notre méthode à partir de squelettes. Tous les exemples contiennent des cycles de
branches. Sur le premier exemple, tous les sommets du squelette sont de degré au plus 3. Le
deuxième et le troisième exemple présentent un noeud de degré 9 et plusieurs branches ont
<figure><img src="image_104.png" /><figcaption>FIGURE 4.25 – (a) – (b) En chaque point intermédiaire de la courbe directrice de la branche, les points de contrôles internes des branches sont positionnés en fonction des tangentes de contrôle.</figcaption></figure>

les mêmes extrémités. Le dernier exemple contient des branches dont les deux extrémités sont incidentes à une même jonction, ainsi que des courbes de différents degrés.

Bien que nous n'ayons pas d'objectif de performance, les temps de calculs sont les suivants :

— 750 ms pour la poubelle (première ligne),

— 117 ms pour le trèfle (deuxième ligne),

— 175 ms pour la pieuvre (troisième ligne)

— 80 ms pour le serpent (quatrième ligne).

4.5 Conclusion

Nous avons rappelé comment construire la réalisation géométrique des complexes simpliciaux abstraits et présenté celle des simplexes simploïdaux abstraits. Nous avons ensuite présenté deux approches permettant d'associer une forme à une structure :

— **plongements linéaires** : de manière générale, pour les structures ne présentant pas de multi-incidence comme les complexes simpliciaux, les complexes simploïdaux abstraits ou les *n*-surfaces, on peut associer une forme respectant la structure en définissant uniquement la position des sommets. La réalisation géométrique des complexes simpliciaux et simploïdaux abstraits permet une telle construction, dans un espace généralement trop grand. De manière générale, il faut s'assurer que les contraintes structurelles sont bien respectées, c'est-à-dire que si deux cellules géométriques s'intersectent, elles s'intersectent en une cellule correspondant à la structure.

— **plongements non linéaires** : les espaces paramétriques de BÉZIER permettent d'associer une forme courbe aux simplexes et aux simploïdes. L'ensemble des points de contrôle définissant un espace de BÉZIER simplicial (resp. simploïdal) est na-
turellement structuré en ensemble simplicial (resp. simploïdal). Si l'on souhaite préserver la structure sur l'objet géométrique afin d'obtenir un CW-complexe, il est là aussi nécessaire d'ajouter des contraintes géométriques sur les intersections ou auto-intersections des cellules.

Nous avons présenté un cadre applicatif utilisant les ensembles simploïdaux : la modélisation d'objets tubulaires volumiques paramétriques à partir de squelettes. La cohérence entre la structure du domaine paramétrique et la géométrie des objets tubulaires est garantie par l'utilisation des ensembles semi-simploïdaux. La géométrie des branches est contrôlée par la définition de *frames* orthogonales en chaque point de contrôle interne de la courbe guidant chaque branche.
<figure><img src="image_105.png" /><figcaption>FIGURE 4.26 – De gauche à droite : des squelettes définis par des assemblages de courbes de BÉZIER (en vert), les points de contrôle sont représentés en noir ; les maillages volumiques 3D correspondants ; un rendu de l'objet ; une seconde vue du même objet.</figcaption></figure>
<figure><img src="image_106.png" /></figure>
# Conclusion - Perspectives

## 5.1 Bilan

### Sommaire

<table><tr><td><strong>5.1 Bilan</strong></td><td><strong>135</strong></td></tr><tr><td>5.1.1 Structures combinatoires</td><td>135</td></tr><tr><td>5.1.2 Calcul de l'homologie</td><td>136</td></tr><tr><td>5.1.3 Objets géométriques</td><td>136</td></tr><tr><td><strong>5.2 Projet de recherche</strong></td><td><strong>137</strong></td></tr><tr><td>5.2.1 Structures combinatoires</td><td>137</td></tr><tr><td>5.2.2 Calcul de l'homologie</td><td>138</td></tr><tr><td>5.2.3 Objets géométriques</td><td>139</td></tr></table>

Nous avons présenté une vision de la modélisation géométrique à base topologique selon le triptyque *structures combinatoires*, *calcul de propriétés topologiques*, *objets géométriques*.

### 5.1.1 Structures combinatoires

Concernant les structures combinatoires, nous avons présenté une classification mettant en jeu différentes structures basées sur des cellules de différents types. Toutes les structures présentées 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.

Afin de présenter une classification complète, nous avons défini les complexes simploïdaux abstraits qui étendent les complexes simpliciaux abstraits, ainsi que la notion de celluloïde qui étend la notion de cellule aux structures simploïdales. Nous avons ainsi posé le cadre permettant de définir les structures combinatoires celluloïdales basées sur les cartes combinatoires ou les graphes d'incidence.

Nous avons enfin montré comment le mécanisme de dégénérescence permet la définition d'opérations de base : les ensembles simpliciaux permettent de définir l'opération de produit cartésien simplicial, les ensembles simploïdaux permettent de définir l'opération de cône simploïdal.

Dès que l'on souhaite représenter un objet subdivisé, il est important de choisir la structure la mieux adaptée au contexte dans lequel on souhaite se placer. Afin de pouvoir effectuer un choix adapté, il est essentiel de répondre aux questions suivantes :
— Quelles sont les cellules manipulées ? On choisira une structure simpliciale ou cu-
bique si les cellules sont régulières et toutes identiques, simploïdales si les cellules
sont régulières mais si plusieurs types de cellules sont nécessaire, cellulaires lorsque
les cellules sont "quelconques".

— Quelles sont les contraintes sur les assemblages ?

— Du point de vue de chaque cellule et son bord, si la multi-incidence est néces-
saire, ou si deux cellules peuvent avoir même bord, on choisira une structure
permettant de représenter des assemblages quelconques : un ensemble semi-
simplicial ou simplicial, un ensemble semi-simploïdal ou simploïdal, ou une carte
combinatoire ;

— du point de vue de l'assemblage global, si l'objectif est de se rapprocher au plus près des variétés, on utilisera une structure optimisée permettant de représenter une quasi-variété simpliciale, simploïdale ou cellulaire (Gcarte ou n-surface).

— Quelles sont opérations que l'on souhaite appliquer ? Excepté l'opération de cône
qui n'est pas définie pour les ensembles semi-simploïdaux, les opérations de cône,
de produit cartésien et d'identification sont définies pour chaque type de structure.

5.1.2 Calcul de l'homologie

Concernant le calcul de groupes d'homologie, nous avons rappelé les principes des méthodes globales basées sur l'étude des relations d'incidence entre cellules, via des réductions de matrices d'incidence. Les résultats classiques définis pour des CW-complexes ont été étendus pour les structures cellulaires dont le bord de chaque cellule a l'homologie d'une sphère.

Nous avons présenté des méthodes incrémentales permettant de déduire l'homologie
d'un objet résultant d'une opération :

— l'homologie d'un objet résultant d'un cône est triviale;

— l'homologie d'un objet résultant d'une identification ou d'une dégénérescence peut être calculée en utilisant le théorème des suites exactes courtes effectives;

— l'homologie d'un objet résultant d'un produit cartésien peut être calculée en utilisant la formule de KÜNNETH.

Les lemmes de perturbation *Easy* et *Basic* permettent de maintenir des équivalences
homologiques sur des structures cellulaires, en se basant sur leur définition constructive
utilisant les opérations de cône et d'identification cellulaire.

5.1.3 Objets géométriques

Concernant les aspects géométriques, nous avons présenté la réalisation géométrique canonique des complexes simpliciaux abstraits et des complexes simploïdaux abstraits.
De manière plus générale, un plongement linéaire peut être associé aux structures sans multi-incidence : la forme de chaque cellule est définie à partir de la position de l'ensemble de ses sommets. Ce type de plongement peut être utilisé pour tout type de structure, y
compris cellulaire. Dans ce cas, les objets doivent être suffisamment subdivisés afin de ne pas contenir de multi-incidence ; ils doivent de plus respecter certaines contraintes géométriques comme la planarité des faces ou l'absence d'intersection de cellules ne respectant pas la structure. Cela permet notamment de générer des maillages non dégénérés. Dans d'autres contextes, par exemple lorsque l'on représente des objets par des ébauches minimalistes, de la multi-incidence peut apparaître et ce type de plongement produit alors des cellules géométriques dégénérées.

Les espaces paramétriques de BÉZIER permettent d'associer une forme courbe aux simplexes et aux simploïdes. Plus généralement, nous avons montré comment les espaces de BÉZIER simpliciaux et simploïdaux sont naturellement structurés en ensembles simpliciaux et simploïdaux. La clé de cette structuration est la numérotation des points de contrôle utilisant les multi-indices. L'ensemble des points de contrôle d'un espace de BÉZIER peut ainsi être réparti sur un ensemble simplicial ou simploïdal, explicitant ainsi les relations d'incidence entre les cellules, tout en évitant de dupliquer de l'information.

Nous avons enfin présenté un cadre applicatif permettant de modéliser des objets tubulaires volumiques définis sur des espaces paramétriques de BÉZIER, dont la structure est contrôlée par un ensemble semi-simploïdal. Les objets tubulaires sont définis à partir de dessins en bâtons, ou squelettes $1D$. Le processus complet utilise différentes structures combinatoires plongées dans $\mathbb{R}^3$ : des ensembles semi-simpliciaux de dimension 1 pour représenter les squelettes, des cartes combinatoires $2D$ pour représenter les quadrangulations de sphères, des ensembles semi-simploïdaux de dimension 2 pour représenter les jonctions, et des ensembles semi-simploïdaux de dimension 3 pour modéliser les objets tubulaires. Nous avons proposé un algorithme incrémental de construction des jonctions, et prouvé que toutes les configurations topologiques d'agencement de branches sont gérées. Nous minimisons les effets de "twist", et une épaisseur globalement constante des branches est assurée par l'utilisation d'un algorithme de *rotation minimizing frames*.

# 5.2 Projet de recherche

## 5.2.1 Structures combinatoires

La classification présentée dans ce manuscrit ne met pas en évidence un manque no-
table de structure ou d'opérations, et les liens les différentes structures sont établis. Il
reste à formaliser les définitions des Gcartes simploïdales permettant de modéliser les
quasi-variétés celluloïdales, des chaînes de cartes celluloïdales permettant de modéliser
des assemblages quelconques de celluloïdes, et les CF-ordres simploïdaux. Il semble égale-
ment intéressant d'étudier des définitions alternatives des complexes simploïdaux abstraits
afin de répondre aux limitations présentées. Par exemple, on peut envisager d'utiliser un
ensemble de sommets non partitionné afin de gérer des simploïdes abstraits dégénérés.

Afin de finaliser ce travail de classification, il reste à établir des liens entre les structures
celluloïdales. En particulier : *la notion de chaînes de surface se généralise-t-elle au produit
cartésien ?* C'est-à-dire : *retrouve-t-on les propriétés de quasi-variétés cellulaires si l'on ne
considère que des CF-celluloïdes dont chaque composante correspond à un cône sur une
n-surface ?*
La définition des ensembles simpliciaux et simploïdaux, intégrant des opérateurs de dégénérescence, a permis en particulier la définition d'opérations de base : le produit cartésien simplicial, et le cône simploïdal.

Nous n'avons pas étudié la définition de structures cellulaires intégrant de la dégénérescence, car l'apport de telles structures ne nous semble pas pertinent. En effet, les opérations de base (cône, identification et produit cartésien) sont définies sur les structures cellulaires, ainsi que de nombreuses opérations (suppression, contraction, split, chanfreinage...).

Récemment, nous avons mis au jour une piste de recherche autour de problématiques de transformations de graphes, en particulier en lien avec le modeleur Jerboa [Belhaouari 2014]. De manière simplifiée, ce modeleur dont le noyau est basé sur les Gcartes permet de prototyper des modeleurs géométriques en spécifiant les opérations géométriques à base de topologique par des règles de transformation de graphes. Lors de premiers échanges avec PASCALE LE GALL (MICS Supélec Paris), ROMAIN PASCUAL (MICS Supélec Paris), AGNÈS ARNOULD (XLIM Poitiers) et HAKIM FERRIER BELHAOUARI (XLIM Poitiers), nous avons identifié d'autres modèles, notamment simpliciaux, qui semblent être adaptés à cette approche. L'objectif est donc d'étudier en profondeur comment ces structures et leurs opérations peuvent entrer dans le cadre de la modélisation géométrique à base de règles de transformations de graphes, où la théorie des *catégories* est au coeur du domaine. La théorie des catégories est largement répandue dans divers domaines des mathématiques, notamment en topologie où les ensembles simpliciaux ont été définis en termes de *catégories*. Nous projetons également, à court terme, d'étudier ce formalisme qui pourrait permettre de transférer des connaissances d'un domaine à l'autre.

Enfin, nous débutons l'encadrement de la thèse de VINCENT COMMIN en collaboration avec SÉBASTIEN HORNA (XLIM POITIERS), ARTHUR CAVALIER (XLIM POITIERS) et CHRONOSPEDIA, encyclopédie du savoir horloger. L'objectif principal est d'automatiser le processus de génération de modèles 3D de systèmes d'horlogerie. Dans un premier temps, nous souhaitons définir un processus de génération procédurale basée sur la paramétrisation de pièces d'horlogerie. L'objectif est de développer des opérations destinées à automatiser la modélisation de systèmes mécaniques d'engrenages. Dans un second temps, l'objectif est d'utiliser ce système de paramétrisation afin d'alimenter un processus d'intelligence artificielle destinée à de la reconnaissance de formes 3D dans une horloge. À terme, il s'agira d'analyser des données issues de différents systèmes d'acquisition (nuages de points, grilles 3D, maillages) et d'utiliser ce système d'IA afin de localiser les différentes pièces pour produire, in fine, un jumeau numérique du mécanisme.

### 5.2.2 Calcul de l'homologie

Concernant le calcul de groupes d'homologie, des pistes de recherches restent encore à explorer concernant les approches incrémentales. En particulier, il semble intéressant de poursuivre l'étude des liens entre homologie effective et homologie persistante. En effet, lors de la construction d'un objet par identifications, la suite des "gros" complexes forme une filtration, qui peut donc être exploitée dans le cadre de l'homologie persistante. Nous avons établi des liens entre l'homologie persistante de tours et l'homologie effective ; il serait
intéressant de poursuivre l'étude des liens entre ces deux approches, notamment afin de pouvoir transférer des résultats existants d'une approche à l'autre.

Concernant le contrôle de l'homologie d'un objet au cours d'un processus de construction, nous avons montré comment maintenir une équivalence homologique pour une opération de cône, d'identification, ou de dégénérescence. La formule de KÜNNETH permet de déduire l'homologie d'un objet résultant d'une opération de produit cartésien, mais le calcul d'une équivalence homologique reste à établir. Cela permettrait de pouvoir appliquer les résultats de l'homologie effective pour toute suite d'opérations de constructions.

Lors des travaux de thèse WASSIM RHARBAOUI, en collaboration avec PASCAL LIENHARDT (XLIM Poitiers), SYLVIE ALAYRANGUES (XLIM Poitiers), et GUILLAUME DAMIAND (LIRIS Lyon), nous avons mis en évidence la possibilité de paralléliser le calcul incrémental de l'homologie d'un objet distribué. À court terme, l'objectif est de finaliser la mise en oeuvre de ces travaux.

Depuis 2020, dans le cadre d'une collaboration initiée avec le Centre d'Investigation Clinique (CIC 1402) du CHU de Poitiers, via l'encadrement d'un stagiaire de M2, nous explorons les apports possibles de l'utilisation de structures combinatoires et leur caractérisation topologique dans le domaine de l'intelligence artificielle. Actuellement, dans le cadre de l'encadrement de la thèse d'INÉS CASTILLA RIESO, en collaboration avec P. CARRÉ (XLIM Poitiers), P.-J. SAULNIER (CIC 1402, CHU Poitiers) et A. JULIAN (CIC 1402, CHU Poitiers), nous travaillons sur la structuration de données issues de l'utilisation de smartphones par des structures simpliciales, et à leur caractérisation topologique via l'homologie persistante. L'objectif est d'utiliser ces informations pour alimenter des algorithmes d'IA, destinés à de l'aide au diagnostic de la maladie d'ALZHEIMER.

Les données en question sont hétérogènes (texte, géolocalisation, utilisation d'appli-cations...) et ne sont, pour la plupart, pas de nature géométrique. Un premier enjeu est de structurer ces données en établissant des relations d'incidence "pertinentes", au sens où l'homologie persistante calculée sur cette structuration mettre en avant des indicateurs concernant la détection de la maladie.

Un second enjeu concerne l'interprétation de l'homologie. En effet, comme nous l'avons présenté dans ce document, l'interprétation de l'homologie est généralement une interprétation géométrique, caractérisant les "trous" d'un espace topologique. Bien que la nature des données ne soient pas ici de nature géométrique, elles sont plongées dans un espace géométrique. La question se pose alors de l'interprétation de ces "trous" sur les données elles-mêmes. Dit autrement : *est-on capable d'interpréter l'information homologique en terme métier neurologique ?*

### 5.2.3 Objets géométriques

Concernant les modèles géométriques, plusieurs pistes de recherche sont actuellement en cours, notamment autour de modèles paramétriques et la modélisation d'objets tubulaires.
Concernant les structures cellulaires, nous projetons d'investiguer la possibilité de plonger les cellules dans différents espaces paramétriques. Si cette approche est classique pour des modeleurs surfaciques, cela nous semble plus rare pour la modélisation cellulaire volumique où, bien souvent, objets géométriques associés aux structures sont obtenus par plongements linéaires. Les modèles sont généralement subdivisés de manière à générer des maillages. Le plongement non linéaire de ces structures permettrait de pouvoir répondre à des enjeux d'optimisation et de visualisation. Par exemple, lorsqu'une structure est simplifiée en supprimant des cellules tout en préservant son homologie, la version minimale présente en général de la multi-incidence. La définition d'un plongement non linéaire permettrait de visualiser une forme correspondant à la structure.

La définition des complexes simploïdaux abstraits nous a permis de faire le lien avec les supercomplexes de GUGENHEIM. En particulier, nous avons mis en évidence les liens géométriques entre deux simploïdes ayant un type ne différant que par des 0. Il semble intéressant de poursuivre l'étude et la définition de la notion de projection d'un espace géométrique à l'autre, afin de pouvoir contrôler la forme géométrique des objets de manière fine.

Concernant les structures simpliciales et simploïdales, dont le plongement est "naturellement" effectuée dans des espaces de BÉZIER, il semble intéressant d'étudier d'autres espaces paramétriques, en particulier les espaces Splines ou NURBS. La structuration de tels espaces en structures simpliciales et simploïdales semble moins directe, mais les travaux initiés dans [Fuchs 1997] semblent une piste intéressante de travail. Cela permettrait en particulier un contrôle paramétrique par morceaux des cellules géométriques, ainsi qu'un contrôle avancé de la continuité [Massarwi 2016].

Concernant la modélisation d'objets tubulaires volumiques, nous travaillons actuellement avec GÉRALDINE MORIN (IRIT Toulouse), sur l'élaboration d'une méthode qui vise à obtenir une quadrangulation de la sphère présentant de bonnes propriétés géométriques. L'objectif à terme est d'obtenir une quadrangulation canonique pour toute configuration de jonction. En complément, les travaux sur l'analyse isogéométrique (IGA) qui proposent d'utiliser directement le modèle géométrique pour effectuer des calculs physiques, ouvre des perspectives intéressantes pour envisager l'utilisation de nos modèles tubulaires dans des cadres applicatifs liés à des problématiques de simulation physique.

Nous avons récemment initié des travaux avec THIERRY BAY (CERAMATHS Valenciennes), LAURA SAINI (CERAMATHS Valenciennes) et GÉRALDINE MORIN (IRIT Toulouse) afin de plonger les objets tubulaires volumiques dans des espaces permettant d'obtenir de manière exacte des branches de section circulaire. Cela n'est pas possible dans les espaces de BÉZIER basés sur les fonctions polynomiales de BERNSTEIN. Les espaces Algebraic Trigonometric Pythagorean Hodograph, ou ATPH [Bay 2022] sont basés sur des fonctions polynomiales et trigonométriques permettant de répondre à ce besoin. À terme, l'objectif est d'établir les liens précis entre la structuration des points de contrôles des espaces ATPH et ceux des ensembles semi-simploïdaux, en utilisant les multi-indices.
Enfin, d'un point de vue pratique, un modeleur simploïdal est actuellement en cours de développement en collaboration avec ARTHUR CAVALIER (XLIM Poitiers). Ce projet s'appuie sur des travaux d'étudiants, en particulier sur les stages de fin de master de DAMIEN AHOLOU et d'ALEXIS LOUAIL. L'objectif à terme est de proposer un modeleur basé sur les ensembles simploïdaux, intégrant à la fois :

- l'ensemble des opérations de construction de base présentées dans ce manuscrit : le cône simplicial, le cône simploïdal, le produit cartésien simplicial, le produit cartésien simploïdal et l'identification;

- le calcul de groupes d'homologie, intégrant à la fois les méthodes globales et incré-mentales;

- un plongement paramétrable dans différents espaces à pôles, comme BÉZIER, ATPH et si possible, également dans des espaces Splines.

Pour conclure, notons que jusqu'à présent j'ai utilisé le pronom *nous* dans tout ce manuscrit. Ce *nous* reflète mon approche de la recherche, basée sur les collaborations et les échanges que j'ai pu avoir avec différents collègues ou étudiants. Pour la suite de ma carrière, je compte m'appuyer sur les collaborations existantes, et en construire de nouvelles, notamment via l'élaboration de projets nationaux et internationaux, en gardant toujours comme ligne de mire le triptyque *structures combinatoires, calcul de propriétés topologiques, formes géométriques*.
<figure><img src="image_107.png" /></figure>
Bibliographie

[Agoston 1976] M. K. Agoston. Algebraic topology, a first course. Pure and applied mathematics. Marcel Dekker Ed., 1976. (Cité en pages 15, 68 et 70.)

[Alayrangues 2008] Sylvie Alayrangues, X. Daragon, Jacques-Olivier Lachaud et Pascal Lienhardt. *Equivalence between Closed Connected $n$-G-Maps without Multi-Incidence and $n$-Surfaces*. Journal of Mathematical Imaging and Vision, vol. 32, pages p.1–22, 2008. (Cité en page 43.)

[Alayrangues 2009a] Sylvie Alayrangues, Guillaume Damiand, Laurent Fuchs, Pascal Lienhardt et Samuel Peltier. *Homology Computation on Cellular Structures in Image Context*. In Computational Topology in Image Context, pages 19–28, St. Kathrein/Offenegg, Austria, Ao?t 2009. (Cité en page 7.)

[Alayrangues 2009b] Sylvie Alayrangues, Samuel Peltier, Guillaume Damiand et Pascal Lienhardt. *Border operator for generalized maps*. In 15th IAPR International Conference on Discrete Geometry for Computer Imagery (DGCI 2009), volume 5810 of *Discrete Geometry for Computer Imagery 15th IAPR International Conference, DGCI 2009, Montréal, Canada, September 30 - October 2, 2009*. *Proceedings*, pages 300–312, Montreal, Canada, Septembre 2009. Springer Berlin/Heidelberg. (Cité en page 7.)

[Alayrangues 2011] S. Alayrangues, G. Damiand., P. Lienhardt et S. Peltier. *A Boundary Operator for Computing the Homology of Cellular Structures*. Research Report 2012-1, XLIM-Sic Laboratory, University of Poitiers, France. http://hal.archives-ouvertes.fr/hal-00683031, 2011. (Cité en page 73.)

[Alayrangues 2015a] Sylvie Alayrangues, Guillaume Damiand, Pascal Lienhardt et Samuel Peltier. *Homology of Cellular Structures Allowing Multi-incidence*. Discrete and Computational Geometry, vol. 54, no. 1, pages 42–77, Juillet 2015. (Cité en pages 7, 73 et 75.)

[Alayrangues 2015b] Sylvie Alayrangues, Laurent Fuchs, Pascal Lienhardt et Samuel Peltier. Incremental Computation of the Homology of Generalized Maps : An Application of Effective Homology Results. working paper or preprint, Avril 2015. (Cité en pages 7, 81, 88 et 96.)

[Alayrangues 2015c] Sylvie Alayrangues, Pascal Lienhardt et Samuel Peltier. *Conversion between chains of maps and chains of surfaces ; application to the computation of incidence graphs homology*. Research report, Université de Poitiers, 2015. (Cité en pages 7 et 44.)

[Batagelj 1989] Vladimir Batagelj. *An inductive definition of the class of 3-connected quadrangulations of the plane*. Discrete Mathematics, vol. 78, no. 1, pages 45–53, 1989. Special Double Issue in Memory of Tory Parsons. (Cité en page 126.)

[Bay 2022] T. Bay, Cattiaux-Huillard I. et L. Saini. *Hermite interpolation by planar cubic-like ATPH*. Adv Comput Math, vol. 48, no. 64, 2022. (Cité en page 140.)
[Bechmann 1997] D. Bechmann, Y. Bertrand et S. Thery. *N-dimensional Bezier-Gregory patches for multidimensional cellular complexes*. In The Fourth International Conference on Mathematical Methods for Curves and Surfaces, Lillehammer, Norway, 3-8, July 1997. (Cité en page 122.)

[Bechmann 2007] B. Bechmann D. et Péroche. Informatique graphique, modélisation géométrique et animation. Signal et Image, Traité IC2. Lavoisier, 2007. (Cité en pages 9 et 14.)

[Belhaouari 2014] Hakim Belhaouari, Agnés Arnould, Pascale Le Gall et Thomas Bellet. *Jerboa : A Graph Transformation Library for Topology-Based Geometric Modeling*. In Holger Giese et Barbara König, editeurs, Graph Transformation, pages 269–284, Cham, 2014. Springer International Publishing. (Cité en page 138.)

[Bertrand 1999a] G. Bertrand. *New notions for discrete topology*. In G. Bertrand, M. Couprie et L. Perroton, editeurs, Proc. DGCI'99, volume 1568 of *Lecture Notes in Computer Science*, pages 218–228, Marne-la-Vallée, France, 1999. Springer. (Cité en page 29.)

[Bertrand 1999b] Gilles Bertrand et Michel Couprie. *A Model for Digital Topology*. In Gilles Bertrand, Michel Couprie et Laurent Perroton, editeurs, Discrete Geometry for Computer Imagery, pages 229–241, Berlin, Heidelberg, 1999. Springer Berlin Heidelberg. (Cité en page 42.)

[Boissonnat 2019] Jean-Daniel Boissonnat et Clément Maria. *Computing persistent homology with various coefficient fields in a single pass*. Journal of Applied and Computational Topology, vol. 3, no. 1-2, pages 59–84, apr 2019. (Cité en page 80.)

[Boltcheva 2010] Dobrina Boltcheva, Sara Merino Aceitunos, Jean-Claude Léon et Franck Hétroy. *Constructive Mayer-Vietoris Algorithm : Computing the Homology of Unions of Simplicial Complexes*. Research Report RR-7471, INRIA, D'embre 2010. (Cité en page 90.)

[Brinkmann 2005] Gunnar Brinkmann, Sam Greenberg, Catherine Greenhill, Brendan D. McKay, Robin Thomas et Paul Wollan. *Generation of simple quadrangulations of the sphere*. Discrete Mathematics, vol. 305, no. 1, pages 33–54, 2005. (Cité en pages 126 et 127.)

[Brisson 1993] E. Brisson. *Representing geometric structures in d dimensions : topology and order*. Discrete & Computational Geometry, vol. 9, no. 1, pages 387–426, 1993. (Cité en page 43.)

[Brown 1981] Ronald Brown et Philip J. Higgins. *On the algebra of cubes*. Journal of Pure and Applied Algebra, vol. 21, no. 3, pages 233–260, 1981. (Cité en pages 19 et 58.)

[Bærentzen 2012] J.A. Bærentzen, M.K. Misztal et K. Wełnicka. *Converting skeletal structures to quad dominant meshes*. Computers & Graphics, vol. 36, no. 5, pages 555–561, 2012. Shape Modeling International (SMI) Conference 2012. (Cité en page 124.)

[Cairns 1961] S. S. Cairns. Introductory topology. Ronald Press Company, 1961. (Cité en page 68.)
[Carlsson 2010] Gunnar Carlsson et Vin De Silva. *Zigzag persistence*. Foundations of computational mathematics, vol. 10, no. 4, pages 367–405, 2010. (Cité en page 81.)

[Cottrell 2009] J Austin Cottrell, Thomas JR Hughes et Yuri Bazilevs. Isogeometric analysis: toward integration of cad and fea. John Wiley & Sons, 2009. (Cité en page 123.)

[Dahmen 1982] W. Dahmen et C. A. Micchelli. *On the linear independence of multivariate B-splines I. Triangulation of simploids*. SIAM J. Numer. Anal., vol. 19, 1982. (Cité en pages 18 et 113.)

[Damiand 2006] Guillaume Damiand, Samuel Peltier et Laurent Fuchs. *Computing Homology for Surfaces with Generalized Maps : Application to 3D Images*. In International Symposium on Visual Computing, volume 4292 of *Advances in Visual Computing*, pages 235–244, Lake Tahoe, Nevada, United States, Novembre 2006. Springer Berlin/Heidelberg. (Cité en page 7.)

[Damiand 2008] Guillaume Damiand, Samuel Peltier et Laurent Fuchs. *Computing Homology Generators for Volumes Using Minimal Generalized Maps*. In International Workshop on Combinatorial Image Analysis, volume 4958 of *LNCS*, pages 63–74, Buffalo, NY, United States, Avril 2008. Springer-Verlag. (Cité en pages 7, 71 et 76.)

[Damiand 2012] Guillaume Damiand, Rocio Gonzalez-Diaz et Samuel Peltier. *Removal Operations in nD Generalized Maps for Efficient Homology Computation*. In International Workshop on Computational Topology in Image Context, volume 7309, pages 20–29, Bertinoro, Italy, Mai 2012. Springer Berlin/Heidelberg. (Cité en pages 7 et 71.)

[Damiand 2014] G. Damiand et P. Lienhardt. Combinatorial maps : Efficient data structures for computer graphics and image processing. A K Peters/CRC Press, September 2014. (Cité en pages 29, 33 et 91.)

[Damiand 2020] Guillaume Damiand, Eduardo Paluzo-Hidalgo, Ryan Slechta et Rocio Gonzalez-Diaz. *Approximating lower-star persistence via 2D combinatorial map simplification*. Pattern Recognition Letters, vol. 131, pages 314–321, 2020. (Cité en page 80.)

[Dantchev 2012] Stefan Dantchev et Ioannis Ivrissimtzis. *Efficient construction of the Čech complex*. Computers & Graphics, vol. 36, no. 6, pages 708–713, 2012. (Cité en page 79.)

[Daragon 2003] X. Daragon, M. Couprie et G. Bertrand. *Discrete frontiers*. In I. Nyström, G. Sanniti di Baja et S. Svensson, editeurs, Proc. DGCI’03, volume 2886 of *Lecture Notes in Computer Science*, pages 236–245, Naples, Italie, 2003. Springer. (Cité en page 30.)

[Daragon 2005] X. Daragon, M. Couprie et G. Bertrand. *Discrete surfaces and frontier orders*. Journal of Mathematical Imaging and Vision, vol. 23, pages 379–399, 2005. (Cité en page 30.)

[De Floriani 2003] Leila De Floriani, Franco Morando et Enrico Puppo. *Representation of Non-Manifold Objects*. In Proceedings of the Eighth ACM Symposium on Solid
Modeling and Applications, SM '03, page 304-309, New York, NY, USA, 2003.
Association for Computing Machinery. (Cité en page 40.)

[Delfinado 1995] C. J. A. Delfinado et H. Edelsbrunner. *An incremental algorithm for Betti numbers of simplicial complexes on the 3-sphere*. Comput. Aided Geom. Design, vol. 12, no. 7, pages 771-784, 1995. (Cité en page 77.)

[DeRose 1993] T. DeRose, R. N. Goldman, H. Hagen et S. Mann. *Functional composition algorithms via blossoming*. Transactions On Graphics, vol. 12, no. 2, pages 113-135, 1993. (Cité en pages 112 et 116.)

[Dey 2008] Tamal K. Dey, Kuiyu Li, Jian Sun et David Cohen-Steiner. *Computing Geometry-Aware Handle and Tunnel Loops in 3D Models*. ACM Trans. Graph., vol. 27, no. 3, page 1-9, aug 2008. (Cité en page 71.)

[Dey 2014] Tamal K Dey, Fengtao Fan et Yusu Wang. *Computing topological persistence for simplicial maps*. In Proceedings of the thirtieth annual symposium on Computational geometry, pages 345-354, 2014. (Cité en page 91.)

[Dey 2018] Tamal K. Dey, Tianqi Li et Yusu Wang. *Efficient Algorithms for Computing a Minimal Homology Basis*. In Michael A. Bender, Martín Farach-Colton et Miguel A. Mosteiro, editeurs, LATIN 2018 : Theoretical Informatics, pages 376-398, Cham, 2018. Springer International Publishing. (Cité en page 71.)

[Dey 2022] Tamal K. Dey et Tao Hou. *Fast Computation of Zigzag Persistence*. In Shiri Chechik, Gonzalo Navarro, Eva Rotenberg et Grzegorz Herman, editeurs, 30th Annual European Symposium on Algorithms (ESA 2022), volume 244 of Leibniz International Proceedings in Informatics (LIPIcs), pages 43:1-43:15, Dagstuhl, Germany, 2022. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. (Cité en page 81.)

[Dlotko 2010] P. Dlotko, Tomas Kaczynski, M. Mrozek et T. Wanner. *Coreduction Homology Algorithm for Regular CW-Complexes*. Discrete Comput. Geom., vol. 46, pages 361-388, 2010. (Cité en page 71.)

[Dobkin 1987] D. Dobkin et M. Laszlo. *Primitives for the Manipulation of Three-Dimensional Subdivisions*. In 3rd Symposium on Computational Geometry, pages 86-99, Waterloo, Canada, June 1987. (Cité en page 37.)

[Dumas 2001] J. G. Dumas, B.D. Saunders et G. Villard. *On efficient sparse integer matrix Smith normal form computations*. J. of Symbolic Computation, vol. 32, no. 1/2, pages 71-99, 2001. (Cité en page 71.)

[Edelsbrunner 1987] H. Edelsbrunner. Algorithms in computational geometry. Springer, New-York, 1987. (Cité en page 29.)

[Edelsbrunner 2010] Herbert Edelsbrunner et John Harer. Computational topology - an introduction. American Mathematical Society, 2010. (Cité en page 79.)

[Edmonds 1960] J. Edmonds. *A Combinatorial Representation for Polyhedral Surfaces*. Notices Amer. Math. Soc., vol. 7, 1960. (Cité en page 36.)

[Elter 1994] H. Elter et P. Lienhardt. *Cellular complexes as structured semi-simplicial sets*. International Journal of Shape Modeling, vol. 1, no. 2, pages 191-217, 1994. (Cité en pages 40 et 41.)
[Evako 1996] A. V. Evako, R. Kopperman et Y. V. Mukhin. *Dimensional properties of graphs and digital spaces*. Journal of Mathematical Imaging and Vision, vol. 6, pages 109-119, 1996. (Cité en page 42.)

[Farin 2002] G. Farin. Curves and surfaces for cagd: A practical guide. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 5th édition, 2002. (Cité en pages 108, 110 et 123.)

[Fuchs 1997] Laurent Fuchs. *Une specification formelle des modeles de courbes et de surfaces de forme libre*. PhD thesis, Université Louis Pasteur, Strasbourg, 1997. 1997STR13239. (Cité en pages 19, 111 et 140.)

[Fuentes Suárez 2018] A.J. Fuentes Suárez et E. Hubert. *Scaffolding skeletons using spherical Voronoi diagrams: Feasibility, regularity and symmetry*. Computer-Aided Design, vol. 102, pages 83–93, 2018. Proceeding of SPM 2018 Symposium. (Cité en page 124.)

[Giblin 1977] P. J. Giblin. Graphs, surfaces and homology. Chapman and Hall, 1977. (Cité en page 97.)

[Giesbrecht 1996] M. Giesbrecht. *Probabilistic Computation Of The Smith Normal Form Of A Sparse Integer Matrix*. In Proceedings of the Second Int. Symp. on Algorithmic Number Theory, LNCS, volume 1122, pages 173–186. Springer-Verlag, 1996. (Cité en page 71.)

[González-Díaz 2009] Rocío González-Díaz, María José Jiménez, Belén Medrano et Pedro Real. *Chain homotopies for object topological representations*. Discrete Applied Mathematics, vol. 157, no. 3, pages 490–499, 2009. (Cité en page 71.)

[Gonzalez-Lorenzo 2022] Aldo Gonzalez-Lorenzo, Alexandra Bac et Jean-Luc Mari. *A Heuristic for Short Homology Basis of Digital Objects*. In International Joint Conference on Discrete Geometry and Mathematical Morphology (DGMM), volume 13493 of *Lecture Notes in Computer Science*, pages 60–70, Strasbourg, France, 2022. Springer International Publishing. (Cité en page 71.)

[Gugenheim 1957] V. K. A. M. Gugenheim. *On supercomplexes*. Transactions of the American Mathematical Society, vol. 85, no. 1, pages 35–51, May 1957. (Cité en page 63.)

[Guibas 1985] L. Guibas et G. Stolfi. *Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams*. Transactions on Graphics, vol. 4, no. 2, pages 74–123, 1985. (Cité en page 36.)

[Hatcher 2002] A. Hatcher. Algebraic topology. Cambridge University Press, 2002. (Cité en page 72.)

[Hughes 2005] T.J.R. Hughes, J.A. Cottrell et Y. Bazilevs. *Isogeometric analysis : CAD, finite elements, NURBS, exact geometry and mesh refinement*. Computer Methods in Applied Mechanics and Engineering, vol. 194, no. 39, pages 4135–4195, 2005. (Cité en page 123.)

[Ichinomiya 2020] Takashi Ichinomiya, Ippei Obayashi et Yasuaki Hiraoka. *Protein-Folding Analysis Using Features Obtained by Persistent Homology*. Biophysical Journal, vol. 118, no. 12, pages 2926–2937, 2020. (Cité en page 79.)
[Kaczynski 1998] T. Kaczynski, M. Mrozek et M. Slusarek. *Homology computation by reduction of chain complexes*. Computers & Math. Appl., vol. 34, no. 4, pages 59–70, 1998. (Cité en page 71.)

[Kaczynski 2004] T. Kaczynski, K. Mischaikow et M. Mrozek. *Computational homology*. Springer, 2004. (Cité en page 71.)

[Kannan 1979] R. Kannan et A. Bachem. *Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix*. SIAM Journal on Computing, vol. 8, no. 4, pages 499–507, November 1979. (Cité en page 68.)

[Kerber 2019] Michael Kerber et Hannah Schreiber. *Barcodes of towers and a streaming algorithm for persistent homology*. Discrete & computational geometry, vol. 61, no. 4, pages 852–879, 2019. (Cité en page 91.)

[Lang 1996] V. Lang et P. Lienhardt. *Simplicial sets and triangular patches*. In Proceedings of CGI’96, Pohang, Korea, 1996. (Cité en pages 54 et 111.)

[Lang 1997] V. Lang et P. Lienhardt. *Cartesian product of simplicial sets*. In Proc. of WSCG’97, Plzen, Czech Republic, 1997. (Cité en pages 57 et 119.)

[Lienhardt 1989] P. Lienhardt. *Subdivisions of n-dimensional spaces and n-dimensional generalized maps*. In ACM Symposium on Computational Geometry, pages 228–236, Juin 1989. (Cité en page 37.)

[Lienhardt 1991] P. Lienhardt. *Topological models for boundary representation : a comparison with n-dimensional generalized maps*. Computer Aided Design, vol. 23, no. 1, pages 59–82, 1991. (Cité en page 37.)

[Lienhardt 1994] P. Lienhardt. *N-Dimensional Generalized Combinatorial Maps and Cellular Quasi-Manifolds*. International Journal of Computational Geometry and Applications, vol. 4, no. 3, pages 275–324, 1994. (Cité en page 27.)

[Lienhardt 2004] P. Lienhardt, X. Skapin et A. Bergey. *Cartesian Product of Simplicial and Cellular Structures*. Int. Journal of Computational Geometry and Applications, vol. 14, no. 3, pages 115–159, June 2004. (Cité en pages 39, 54 et 57.)

[Lienhardt 2009] Pascal Lienhardt, Laurent Fuchs et Yves Bertrand. *Combinatorial models for topology-based geometric modeling*. In S. Naimpally G. Di Maio, editeur, Theory and applications of proximity, nearness and uniformity, pages 151–198. Quaderni di matematica, dipartimento di matematica, seconda universita di Napoli, 2009. (Cité en page 9.)

[Lienhardt 2016] Pascal Lienhardt et Samuel Peltier. *Homology Computation During an Incremental Construction Process*. In Jean-Luc Mari Alexandra Bac, editeur, Computational Topology in Image Context - CTIC 2016, volume 9667 of *Computational Topology in Image Context (CTIC 2016)*, pages 7–15, Marseille, France, Juin 2016. Springer. (Cité en page 7.)

[Livesu 2016] Marco Livesu, Alessandro Muntoni, Enrico Puppo et Riccardo Scateni. *Skeleton-driven Adaptive Hexahedral Meshing of Tubular Shapes*. Computer Graphics Forum, vol. 35, no. 7, pages 237–246, 2016. (Cité en page 124.)
[Livesu 2017] Marco Livesu, Stefano Ellero, Jonàs Martínez, Sylvain Lefebvre et Marco Attene. *From 3D models to 3D prints : an overview of the processing pipeline*. In Computer Graphics Forum, volume 36, pages 537-564. Wiley Online Library, 2017. (Cité en pages 123 et 124.)

[Lyon 2016] Max Lyon, David Bommes et Leif Kobbelt. *HexEx : robust hexahedral mesh extraction*. ACM Transactions on Graphics (TOG), vol. 35, no. 4, pages 1-11, 2016. (Cité en page 123.)

[Mäntylä 1988] M. Mäntylä. An introduction to solid modeling. Computer Science Press, 1988. (Cité en page 36.)

[Masoomy 2021] H. Masoomy, B. Askari, S. Tajik et al. *Topological analysis of interaction patterns in cancer-specific gene regulatory network : persistent homology approach*. Nature, Scientific report, no. 16414, 2021. (Cité en page 77.)

[Massarwi 2016] Fady Massarwi et Gershon Elber. *A B-spline based framework for volumetric object modeling*. Computer-Aided Design, vol. 78, pages 36-47, 2016. (Cité en pages 123 et 140.)

[Massarwi 2019] Fady Massarwi, Pablo Antolin et Gershon Elber. *Volumetric untrimming : Precise decomposition of trimmed trivariates into tensor products*. Computer Aided Geometric Design, vol. 71, pages 1-15, 2019. (Cité en pages 123 et 124.)

[May 1967] J. P. May. Simplicial objects in algebraic topology. Van Nostrand, Princeton, 1967. (Cité en page 54.)

[Milosavljević 2011] Nikola Milosavljević, Dmitriy Morozov et Primoz Skraba. *Zigzag persistent homology in matrix multiplication time*. In Proceedings of the twenty-seventh annual symposium on Computational geometry, pages 216-225, 2011. (Cité en page 81.)

[Morin 2001] Géraldine Morin et Ron Goldman. *On the smooth convergence of subdivision and degree elevation for Bézier curves*. Computer Aided Geometric Design, vol. 18, no. 7, pages 657-666, 2001. (Cité en page 130.)

[Munkres 1984] J. R. Munkres. Elements of algebraic topology. Perseus Books, 1984. (Cité en pages 66, 67, 68 et 93.)

[Nakamoto 1996] Atsuhiro Nakamoto. *Diagonal transformations in quadrangulations of surfaces*. Journal of Graph Theory, vol. 21, no. 3, pages 289-299, 1996. (Cité en page 126.)

[Panotopoulou 2018] Athina Panotopoulou, Elissa Ross, Kathrin Welker, Evelyne Hubert et Géraldine Morin. *Scaffolding a skeleton*. In Research in Shape Analysis, pages 17-35. Springer, 2018. (Cité en pages 124, 125, 126 et 129.)

[Peltier 2006a] S. Peltier. *Calcul de groupes d'homologie sur des structures simpliciales, simplo idales et cellulaires*. PhD thesis, Université de Poitiers, Poitiers, France, 2006. (Cité en pages 22, 70 et 72.)

[Peltier 2006b] S. Peltier, S. Alayrangues, L. Fuchs et J.-O. Lachaud. *Computation of homology groups and generators*. Comput. & Graph., vol. 30, pages 62-69, feb. 2006. (Cité en page 68.)
[Peltier 2007a] Samuel Peltier, Adrian Ion, Yll Haxhimusa, Walter Kropatsch et Guillaume Damiand. *Computing Homology Group Generators of Images Using Irregular Graph Pyramids*. In Graph-Based Representations in Pattern Recognition, volume 4538 of *Graph-Based Representations in Pattern Recognition*, pages 283–294, Alicante, Spain, Juin 2007. Springer Berlin / Heidelberg. (Cité en page 7.)

[Peltier 2007b] Samuel Peltier, Adrian Ion, Yll Haxhimusa et Walter G. Kropatsch. *Controlling Geometry of Homology Generators*. In Computer Vision Winter Workshop, pages 115–121, Graz, Austria, F ?rier 2007. (Cité en page 7.)

[Peltier 2009a] L. Peltier S. Fuchs et P. Lienhardt. *Simploidals sets : Definitions, operations and comparison with simplicial sets*. Discrete Applied Mathematics, vol. 157, no. 3, pages 542–557, 2009. International Conference on Discrete Geometry for Computer Imagery. (Cité en pages 7, 13 et 19.)

[Peltier 2009b] Samuel Peltier, Adrian Ion, Walter G. Kropatsch, Guillaume Damiand et Yll Haxhimusa. *Directly Computing the Generators of Image Homology using Graph Pyramids*. Image and Vision Computing, vol. 27, no. 7, pages 846–853, Juin 2009. (Cité en page 7.)

[Peltier 2018] S. Peltier et P. Lienhardt. *Simploidal Sets : a data structure for handling simploidal Bezier spaces*. Computer Aided Geometric Design, vol. 62, pages 44 – 62, Mai 2018. (Cité en pages 7, 54, 56, 59, 64, 112, 117 et 119.)

[Peltier 2021] Samuel Peltier, Géraldine Morin et Damien Aholou. *Tubular parametric volume objects : Thickening a piecewise smooth 3D stick figure*. Computer Aided Geometric Design, vol. 85, page 101981, F ?rier 2021. (Cité en pages 7, 123 et 127.)

[Peltier 2023] S. Peltier. Informatique mathématique : une photographie en 2023. chapitre i : Structures combinatoires pour la modélisation géométrique à base topologique. Elements of mathematics. CNRS éditions, 2023. (Cité en page 7.)

[Pranav 2016] Pratyush Pranav, Herbert Edelsbrunner, Rien van de Weygaert, Gert Vegter, Michael Kerber, Bernard J. T. Jones et Mathijs Wintraecken. *The topology of the cosmic web in terms of persistent Betti numbers*. Monthly Notices of the Royal Astronomical Society, vol. 465, no. 4, pages 4281–4310, nov 2016. (Cité en page 77.)

[Raptis 2011] Michalis Raptis, Darko Kirovski et Hugues Hoppe. *Real-time classification of dance gestures from skeleton animation*. In Proceedings of the 2011 ACM SIGGRAPH/Eurographics symposium on computer animation, pages 147–156, 2011. (Cité en page 124.)

[Rharbaoui 2020] Wassim Rharbaoui, Sylvie Alayrangues, Pascal Lienhardt et Samuel Peltier. *Local computation of homology variations over a construction process*. Computer Aided Geometric Design, vol. 81, page 101907, 2020. (Cité en pages 7, 81 et 86.)

[Rharbaoui 2022] Wassim Rharbaoui. *Calcul incrémental des groupes d'homologie d'un objet au cours d'un processus de construction*. PhD thesis, Université de Poitiers, 2022. Thèse de doctorat dirigée par Lienhardt, Pascal Peltier, Samuel et Alayrangues, Sylvie Informatique. (Cité en pages 81, 85, 86, 87, 89, 90 et 91.)
[Rossignac 1989] J. Rossignac et M. O'Connor. *A Dimension-Independent Model for Pointsets with Internal Structures and Incomplete boundaries*. Geometric modeling for Product Engineering, pages 145-180, 1989. (Cité en page 29.)

[Rubio 2006] J. Rubio et F. Sergeraert. *Constructive Homological Algebra and Applications*, August, 28 - September, 02 2006. http://arxiv.org/abs/1208.3816. (Cité en pages 81, 85 et 96.)

[Serre 1951] Jean-Pierre Serre. *Homologie Singuliere Des Espaces Fibres*. The Annals of Mathematics, vol. 54, no. 3, pages pp. 425-505, 1951. (Cité en pages 19 et 58.)

[Sobhanpanah 1989] C. Sobhanpanah. *Extension of a Boundary Representation Technique for the Description of N-Dimensional Polytopes*. Computer and Graphics, vol. 13, no. 1, pages 17-23, 1989. (Cité en page 29.)

[Storjohann 1996] A. Storjohann. *Near Optimal Algorithms for Computing Smith Normal Forms of Integer Matrices*. In Y. N. Lakshman, editeur, Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation, pages 267-274. ACM, 1996. (Cité en page 71.)

[Sundar 2003] Hari Sundar, Deborah Silver, Nikhil Gagvani et Sven Dickinson. *Skeleton based shape matching and retrieval*. In 2003 Shape Modeling International., pages 130-139. IEEE, 2003. (Cité en page 124.)

[Suzuki 2020] A. Suzuki, M. Miyazawa, A. Okamoto, H. Shimizu, I. Obayashi, Y. Hiraoka, T. Tsuji, P.K. Kang et T. Ito. *Inferring fracture forming processes by characterizing fracture network patterns with persistent homology*. Computers & Geosciences, vol. 143, page 104550, 2020. (Cité en page 77.)

[Tagliasacchi 2016] Andrea Tagliasacchi, Thomas Delame, Michela Spagnuolo, Nina Amenta et Alexandru C Telea. *3D Skeletons: A State-of-the-Art Report*. Computer Graphics Forum, vol. 35, no. 2, pages 573-597, Mai 2016. (Cité en page 124.)

[Usai 2016] Francesco Usai, Marco Livesu, Enrico Puppo, Marco Tarini et Riccardo Sca-teni. *Extraction of the Quad Layout of a Triangle Mesh Guided by Its Curve Skeleton*. ACM Trans. Graph., vol. 35, no. 1, D?embre 2016. (Cité en page 124.)

[Vince 1983] A. Vince. *Combinatorial Maps*. Journal of Combinatorial Theory Series B, vol. 34, pages 1-21, 1983. (Cité en page 37.)

[Viville 2021] P. Viville, P. Kraemer et D. Bechmann. *Hexahedral Mesh Generation For Tubular Shapes Using Skeletons and Connection Surfaces*. In International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications (VISIGRAPP), Feb 2021. (Cité en pages 124 et 126.)

[Wang 2008] Wenping Wang, Bert Jüttler, Dayue Zheng et Yang Liu. *Computation of rotation minimizing frames*. ACM Transactions on Graphics (TOG), vol. 27, no. 1, pages 1-18, 2008. (Cité en pages 129 et 130.)

[Weiler 1985] K. Weiler. *Edge-based data structures for solid modelling in curved-surface environments*. Computer Graphics and Applications, vol. 5, no. 1, pages 21-40, 1985. (Cité en page 36.)
[Whitehead 1949] J. H. C. Whitehead. *Combinatorial homotopy. I.* Bulletin of the American Mathematical Society, vol. 55, no. 3.P1, pages 213 – 245, 1949. (Cité en page 5.)

[Zomorodian 2010] Afra Zomorodian. *Fast construction of the Vietoris-Rips complex.* Computers & Graphics, vol. 34, no. 3, pages 263–271, 2010. (Cité en page 79.)
Résumé

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. Ce manuscrit propose une vision de
la modélisation géométrique à base topologique selon le triptyque *structures combinatoires*,
*calcul de propriétés topologiques, formes géométriques*.

*Structures combinatoires* : dans ce premier volet, une classification est proposée, où les structures simpliciales, simploïdales (un simploïde est un produit de simplexes quelconques) et cellulaires 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 multiincidence. Le mécanisme de dégénérescence est ensuite présenté. Ce dernier permet de définir le produit cartésien simplicial et de cône simploïdal.

*Calcul de propriétés topologiques* : l'homologie permet de caractériser les "trous" d'un objet subdivisé (composantes connexes, tunnels, cavités, etc.). Dans ce deuxième volet, le calcul de l'homologie est étudié pour les structures simpliciales, simploïdales et cellulaires selon deux approches. L'approche classique "globale" est basée sur des réductions de matrices décrivant les relations d'incidence entre les cellules d'un objet subdivisé. Le calcul incrémental de l'homologie s'attache à effectuer le calcul étape après étape. L'approche est ici "locale" : connaissant l'homologie d'un objet et l'homologie de la partie impactée par l'opération, il est possible d'en déduire l'homologie de l'objet résultant. Cette approche, basée sur les outils de l'homologie effective, permet en particulier de maintenir l'homologie d'un objet construit par une suite d'identifications. Le calcul incrémental basé sur le produit cartésien, mettant en avant la formule de KÜNNETH est également présenté.

*Formes géométriques* : deux approches permettant d'associer une forme aux structures simpliciales, simploïdales et cellulaires sont abordées dans ce dernier volet : les plongements linéaires où la forme de chaque cellule est déduite des positions de l'ensemble des sommets de son bord, et les plongements non linéaires où une forme courbe peut être donnée à chaque cellule. En particulier, les espaces paramétriques de BÉZIER sont présentés, et les propriétés permettant de retrouver les structures d'ensembles simpliciaux et simploïdaux au sein même de ces espaces sont établies. Enfin, un champ d'application des ensembles semi-simploïdaux est présenté : la modélisation d'objets tubulaires volumiques paramétriques à partir de squelettes.

Mots clés : modélisation géométrique, structures simpliciales, structures simploïdales, structures cellulaires, structures celluloïdales, calculs de groupes d'homologie, homologie effective, espaces simpliciaux de BÉZIER, espaces simploïdaux de BÉZIER.