Décomposition simpliciale adaptative

Dans plusieurs applications on aimerait décomposer le domaine de l'espace où l'on travaille en une collection de simplexes. Par exemple, en méthode d'éléments finis on veut trianguler les surfaces, en physique d'interfaces on veut étudier les fluctuations dynamiques des surfaces discrétisées etc. Dans la suite, on propose une méthode générale et abstraite qui peut être adaptée, avec des légères modifications, à plusieurs situations pratiques. Il s'agit d'une méthode dynamique [AMBJøRN ET AL.] et adaptative de triangulation d'une surface fermée avec la topologie de la 2-sphère. Ici, on se limite, essentiellement, à la prise en compte des charactéristiques topologiques de la surface ; on peut alors imaginer la triangulation composée de triangles équilatéraux. Il est cependant possible d'incorporer des considérations de nature métrique soit par plongement plongement de la surface triangulée dans soit par une autre méthode de métrisation.

Définitions

Une triangulation fermée, , de la 2-sphère est un complexe simplicial bi-dimensionnel c'est-à-dire un ensemble de triangles (2-simplexes), arêtes (1-simplexes) et sommets (0-simplexes) tel que

1. si un -simplexe appartient à alors tous les -simplexes de sa frontière appartiennent à , pour et
2. chaque arête de appartient à exactement 2 triangles de .

On exclut la présence d'arêtes qui forment des 1- ou 2-boucles, c'est-à-dire on exclut la présence d'arêtes dont le bord est dégéré à un seul point ( ) ou d'arêtes de multiplicité 2 (ou plus). Dans la suite, on considère de triangulations connexes et planaires : elles sont composées d'une seule composante connexe et leur genre , donné par la relation d'Euler

est nul^D.2 (). Une triangulation de la sphère peut alors être vue comme un graphe planaire, dual d'un graphe planaire dont tous les sommets ont un degré 3.

La courbure intrinsèque de la sphère est concentrée sur les sommets de la triangulation. Si dénote le degré du sommet , la densité locale de courbure au sommet sera

Avec cette normalisation pour la courbure locale, l'élément de surface sera

Questions

1. Montrer qu'un graphe est plongeable dans un plan si, et seulement si, il est plongeable dans une sphère.
2. Utiliser le fait que la sphère est une surface de genre 0 et une relation évidente entre les entiers et pour conclure que , et sont nécessairement de la forme
   
   
   
   
   
   
   avec entier supérieur ou égal à 2.
3. Calculer la courbure totale de la triangulation
   
   
   
   ainsi que la surface totale de la triangulation
   
   
   
   où est l'ensemble de sommets de la triangulation .
4. Proposer deux mouvements locaux qui permettent de modifier la triangulation en soit en ajoutant un sommet soit en enlevant un sommet. Bien décrire toutes les modifications locales à apporter aux éléments consitutifs de la triangulation (sommets, arêtes et triangles). Les figures suivantes (détails d'une triangulation avant et après modification) peuvent vous guider.
   unit=5mm (20,9) (5mm,5mm) (1,4)(5,2)(7,4)(6,6)(4,7)(2,6)(1,4) (1,4)(4,5)(6,6) (1,4)(5,4)(7,4) (4,5)(7,4) (4,5)(7,4) (2,6)(4,5)(5,4)(5,2) (4,7)(4,5) ->(9,4.5)(11,4.5) ->(11,3.5)(9,3.5) (13,4)(17,2)(19,4)(18,6)(16,7)(14,6)(13,4) (13,4)(16,5)(18,6) (13,4)(17,4)(19,4) (14,6)(16,5)(17,4)(17,2) (16,5)(19,4) (16,7)(16,5) (13,4)(16,3)(17,4) (16,3)(17,2)

   Est-il toujours possible d'enlever un sommet?

5. Donner un argument qui montre que les mouvments locaux proposés ci-dessus permettent de transformer une triangulation arbitraire (admissible) dans une autre triangulation arbitraire admissible.
6. Sur l'ensemble de toutes les triangulations possibles, on introduit un hamiltonien
   
   
   
   où . Proposer un algorithme Monte Carlo qui permet d'échantillonner selon la mesure ``de Gibbs''
   
   
   
   pour où
   
   
   
   et représente l'ensemble de triangulations admissibles à sommets. Le dénominateur dénote, comme d'habitude, le facteur de normalisation.
7. Proposer une structure de données qui permet de mettre à jour, de manière efficace, toutes les informations nécessaires pour la définition de la triangulation.
8. Programmer l'algorithme ci-dessus.
9. Faire une simulation pour estimer l'espérance de la surface totale d'une triangulation pour différents choix des paramètres et .