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.

Niveau requis : aucun (INF555 est conseillé)

Modalités d'évaluation : Examen écrit + mini-projet (non-obligatoire, en binômes)

Mini-projets (international programming contests): en 2019-20 et 2020-21 le but était de concevoir et implanter des solutions algorithmiques efficaces pour la solution de problèmes d'optimisation géométrique proposés par deux compétitions internationales: le CG:SHOP Competition (in conjuction with the Annual Symp. on Computational Geometry) et le Graph Drawing Live Challenge (programming contest organized during the annual Symp. on Graph Drawing and Network Visualization).

Langue du cours : anglais

Credits ECTS : 4




Computational geometry is a rather novel field whose aim is to study the properties of geometric objects such as point clouds, arrangements, geometric graphs or triangulations, both from a combinatorial and from an algorithmic point of view.

This course proposes a walkthrough of the discipline, to illustrate its variety in terms of topics as well as its potential in terms of applications. In this context, we will introduce a panel of theoretical questions, from very classical (e.g. computing convex hulls or Delaunay triangulations) to very recent (e.g. reconstruction from unorganized point clouds, approximation of geometric NP-complete problems, or effective proximity queries in high dimensions). Our goal will be twofold: on the one hand, to emphasize the elegance and theoretical soundness of the proposed approaches; on the other hand, to illustrate their practicality through a range of applications in computer graphics, robotics, machine learning, and image processing.

No course prerequisites (INF555 is strongly suggested)

Final evaluation: written exam + mini-project (not mandatory, done in pairs)

Mini-projects (international programming contests): in 2019-20 and 2020-21 students have been asked to design and implement algorithmic tools for solving the optimization problems proposed by two international programming contests: the CG:SHOP Competition (in conjuction with the Annual Symp. on Computational Geometry) and the Graph Drawing Live Challenge (programming contest organized during the annual Symp. on Graph Drawing and Network Visualization).

Language: english