Cours : Géométrie Algorithmique
Responsable : Francis Avnaim, Olivier Devillers
Objectifs :
- Découvrir
un domaine récent de l'informatique théorique (1978)
qui trouve des applications dans de très nombreux domaines
de la science (ex : Robotique, CAO, Traitement d'images,
Modélisation moléculaire, etc.)
- Au travers
de l'introduction au domaine, solidifier ses connaissances sur les
structures de données et la complexité des algorithmes
- Appliquer les connaissances théoriques apprises en programmant une application graphiques (en utilisant le langage de son choix)
Structure :
6 cours de 1.5h
3 TPs machines de 2h
3 TDs de 2h
Programme :
- Enveloppes convexes
- Applications de l'enveloppe convexe 2D
- Intersections (droites, segments, etc.)
- Diagramme de Voronoi, triangulation de Delaunay
- Applications de Delaunay
Pré-requis :
- Géométrie du lycée
- Complexité des algorithmes
- Connaissances des structures de données classiques (listes, arbres, dictionnaires) et des complexités des opérations sur ces structures
Références :
- Computational Geometry an introduction, Preparata Shamos, Springer
- Computational Geometry Algorithms and Applications, De Berg, van Kreveld, Overmars,Schwarzkopf, Springer
- Computational Geometry in C, O'Rourke, Cambridge University Press