Cours géométrie algorithmique

Aperçu de topologie des surfaces

Surfaces topologiques

Le but de ce chapitre est notamment de répondre à la question suivante : qu’est-ce qu’une surface ? Vaste question . . . Tous les objets suivants, plongés dans R3, peuvent etre considérés, à des degrés divers, comme des surfaces, meme si le premier n’est pas connexe, si le deuxième possède un trou, si le troisième n’est pas orientable (il n’y a pas d’intérieur et d’extérieur !) et si le quatrième n’est pas borné.
En topologie, une surface va etre définie comme un espace topologique particulier. Définition 1 (Espace topologique). Un espace topologique est un ensemble X et un système X de sous-ensembles de X tels que :
• ∅,X∈X;
• une union d’éléments de X est dans X ;
• une intersection finie d’éléments de X est dans X.
X est appel´ une topologie et les eléments de X sont appelés les ouverts de X. Un sous-espace topologique (Y, Y ) de (X, X) est constitué d’un sous-ensemble Y ⊆ X et de la topologie de sous-espace définie par Y = {Y ∩ A, A ∈ X}
Exemple. L’espace euclidien a` d dimensions Rd est un espace topologique.
Nous nous intéressons maintenant a` des espaces topologiques particuliers. Nous rappelons qu’un voisinage d’un point x ∈ X est simplement un ensemble ouvert contenant x.
Définition 2 (Variété). Un espace topologique X est une k-variét´ si tout point x ∈ X possède un voisinage V dans X homéomorphe à Rk (c’est-à-dire qu’il existe une fonction f : V → Rk bijective, continue et d’inverse continue).
Définition 3 (Variét´ à bord). Soit Hk le demi-espace à k dimensions : Hk = {x = (x1, . . . , xk )
∈ Rk , x1 ≥ 0}. Un espace X est une k-variét´ à bord si tout point x ∈ X possède un voisinage dans X homéomorphe à Rk ou à Hk . La frontière (ou le bord) de X est l’ensemble des points de X qui ont un voisinage homéomorphe à Hk . C’est soit une (k − 1)-variét´ (sans bord), soit l’ensemble vide.
La définition 2 implique que si M est une k-variété, alors on peut trouver un nombre dénombrable d’ensembles ouverts Ui et d’homéomorphismes φi : Ui → Rk , tels que M = Ui.
Définition 4 (Plongement, immersion). On appelle plongement d’une k-variét´ X dans Rn une application f : X → Rn dont la restriction a` l’image de X est un homéomorphisme. Si une telle application existe, on dit que X est plongée dans Rn. Si f est simplement injective de X dans Rn, on dit que f est une immersion.
Nous pouvons maintenant définir une surface.
Définition 5 (Surface). Une surface est une 2-variété
Définition 6 (Surface a` bord). Une surface a` bord est une 2-variété à bord.

Classification des surfaces

Nous allons maintenant utiliser les définitions précédentes afin de classer les surfaces. Les sur-faces que nous allons étudier seront compactes, connexes et plongées dans R3.
Définition 7 (Ensemble compact). Un sous-ensemble de la fois ferm´ (c’est-a`-dire que son complémentaire dans Rn une boule euclidienne de rayon fini).
Rn, n ≥ 1, est dit compact s’il est a` est un ouvert) et borné (inclus dans Définition 8 (Surface connexe). Une surface est dite connexe si deux points quelconques sur la surface peuvent ˆetre connectés par une courbe continue contenue dans la surface.
Nous allons étudier les propriétés topologiques de telles surfaces. Deux surfaces seront considérées comme topologiquement équivalentes s’il existe un homéomorphisme entre elles. Il se trouve que, grˆace a` cette relation d’équivalence, il est possible de classer les surfaces.
Théorème 9 (Classification des surfaces). Toute surface (sans bord) compacte connexe est homéomorphe soit a` une sphère a` g trous, g ≥ 0, soit a` une sphère a` g bonnets croisés1, g ≥ 1. Une surface du premier type ne peut pas ˆetre homéomorphe a` une surface du second type, et deux surfaces de mˆeme type mais avec des valeurs de g différentes ne peuvent pas ˆetre homéomorphes.
Exemple. L’exemple de la figure 2.1 (a) n’est pas connexe, mais est composé de deux sphères. Le tore est lui homéomorphe a` une sphère a` un trou, et la bouteille de Klein a` une sphère a` un bonnet croisé. Le cylindre infini ne peut pas ˆetre classé selon le théorème précédent, car ce n’est pas une surface compacte (il n’est pas borné).
Définition 10 (Genre). g est appel´ le genre de la surface.
Définition 11 (Surface orientable). Une surface homéomorphe à une sphère à g trous, g ≥ 0, est dite orientable, et une surface homéomorphe a` une sphère a` g bonnets croisés, g ≥ 1, est dite non orientable.
Propriét´ 12. Une surface orientable peut ˆetre plongée dans R3. Une surface non-orientable ne peut pas ˆetre plongée dans R3, mais peut y ˆetre immergée.

Triangulations

Les deux sections précédentes nous ont permis de définir rigoureusement une surface, d’un point de vue topologique. Nous allons maintenant nous restreindre au cas des surfaces discrètes, c’est-a`-dire définies a` partir d’un nombre fini de points. En effet, on travaille souvent en informatique sur de telles surfaces, qui sont généralement des approximations de surfaces réelles ou idéales : par exemple, le lapin de la figure 2.3 – le célèbre bunny de Stanford – est une surface maillée, créée en scannant un modèle réel en argile (le scanner détecte la position géométrique d’un certain nombre de points du modèle, et ces points sont ensuite reliés trois a` trois pour former des triangles, grˆace a` un algorithme adéquat).
Définition 13 (Simplexe). Soit e0, . . . , en un ensemble de n+1 points linéairement indépendants dans un espace euclidien Em, m ≥ n ≥ 0. On appelle n-simplexe de sommets e0, . . . , en l’enve-loppe convexe σ de ces points. n est la dimension de σ. Par ailleurs, on appelle −1-simplexe l’ensemble vide.
Exemple. Dans R3, un 0-simplexe est un sommet, un 1-simplexe une arˆete, un 2-simplexe un triangle et un 3-simplexe un tétraèdre (cf. figure 2.4).
Définition 14 (Face). Soit S un ensemble de points linéairement indépendants et σ son en-veloppe convexe. Alors l’enveloppe convexe τ de tout sous-ensemble T de S est également un simplexe, sous-ensemble de σ. On dit que τ est une face de σ, et on note τ ≤ σ.
Définition 15 (Complexe simplicial). Un complexe simplicial est une collection K de faces d’un nombre fini de simplexes, tels que :
• σ∈K∧τ ≤σ⇒τ ∈K;
• σ,ν∈K⇒σ∩ν≤σ,ν.
Autrement dit, si σ est dans K alors toute face de σ est aussi dans K, et si σ et ν sont dans K alors leur intersection est à la fois une face de σ et une face de ν.
La dimension d’un complexe simplicial est la dimension de son plus grand simplexe.
Nous définissons maintenant deux notions importantes concernant la structure locale d’un com-plexe simplicial.
Définition 16 (Etoilé, lien). Soit K un complexe simplicial et σ un simplexe dans K. L’etoilé de σ est l’ensemble des simplexes de K contenant σ : St(σ) = {τ ∈ K, σ ≤ τ }. Notons St(σ) le plus petit sous-complexe de K contenant St(σ). Le lien de σ est l’ensemble des faces des simplexes de l’étoil´ de σ n’intersectant pas σ : Lk(σ) = {τ ∈ St(σ), τ ∩ σ = ∅}.
Exemple. La figure 2.5 représente l’étoil´ et le lien d’un sommet dans R3.
Restreignons-nous maintenant aux espaces euclidiens Rn.
Nous allons maintenant établir un lien entre la topologie d’un ensemble de points et la topologie combinatoire, plus exactement entre les notions d’espace topologique et de complexe simplicial. Rappelons que ∀n ≥ 1, Rn est un espace topologique.
Définition 17 (Polyèdre). Soit K un complexe simplicial dans Rn. L’union |K| de tous les simplexes de K avec la topologie de sous-espace de Rn est appelée le polyèdre (ou parfois l’espace sous-jacent) de K.
Définition 18 (Triangulation). La triangulation d’un espace topologique X est un complexe simplicial K dont le polyèdre |K| est homéomorphe à X. Si un tel complexe simplicial existe, on dit que X est triangulée.
Exemple. Une surface triangulée est une 2-variét´ homéomorphe au polyèdre d’un complexe simplicial.

Caractéristique d’Euler

Nous allons maintenant voir que les notions de surface triangulée et de surface topologique sont liées.
Définition 19 (Caractéristique d’Euler). La caractéristique d’Euler χK d’un complexe simpli-cial K est la somme alternée du nombre de ses simplexes suivant leur dimension :
d  χK = (−1)i si, (2.1) i=0
où d est la dimension de K et ∀0 ≤ i ≤ d, si est le nombre de i-simplexes dans K.
Remarque. On peut réécrire χK sous la forme : χK = (−1)dim(σ) , avec ∀σ ∈ K, dim(σ)
σ∈K,σ=∅ la dimension de σ.
Exemple. Pour une surface triangulée, χK = V − E + F , avec V le nombre de sommets de la triangulation, E son nombre d’arˆetes et F son nombre de faces.
Propriét´ 20. Soient A et B deux complexes simpliciaux. Alors χA∪B = χA + χB − χA∩B .
Théorème 21 (Relation d’Euler). La caractéristique d’Euler d’une surface M compacte, connexe, de genre g et à bc bonnets croisés vaut χM = 2 − 2g − bc.
Théorème 22 (Relation d’Euler généralisée). La caractéristique d’Euler d’une surface M com-pacte, connexe, a` bord, de genre g et a` bc bonnets croisés et dont la frontière est constituée de bo composantes connexes (les bords) vaut χM = 2 − 2g − bc − bo .
Ces deux théorèmes nous indiquent en particulier que pour une surface triangulée, la quantité V − E + F ne dépend que de sa topologie.

1 Introduction 
2 Apercu de topologie des surfaces 
2.1 Surfaces topologiques
2.2 Classification des surfaces
2.3 Triangulations
2.4 Caracteristique d’Euler
3 Diagramme de Voronoı et triangulation de Delaunay : definitions et proprietes 
3.1 Diagramme de Voronoı
3.1.1 Definitions
3.1.2 Proprietes
3.2 Triangulation de Delaunay
3.2.1 Definitions
3.2.2 Proprietes simples
3.2.3 Propriete fondamentale
3.2.4 Propriete angulaire
4 Diagramme de Vorono¨ı et triangulation de Delaunay : algorithmes 
4.1 Vorono¨ı : intersection de demi-plans
4.2 Vorono¨ı : construction incrementale
4.3 Vorono¨ı : diviser pour regner
4.4 Vorono¨ı : algorithme par balayage
4.5 Delaunay : construction incrementale
4.6 Quelques applications
4.6.1 Probl`eme des bureaux de Poste
4.6.2 Cristallographie
4.6.3 Planification de trajectoire
4.6.4 M´ethode des ´el´ements finis
4.6.5 Arbre couvrant minimal
4.6.6 Reconstruction de surface
5 Extension : diagramme de Laguerre 
5.1 Introduction
5.2 Definitions
5.3 Proprietes
Annexe : lexique anglais-fran¸cais 
Bibliographie