Patrons d'un polyèdre convexe

On s'intéresse ici aux polyèdres convexes et à la manière de les construire à partir d'une feuille de papier, ce qu'on appelle un patron. Pour la définition d'un polyèdre convexe, voir le document Doc Polyèdres convexes semi-réguliers .
Nous parlerons donc des sommets, des arêtes et des faces du polyèdre. En particulier, chaque face est contenue dans un plan qui divise l'espace en deux régions et le polyèdre est convexe si, pour chacune de ses faces, il se trouve entièrement dans l'une des régions délimitée par le plan qui contient cette face.
Voir aussi l'outil de visualisation Polyèdres convexes montre des polyèdres convexes et leurs patrons.

Graphe associé à un polyèdre

Patron

Algorithme d'obtention de patrons

Retrouver le polyèdre à partir du patron

Exemples

Dualité

Bibliographie

On associe à un polyèdre un graphe de la manière suivante. Les sommets du graphe sont les faces du polyèdre et deux sommets du graphe sont reliés si les deux faces correspondantes de ont une arête commune. Les arêtes de correspondent aux arêtes du graphe . Le graphe est connexe.
Si M est la matrice d'adjacence de (une fois choisi un ordre dans la liste des faces de , ce que nous supposerons désormais), le nombre de 1 sur une ligne (et sur une colonne) est le nombre de côtés de la face correspondante.
Nous parlerons de polyèdre combinatoire quand seules sont connues ou utilisées les données du graphe et pas les coordonnées dans : plus précisément, c'est un graphe augmenté de la donnée de cycles qu'on appelle faces, chaque arête apparaissant dans exactement deux cycles, une fois dans chaque sens.
Exemple [ Tétraèdre ]
Exemple [ Cube ]
Exemple [ Dodécaèdre régulier ]
Exemple [ Cuboctaèdre ]

Technique de confection d'un patron

Patron et arbre couvrant

Fonction associée à un arbre couvrant (ou à un patron)

Commençons par une description concrète (nous ne formaliserons pas la définition, rappelons la définition du dictionnaire encyclopédique Quillet: patron: Modèle sur lequel ou d'après lequel on travaille. Morceau de papier que les tailleurs, les couturières, les brodeuses, etc découpent de manière à figurer les différentes parties de leur ouvrage et d'après lequel ils taillent l'étoffe dont ces ouvrages doivent être faits; nous rajouterons ici que l'on désire ensuite faire le moins de coutures possibles).
On désire construire un polyèdre convexe à l'aide d'une feuille de papier. Pour cela, on doit aplatir le polyèdre en découpant certaines arêtes. Il faut découper suffisamment d'arêtes pour pouvoir l'étaler sur une feuille de papier et pas trop pour qu'il n'y ait qu'un seul morceau. Il faut aussi que les différents polygones obtenus à partir des faces du polyèdre ne se chevauchent pas. On appelle le résultat un patron du polyèdre. C'est donc une réunion de polygones dans le plan tels que l'intersection de deux de ces polygones est soit vide, soit un sommet commun, soit une arête commune. On désigne encore ces polygones par le nom de faces du patron. Les arêtes du polyèdre qui ne sont pas découpées deviennent des côtés communs à deux des faces (arêtes de pliage du patron). Les arêtes qui sont découpées deviennent deux côtés du bord du patron. Lorsque la condition de non-chevauchement n'est pas vérifiée, nous parlerons de pseudo-patron.
On conjecture que tout polyèdre convexe a au moins un patron (Albrecht Dürer (1525), énoncé comme une conjecture en 1975 par G. Shephard Shephard ).
On associe à un patron (ou à un pseudo-patron) un graphe : ses sommets sont les faces du patron et deux sommets sont reliés dans le graphe si les faces ont un côté commun dans le patron. Les faces du polyèdre correspondent aux faces du patron, l'ensemble des arêtes du graphe du patron (arêtes de pliages du patron) est un sous-ensemble des arêtes du graphe associé du polyèdre. Donc, est un sous-graphe du graphe du polyèdre .
Quand on a bien découpé le polyèdre, on peut aller d'un sommet à un autre (connexité), d'une seule manière (acyclicité): le graphe associé est ce qu'on appelle un arbre couvrant de .

Rappelons quelques définitions (voir le document Graphes pour des explications plus complètes). Si G est un graphe connexe, un graphe couvrant de G est un graphe dont les sommets sont exactement les sommets de G et dont les arêtes forment un sous-ensemble de celles de G . Un arbre couvrant d'un graphe connexe est un graphe couvrant qui est un arbre, c'est-à-dire qu'il est connexe et acyclique.
Soit un patron de d'arbre couvrant . Soient s , f et a le nombre de sommets, de faces et d'arêtes du polyèdre et soient n₁ , ..., n_f les nombres de sommets des faces du polyèdre.

1. Le graphe G de a f sommets et a arêtes.
2. L'arbre a f sommets et f-1 arêtes (comme tout arbre).
3. Le patron a f faces (correspondant aux f sommets de et aux f faces de ) et f-1 arêtes (arêtes de pliage).
4. On obtient un patron en partant d'une face à n₁ sommets et en recollant une à une les autres faces. Cette opération ajoute n_i-2 nouveaux sommets. Le nombre de sommets de est donc

Comment retrouver les nombres s , a et f du polyèdre à partir des caractéristiques du patron? Soit c le nombre de côtés extérieurs du patron. Le nombre de côtés intérieurs du patron est f-1 .

1. Le nombre a d'arêtes de est égal à .
2. Le nombre s de sommets de est égal à .

Pour le démontrer, on peut utiliser la formule d'Euler appliquée au polyèdre convexe qui dit que s-a+f=2 .
Exemple
Exemple
Exemple

Numérotons de 1 à d les faces du polyèdre. Choisissons une face r du polyèdre. Nous allons associer à un patron une fonction de dans lui-même de la manière suivante. Soit j une face. Il existe un seul chemin simple allant de j à r . On définit comme la première étape sur ce chemin. Par convention, .
On obtient ainsi une fonction de dans lui-même telle que et que pour tout j , il existe k<d tel que .
Toute fonction de ce type donne un graphe dont la matrice d'adjacence vérifie que si et seulement si ( ou ) et . Ce graphe est un arbre couvrant car il est clairement connexe et a d-1 arêtes (cf. Graphes ).
On coupe les arêtes du polyèdre séparant deux faces i et j si et seulement si et . Cela permet d'étaler le polyèdre sur un plan. Si les morceaux de papier obtenus ne se chevauchent pas, on a obtenu un patron. Sinon, c'est juste un pseudo-patron. Par exemple, la matrice associée à l'arbre couvrant tel que , , , est On note une telle fonction par .
Exemple
Exemple
Exemple

Calcul d'un arbre couvrant

Préliminaires géométriques

Calcul des coordonnées des sommets du patron

On peut facilement énumérer toutes les fonctions de dans lui même, et tester pour chacune si elle vérifie la condition que et que pour tout j , il existe k < d tel que . Mais leur nombre pouvant être énorme, il est utile de pouvoir en choisir une au hasard.
L'algorithme suivant de A. Broder Generating random spanning trees A. Broder 30th Annual Symposium on Foundations of Computer Science Year: 1989 | Conference Paper | Publisher: IEEE permet de trouver un arbre couvrant aléatoire de manière uniformément distribuée. On obtient un arbre couvrant car est connexe avec s sommets et s - 1 arêtes (une pour chaque arête différente de r ). On montre qu'il est uniformément distribué.
Exemple

On travaille dans l'espace euclidien de base canonique ou dans le plan euclidien vu comme le plan d'équation z=0 orthogonal à .

Lemme

Lemme

Lemme

Lemme

Nous allons le calculer explicitement. Pour simplifier les formules, supposons que et sont unitaires. Le vecteur est donné par et on a On veut donc envoyer ( , , ) sur ( , , ). La matrice de ( , , ) dans la base est avec . En posant et , la matrice de ( , , ) dans la base est La matrice de la transformation dans la base canonique est donc . La troisième colonne de M₂ M₁^t est la troisième colonne de M₂ (autrement dit ) puisqu'on envoie sur .

Supposons le polyèdre donné par les coordonnées de ses sommets et par la liste de ses faces: chaque face est donnée par la liste de ses sommets consécutifs orientée par une normale extérieure au polyèdre, c'est-à-dire que si les sommets sont , pour et sont des normales extérieures à la face.
Fixons une face, par exemple la dernière dans la liste des faces, nommée d . Soit un arbre couvrant du graphe des faces donné par la fonction en direction de d : si j est une face, est la face suivant j si l'on désire aller de la face j à la face d . Le but est donc d'avoir la liste des coordonnées des sommets du patron et la liste des faces.
On commence par la face d que l'on déplace dans le plan d'équation z=0 . On va ensuite rajouter les faces une à une. Expliquons comment on ajoute à une face s déjà calculée une face t non encore calculée telle que .

1. On calcule l'arête (S₁ S₂) du polyèdre de la face t telle que (S₂ S₁) est une arête de la face s . On connait les sommets et correspondants sur le patron.
2. On calcule alors le déplacement qui envoie les sommets S₁ et S₂ du polyèdre sur les sommets et du patron et la normale extérieure unitaire à la face t sur le vecteur unitaire (lemme deptheta avec ).
3. On l'applique à tous les sommets de la face t . Cela permet donc de tracer l'image de la face t dans le patron dans le plan d'équation z=0 .
4. S'il y a un chevauchement de cette face t avec les autres faces déjà calculées, on rejette l'arbre couvrant en question car il correspond à un pseudo-patron et non à un patron. Sinon, on continue à ajouter les nouvelles faces jusqu'à épuisement des faces du polyèdre.

On a maintenant un arbre couvrant et le patron associé. On cherche à replier le patron pour obtenir le polyèdre. Les données sont donc maintenant

• les coordonnées des sommets et les faces du polyèdre;
• les coordonnées des sommets et les faces du patron, celles-ci étant dans le même ordre que les faces du polyèdre;
• la correspondance entre les sommets du patron et les sommets du polyèdre;
• pour chaque face s du polyèdre, sa normale unitaire extérieure .

On se donne un paramètre u entre 0 et 1 et on cherche à visualiser le patron qui commence à se replier. On note cette "coque" . Le patron que l'on désire replier dans le plan orthogonal à est et le polyèdre dans est . On procède comme pour la construction du patron.
Supposons qu'une face numéro s de soit déjà calculée ainsi qu'une normale unitaire et que la face numéro t de où n'ait pas été encore calculée. On calcule l'arête (S₁,S₂) du polyèdre de la face t telle que (S₂,S₁) est une arête de la face s . On connait l'arête (resp. ) correspondante sur (resp. ). Le lemme deptheta avec

1. , ,
2. la normale extérieure de la face numéro s de ,
3. avec l'angle entre les faces numéro s et t du polyèdre

permet de trouver un déplacement que l'on applique à tous les sommets de la face numéro t de et d'obtenir la normale extérieure (le du lemme deptheta ) et on continue

Patron associé à l'arbre couvrant représenté par []

Soit un polyèdre combinatoire. Le polyèdre combinatoire dual de est obtenu de la manière suivante. On associe à chaque face f de un sommet s_f de . Soit t un sommet de . Soit l'ensemble des faces auquel t appartient, ordonné de manière à ce que

1. f_i et ont une arête commune
2. si , le successeur de t dans la face est s (cela restera alors vrai pour ).

On a alors . Si on est parti d'un polyèdre, est simplement la liste des faces qui se rencontrent au sommet t dans l'ordre trigonométrique vu de l'extérieur.
On associe au sommet t la face de et on associe à une arête a de entre les faces f₁ et f₂ l'arête de qui relie les sommets et .
Les sommets du graphe associé à (qui sont les faces de ) sont donc en bijection naturelle avec les sommets de .
Une construction géométrique du polyèdre dual d'un polyèdre convexe est la suivante. On part du centre C du polyèdre (convexe), c'est-à-dire l'isobarycentre des sommets. On considère une sphère de centre C et de rayon r , par exemple 1. On définit géométriquement le polyèdre dual par polarité par rapport à cette sphère: à chaque sommet A , on associe le plan P_A perpendiculaire au segment C A et tel que le produit des distances algébriques de C à A et à P_A est égale à r² . Le polyèdre dual est le polyèdre convexe dont les faces sont contenues dans les plans P_A . La face du polyèdre dual associée à A est la face contenue dans le plan P_A .
À un arbre couvrant du graphe associé à , on associe un arbre couvrant du graphe associé à de la manière suivante. Si l'arbre de est obtenu en supprimant le sous-ensemble X d'arêtes de , l'arbre couvrant associé est obtenu en supprimant le complémentaire de l'image de X dans l'ensemble des arêtes de . Ainsi, à tout pseudo-patron de obtenu en découpant les arêtes appartenant à X , on fait correspondre le pseudo-patron de obtenu en découpant les arêtes de "croisant" (par projection sur la sphère) celles de qui ne sont pas dans X .
Exemples

La bibliographie est très partielle. Beaucoup de sites internet parlent de ce sujet. Le but de ce document est simplement de présenter les algorithmes que nous avons utilisés pour permettre d'obtenir des patrons à découper (par exemple en tikz dans Polyèdres convexes ).

• [Broder] Broder, A., Generating random spanning trees, 30th Annual Symposium on Foundations of Computer Science Year: 1989 | Conference Paper | Publisher: IEEE
• [Dürer] Dürer, A., Unterweisung der Messung mit dem Zirkel und Richtscheit, 1525. English translation and commentary, W. Strauss, The Painter's Manual, Abaris, New York, 1977.
• [Shephard] Shephard, G., Convex polytopes with convex nets, Math. Proc. Camb. Phil. Soc. 78 (1975) 389-403.