Le monde numérique n’est maintenant plus limité au texte, au son et aux images, et les représentations numériques de formes tridimensionnelles jouent un rôle central dans de très nombreux domaines. Citons, parmi bien d’autres, l’ingénierie, la cartographie, le cinéma et les jeux vidéo, l’architecture, la préservation du patrimoine culturel, l’exploration pétrolière, la médecine ou encore la conception de médicaments. On peut aujourd’hui modéliser les formes complexes de la nature de l’échelle microscopique à l’échelle astronomique, les statues de Michel-Ange ou des villes. Les formes qu’on peut représenter sur un ordinateur sont très variées et les données 3D qu’il faut traiter sont énormes. La conception d’algorithmes efficaces et l’étude de leur complexité est critique. C’est le sujet de la géométrie algorithmique.
Dans une première partie, ce cours étudie les interactions entre géométrie et calcul, et étudie de manière systématique plusieurs structures géométriques fondamentales du point de vue algorithmique. Les algorithmes probabilistes jouent un rôle central et les questions de robustesse et de précision numérique sont discutées. Il faut s’appuyer sur des modèles de calcul suffisamment simples pour permettre d’effectuer les analyses mais suffisamment réalistes pour que celles-ci soient utiles en pratique.
Dans une deuxième partie, on s’intéresse à la représentation des formes géométriques qu’on peut maintenant numériser. Comment construire des modèles informatiques de ces formes complexes et garantir la qualité des approximations‹ ? Le cours s’intéresse d’abord aux maillages des surfaces dans l’espace tridimensionnel puis aborde le cas des objets de plus grandes dimensions qui posent des questions de nature topologique et algorithmique nouvelles. On peut alors développer les techniques de la géométrie algorithmique pour aborder l’analyse de données d’un point de vue géométrique original et fécond.