Géométrie algorithmique

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 : 21
• TD : 28.5
• TP : 0

Diplômes intégrant cette UE

• LICENCE MATHEMATIQUES
• LICENCE INFORMATIQUE