Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

cours:c-2-14 [2011/07/12 19:26] (current)
Line 1: Line 1:
 +
 +===== Géométrie algorithmique (48h, 6 ECTS) =====
 +
 +Responsables : Jean-Daniel Boissonnat et Michel Pocchiola
 +
 +==== Plan du cours et intervenants prévus pour 2005-2006 ====
 +
 +  -  Topologie algorithmique. (12h, [[http://www.di.ens.fr/users/pocchiol/|Michel Pocchiola]], les 26 oct.  et 02, 09 et 16 nov. reporté au 15 fév. 06
 +  -  Géométrie algorithmique en grandes dimensions. (12h, Michel Pocchiola, les 18 et 25 janv. et 01 et  08 fév. 
 +  -  Triangulations et maillages  (12h, Mariette Yvinec, les 28 sept. et 05, 12 et 19 oct.
 +  -  Maillages de surfaces   (12h, Jean-Daniel Boissonnat, les 07 et 14 déc. et 04 et 11 janv.
 +  -  Liens  [[http://www.di.ens.fr/users/pocchiol/mpri205.html|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 ====
 +   -**Topologie algorithmique** (M. Pocchiola).
 + <ul>
 + <li> Calcul d'homotopie sur les surfaces combinatoires. [[http://www.di.ens.fr/users/pocchiol/Cours05-MPRI2/slide261005.ps|Support de cours]]
 + <li> Homologie, éléments de théorie de Morse.
 + <li> Persistance, simplification topologique.
 + </ul>
 +   -**Géométrie algorithmique en grandes dimensions** (Michel Pocchiola).
 + <ul>
 + <li> La méthode de projection aléatoire.
 + <li> Plus proches voisins, indexation et groupage.
 + <li> Calcul sur des flots de données géométriques.
 + </ul> 
 +   -**Triangulations et maillages** (M. Yvinec).
 + <ul>
 + <li> [[ftp://ftp-sop.inria.fr/geometrica/yvinec/Slides/mpri04pres.pdf|Présentation]]
 + <li> 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)
 + [[ftp://ftp-sop.inria.fr/geometrica/boissonnat/Cours/Course//notes//voronoi-delaunay.pdf|Support de cours]]
 + <li>  Triangulations contraintes: Condition d'existence et construction des triangulations contraintes. Optimalité des triangulations Delaunay contraintes. [[ftp://ftp-sop.inria.fr/geometrica/yvinec/Slides/MPRI05_constrained.pdf|Slides]].
 + <li> Introduction aux maillages. Maillages par raffinement de Delaunay. La méthode de Ruppert en dimension 2 et 3. 
 +   [[ftp://ftp-sop.inria.fr/geometrica/yvinec/Slides/MPRI05_m1.pdf|Slides1]].
 +   [[ftp://ftp-sop.inria.fr/geometrica/yvinec/Slides/MPRI05_m2.pdf|Slides2]].
 + <li> Autres méthodes de maillages. Evaluation des maillages et critères de qualité. Introduction à la méthode des éléments finis. 
 + [[ftp://ftp-sop.inria.fr/geometrica/yvinec/Slides/MPRI05_m3.pdf|Slides3]].
 +  </ul>
 +   -**Maillage de surfaces** (J-D. Boissonnat)
 +  <ul>
 +  <li> Présentation
 +  <li> Echantillonnage de surfaces. Triangulation de Delaunay restreinte. Propriétés géométriques et topologiques. Algorithme de maillage.
 +   [[ftp://ftp-sop.inria.fr/geometrica/boissonnat/Cours/Transp/surfapprox1.pdf|Slides1]],
 +   [[ftp://ftp-sop.inria.fr/geometrica/boissonnat/Cours/Transp/surfapprox2.pdf|Slides2]],
 +   [[ftp://ftp-sop.inria.fr/geometrica/boissonnat/Cours/Course//notes//surf_approx.pdf|Support de cours]]  
 +  <li> Axe médian, homotopie, stabilité, approximation. Flot dans un diagramme de Voronoi.
 +  <li> Interpolation. Reconstruction de surface. Interpolation de données non structurées. Voisins naturels. Moindres carrés glissant (MLS moving least square).
 + [[ftp://ftp-sop.inria.fr/geometrica/boissonnat/Cours/Transp/surfreconstruction.pdf|Slides3]],
 + [[ftp://ftp-sop.inria.fr/geometrica/boissonnat/Cours/Course//notes//syst-coordonnees.pdf|Support de cours]]  
 + <li> Approximation des courbures, approximation de l'axe médian.(MY) 
 + [[ftp://ftp-sop.inria.fr/geometrica/yvinec/Slides/mpri05_courbures.pdf|Slides4]],
 + [[ftp://ftp-sop.inria.fr/geometrica/yvinec/Slides/mpri05_ma.pdf|Slides5]]
 +
 +  </ul>
 +
 +==== 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 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 &amp; 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(1-3):21-74, May 2002. 
 +   [[http://www.cs.berkeley.edu/~jrs/papers/2dj.ps|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,
 +Issue 4 , July 2005, Pages 304-331
 +
 +==== Intervenants  ====
 +
 +| J-D. Boissonnat | DR | INRIA | Sophia-Antipolis |
 +| M. Pocchiola | MC | ENS Ulm | LIENS |
 +| M. Yvinec | CR | INRIA | Sophia-Antipolis |
 +
 +==== Les années précédentes ====
 +
 +      * [[2009-2010-C-2-14|Année 2009-2010]]
 +** Année  [[2008-2009-C-2-14|2008-2009]]
 +
 +------
 +   * Set ALLOWTOPICCHANGE = %MAINWEB%.WebMastersGroup, %MAINWEB%.MichelPocchiola, %MAINWEB%.MarietteYvinec, %MAINWEB%.JeandanielBoissonnat
 +
  
 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA