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 : 21
- TD : 28.5
- TP : 0
Diplômes intégrant cette UE
En bref
Crédits ECTS 5
Nombre d'heures 51 HE
Période de l'année
S6
Contact(s)
Composante
Faculté des Sciences
Responsable(s)
Jonathan Chappelon (jonathan.chappelon @ umontpellier.fr)
Téléphone : +33 4 67 14 41 66