Géométrie algorithmique.
Équipe GEOMETRICA
INRIA Saclay Île-de-France
1 rue Honoré d'Estienne d'Orves
Bâtiment Alan Turing
Campus de l'École Polytechnique
91120 Palaiseau
FRANCE
Nozha Boujemaa
Nozha POINT Boujemaa À inria POINT fr
Souvent, on s'intéresse à un objet (matériel ou pas) qu'on ne connaît pas exactement, mais pour lequel on dispose d'un nuage de points dont on suppose qu'il approche bien l'objet (ou son bord). Reconstruire l'objet va consister à trouver un objet discret explicite (comme un polyèdre) qui ressemble bien à l'objet de départ, à la fois en étant géométriquement proche, mais aussi en ayant la même topologie (composantes connexes, tunnels, cavités).
Une chose naturelle à faire avec un nuage de points, c'est de remplacer chaque point par une petite boule. L'union de ces boules, dans les bons cas, est une reconstruction de l'objet (mais pas une très pratique). Et le théorème du nerf nous dit qu'en partant des points et en ajoutant des arêtes quand deux boules s'intersectent et des triangles dès que 3 boules s'intersectent, on obtient un objet de même topologie que l'union des boules, et on a gagné. Malheureusement, les bons cas sont rares, et nécessitent essentiellement que la surface soit lisse.
Cependant, on sait calculer la topologie même dans des cas où on ne sait pas reconstruire, en utilisant la persistance homologique. Essentiellement, au lieu de choisir un rayon magique pour les boules, on en prend 2, et on compare. Les caractéristiques topologiques communes aux 2 unions de boules correspondent à celles de l'objet, sous des hypothèses assez faibles. On sait même qu'on peut reconstruire l'objet en prenant l'union des petites boules et en ajoutant des morceaux bien choisis des grosses boules.
On est du coup tenté de faire pareil avec les objets discrets obtenus par le théorème du nerf, on a 2 ensembles de points / segments / triangles / tétraèdres, inclus l'un dans l'autre, et on veut trouver, par exemple en partant du petit en en rajoutant quelques objets du gros, quelque chose qui a pour caractéristiques topologiques exactement celles communes aux 2 (ni plus ni moins). En toute généralité, à moins de travailler dans le plan, savoir si une telle construction est faisable est NP-complet. Dans certains cas particuliers (si le petit est connexe), c'est polynomial.
L'objectif du stage serait d'étudier en profondeur ce cas polynomial :