Géométrie algorithmique

Géométrie algorithmiqueCode de l'UE : HLMA608

Présentation

Programme
Triangulations
- Diagrammes de Voronoi: caractérisation et algorithmes
- Triangulations de Delaunay
- Applications géométriques (problème de distance, optimisation des déplacements)
Problème de Galerie d'art
- Théorème de Chvatal, complexité
- Variantes (polygone orthogonaux, gardiens en mouvement, etc.)
Problème d'illumination
- Famille de convexes
- Segments de droites
Géométrie convexe
- Théorèmes de Carathéodory, Radon et Helly (applications)
- Théorème de Hadwiger
Arrangements de lignes
- Combinatoire des cellules
- Dualité et configurations de points dans le plan
- Application (transversal, modélisation des molécules, robotique)
Visibilité dans le plan
- Graphes de visibilité
- Point de visibilité dans des polygones
 

Objectifs

L'objectif de ce cours est d'introduire des méthodes effectives en géométrie et de mettre en évidence plusieurs applications
concrètes issues des nouvelles technologies : informatique graphique, robotique, vision, etc.

Volume horaire

  • CM : 24
  • TD : 27
  • TP : 0
Diplômes intégrant cette UE

En bref

Crédits ECTS 5