La géométrie algorithmique est une jeune discipline de l'informatique qui étudie d'un point de vue combinatoire et algorithmique les propriétés d'objets géométriques tels que nuages de points, arrangements, graphes géométriques, ou encore triangulations.
Ce cours propose une promenade au sein de cette discipline afin d'en illustrer la richesse sur le plan théorique et applicatif. Dans ce contexte, nous introduirons un éventail de problèmes issus du domaine, des plus classiques comme le calcul d'enveloppes convexes ou de triangulations de Delaunay, aux plus récents comme la reconstruction à partir de nuages de points, l'approximation de problèmes géométriques NP-difficiles, ou la localisation éfficace de points en grandes dimensions.
L'objectif du cours sera double : d'une part, mettre en relief l'élégance et la validité théorique des solutions proposées ; d'autre part, montrer leur potentiel au travers d'applications issues de domaines tels que l'informatique graphique, la robotique, l'apprentissage ou le traitement d'images.
Modalités d'évaluation : Examen écrit + partiel ecrit et sur machine
Langue du cours : Français
Algorithmic Geometry is a young discipline that study from a combinatory and algorithmic perspective the properties of geometric objects like scatter plots, arrangments, geometric graphs or triangulations.
This course takes you on a tour of this discipline, illustrating its wealth of theoretical and practical aspects. In this context, we will introduct a range of problems from the field, from the more classical ones like the calculation of convex envelopes or Delaunay triangulations, to the more recent ones like reconstruction starting of scatter plots, approximation of NP-hard geometric problems, or efficient localisation of plots in large dimensions.
The aim for this course are twofold : on the one hand, highlight the elegance and theoretical validity of the proposed solutions; on the other, show their potential throught applications from fields like graphic informatics, robotics, learning or image processing.
Evaluation modalities: Written exam + written and on machine end-of-term exam
Language: French
- Teaching coordinator: Castelli Aleardi Luca