Surfaces et polyèdres - Bienvenue sur perso.math.u-pem.fr

Chapitre II

Surfaces et polyèdres

Dans ce chapitre nous introduisons les objets principaux de notre étude : les surfacesdiscrètes ou polyédriques. Nous définirons les invariants géométriques, combinatoires ettopologiques de base nous permettant de mieux comprendre et manipuler les surfaces,en prélude aux applications et constructions plus sophistiquées des chapitres qui suivent.Ces invariants s’avèrent remarquablement riches bien qu’élémentaires (notammentles courbures) comparés au cas des surfaces lisses, et leur compréhension ne requiertqu’une bonne vision dans l’espace et une connaissance de la géométrie euclidienneclassique. Nous terminerons en traitant rapidement des problèmes de convergence etd’approximation.

1 Combinatoire des surfaces discrètesDéfinition 1. Une surface polyédrique abstraite ou surface discrète abstraite S(aussi appelée complexe cellulaire de dimension 2) est la donnée

– d’un ensemble de sommets (vertices en anglais) V =V (S) fini ou infini– d’un ensemble E = E(S) d’arêtes (edges) formées de couples (non ordonnés) de

sommets distincts, notées e = (p1 p2)= (p2 p1) ; cet ensemble est toujours supposélocalement fini : tout sommet appartient à un nombre fini d’arêtes

– d’un ensemble F = F(S) de faces f = (p1 . . . pn) où les pi sont des sommets distinctset (pi pi+1) 2 E pour tout i = 1, . . . ,n (avec la convention que pn+1 = p1 de façon àobtenir une boucle 1)

satisfaisant les conditions ci-dessous : en notant Fp l’ensemble des faces contenantle sommet p, Fe l’ensemble des faces contenant l’arête e et Ep l’ensemble des arêtescontenant p, et |S| le cardinal d’un ensemble S, c-à-d le nombre de ses éléments,

(A) tout sommet est l’extrémité d’au moins 3 arêtes (2 s’il est au bord) : |Fp| 3(|Fp| 2 au bord)

1. Pour des raisons de simplicité on se limite aux faces simplement connexes, autrement dit polygonales,dont les arêtes du bord forment une seule courbe.

18 II. Surfaces et polyèdres

(B) toute arête est incidente à 2 faces (une seule si l’arête est au bord) : |Fe| = 2(|Fe| = 1 au bord)

(C) toute face possède au moins 3 arêtes 2 (ou 3 sommets, ce qui revient au même)

(D) pour tout sommet p, si les qi sont les sommets des faces contenant p (p excepté)prises dans l’ordre, alors les arêtes (qi qi+1) forment une courbe fermée, saufquand p est sur le bord, auquel cas c’est la courbe formée des arêtes (pq1), (q1q2),. . . , (qn°1qn), (qn p) qui est fermée

(E) les sommets et arêtes du bord forment une ou plusieurs courbes discrètes fermées.

Définitions. Un sommet p est incident à une arête e ou une face f (noté p 2 e oup 2 f ) si p est l’une des extrémités de l’arête e, ou l’un des sommets de f . De mêmeune arête e est incidente à une face f = (p1 . . . pn) si e est l’une des arêtes (pi pi+1). Onutilisera parfois appartenance pour signifier incidence. Deux sommets p, q sont voisins(ou adjacents) si (pq) 2 E, ce qui est noté p ª q. Une courbe est une suite p1, . . . , pn desommets voisins ; elle est dite fermée si elle forme une boucle, autrement dit si pn = p1.On parlera aussi de lacet.

Cas particulier : une triangulation ou surface triangulée est une surface polyé-drique dont les faces sont toutes triangulaires. Ce sont les surfaces les plus simples àobtenir et manipuler, mais pas nécessairement les plus simples géométriquement.

Remarque 1. De même que la donnée des sommets ne suffit pas à déterminer une courbediscrète, les ensembles V et E ne suffisent pas à déterminer F. Par exemple, on peutretirer au cube (8 sommets, 12 arêtes, 6 faces) une face ou deux faces opposées, sanschanger ni les sommets ni les arêtes (mais en créant des bords, voir ci-dessous).

Note 1. On supposera que les surfaces considérées sont connexes, c-à-d que deuxsommets quelconques de V peuvent toujours être reliés l’un à l’autre par un chemin (engénéral non unique). Si S n’est pas connexe, elle se décompose en plusieurs sous-partiesconnexes, elles aussi polyédriques, appelées composantes connexes.

On partitionne naturellement V en sommets intérieurs/internes, dont l’ensemblesera noté V , et sommets du bord ou externes/extérieurs, (ensemble V @) ; de mêmel’ensemble E des arêtes se compose des arêtes intérieures ou internes (sous-ensembleE) et des arêtes du bord ou externes (sous-ensemble E@). Une arête est intérieure si elleest incidente à deux faces, et extérieure si elle appartient à une seule. Un sommet pest intérieur (resp. extérieur) si |Fp| = |Ep| et extérieur si |Fp|+1 = |Ep| ou, de façonéquivalente, si p appartient à une arête externe. Le bord @S est constitué de la ou descourbe(s) polygonale(s) constitué des points de V @ reliés par les arêtes de E@. La surfaceest un polyèdre si elle est finie et n’a pas de bord : @S =?.

2. Cette hypothèse n’est pas cruciale, mais permet d’éviter certaines difficultés techniques, par exempledans la définition de l’axiome (D). On verra des cas où elle n’est pas satisfaite, ce qui n’empêche pas la plupartdes raisonnements.

1. Combinatoire des surfaces discrètes 19

p

(a)

q1

p1

p2

q2

(b)

q

p

(c)

p1 p2

p3

m

q1 q2

q3

(d)

FIGURE 1 – Exemples qui ne sont pas des surfaces discrètes. Dans (a) le sommetp contredit l’axiome A. Dans (b), les arêtes (p1q1) et (p2q2) sont respectivementincidentes à 0 et 1 face, ce qui contredit B, et p1, q1, q2 contredisent A. Dans (c), quel’on doit imaginer en perspective dans l’espace, l’arête (pq) est incidente à 3 faces,contredisant B. La figure (d) représente deux tétraèdres tête-bêche, ce qui contredit D,car les sommets voisins de m forment deux courbes (p1, p2, p3) et (q1, q2, q3).

On retrouve la notion habituelle de polyèdre avec la définition suivante :

Définition 2. Une surface polyédrique de l’espace, dite aussi concrète, est la donnéed’une surface polyédrique abstraite et d’une application f : V ! R3 avec la conditionsuivante : les points d’une même face sont coplanaires et il existe dans ce plan undomaine borné polygonal connexe, d’aire non vide, dont le bord est l’union des arêtes( f (pi), f (pi+1)) ; ce domaine sera identifié à la face. Les sommets de la face sont ceux dupolygone, et de même pour les arêtes.

L’idée derrière cette définition est que la surface de l’espace dicte la structureabstraite : les faces déterminent les sommets et les arêtes. Implicitement, cela exclutdeux arêtes consécutives parallèles (c-à-d trois sommets consécutifs alignés), et à plusforte raison des arêtes de longueur nulle. De même, la face est d’aire non nulle pouréliminer les faces aplaties, et les arêtes ne se coupent pas. On se restreint souvent aux


faces convexes, auquel cas chaque face est l’enveloppe convexe 3 de ses sommets. Le casle plus connu de surface polyédrique concrète est celui des polyèdres convexes : ce sontles enveloppes convexes dans l’espace d’un ensemble fini de points (chaque face estconvexe, mais on a mieux : le volume délimité par S est lui-même convexe).

Pour une surface polyédrique de l’espace, la donnée des ensembles abstraits V , E, Fest appelée la combinatoire de la surface, et elle détermine sa topologie, autrementdit sa structure à déformation continue près. Mais deux surfaces peuvent avoir unecombinatoire identique et des géométries (aspects) très différentes.

Il est intéressant de disposer d’une notion intermédiaire entre la surface abstraiteet la surface concrète.

Définition 3. Une immersion d’une surface abstraite S dans l’espace est une applica-tion f : V (S)!R3, autrement dit prescrivant l’image Pi de chaque sommet abstrait pi,telle que

– l’image d’une arête ne soit jamais de longueur nulle : si (p1 p2) 2 E alors P1 6= P2 ;– l’image d’une face ne soient jamais contenue dans une droite.

En d’autres termes, f identifie les arêtes abstraites (p1 p2) à des segments concretsde l’espace (P1P2) qui ne doivent pas être de longueur nulle. Cela n’exclut nullement quef (p1) soit égal à f (p2) si p1 et p2 ne sont pas voisins, donc f peut ne pas être injective.La notion d’immersion tient compte des sommets et par conséquent des arêtes, maisoublie en partie les faces. De plus, rien ne garantit que les sommets soient coplanaires.

Remarque 2. Les graphes sont des proches cousins des surfaces discrètes. Ils ne sontdonnés que par un ensemble de sommets V et d’arêtes E, et a priori sans les conditionsadditionnelles que nous exigeons pour les surfaces. Par exemple, des sommets peuventêtre isolés, deux sommets peuvent être reliés par plusieurs arêtes, voire un sommet reliéà lui-même (si le graphe est réflexif). Les graphes englobent des situations beaucoupplus générales que les surfaces polyédriques, et ces dernières peuvent être vues commedes cas particuliers de graphes. Il n’y a pas par contre de notion immédiate de dimensioncar il n’y a pas de face 4, par conséquent un grand nombre d’outils géométriques outopologiques ne peuvent pas être définis à ce niveau de généralité (cf. le chapitre sur lecalcul différentiel). De même les notions métriques (distance, angles, aires et courbures)sont moins naturelles 5. Certains concepts présentés dans la suite seront applicablesaux graphes (par exemple la caractéristique d’EULER), d’autres seront spécifiques àla géométrie discrète, comme l’orientation. Enfin nous verrons comment parfois leraisonnement purement combinatoire de la théorie des graphes possède un équivalentgéométrique, quand le graphe est une surface discrète munie d’une métrique appropriéedite métrique équilatérale.

3. L’enveloppe convexe d’un ensemble S est le plus petit convexe contenant S, c’est aussi l’ensemble desbarycentres à coefficients positifs ou nuls de points de S.

4. Même si la notion de clique peut s’y substituer parfois.5. On peut toutefois définir facilement une distance sur un graphe pondéré ou non, et des définitions pour

la courbure ont été proposées (voir par exemple [LLY11, JL11]). On obtient logiquement des résultats plusgénéraux mais moins fins. D’une certaine façon, les graphes ressemblent aux espaces métriques (ce qu’ils sontd’ailleurs), là où les surfaces discrètes sont les analogues des surfaces différentielles.

2. Orientation et topologie 21

Nous utiliserons quelques définitions issues de la théorie des graphes :– Distance sur les graphes : la distance d(p, q) entre deux sommets p, q d’un

graphe est la longueur (c-à-d le nombre d’arêtes) du plus court chemin reliantp à q. Si le graphe est connexe, un tel chemin existe toujours, bien qu’il ne soitpas nécessairement unique. Deux sommets sont voisins s’ils sont à distance 1.

– L’étoile d’un sommet p, notée star(p), est l’ensemble des arêtes et faces conte-nant p.

– L’étoile d’une arête e est l’ensemble des faces et arêtes touchant e.– Si p est un sommet, son degré n (aussi appelé valence) est le nombre d’arêtes le

contenant.– L’anneau en un sommet p de degré n est l’ensemble des n sommets situés sur les

arêtes incidentes 6 à p ; l’anneau orienté est constitué des sommets rangés dansl’ordre induit par leur face commune avec p. Plus généralement l’anneau de pà distance d est l’ensemble des sommets situés à distance d de p, au sens de ladistance des graphes.

2 Orientation et topologieUne arête e est un couple de sommets noté e = (pq). Par convention, les couples (pq)

et (qp) désignent la même arête e, mais si l’on prend en compte l’orientation (autrementdit le sens de parcours), alors on distinguera les deux arêtes orientées (pq) et (qp),qui sont d’orientations opposées. Pour ce faire, on note l’arête ~e = °!pq = °°!qp, ce quicorrespond au vecteur le long de l’arête, quand S est une surface concrète. L’ensembledes arêtes orientées est noté ~E. Selon le contexte, on utilisera des arêtes orientées ounon.

On peut aussi orienter les sommets, simplement en leur affectant un signe positif ounégatif (ou ce qui revient au même une valeur +1 ou °1). Enfin une face est orientée parle choix d’un sens de parcours de ses sommets consécutifs ; il y a là encore deux orien-tations opposées possibles : (p1 p2 . . . pn°1 pn) et (pn pn°1 . . . p2 p1), qui lui est opposée.L’ensemble des sommets orientés est noté ~V , celui des faces orientées ~F.

Une surface discrète S est dite orientée si

1. pour chaque face f , on s’est donné une orientation (parmi les deux possibles) ;l’orientation de f induit une orientation (un sens de parcours) sur chaque arête ede f ;

2. chaque fois qu’une arête e appartient à deux faces f1, f2 (c-à-d toutes les arêtessauf celles du bord), les deux orientations induites par f1 et f2 sont opposées. Ondit alors que les orientations sur f1 et f2 sont compatibles.

Une surface est orientable si elle possède une orientation (et donc forcément deux).On remarquera que l’orientation de S permet de choisir aussi un sens de parcours surle bord de star(p).

6. Attention : si les faces ne sont pas triangulaires, l’anneau en p ne contient pas tous les sommets del’étoile de p.


p1

p2

p3 p4

p5

(a) (b)

p3

p2 p5

p4

p1

FIGURE 2 – Orientations induites sur deux faces adjacentes. Dans le cas (a), lesorientations (p1 p2 p3) et (p2 p1 p4 p5) induisent deux orientations opposées sur l’arête(p1 p2), elles sont donc compatibles. Dans (b) au contraire, les orientations (p1 p2 p3) et(p1 p2 p5 p4)=°(p2 p1 p4 p5) sont non compatibles.

Remarque 3. Une arête orientée~e = (pq)=°!pq induit elle aussi une orientation sur lesdeux sommets extrémités : par convention elle vaut +1 au point d’arrivée q et °1 aupoint de départ. L’interprétation de cette convention sera donnée dans le chapitre sur lecalcul différentiel (§IV.1.1).

Pour une surface polyédrique concrète de l’espace, l’orientation d’une face est ma-térialisée par un vecteur normal (unité) ~N orthogonal au plan de la face, et tel que lenombre de rotation du bord de la face soit +1 (soit encore : la somme des angles derotation soit +2º). En pratique, il faut et il suffit que ~N ^°°°°°!pi pi+1 pointe vers l’intérieurde la face, quelle que soit l’arête positivement orientée °°°°°!pi pi+1. Notons que si la face estconvexe (notamment un triangle), et p1, p2, p3 sont trois points non alignés consécutifspris dans l’ordre, alors ~N est un multiple positif de °°°!p1 p2 ^°°°!p2 p3.

Il faut se rappeler qu’il est très simple de construire des surfaces non orientables(discrètes ou continues), comme la plus célèbre, le ruban de MÖBIUS (par contre, unesurface non orientable ne pourra jamais border un solide de l’espace). Dans la suitetoutes les surfaces considérées seront supposées orientées.

Définition 4. La caractéristique d’EULER de S est le nombre entier ¬= |V |°|E|+|F|.Quand S est une surface sans bord, ¬ est paire, et on définit le genre comme l’entier gtel que ¬= 2°2g.

La caractéristique d’EULER est un invariant combinatoire (ou topologique) de lasurface polyédrique, au sens où il caractérise de façon très grossière la forme de lasurface (abstraite). Deux surfaces ayant des invariants différents ne sont jamais équi-valentes 7. Pour une surface sans bord, le genre g = 2°¬

2 est le nombre de poignées de

7. Pour une définition rigoureuse il faudrait préciser de quelle équivalence il s’agit. Évidemment, deuxcombinatoires bijectives (c-à-d qu’il existe une bijection qui échange sommets, arêtes et faces) sont équivalentes,mais cette définition est trop restrictive. Une démonstration rigoureuse nous entrainerait trop loin, mais onpeut au moins considérer que le raffinement d’une surface donne une surface équivalente : le découpage d’une

2. Orientation et topologie 23

cette surface, et plus généralement, pour une surface avec g poignées dont le bordse compose de r courbes, ¬ = 2°2g° r. Une démonstration (partielle) de ce résultatest donnée en proposition IV.3. Noter que la caractéristique d’EULER est aussi défi-nie — différemment — pour les surfaces continues (voir [Mun84, Pha99], ainsi quehttp://www.ics.uci.edu/˜eppstein/junkyard/euler/ pour plus de détails).

FIGURE 3 – Tétraèdre et cube. Leurs caractéristiques d’Euler respectives sont lesmêmes : ¬= 4°6+4= 2 et ¬= 8°12+6= 2. Ce sont des polyèdres réguliers : le degréet le nombre de sommets par face sont constants, et la courbure combinatoire (voirci-dessous) est constante égale à 1/2 pour le tétraèdre et 1/4 pour le carré.

FIGURE 4 – Tore (genre 1 et caractéristique d’EULER ¬= 16°32+16= 0). Les faces sonttoutes quadrilatérales et le degré des sommets est 4, donc la courbure combinatoire(voir définition 5) est constante égale à 0.

Le premier invariant différentiel que l’on rencontre a été introduit par GROMOV

[Gro87] pour les graphes ; il s’applique donc aux surfaces polyédriques. Comme engéométrie continue, on retrouve un lien avec la topologie.

face en plusieurs faces via l’ajout d’un sommet. Si la face de départ possède m côtés, alors V !V+1, E ! E+met F ! F +m°1 (la face d’origine disparaissant), donc la caractéristique d’EULER ne change pas. D’où l’idéede définir comme équivalentes des surfaces pouvant être raffinées jusqu’à posséder la même combinatoire.Clairement deux surfaces équivalentes doivent avoir la même caractéristique d’EULER. Notons que l’opérationinverse du raffinage (la fusion de deux faces adjacentes) ne change pas non plus la caractéristique d’EULER.


Définition 5. La courbure combinatoire en un point p d’une surface polyédriqueest la grandeur

K(p)= 1° d2+

X

f 3p

1| f | (1)

où d est le degré de p, et la somme est prise sur toutes les faces f contenant p, | f | étantle nombre de côtés (ou de sommets) de la face f .

Proposition 1. La somme des courbures combinatoires est égale à la caractéristiqued’EULER de la surface polyédrique. En particulier c’est un nombre entier.

Démonstration. ClairementP

p2V 1= |V | ; Pp2V d(p)= 2|E| car chaque arête est comp-

tée deux fois (une fois pour chaque extrémité). Enfin si l’on somme pour chaque sommetles faces adjacentes, chaque face va être comptée autant de fois qu’elle a des sommets,donc X

p2V

X

f 3p

1| f | =

X

f 2F

X

p2 f

1| f | =

X

f 2F1= |F|.

Par conséquent

X

p2VK(p)=

X

p2V1° 1

2X

p2Vd(p)+

X

p2V

X

f 3p

1| f | = |V |° |E|+ |F| = ¬(S).

A priori, cette définition est purement combinatoire et non géométrique : elle n’utiliseaucune notion de longueur, d’aire ou d’angle, et elle ne changerait pas si notre polyèdreconcret était déformé en allongeant ou rétrécissant ses dimensions. Néanmoins il y a unlien avec la géométrie, voir la remarque 5 plus bas.

Exercice 1. On dit qu’une triangulation est régulière si le degré est toujours égal à6. Exprimer cette condition en fonction de la courbure combinatoire, et en déduirequ’il n’existe aucune triangulation de la sphère (¬= 2) qui soit régulière : au moins unsommet est de degré inférieur à 6.

Idem pour les quadrangulations (surfaces discrètes dont les faces ont toutes 4 côtés),qui sont régulières si le degré est 4.

Exercice 2. Pour tout entier k, notons vk le nombre de sommets de degré k et wk lenombre de faces ayant k côtés. Alors |V | =P

k vk et |F| =Pk wk, donc la caractéristique

d’EULER est¬=

X

kvk ° |E|+

X

kwk.

Montrer la formule de double comptage pour une surface sans bord :X

kkvk =

X

kkwk = 2|E|.

Elle est partiellement fausse si E@ 6=? ; quelle est sa généralisation (en fonction de |E|et |E@|) ?

3. Géométrie intrinsèque : le défaut angulaire 25

En déduire que pour une surface finie sans bord dont les faces possèdent toutes ncôtés, le degré moyen

d =P

k kvkPk vk

tend vers 2nn°2 (qui n’est entier que si n 2 {3,4,6}), quand |V | tend vers l’infini. On notera

que la formule est exacte (sans passage à la limite) quand ¬ = 0. En particulier onretrouve que le degré moyen pour une triangulation avec beaucoup de triangles est 6, et4 pour une quadrangulation.

3 Géométrie intrinsèque : le défaut angulaireMunissons maintenant les surfaces discrètes d’une structure géométrique. Dans

l’espace, les quantités géométriques naturelles, appelés invariants, d’une surface polyé-drique sont les longueurs et les angles à l’intérieur des faces. Pour une surface concrète,ils se déduisent évidemment des positions des sommets et de la combinatoire ; néan-moins les positions ne sont pas invariantes par un déplacement isométrique (translation,rotation ou symétrie), contrairement aux longueurs et angles mesurés dans les faces.Ces derniers déterminent la géométrie intrinsèque de la surface : tout ce qui peut êtremesuré sur la surface indépendamment de la façon dont elle se place dans l’espace(et qui peut même être défini pour une surface abstraite). Les angles diédraux (voirci-dessous) au contraire expriment sa géométrie extrinsèque, à savoir la façon dont elleest positionnée dans l’espace. Notons que deux surfaces peuvent posséder la mêmegéométrie intrinsèque — on dit qu’elles sont isométriques — sans pour autant êtrecongruentes, c-à-d image l’une de l’autre par une isométrie de l’espace.

On munit une surface polyédrique abstraite d’une géométrie intrinsèque, aussiappelée structure métrique ou simplement métrique, en identifiant chaque face à uneface du plan. Par exemple une face à trois sommets (p1 p2 p3) est identifiée métriquementà un (vrai) triangle (P1P2P3) du plan, et hérite de ses invariants métriques : la longueurp1 p2 est égale à P1P2, l’angle (p1 p2 p3) est égal à (P1P2P3) etc. Naturellement, si lasurface est en fait concrète (elle vit dans l’espace), cette identification entre faces estautomatique (et implicite). Cette identification obéit à une seule exigence : la longueurd’une arête doit être la même dans les deux faces la contenant. Notons en passant qu’untriangle est entièrement déterminé par les longueurs de ses côtés 8 donc les angles auxsommets sont inutiles et il en va de même pour toute surface triangulée. Par contre cen’est pas vrai pour des polygones plus généraux.

Exemple 1. Dans la métrique équilatérale, chaque face est identifiée à un polygonerégulier dont les arêtes sont de longueur 1. L’angle Æ f (p) que fait la face f en le sommetp est par conséquent º° 2º

n si la face f possède n côtés (cf. corollaire A.1 en annexe).La distance induite par la métrique équilatérale est la distance des graphes, et cettemétrique reflète essentiellement la combinatoire du graphe (voir plus bas la remarque 5).

8. À réflexion près, ce qui ne joue pas de rôle ici.


Avec le concept de métrique arrivent aussi deux notions de distance 9. Une premièredistance d(p, q) entre deux sommets de V est définie comme la longueur du plus courtchemin reliant p à q : si ∞= (p0, p1, . . . , pn) est un chemin reliant p = p0 à q = pn, alorsla longueur de ∞ est la somme des longueurs pi pi+1 des arêtes successives :

`(∞)=n°1X

i=0pi pi+1.

Comme S est connexe un tel chemin existe toujours, et d(p, q) est par définition la borneinférieure des longueurs de ces chemins. Quand S est finie, ou infinie mais localementfinie et de longueur minorée, la borne inférieure existe et est clairement strictement po-sitive (si p 6= q). Si S est infini, la distance est a priori un infimum, mais les hypothèsesci-dessus garantissent que l’infimum est atteint, bien que plusieurs chemins distinctspuissent le réaliser (voir exercice 3 ci-dessous). Dans le cas de la métrique équilatérale,on retrouve la distance habituelle sur les graphes.

On peut aussi définir une distance intrinsèque (non combinatoire) en considérantla surface S comme pleine, autrement dit en prenant aussi en compte les points àl’intérieur des faces. On peut alors encore tracer des chemins entre deux points pet q, qui ne sont plus nécessairement des sommets, constitués de courbes tracéessuccessivement sur chaque face. La distance est alors l’infimum de des longueurs detous ces chemins. On est alors dans le cadre de la géométrie riemannienne sur unesurface localement plate à singularités coniques.

Exercice 3. Montrer que si S est une surface discrète infinie munie d’une métrique,mais localement finie et dont les arêtes sont de longueur minorée, alors l’infimum de ladistance entre deux sommets est atteint par un chemin. On supposera, par l’absurde,qu’il existe une suite (∞n) de chemins de longueurs décroissantes avec `(∞n)! d(p, q),et on montrera que l’on peut fixer le premier point du chemin (après p). Montrer alorsque le nombre de sommets de ces chemins est majoré et conclure.

Dès que S est munie d’une métrique, on peut calculer des longueurs et des anglesà l’intérieur de chaque face par identification avec le plan. Il est aussi possible detravailler avec deux faces adjacentes : tout se passe comme si l’union des deux facesétait un polygone du plan formé des deux polygones correspondants, quitte à déplacerl’un des polygones pour le recoller le long de l’arête commune 10. C’est l’opération

9. Le lecteur notera l’ambivalence du mot « métrique », parfois synonyme de distance ; dans cet ouvrage,nous emploierons « métrique » comme en géométrie différentielle, comme une façon de mesurer les longueurset les angles.

10. Deux problèmes se posent : (i) les polygones images recollés peuvent se superposer ailleurs que le longde l’arête commune et (ii) il peut y avoir plusieurs arêtes communes. Le dépliage donnerait alors une fausseimage. Le cas (i) est visuellement gênant, mais ne change rien à la structure sous-jacente ; il se traite enconsidérant différemment un point selon qu’il est issu d’une face ou de l’autre (c’est le principe des immersions,et plus généralement des revêtements, cf. §IV.3.3). Le cas (ii) est visuellement cohérent, mais implique unecombinatoire parfois plus complexe. On l’évite en imposant que la surface soit quasi-convexe : deux faces nepossèdent au plus qu’une arête commune. On peut écarter ces deux problèmes en ne travaillant qu’avec desfaces convexes.


dite de dépliage : voir la figure 5 pour un exemple de dépliage de trois faces d’untétraèdre. Il faut noter qu’on ne peut pas en général déplier autant de faces que l’onveut et garder collées toutes les arêtes, sauf dans le cas trivial d’une surface plane. Cesobstructions au dépliage viennent de la topologie/combinatoire (un cylindre n’est pasdépliable globalement, bien qu’il soit plat) ou de la géométrie (un carré privé d’une faceest topologiquement identique à un disque, mais la courbure de ses sommets empêchede le déplier). L’invariant géométrique mesurant l’obstruction locale au dépliage est lacourbure gaussienne, incarnée par le défaut angulaire.

Définition 6. Soit p un sommet, Æ1, . . . ,Æn les angles en p des faces contenant cesommet (aussi notés Æ f (p) pour la face f ). On suppose la surface orientée, donc cesangles sont mesurés par rapport à cette orientation. L’angle total au sommet p est lasomme

µ(p) :=X

iÆi =

X

f 3pÆ f (p)

et le défaut angulaire en p (vertex angle excess) est

Æ(p) :=Ω

2º°µ(p) si p est intérieurº°µ(p) si p 2 @S

Q Æ1 Æ2

Æ3

Æ1 Æ2

Æ3

Æpp

f1f2

f3

f1

f3

f2

FIGURE 5 – Dépliage d’un tétraèdre (privé de sa face inférieure) autour du sommet p.La face f3 est située derrière le tétraèdre. Le dépliage se fait le long des arêtes f1 \ f2et f2 \ f3 et la découpe le long de l’arête f1 \ f3 (symbole Q). Au sommet p, le défautangulaire Æ= 2º°Æ1 °Æ2 °Æ3 mesure ce qui manque au tétraèdre déplié pour faireun tour complet.

Le nom de défaut angulaire vient de ce que Æ = 0 si et seulement si la surfaceest plane en p ; on parle alors de sommet euclidien. L’étoile d’un sommet euclidienest dépliable à plat (et réciproquement). Si Æ < 2º (resp. Æ > 2º) le sommet est ditsphérique (resp. hyperbolique). Si par exemple la surface est strictement convexealors Æ< 2º (mais la réciproque est fausse : attention aux plis), et si elle est en forme deselle, Æ> 2º. Par contre le défaut angulaire ne fait pas la différence entre angle rentrantet angle saillant (voir plus bas en page 34, l’angle diédral).


∞

q

∞

Æ1 Æ2 Æ1 Æ2

µ

Æq

f1f2

f3

f1

f2

FIGURE 6 – En un sommet q du bord ∞ d’un tétraèdre privé de sa face inférieure, ondétermine les angles aux faces Æ1,Æ2 et l’angle total µ =Æ1+Æ2 en dépliant sur un planle long de l’arête commune f1 \ f2. Le défaut angulaire Æ=º°µ mesure alors l’anglede rotation de la courbe par rapport à un trajet rectiligne, autrement dit la courburegéodésique.

En géométrie différentielle continue, la courbure gaussienne classique est infinieau sommet (c’est un Dirac au sens de la théorie de la mesure), mais l’intégrale de lacourbure est finie et est mesurée justement par le défaut angulaire. En ce sens, ledéfaut angulaire est une quantité intégrale et non une courbure ponctuelle. On obtient ledéfaut angulaire Æ comme mesure de la courbure gaussienne en appliquant la formulede GAUSS–BONNET à star(p), dont le bord est la courbe ∞ passant par q1, . . . , qn. Eneffet, notons '°

i ,'+i les deux angles en qi des bords de star(p), alors la face (pqi qi+1)

aura comme angles Æi,'+i ,'°

i+1. Le théorème de GAUSS–BONNET A.6 appliqué à star(p)donne

Æ(p)= courbure totale de star(p)= 2º°courbure géodésique totale de la courbe ∞

or ∞ est rectiligne par morceaux donc sa courbure ne vient que des changement dedirections aux arêtes, qui valent chacun º°'°

i °'+i (pour s’en convaincre mettre les

faces à plats : dans un plan la seule courbure est la courbure géodésique). Par conséquentZ

star(p)K = 2º°

X

i(º°'°

i °'+i )= 2º°

X

i(º°'°

i°1 °'+i )= 2º°

X

iÆi =Æ

ce qui montre bien que le défaut angulaire est une quantité intégrale.

Remarque 4. Le calcul ci-dessus est fait dans le cas où star(p) est composé de triangles,mais de fait la présence de polygones plus compliqués ne change rien. En effet on peutraffiner la triangulation en découpant chaque face contenant p en un triangle et uneface complémentaire. L’apport de ces faces complémentaires à la courbure en p est nul.


On peut alors définir la courbure gaussienne au sommet p comme

K(p)= 3Æ(p)aire(star(p))

(2)

obtenant ainsi une quantité homogène de degré °2. Le facteur 3 est relativementarbitraire, et correspond au point de vue suivant, consistant à « diffuser » la courburesur les faces, dans le cas d’une surface triangulée. En effet on peut dans ce cas définirune fonction continue K sur les faces par interpolation linéaire entre les valeurs fixéesaux sommets par (2) aux sommets, alors le facteur 3 garantit que la formule de GAUSS–BONNET reste vraie.

On notera néanmoins que cette quantité n’est pas forcément cohérente avec lemodèle continu, voir la section §6.

Note 2. Le défaut angulaire est aussi appelé courbure concentrée ou distorsiondiscrète en un sommet (voir [MDFP08]), et peut se généraliser à des dimensionssupérieures.

Comme en géométrie continue, on peut énoncer un lien entre courbure locale etcombinatoire (lien en fait historiquement antérieur).

Théorème 1. (Formule de GAUSS–BONNET simpliciale)Sur une surface polyédrique S finie

X

p2VÆ(p)=

Z

SKdA = 2º¬(S)= 2º(|V |° |E|° |F|).

De façon équivalente, en notant V @ l’ensemble des points du bord et V =V °V @ l’ensembledes sommets intérieurs, il vient donc,

X

p2V(2º°µ(p))+

X

p2V @

(º°µ(p))= 2º¬(S) (3)

où µ(p) l’angle total au sommet p.

Démonstration. On peut évidemment se reporter au théorème de GAUSS–BONNET A.6mais une démonstration directe et plus élémentaire est possible. Supposons pour com-mencer que la surface S n’ait pas de bord, alors

X

p2VÆ(p)=

X

p2V(2º°µ(p))= 2º|V |°

X

p2V

X

f 3pÆ f (p)

où Æ f est l’angle en p de la face f . Soit | f | le nombre de sommets (ou d’arêtes) de laface f , X

p2V

X

f 3pÆ f (p)=

X

f 2F

X

p2 fÆ f (p)=

X

f 2F(| f |°2)º

en utilisant le corollaire A.1. EnfinP

f | f | compte les arêtes deux fois (une pour chaqueface). Par conséquent

X

p2VÆ(p)= 2º|V |°

X

f(| f |°2)º= 2º|V |°2º|E|+2º|F| = 2º¬(S).


Si maintenant S possède un bord, le raisonnement fonctionne à ceci près que lesarêtes du bord n’appartiennent qu’à une face donc ne seront comptées qu’une fois.Notons donc E@ l’ensemble des arêtes du bord et E = E°E@. Alors

X

pÆ(p) =

X

p2V(2º°µ(p))+

X

p2V @

(º°µ(p))= 2º|V |+º|V @|°X

p2V

X

f 3pÆ f (p)

= 2º|V |+º|V @|°X

f 2F

X

p2 f(| f |°2)º

= 2º|V |+º|V @|° (2|E|+ |E@|)º+2º|F|= 2º(|V |° |E|+ |F|)= 2º(|V |° |E|+ |F|)

où l’on se sert deux fois du fait que |V @| = |E@|. Voir [Res93, PS06] pour plus de détailssur cette démonstration.

Remarque 5. Il y a un lien fort entre le défaut angulaire et la courbure combinatoiredéfinie plus haut (définition 5). En effet si l’on se donne une surface polyédrique abstraite,et que l’on fixe comme métrique la métrique équilatérale (définie en §1), alors la courburecombinatoire en p est égale à Æ(p)

2º . En effet, si une face f contenant p est un polygonerégulier à | f | côtés, alors l’angle en p est º° 2º

| f | (corollaire A.1). Sommons en distinguantdeux cas :

– si p est un point intérieur, le nombre de faces en p est égal au nombre d’arêtes lecontenant (autrement dit le degré) : |Fp| = |Ep| = d(p) donc

Æ(p)= 2º°µ(p)= 2º°X

f 2Fp

µº° 2º

| f |

∂= 2º

√

1° d2+

X

f 2Fp

1| f |

!

= 2ºKcombinatoire

– si p est sur le bord, |Fp| = d°1 et

Æ(p)=º°µ(p)= 2º

√12° d°1

2+

X

f 2Fp

1| f |

!

= 2ºKcombinatoire.

Dans ce cas (et dans ce cas uniquement) le défaut angulaire d’une surface polyédriqueest égal à 2º fois la courbure combinatoire. La proposition 1 est donc une conséquencedu théorème 1 et sa démonstration est en fait un cas particulier de celle du théorème.

4 Courbure géodésiqueLa formule de GAUSS–BONNET indique clairement que le bord de S joue un rôle

particulier. Dans le cas continu (voir A.6) on fait la somme de l’intégrale (de surface)de la courbure gaussienne sur S et l’intégrale (curviligne) le long de la courbe @S dubord d’une quantité appelée courbure géodésique. Il est utile de généraliser cettecourbure au cas d’une courbe ∞ tracée sur S (qui n’est plus nécessairement la courbedu bord). La courbure géodésique mesure la déviation de ∞ par rapport à la « lignedroite », le concept de ligne droite étant généralisé en géométrie différentielle par celui

4. Courbure géodésique 31

de géodésique, autrement dit, de plus court chemin entre deux points. Cette définitionest claire et solide mais nécessite un bagage technique relativement important (qui peutnéanmoins être simplifié pour les courbes et surfaces de l’espace, voir annexe §A.2.3).En particulier, il y a localement une unique géodésique entre deux points d’une surface.

Dans le cas discret la situation est différente. On définit une courbe tracée sur unesurface polyédrique S comme une suite d’arcs tracés chacun sur une face et recolléspar continuité. Trois niveaux de généralité sont possibles, par ordre de simplificationcroissante :

1. la restriction de la courbe à chaque face est un arc régulier du plan reliant deuxpoints du bord de la face, et la tangente à l’arc possède une limite aux extrémités ;

2. idem, mais l’arc est un segment (par conséquent la limite aux extrémités existetrivialement) ;

3. la courbe est composée d’une succession d’arêtes de S (cas d’un bord commeci-dessus).

L’étude de la courbe à l’intérieur d’une face relève de la géométrie différentielle planeclassique (cf. annexe). On sait par exemple qu’un plus court chemin sera forcémentrectiligne à l’intérieur d’une face, autrement dit ce sera un segment. La nouveauté engéométrie discrète vient des transitions entre faces. Deux possibilités existent, selon quele point de raccord se situe le long d’une arête ou en un sommet. Si la courbe traverseune arête entre les faces f°, f+ (mais pas un sommet), tout se passe comme si l’arêteétait dépliée. La courbe est alors dite rectiligne si sa version dépliée l’est. Notons ~T° levecteur tangent limite sortant à la fin de l’arc ∞° = ∞\ f° et ~T+ le vecteur tangent limiteentrant au début de l’arc ∞+ = ∞\ f+. Alors on dira que la courbe se poursuit de façonrégulière si les angles (~T°,~e) et (~T+,~e) sont identiques, où~e est un vecteur directeur del’arête (peu importe son sens) 11. De façon générale la courbure géodésique au point p où∞ traverse l’arête est

∑g(p)= (~T+,~e)° (~T°,~e)

et cette fois-ci le sens de~e est choisi de sorte que (~T°,~e) soit positivement orienté dansla face f°. On peut aussi mesurer cet angle en prenant l’angle ' entre ∞° et ∞+ mesurédans le dépliage, ou bien en additionnant les angle entre ∞° et les arêtes successives,jusqu’à ∞+, en tournant dans le sens positif. Alors

∑g(p)='°º.

Le point p de la courbe ∞ sera dit régulier si ∑g(p)= 0 et anguleux sinon.Si la courbe ∞ passe par un sommet p 2 V il devient délicat de définir la courbure

géodésique car aucun dépliage ne convient (sauf dans le cas exceptionnel d’un sommeteuclidien où Æ(p) = 0). Pour une courbe générique, passer par un sommet est rare(cela n’arrive presque jamais au sens de la mesure), mais à l’inverse, pour une courbeconstituées d’arêtes, les sommets de la courbe sont systématiquement des sommets dela surface. Cette difficulté de définition entraine une réelle différence entre le cas discret

11. Remarquons que ce critère est bien intrinsèque, même si on peut l’appliquer à une surface concrète del’espace ; les vecteurs ~T+,~T°,~e n’ont plus la même interprétation mais les angles sont inchangés.


et le cas continu : dans le cas discret, on perd l’unicité locale des plus courts cheminsquand on passe par un sommet. Autrement dit (i) on n’a plus nécessairement un pluscourt chemin unique, reliant deux points à proximité d’un sommet et (ii) une lignedroite partant d’un point et passant par un sommet peut être prolongée par une infinitéde lignes droites au delà du sommet (ce qui est impossible en géométrie différentielleclassique).

On peut résoudre en partie cette difficulté en séparant le concept de géodésique (ausens de ligne droite 12) de celui de plus court chemin, comme le proposent POLTHIER

& SCHMIES dans [PS06]. Ils définissent la courbure géodésique discrète de ∞ en unsommet p de la manière suivante. Soit µ l’angle total en p, et ' l’angle intrinsèqueentre (°~T°) et ~T+, mesuré sur la surface en additionnant les angles successifs entre lesegment ∞° = ∞\ f° et les arêtes avoisinantes, jusqu’à ∞+ = ∞\ f+. Il y a deux façons defaire le tour du sommet p, nous choisirons de tourner dans le sens positif autour de p,c-à-d en partant à droite de ∞ (par rapport à sens de ∞). Notons que la somme des anglesdans l’autre sens est égale à Ø= µ°' par définition de l’angle total. Alors

∑g(p) := 2ºµ

µ'° µ

2

∂

est la courbure géodésique discrète. En particulier elle est nulle si '= µ/2, autrementdit si '= µ°'=Ø : l’angle (∞°,∞+) est le même mesuré dans un sens ou dans l’autre. Ence sens, une courbe de courbure géodésique nulle adopte la position la plus symétriquepossible. Si ∑g s’annule, ∞ est dite régulière, sinon elle dite anguleuse, et l’on mesurealors sa déviation par rapport à la ligne droite, normalisée sur 2º.

On récupère alors la propriété d’unicité du prolongement, mais on perd a priori toutenotion de plus court chemin. Notons enfin aussi que si le point est euclidien, Æ(p)= 0,µ(p)= 2º et l’on retombe sur le cas précédent : ∑g(p)='°º.

Remarque 6. Il faut noter que les courbures géodésiques définies ci-dessus sont en faitdes quantités intégrales, comme c’est le cas pour les points anguleux d’une courbe duplan. Une définition plus rigoureuse et plus générale (mais abstraite) associerait à ∞

une mesure µ comprenant une partie densité ∑g(s)ds, égale à la courbure géodésiquedifférentielle habituelle sur chaque face, sauf peut-être en quelques points anguleux, etdes mesures de DIRAC en chaque point anguleux, qu’il soit à l’intérieur d’une face, surune arête ou en un sommet. En intégrant il viendra donc

Z

∞µ=

n°1X

i=0

Zpi+1

pi∑g(s)ds+

n°1X

i=1∑g(pi).

Dans la plupart des cas les courbes seront rectiligne à l’intérieur de chaque face, parconséquent il n’y aura aucune contribution de type intégral, mais seulement des sommesd’angles.

12. Appelée « géodésique la plus droite » (straightest geodesic) par POLTHIER & SCHMIES, pour la distinguerdes autres concepts de géodésiques.

5. Géométrie extrinsèque 33

Nous pouvons revisiter la formule de GAUSS–BONNET en cherchant l’analogue plusprécis du cas continu Z

≠KdA+

Z

@≠∑gds = 2º¬(≠)

dans le cas où ≠ est un sous-domaine strict. Cela permet de traiter le cas d’un domaine≠Ω S polyédrique union de faces de S. Son bord orienté @≠ sera représenté par une 13

courbe ∞ et on suppose que @≠\@S =? (par exemple si @S =?). La formule de GAUSS–BONNET reste vraie en corrigeant le terme d’intégrale de la courbure gaussienne(autrement dit le défaut angulaire) près du bord de ≠, pour tenir compte de ce que ledomaine d’intégration ne couvre pas toutes les faces de S mais seulement celles de ≠.On a alors [PS06] :

Théorème 2 (Formule de GAUSS–BONNET simpliciale avec courbure géodésique).Notons Æ≠ le défaut angulaire restreint à ≠ défini par

Æ≠(p)=(

2º°µ(p) si p 2 ≠Ø(p)µ(p) (2º°µ(p)) si p 2 @≠

où µ(p) est l’angle total en p (lié à la géométrie de S) et pour p 2 @≠, Ø(p) est la sommedes angles en p des faces de ≠. Alors

X

p2≠Æ≠(p)+

X

@≠

∑g(p)= 2º¬(≠).

Démonstration. La démonstration part de la formule de GAUSS–BONNET (3) qui resteapplicable à ≠ (indépendamment de S). Pour la partie intérieure à ≠, Æ≠ =Æ donc lescontributions sont identiques. Pour ce qui est du bord, ce qui dans (3) est l’angle totalau bord µ(p) est ici remplacé par Ø(p). Or Ø n’est autre que le complément de l’angle derotation de la courbe bord ∞ : Ø= µ°'. Il vient alors

Æ≠+∑g =µ°'µ

(2º°µ)+ 2ºµ

µ'° µ

2

∂=º° (µ°')=º°Ø

ce qui est exactement le terme de bord dans (3).

5 Géométrie extrinsèque

Nous allons maintenant analyser la façon dont une surface discrète concrète estpositionnée dans l’espace (sa géométrie extrinsèque) et le lien entre cell-ci et sa géométrieintrinsèque, via le polygone de GAUSS.

13. On parle toujours du bord comme d’une seule courbe, mais il y peut y en avoir plusieurs. Le raisonne-ment ne supposant pas la connexité de ∞, peu importe en fait qu’il y ait une composante ou plusieurs, et unecourbe de bord ou plusieurs.


L’angle diédral

Considérons une arête e = (pq) appartenant à deux faces orientées ~f1,~f2. À cause dela compatibilité, l’orientation de chaque face induit une orientation sur e, et ces deuxorientations sont opposées : on les note~e1 =°!pq et~e2 =°~e1 =°!qp. On peut aussi définirles vecteurs directeurs unitaires orientés des arêtes par ~ui =~ei/k~eik. Dans chaque face~f i on définit alors le vecteur conormal (ou conormale) ~ni, perpendiculaire à ~ui etorienté de telle sorte que (~ui,~ni) soit une base orthonormale directe de f i (en pratiqueon notera que la conormale ~ni est orientée vers l’intérieur de la face, et ce, quelle quesoit l’orientation de celle-ci). On définit par la même opération la normale (ou vecteurnormal) ~Ni à la face ~f i par ~Ni :=~ui ^~ni. Réciproquement, la normale ~Ni définit unsens de rotation dans la face (règle du tire-bouchon) donc un ordre sur les sommets, et~ni = ~Ni ^~ui.

f1

~n2~n1

q

p

~N1

f2

~N2

FIGURE 7 – Deux faces adjacentes f1, f2, avec leurs normales ~N1, ~N2 et les conormales~n1,~n2 le long de l’arête commune.

Rappelons que l’angle diédral µ de deux plans orientés dont les normales sont ~N1, ~N2est l’angle non orienté (~N1, ~N2), donné par cosµ = ~N1 ·~N2 (défini donc modulo 2º, mais ausigne près). On définit de façon analogue l’angle entre deux faces adjacentes orientées,de mesure µ 2 [°º,º] avec µ = 0 si et seulement si les faces sont coplanaires. Mais dansce cas, on donne à l’angle une orientation (c-à-d que µ donne une configuration différentede °µ). L’angle sera choisi positif si le secteur est saillant (par rapport aux orientationdes faces : les normales sont réputées partir vers l’extérieur 14) et négatif si rentrant.Une façon de calculer cela est de considérer sur l’arête e le vecteur directeur ~u1 orientépar la première face f1, dont le vecteur normal est ~N1. Comme ~u1 est orthogonal à ~N1et ~N2, il définit une orientation sur le plan (~N1, ~N2), ce qui permet de donner un signe àl’angle (~N1, ~N2). En pratique :

~N2 = cosµ~N1 +sinµ~u1 ^ ~N1 (4)

ce qui équivaut à la réciproque

~N1 = cosµ~N2 °sinµ~u1 ^ ~N2 = cosµ~N2 +sinµ~u2 ^ ~N2 .

14. Si on change l’orientation de la surface, les angles diédraux changent donc de signe.


On voit immédiatement que cet angle (avec son signe) ne dépend pas de l’ordre danslequel on prend les faces : l’angle diédral des faces f1, f2 est le même que celui des facesf2, f1 (~N1 et ~N2 sont échangés et ~u1 est remplacé par ~u2 =°~u1).

f1

µ

f2f1

µ

f2

~u1

~u1

~N1 ~N2

(a)

~n2~n1

~N1~N2

~n2~n1

(b)

FIGURE 8 – Deux cas de figure pour l’angle diédral : (a) saillant : µ > 0, (b) rentrant :µ < 0. Les deux faces sont vues de profil, dans le plan contenant les normales ~N1 et~N2 et les conormales ~n1,~n2 orientées vers l’intérieur des faces. Leur perpendiculairecommune, ~u1 est orthogonale au plan du dessin et fuyante.

On peut aussi définir la normale le long de l’arête

~Ne =~N1 + ~N2

k~N1 + ~N2k=~N1 + ~N2

2cos µ2

·

Remarquons que si les deux faces adjacentes ne sont pas coplanaires, le vecteur ~u1 estdéfini au signe près comme le vecteur directeur unité de la droite d’intersection desplans ~N?

1 et ~N?2 .

Polygone de GAUSS

On peut aussi comprendre la courbure gaussienne grâce au polygone de GAUSSqui est le polygone sphérique (voir annexe B) construit de la façon suivante. À chaqueface f on associe le point de la sphère donné par la normale ~Nf à la face ; deux points~N1, ~N2 sur la sphère seront reliés par une arête (sphérique, c-à-d un arc de grand cercle),si les deux faces correspondantes sont adjacentes. (On peut aussi voir ce polygone commeun polyèdre sphérique dans l’espace, en rajoutant des faces : chaque face sphériquecorrespond à un sommet de la surface originelle. Voir pour cela la notion de graphe dual§IV.1.3).

Comme nous travaillons localement, nous n’aurons besoin que du polygone de GAUSS

P en un sommet p qui contient les normales aux faces de l’étoile de p. Pour simplifierles notations, nous allons supposer que les faces sont triangulaires, mais la constructions’étend sans difficulté à des faces quelconques. Soit q1, . . . , qn les sommets de l’anneauen p, pris dans l’ordre induit par l’orientation. On note ~ai =

°°!pqik°°!pqik

les vecteurs unités

partants de p le long des arêtes et ~Ni le vecteur normal à la face orientée ~f i = (pqi qi+1) ;par conséquent (~ai,~ai+1, ~Ni) est direct. L’angle Æi au sommet satisfait cosÆi =~ai ·~ai+1


et plus précisément~ai+1 = cosÆi~ai +sinÆi~Ni ^~ai (5)

tandis que la géométrie extrinsèque est décrite par

~Ni+1 = cosµi+1~Ni °sinµi+1~ai+1 ^ ~Ni (6)

où µi+1 est l’angle diédral de l’arête (pqi+1) (le signe négatif venant de ce que ~ai+1 al’orientation opposée à celle induite par f i).

Æ1

Æ2

Æ3

Æ4

p

~N1

~N2

~N3

~N4

O

~N1

~N2

~N3

~N4

FIGURE 9 – Étoile d’un sommet p de degré 4 avec vecteurs normaux ~Ni à chaque face,et polygone de GAUSS associé, dont les sommets sont les vecteurs ~Ni . Les angles Æique font les faces au sommet p se retrouvent comme angles de rotation du polygonesphérique.

On remarquera que la longueur de l’arc sphérique (~Ni~Ni+1) est exactement |µi+1|.Cet arc est la partie d’extrémités ~Ni, ~Ni+1 du grand cercle intersection de la sphèreunité avec le plan orienté (O, ~Ni, ~Ni+1)=~a?

i+1. Enfin le polygone sphérique P est le bordd’une face de S2 (qui — contrairement à un polygone plan — ne peut être déterminéepar la simple donnée du polygone). Cette face est fixée en demandant que chaque ~aipointe vers l’extérieur de l’arc (~Ni°1~Ni). L’angle de rotation au sommet ~Ni entre lesdeux arcs successifs (~Ni°1~Ni) et (~Ni~Ni+1) est mesuré par la rotation entre les plans ~a?

iet ~a?

i+1, autrement dit l’angle (~ai,~ai+1) dans le plan orienté par leur normale commune~Ni : c’est Æi. (Accessoirement, on a donc que l’angle au sommet ~Ni est Øi =º°Æi.) Lethéorème de GAUSS-BONNET nous donne pour la face f p = ~N1, . . . , ~Nn du polygone deGAUSS :

2º= aire( f p)+X

iÆi .

Par conséquent,

Proposition 2. Le défaut angulaire en p est donc l’aire sphérique du polygone de GAUSS

de l’étoile de p.

De l’existence même de la surface polyédrique, on déduit une condition nécessairepour construire localement une surface polyédrique : les longueurs |µi| et les angles


au sommet Øi sont liés, au sens où il faut pouvoir construire un polygone sphérique delongueurs et angles prescrits. Cette condition est compliquée en général, mais dans lecas d’un sommet de degré 3 (de type tétraèdre), le polygone de GAUSS est un triangleet de nombreuses relations sont connues sur les triangles sphériques. Ainsi la loi descosinus donne-t-elle

cosµ1 =cosØ2 +cosØ1 cosØ3

sinØ1 sinØ3·

(Le lecteur trouvera plus de formules concernant la géométrie sphérique en annexe Bainsi que dans l’article Spherical Trigonometry de la CRC Concise Encyclopaedia ofMathematics de WEISSTEIN [Wei03].)

Théorème de BONNET

On a vu ci-dessus que l’existence d’une surface discrète est soumise (localement) àdes conditions nécessaires sur sa géométrie intrinsèque (longueurs des arêtes et anglesentre les arêtes d’une face) et sa géométrie extrinsèque (angles diédraux). La questionde savoir si ces conditions sont aussi suffisantes est donnée par le théorème de BONNET.

En géométrie classique, le théorème de BONNET donne des conditions nécessaires etsuffisantes pour qu’une surface donnée abstraitement par ses première et seconde formesfondamentales existe comme surface immergée (localement) dans l’espace euclidien.Afin d’énoncer son analogue discret, résolvons d’abord le problème local : si l’on considèreuniquement un sommet p et son étoile, avec sa géométrie intrinsèque et des angles µipour chaque arête contenant p. Pour simplifier, on supposera aussi que les faces sonttoutes triangulaires.

Lemme 1. L’étoile en p d’une surface abstraite triangulée déterminée par ses angles auxsommets Æi et angles diédraux µi possède une image dans l’espace si et seulement s’ilexiste un polygone sphérique dont les longueurs sont µi et les angles de rotation sont Æi.

Démonstration. On se place dans le cadre suivant : un sommet p appartenant à narêtes e1, . . . , en, dirigées par des vecteurs unités ~a1, . . . ,~an partant de p, n faces f icontenant les arêtes ei et ei+1, de vecteurs normaux ~Ni. La géométrie est donnée parles angles au sommet Æi sur la face f i et les angles diédraux µi sur l’arête ei, ce quifixe la configuration dans l’espace de proche en proche, dès que l’on a choisi un ~a1 et~N1 (avec ~a1 ? ~N1) : ~ai+1 = cosÆi~ai +sinÆi~Ni ^~ai et ~Ni+1 = cosµi~Ni °sinµi~ai+1^ ~Ni. Onretrouve les contraintes (5) et (6), et on construit ainsi les arêtes jusqu’à en+1.

Le problème est de savoir si en+1 = e1. Le problème est bien posé puisque la méthodeci-dessus est itérative, mais cette formulation repose sur des données extrinsèques (les~ai et ~Ni). Partons plutôt des données intrinsèques à savoir les angles Æi,µi. La donnéedes longueurs des arcs sphériques et des angles de rotations Æi définit une courbesphérique de sommets ~Ni, unique à rotation près. Si l’étoile en p existe dans R3, alorscette courbe polygonale sphérique est le polygone de GAUSS autour du sommet p doncelle se referme (ce qui implique des conditions sur les angles). Réciproquement, onreconstruit l’étoile en p à partir de la courbe sphérique. En effet les ~ai sont forcémentles normales aux plans engendrés par ~Ni, ~Ni+1 et elles satisfont les équations (5) et (6).


(Noter que le signe de ~ai est déterminé par la seconde équation.) Si la courbe se referme,alors ~an+1 =~a1 donc la condition de fermeture de la courbe polygonale sphérique estnécessaire et suffisante.

Remarque : pour ce lemme, nul besoin de définir les faces exactement ni mêmeles longueurs il suffit de considérer des secteurs angulaires orientés bordés par lesdemi-droites issues de p et dirigées par les arêtes.

Nous pouvons maintenant énoncer le théorème de reconstruction de BONNET.

Théorème 3. Soit S = (V ,E,F) une surface polyédrique abstraite orientée, simplementconnexe, munie d’une métrique donnée par (i) une métrique plate sur chaque face, au-trement dit une bijection de la face vers une face du plan de même combinatoire et (ii)des angles µe pour chaque arête e. Supposons qu’en chaque sommet intérieur de S, lesangles des arêtes µe et les angles au sommet Æi déterminent un polygone sphérique, alorsil existe une surface polyédrique concrète S0, de même combinatoire, dont les faces sontisométriques à la face correspondante de S, et telle que les µe soient les angles diédraux.Cette surface est unique à isométrie de l’espace près.

Démonstration. On supposera pour simplifier que la surface est triangulée et que lesangles µe ne sont jamais nuls. L’unicité à rotation près découlera de la nécessité de laconstruction.

La construction d’une telle surface suit l’algorithme suivant. Choisissons une facetriangulaire initiale dans S et un triangle orienté qui lui est isométrique dans R3. Cedernier est unique à isométrie de l’espace près. Les arêtes e de ce triangle initial quine sont pas sur le bord de S sont dites externes (au sens de cet algorithme), c’est-à-direqu’une seule de deux faces incidentes à e a été construite.

Considérons une face f2 non construite adjacente à une face déjà construite f1. Parhypothèse, au moins une de ses arêtes est externe : e = f1 \ f2. La question est de savoirsi elle en possède une autre ou pas. Si elle n’en possède qu’une, on construit son imagef 02 dans R3 de façon unique, en connaissant sa géométrie intrinsèque et en recollantgrâce à l’angle diédral. On retire de la liste des arêtes externes l’arête e et on y rajouteles deux arêtes restantes de f2. Par contre si f2 possède une deuxième arête externe edéjà construite, il faut alors vérifier que l’image e0 construite en recollant f 02 coïncideavec l’image existante. Cela revient à la construction de l’étoile en p = e\ e, traitée dansle lemme. En effet f2 doit être l’ultime face non construite de star(p), à moins que l’onait laissé des trous dans la construction. Or par hypothèse, S est simplement connexe,donc les seuls trous possibles doivent être comblés par des triangles. Pour éviter cettesituation, il suffira de construire en priorité les faces dès que surgissent deux arêtesexternes adjacentes (autrement dit, en s’assurant que la partie de S traitée reste degenre zéro).

On recommence tant qu’il reste des arêtes externes n’appartenant pas au bord (cequi est un processus fini).

Note 3. Le théorème de BONNET donne deux ingrédients pour construire une surfacepolyédrique : les métriques sur les faces, ce qui détermine la métrique intrinsèque à S,

6. Convergence et approximation 39

à savoir les distances sur S, et les angles diédraux, qui sont une donnée extrinsèque,autrement dit détermine la façon dont la surface se déploie dans l’espace. Le théorèmeajoute que ces deux quantités doivent être liées pour qu’une immersion soit possible.Par analogie avec le cas continu, les quantités intrinsèques correspondent à la courburegaussienne dont on voit qu’elle est liée aux sommets (angles), tandis que les quantitésextrinsèques correspondent à la courbure moyenne, qui est donc liée aux arêtes. Onreviendra plus en détail sur cette dernière au chapitre III.

6 Convergence et approximationPour définir des analogues discrets des quantités différentielles, nous avons jusqu’ici

été guidés par leurs propriétés fonctionnelles, plutôt que par une transposition naïve desformules continues au discret. Si dans certains cas, la géométrie est purement discrète(polyèdres, graphes), dans d’autres, le discret est conçu comme une approximation d’unobjet continu. Il est alors intéressant de voir dans quelle mesure les deux se rejoignentquand l’approximation s’améliore, par exemple quand le maillage de la surface devientplus fin. C’est le problème de la convergence.

La réponse est, de façon surprenante, partiellement négative. Même en prenant desanalogues sensés des courbures différentielles continues (sans parler des formules moinsbien choisies), la convergence n’est pas très bonne. Les travaux de BORRELLI, CAZALS

& MORVAN [BCM03] établissent la non-convergence a priori des mesures discrètes versles mesures continues de courbure, avec des différences dépendant des types de maillage.Cela amène d’ailleurs COHEN-STEINER & MORVAN ([CSM06, Mor08b]) à définir desnotions de mesure de courbure pour énoncer des théorèmes de convergence corrects.De même XU, XU & SUN [XXS05] montrent un résultat encore plus surprenant : iln’existe aucune formule calculée à partir du k-anneau d’un point du maillage, quiconverge vers la courbure gaussienne ou moyenne pour tous les maillages. Cela n’exclutpas néanmoins la convergence pour certains maillages, ce qui est d’ailleurs l’approcheproposée par BAUER, POLTHIER & WARDETZKY [BPW10a] (qui considèrent un maillagele long des lignes de courbures principales).

Nous montrerons ci-dessous quelques-uns des problèmes qui surgissent. Notre espoirétant que le lecteur averti évitera d’accorder une confiance aveugle aux différentesformules de courbure qui abondent dans la littérature scientifique, et cultivera un sainscepticisme.

6.1 Influence du degré du sommet

On prendra ici comme illustration la plus simple la sphère de rayon 1, que l’onsuppose triangulée de façon régulière en un sommet, et on testera les valeurs limitesdes grandeurs définies plus haut, quand le pas du maillage devient de plus en plus petit.Cela revient à considérer des surfaces inscrites dans la sphère, ce qui est en soi un choixà discuter ; on pourrait aussi prendre des surfaces exinscrites ou semi-inscrites.

On se place donc en un point p de la sphère unité, et on considère le polygone


Øº/3

µ

p

p0`

a

FIGURE 10 – Polygone régulier à 6 côtés centré en p, inscrit sur la sphère unité.La distance sphérique entre le centre p et un sommet est µ, la longueur de l’arête(droite) est ` = 2sin µ

2 . Les 6 sommets sont sur un cercle de centre p0 et forment unpolygone régulier plan dans le plan de ce cercle.

régulier de l’espace formés par n points de la sphère situés à une distance sphérique(donc angulaire) µ de p. Une arête issue de p aura comme longueur `= 2sin µ

2 . Soit a lalongueur de l’arête opposée à p. Les n points de star(p) forment un polygone régulier del’espace (dont le centre n’est pas p mais un point p0 proche de p, situé à l’intérieur de laboule unité), de diamètre 2`0 où `0 = sinµ, d’où a = 2`0 sin º

n = 2sinµsin ºn . On en déduit

l’angle Ø en p de chaque triangle puisque a = 2`sin Ø2 d’où

sinØ

2= sin

º

n`0

`= sin

º

nsinµ

2sin µ2= sin

º

ncos

µ

2·

Enfin l’aire d’un triangle sera A = 12`

2 sinØ= 2sin2 µ2 sinØ.

En première approximation, quand µ est petit, il vient (en utilisant la parité)

Ø= 2ºn

° µ2

4tan

º

n+ o(µ3)

ce qui induit un défaut angulaire en p de

Æ(p)= 2º°nØª nµ2

4tan

º

n

tandis que l’aire est

A(star(p))= nA = 2nsin2 µ

2sinØª nµ2

2sin

2ºn


la courbure gaussienne est donc

K(p)= 3Æ(p)A(star(p))

ª3n4 µ2 tan º

nnµ2

2 sin 2ºn

=3tan º

n

2sin 2ºn

= 34cos2 º

n= 3

4

≥1+ tan2 º

n

¥.

La courbure discrète K(p) possède donc une limite quand µ tend vers zéro, mais celle-cidépend du degré n en p ; en particulier, elle est différente de 1 quand n 6= 6. Enfin, sil’on force simultanément n à tendre vers l’infini, K(p) tend vers 3

4 6= 1. Ce phénomèneest analysé dans [BCM03] et illustré dans [Rus04].

Pour le calcul de la courbure moyenne sur une arête, il nous faut considérer lepolygone de GAUSS (cf. §5), dont les sommets sont les normales aux faces. L’angle '

entre les normales et p est donné par

sin'=sin µ

2q1°cos2 µ

2 sin2 ºn

= µ

2sin ºn+ o(µ)

tandis que

cos'=cos µ

2 cos ºnq

1°cos2 µ2 sin2 º

n

= 1° µ2

8cos2 ºn+ o(µ3) .

L’angle ' représente la distance sphérique entre les sommets du polygone de GAUSS, quiest régulier à n côtés, et son sommet. Soit ± l’angle diédral, autrement dit la longueursphérique du côté de ce polygone :

cos±= cos2'+sin2'cos2ºn

= 1°sin2 µ

2

1°cos2 µ2 sin2 º

n

µ1°cos

2ºn

∂= 1°

2sin2 µ2 sin2 º

n

1°cos2 µ2 sin2 º

n

=1°cos2 µ

2 sin2 ºn °2sin2 µ

2 sin2 ºn

1°cos2 µ2 sin2 º

n=

1°sin2 ºn

°1+sin2 µ

2¢

1°cos2 µ2 sin2 º

n

soit sin±= µ tan ºn + o(µ). Enfin la courbure moyenne en p est

H(p)= n`2

sin±cos'= nsinµ

2sin±cos'ª n

µ2

2tan

º

n

En divisant par la masse concentrée, il vient

3H(p)aire(star(p))

ª3n µ2

2 tan ºn

nsin 2ºn

µ2

2

=3tan º

n

sin 2ºn

= 32cos2 º

n= 3

2

≥1+ tan2 º

n

¥.

On retrouve la même dépendance en n, le degré de p.

Remarque 7. Il est à noter que ce phénomène n’apparait pas en dimension 2. En effetsi l’on considère trois points sur le cercle de rayon 1, p et ses deux voisins, situés à


distances angulaires µ1,µ2 et à distances cordales respectives `i = 2sin µi2 , alors l’angle

de rotation en p est

µ = µ1 +µ2

2

et la courbure mesurée en divisant par la demi-aire de l’étoile en p est

k = 2µ`1 +`2

= µ1 +µ2

2≥sin µ1

2 +sin µ22

¥ ª 1 .

Cette propriété est vraie pour toute approximation polygonale d’une courbe (de classe C 3

ou mieux), et converge plus vite si le polygone a ses côtés de même longueur [BCM03].On peut aussi diviser par la longueur du segment reliant les milieux et on obtient

encore une quantité équivalente à 1. De façon intéressante, cette longueur ne dépendque de µ et non de la répartition µ1,µ2, car c’est la moitié de la longueur de la cordereliant les deux voisins.

6.2 Le problème de l’approximation quadratique

Dans leur article [XXS05], XU, XU & SUN répondent par la négative à la questionposée par MEEK & WALTON [MW00], de savoir s’il existe une formule, dépendant desdonnées géométriques, approximant la courbure (gaussienne ou moyenne) avec uneprécision croissante quand le maillage devient plus fin. Leur approche élégante revientà inverser le problème : plutôt que de fixer une surface et de changer le maillage pourmontrer la non-convergence de la formule, ils fixent des points et font varier la surface(passant par ces points). Or toute expression dépendant du maillage restera constantepuisque les points ne bougent pas. Par contre, on voit rapidement que les courburesvont changer, donc ne peuvent pas être égales à l’expression, quelle qu’elle soit.

Plus précisément, soit S une surface donnée régulière (par exemple de classe C 2)passant par l’origine p = (0,0,0) avec un plan tangent horizontal. Elle est décritelocalement comme le graphe d’une fonction f :

f (x, y)= 12

(ax2 +2bxy+ cy2)+≤

où ≤= o(x2+ y2) est l’erreur que l’on fait en approximant S par son développement limitéà l’ordre 2. Les coefficients (constants) a,b, c se déduisent des dérivées secondes de f en(0,0). Les courbures de S en p dépendent uniquement de a,b, c : la courbure gaussienneest K = ac°b2 et la courbure moyenne a+ c. Par conséquent, pour étudier les courbures,on peut négliger l’erreur ≤ et se contenter de la partie quadratique de f , autrementil suffit de considérer les paraboloïdes z = 1

2 (ax2 +2bxy+ cy2), et on aura traité le casgénéral.

On suppose aussi que p est un sommet d’un maillage de degré 4 en p, et on noteq1, . . . , q4 ses voisins. Pour cela on prend un pas h > 0 aussi petit que l’on veut et des


coordonnées x1, . . . , x4, y1, . . . , y4 et l’on pose

qi = h(xi, yi, zi)= (hxi,hyi, f (hxi,hyi))=µhxi,hyi,

h2

2(ax2

i +2bxi yi + cy2i )

∂.

On suppose enfin donnée une fonction © calculée à partir de l’anneau à distance 1 en p(qui serait la fonction courbure cherchée).

L’idée de XU, XU & SUN est de faire varier a,b, c en laissant fixes les pointsp, q1, . . . , q4. En effet, si ces points sont donnés, les coefficients a,b, c satisfont le systèmesuivant :

pour tout i, ax2i +2bxi yi + cy2

i = 2zi/h

À qi fixé, le système possède une, plusieurs ou aucune solution selon les valeurs desxi, yi, zi. Nous nous intéressons au cas sous-déterminé, c-à-d quand le système possèdeplusieurs solutions (donc une infinité), autrement dit quand la matrice

0

BBB@

x21 2x1 y1 y2

1x2

2 2x2 y2 y22

x23 2x3 y3 y2

3x2

4 2x4 y4 y24

1

CCCA

est de rang 2, par exemple si les points sont opposés : xi+2 = °xi, yi+2 = °yi. Pourfixer les idées, choisissons par exemple (x1, y1)= (1,0) et (x2, y2)= (1,1). Les équationsimposent a = 2z1/h, et b est determiné par tout choix de c : b = (z2 ° z1)/h° c/2. Enfaisant varier c, on obtient des surfaces distinctes, dont les courbures gaussienne etmoyenne sont différentes, et qui pourtant passent toutes par les 5 points prescrits, etont donc la même valeur de ©(p, q1, . . . , q4). Et ce, même si l’on faut tendre h vers zéro.

Notons quand même que ce raisonnement n’interdit pas a priori de calculer lescourbures, si l’on a exclu les cas pathologiques comme ci-dessus. Ne pourrait-on croirealors que ces cas sont « rarissimes » (voire qu’ils résultent d’une construction mathé-matique abstraite qu’on ne rencontrerait jamais en pratique) ? Effectivement, il s’agitd’un cas non générique (c-à-d ayant lieu sur ensemble fermé de mesure nulle), commel’est une division par zéro. Mais le problème lui est générique. En effet, quand on s’ap-proche numériquement d’un de ces cas, les solutions a,b, c (même uniques) exhibentune sensibilité aux données initiales accrue (et tendent vers l’infini pour c par exemple).Autrement dit, de légères variations numériques induisent des changements importantspour ©. On a donc affaire à un vrai problème.

6.3 Lanterne de SCHWARZ (ou vénitienne)Rappelons enfin un contre-exemple classique en géométrie (dû à H. A. SCHWARZ

en 1890), qui montre que la convergence en distance (en l’occurrence la distance deHAUSDORFF) n’implique pas nécessairement la convergence des aires.

Soit C le cylindre centré d’axe (Oz), de hauteur h et de rayon r donné par

C =©x2 + y2 = r2, 0… z … h

™.


On considère la triangulation suivante, dépendant de deux entiers n,m : à chaquehauteur jh

m on considère les sommets d’un polygone régulier à n côtés inscrit dansle cercle de rayon r, avec une rotation de º

n entre deux polygones successifs. À lahauteur jh/m (pour 0… j … m) on prend les points pi, j :=

≥r cos 2iº

n , rsin 2iºn , jh

m

¥si j est

pair, pi, j :=≥r cos (2i+1)º

n , rsin (2i+1)ºn , jh

m

¥si j est impair. Les faces sont constituées des

triangles suivants : (pi, j pi+1, j pi, j+1) et (pi, j pi, j°1 pi+1, j) si j est pair, (pi, j pi+1, j pi+1, j+1)et (pi, j pi+1, j°1 pi+1, j) si j est impair. La distance entre un triangle et le cylindre estmajorée par r

°1°cos º

n¢

donc tend vers zéro, tandis que l’aire d’un triangle est

AT = rsinº

n

sh2

m2 +4r2 sin4 2ºn

et l’aire totale est

A = 2nmAT = 2rh≥nsin

º

n

¥s

1+ 4r2

h2 m2 sin4 2ºn

°!n !+1m fixe

2ºrh = aire(C).

Mais un choix différent de raffinement de la triangulation, faisant changer simultané-ment m et n, donnera des résultats différents. On peut obtenir n’importe quelle valeurde Ø= A/aire(C) 1 en choisissant n,m !+1 avec m/n2 ! h

8º2r

pØ2 °1, et même une

aire tendant vers l’infini, si m/n2 !+1.Le chapitre 3 de la thèse de WARDETZKY [War06] explique plus en détails en

quoi la lanterne de SCHWARZ illustre précisément ce qui empêche la convergence :la non-convergence des normales. COHEN-STEINER & MORVAN [CSM06] présententaussi ce contre-exemple 15, et proposent une approche plus générale du problème del’approximation et des données géométriques.

15. Modulo quelques erreurs de calcul.

Documents

Surfaces et polyèdres - Bienvenue sur perso.math.u-pem.fr