Parisian Master of Research in Computer Science

Master Parisien de Recherche en Informatique (MPRI)

Géométrie algorithmique (48h, 6 ECTS)

Responsables : Jean-Daniel Boissonnat et Michel Pocchiola

Plan du cours et intervenants prévus pour 2005-2006

1. Topologie algorithmique. (12h, Michel Pocchiola, les 26 oct. et 02, 09 et 16 nov. reporté au 15 fév. 06)
2. Géométrie algorithmique en grandes dimensions. (12h, Michel Pocchiola, les 18 et 25 janv. et 01 et 08 fév. )
3. Triangulations et maillages (12h, Mariette Yvinec, les 28 sept. et 05, 12 et 19 oct.)
4. Maillages de surfaces (12h, Jean-Daniel Boissonnat, les 07 et 14 déc. et 04 et 11 janv.)
5. Liens Enoncé et corrigé du partiel du 30 nov. 05

Objectifs

L'objectif de ce cours est donner aux étudiants les connaissances de base nécessaires pour aborder la littérature récente en géométrie algorithmique (topologie, grandes dimensions, flots de données, techniques d'échantillonnage, approximation) et de présenter les techniques émergeantes en modélisation géométrique.

Plan du cours

1. Topologie algorithmique (M. Pocchiola).
   • Calcul d'homotopie sur les surfaces combinatoires. Support de cours
   • Homologie, éléments de théorie de Morse.
   • Persistance, simplification topologique.
2. Géométrie algorithmique en grandes dimensions (Michel Pocchiola).
   • La méthode de projection aléatoire.
   • Plus proches voisins, indexation et groupage.
   • Calcul sur des flots de données géométriques.
3. Triangulations et maillages (M. Yvinec).
   • Présentation
   • Triangulations et diagrammes de Voronoi: Complexes simpliciaux. Complexite des triangulations en dimension 2 et 3. Diagrammes de Voronoi, Triangulation de Delaunay, espace des sphères. Diagrammes de puissance et triangulations régulières. (JDB) Support de cours
   • Triangulations contraintes: Condition d'existence et construction des triangulations contraintes. Optimalité des triangulations Delaunay contraintes. Slides.
   • Introduction aux maillages. Maillages par raffinement de Delaunay. La méthode de Ruppert en dimension 2 et 3. Slides1. Slides2.
   • Autres méthodes de maillages. Evaluation des maillages et critères de qualité. Introduction à la méthode des éléments finis. Slides3.
4. Maillage de surfaces (J-D. Boissonnat)
   • Présentation
   • Echantillonnage de surfaces. Triangulation de Delaunay restreinte. Propriétés géométriques et topologiques. Algorithme de maillage. Slides1, Slides2, Support de cours
   • Axe médian, homotopie, stabilité, approximation. Flot dans un diagramme de Voronoi.
   • Interpolation. Reconstruction de surface. Interpolation de données non structurées. Voisins naturels. Moindres carrés glissant (MLS moving least square). Slides3, Support de cours
   • Approximation des courbures, approximation de l'axe médian.(MY) Slides4, Slides5

Pré-requis

Sans être indispensable un premier contact avec le objets, les techniques et les applications de la geométrie algorithmique du niveau du livre de Berg et al. ou du niveau du cours de geometrie discrete et algorithmique de la première année du master (cours C-1-11) devrait faciliter l'assimilation et la compréhension du cours.

Bibliographie

• B. Chazelle. The Discrepancy Method -- Randomness and Complexity. Cambridge University Press, 2000.
• M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin, Germany, 2nd edition, 2000.
• J-D. Boissonnat and M. Yvinec. Algorithmic Geometry. Cambridge University Press, UK, 1998. Translated by Hervé Brönnimann.
• E. Edelsbrunner. Geometry and Topology for Mesh Generation. Cambridge, 2001.
• J. E. Goodman and J. O'Rourke, editors. Handbook of Discrete and Computational Geometry. CRC Press, 2nd edition, 2004.
• P. Indyk. High-dimensional computational geometry. Thesis, 2001.
• J. Matousek. Geometric Discrepancy. Number 18 in Algorithms and Combinatorics. Springer-Verlag, 1999.
• J. Matousek. Lectures on discrete geometry. Number 212 in Graduate Texts in Mathematics. Springer-Verlag, 2002.
• K. Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ, 1994.
• J. Pach and P. K. Agarwal. Combinatorial Geometry. John Wiley & Sons, New York, NY, 1995.
• S. S. Vempala. The random projection method. Volume 65 in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, 2004.
• J. Shewchuk. Delaunay Refinement Algorithms for Triangular Mesh Generation, Computational Geometry: Theory and Applications 22(C-1-3):21-74, May 2002. PostScript (5,128k, 54 pages)
• A.J. Zomorodian. Topology for computing. Number 16 in Cambridge Monographs on Applied and Computational Mathematics. Cambridge, 2005.
• M. Bern and D. Eppstein. Mesh generation and optimal triangulation. In Computing in Euclidean Geometry. D.Z. Du and F.K.  Hwang editors, World Scientific, 2nd edition, 1995.
• J. Shewchuk. What is a good linear finite element? Interpolation, conditioning, anisotropy and quality measures. unpublished preprint, 2002. Available from J. Shewchuk web page.
• David Cohen Steiner and Jean Marie Morvan Restricted Delaunay triangulation and normal cycles, ACM Symposium on computational geommetry 2003
• Frédéric Chazal and André Lieutier, The lambda medial axis, Graphical Models, Volume 67,

Intervenants