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: Introduction (par Steve) |
TD1 |
mardi 8 janvier |
|
| Slides |
Amphi 2: Delaunay triangulations (I) (par Steve) | TD2 (solution) |
mardi 15 janvier | |
| Slides |
Amphi 3: Graphs I: geometric aspects of planar graphs
(par Luca) |
TD3 |
mardi 22 janvier | |
| Slides |
Amphi 4: Geometric proximity problems (par Luca) | TD4 |
mardi 29 janvier |
|
| Slides |
Amphi 5: Delaunay triangulations (II) (par Steve) |
TD5 (solution) |
mardi 5 février |
|
| PC+TD: solving geometric problems, with implementation
(Luca) |
TD6 |
mardi 12 février |
TD noté |
|
| Slides |
Amphi 7: Curve and surface reconstruction (par Steve) | TD7 (solution) |
mardi 19 février | |
| Slides |
Amphi 8: Graphs II: convex geometry and planar
separators (par Luca) |
graph separators
(complément) |
mardi 26 février | |
| Slides |
Amphi 9: Geometric approximation algorithms (par Steve) | TD9 (solution) |
mardi 12 mars |
Cours en PC3 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 :