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

Computational Geometry Learning : (3 ECTS)

Contact : Jean-Daniel Boissonnat .

Teachers

Marc Glisse, DataShape, INRIA Saclay - .

Clément Maria, DataShape, INRIA Sophia Antipolis - .

Goals

This course is an introduction to the emerging field of Geometric and Topological Data Analysis. Fundamental questions to be addressed are : how can we represent complex shapes in high-dimensional spaces? how can we infer properties of shapes from samples? how can we handle noisy data? how can we walk around the curse of dimensionality?

Language

The course will be given in English, except if all participants speak French fluently. Slides and course notes are in English.

.

Course planning

2018-2019: New schedule in preparation, class starts in December. The course consists of 8 lectures of 3h each, on Tuesdays at 12:45.

  • [18/12] Polytopes [MG]
  • [8/1] Delaunay triangulations [MG]
  • [15/1] Higher dimensions [MG]
  • [22/1] Homology theory [CM]
  • [29/1] Discrete Morse theory [CM]
  • [5/2] Persistent homology [CM]
  • [12/2] Stability and topological inference [CM]
  • [5/3] exam (you can use your notes, the slides, and the book “Geometric and Topological Inference”)

2017:

Introduction .

  • 2. [18/09] Polytopes and Delaunay complexes (26/09). Weighted Delaunay .[JDB]
  • 3. [25/09] Robustness and practical Delaunay computation [MG]
  • 4. [02/10] Good meshes . [JDB]
  • 5. [09/10] Distance functions . . [MG]
  • 6. [16/10] Reconstruction of submanifolds . . [JDB]
  • 7. [23/10] Topological persistence . [MG]
  • 8. [30/10] Randomized algorithms [JDB]
  • 9. [06/11] Multi-scale inference and applications . [MG]
  • [27/11] exam

A related course and additional slides (in french) can be found at http://www.college-de-france.fr/site/jean-daniel-boissonnat/course-2016-2017.htm

Prerequisite

All fundamental notions will be introduced.

Bibliography

Text books

- J-D. Boissonnat, F. Chazal and M. Yvinec, Geometric and Topological Inference, Cambridge University Press .

- J-D. Boissonnat and M. Yvinec, Algorithmic Geometry. Cambridge University Press, 1998.

- E. Edelsbrunner and J. Harer, Computational Topology, an introduction. AMS 2010.

- S. Har-Peled, Geometric Approximation Algorithms, American Mathematical Society, USA 2011

- Motwani and Raghavan, Randomized Algorithms, Cambridge University Press, 1995.

Research papers

- J-D. Boissonnat, A. Ghosh. Manifold reconstruction using tangential Delaunay complexes. Discrete Comput. Geom., 51: 221-267, 2014.

- F. Chazal, D. Cohen-Steiner, A. Lieutier. A Sampling Theory for Compacts in Euclidean Space, Discrete Comput. Geom., 41:461-479, 2009.

- F. Chazal, D. Cohen-Steiner, Q. Mérigot. Geometric Inference for Probability Measures. J. Foundations of Comp. Math., 2011, Vol. 11, No 6.

- F. Chazal, L. J. Guibas, S. Y. Oudot, P. Skraba. Persistence-Based Clustering in Riemannian Manifolds. J. of the ACM, Vol 60, No 6, article 41.

On-going projects

- European Research Council (ERC): Advanced Grant GUDHI : Geometric Understanding in Higher Dimensions .

- Agence Nationale de la Recherche (ANR) : TopData : Topological Data Analysis: Statistical Methods and Inference .

Relevant courses

Pedagogic team

Jean Daniel Boissonnat

Marc Glisse

Clément Maria

 
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