Luca Castelli Aleardi et Steve Oudot
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.
| Slides Amphi 1 |
Amphi 1: Introduction (par Luca) |
TD1 |
mardi 3 janvier |
exos 1 et 3 (deadline 24
janvier) |
| Slides Amphi 2 | Amphi 2: Graphs I: geometric aspects of planar graphs (par Luca) | TD2 |
mardi 10 janvier | exos 1, 2 et 3 (deadline 31 janvier) |
| Slides_Amphi_3 |
Amphi 3: Geometric proximity problems (par Luca) | TD3 |
mardi 17 janvier | tout (deadline 7
février) |
| Slides_Amphi_4 |
Amphi 4: Graphs II: planar separators and applications (par Luca) | TD4 |
mardi 24 janvier |
tout (deadline 14 février) |
| Slides_Amphi_5 |
Amphi 5: Delaunay triangulations and Voronoi diagrams I (par Steve) | TD5 | mardi 31 janvier |
tout (deadline 21 février) |
| Slides_Amphi_6 |
Amphi 6: Delaunay triangulations and Voronoi diagrams II (par Steve) | TD6 | mardi 14 février | tout (deadline 6 mars) |
| Slides_Amphi_7 |
Amphi 7: Curve and surface reconstruction (par Steve) | TD7 | mardi 28 février | tout (deadline 20 Mars) |
| Slides_Amphi_8 | Amphi 8: Geometric approximation algorithms (par Steve) | TD8 | mardi 6 mars | exo 1 (deadline 27 mars) |
| Amphi 9: Quadtrees (conférencier invité : Donald Sheehy) |
TD9 | mardi 13 mars |
tous les exos (rien à rendre) |
Cours en PC 19 de 13h30 à 15h et TD en salle info 33 de 15h15
à 17h15 (mardi
après-midi)
Chacun des 9 blocs du cours est constitué d'1h30 en amphi,
consacrées au cours, suivies de 2 heures en petite classe,
consacrées à la mise en pratique des techniques vues
en amphi (sous forme de programmation en Java).
* ALGORITHMIQUE DES GRAPHES
PLONGÉS SUR DES SURFACES: du dessin au codage de graphes
(html)
(proposé par Luca Castelli Aleardi et Eric Fusy, LIX, Ecole
Polytechnique)
* STRUCTURES DE DONNEES COMPACTES POUR LES MAILLAGES
(html)
(proposé par Luca Castelli Aleardi et Gilles Schaeffer,
LIX, Ecole Polytechnique)
La communauté représente environ une centaine de chercheurs permanents à travers le monde, dont un peu plus d'une vingtaine en France.
Équipes en France :