---

Module Géométrie algorithmique

M1 Informatique, M1 Math/Info

FMIN 215

---

    Corrigé et notes du CC:

Notes
Énoncé     Corrigé page 1     Corrigé page 2     Corrigé page 3

    Actualitées:

Contrôle continu le lundi 26 mars de 15h à 16h30, salle SC11.01 !!! sur le crénau de TD, il y aura cours avant, mais pas de tp après. Programme: jusqu'à 'Graphe Planaire' inclus, sans document.

    Planning 2011/2012:

Les créneaux de cours-td sont le lundi de 13h15 à 16h30, Salle SC11.01 (à partir du 19 mars), voir l'emploi du temps de la fac de sciences.
Les tps ont lieu le le lundi de 16h45 à 18h15 au bâtiment 6.

Début des cours et td le lundi 23 janvier, pas de tp ce jour-là.

    Contenu du cours:

15h de cours, 15h de tds, 15h de tps.

• Chapitre 1: Calcul d'intersections Intersections d'un ensemble de segments dans le plan, exemple d'algorithme par balayage. diagramme de Voronoi.
• Chapitre 2: Enveloppe convexe Enveloppe convexe d'un ensemble de points du plan: algorithmes de Graham et de Jarvis. Généralisation pour un ensemble de points de l'espace.
• Chapitre 3: Graphes planaires Lien avec les triangulations d'objet 3D. Formule d'Euler, encodage compact des graphes planaires. Localisation dans un graphe planaire.
• Chapitre 4: Triangulations Triangulation d'un ensemble de points du plan. Triangulation de Delaunay et diagramme de Voronoï. Algorithme par balayage de Fortune pour le calcul du diagramme de Voronoï.
• Chapitre 5: Applications et extensions alpha-shape et alpha-complexe (reconnaisances de forme), sommes de Minkowski (intersections de polygones) et BSP (algorithme du peintre).

    Notes de cours:

Ces notes ont été prises par les étudiants de Master1 lors de l'année universitaire 2007/2008 (merci à eux). Le cours a toutefois un peu changé depuis...

• Cours 1 et 2: Intersections de segments et enveloppes convexes.
• Cours 3: Graphes planaires.
• Cours 4: Triangulation et diagramme de Voronoi.

    Fiches de TD:

En cours d'actualisation...

• TD1: Calculs de base dans R²
• TD2: Intersections de segments et enveloppes convexes
  
• TD3: Graphes planaires
• TD4: Triangulations

   Fiches de TP:

• TP1: Intersection de segments.
  Primitives de bases et trame de programme en C pour:
  - Recherche d'une intersection: Intersection.cc
  - Classe ARN pour gérer les arbres rouges et noir: ARN.h et ARN.cc.
• TP2: Calculs d'enveloppes convexes.
  Primitives de bases et trame de programme en C pour:
  - le parcours de Jarvis: Jarvis.cc
  - l'algorithme de Graham: Graham.cc
  
• TP3: Triangulations.
  Primitives de bases et trame de programme en C pour:
  - le calcul incrémental: Triangulation.cc
  - le passage à une triangulation de Delaunay: Delaunay.cc
  
• TP4: Alpha-Shapes.
  Echantillons de points:
  - Echantillon 1.
  - Echantillon 2.
  - Echantillon 3.
  

   Contrôle des connaissances

Il y aura un examen, et un controle continu comptant pour un tiers dans la note finale (avec règle du max...). Suivant le nombre d'étudiants, ce controle sera un partiel ou un tp noté ou les deux ou une présentation d'articles...

Annales:

• Examen 2006 (exercices 1 et 4).
• Examen 2007 (exercices 2 et 4).

   Bibliographie:

• Computational Geometry, M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Ed. Springer.
• Introduction à l'algorithmique, T. Cormen, C. Leiserson, R. Rivest, Ed. Dunod, chapitre 35.
• Computational Geometry, F.P. Preparata, M.I. Shamos, Ed. Springer.
• Géométrie algorithmique, J.D. Boissonnat, M. Yvinec, Ed. Ediscience.

---