Marc Glisse, DataShape, INRIA Saclay - .

Clément Maria, DataShape, INRIA Sophia Antipolis - . (until 2023-2024)

Steve Oudot, GeomeriX, Inria Saclay - .

This course is an introduction to the field of Computational Geometry and Topology (the later has become popular under the name 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?

The course will be given in English, except if all participants speak French fluently. All material is in English.

2024-2025: The course consists of 8 lectures of 3h each, on Tuesdays at 8:45. Lectures will take place in room 1002 of the Sophie Germain building.

• [17/9] Warm up: 2D convex geometry [MG] .
• [24/9] Comparing objects, polytopes [MG] .
• [1/10] Clustering [SO] slides
• [8/10] Voronoi, Delaunay [MG] .
• [15/10] Reconstruction in higher dimension [MG] (slides: some parts of .)
• [29/10] Nearest neighbor search [SO] slides (exercise on the proof of LSH, solution)
• [5/11] Homology and persistent homology [SO] notes on homology, notes on persistent homology, exercises, solutions
• [12/11] Stability of persistent homology - homology inference [SO] notes on stability, notes on homology inference
• [26/11] Written exam in class (you can use your notes, the slides, and the book “Geometric and Topological Inference”, all on your laptop)

2023-2024: The course consists of 8 lectures of 3h each, on Thursdays at 12:45. Lectures taught by [SO] will take place in room 1002 of the Sophie Germain building. Lectures taught by [CM] are remote, through BBB or a similar visio system (details will be sent by e-mail).

• [14/9] Voronoi diagrams and Delaunay triangulations [SO] —— slides
• [21/09] Nearest neighbor search [SO] —— slides
• [28/09] Manifold reconstruction [SO] —— slides
• [05/10] Homology theory [CM] – slides
• [12/10] Clustering [SO] —— slides
• [19/10] Discrete Morse theory [CM] – slides
• [26/10] Persistent homology [CM] – slides
• [09/11] Stability and topological inference [CM] – visio slides
• [30/11] Exam: oral paper presentation+questions (visio)

2022-2023: The course consists of 8 lectures of 3h each, on Mondays at 16:15. The first 4 lectures will take place in room 1004. The last 4 will be remote, through BBB or a similar visio system.

• [19/9] Warm up: 2D convex geometry .
• [26/9] Comparing objects, polytopes .
• [3/10] Voronoi, Delaunay .
• [10/10] Reconstruction in higher dimension
• [17/10] Homology theory [CM] —— 0 Overview 1 Homology theory
• [24/10] Discrete Morse Theory [CM] –—- 2 Discrete Morse theory
• [31/10] Persistent homology [CM] —— 3 Persistent homology
• [07/11] Stability and topological inference [CM] —— 4 Topology inference
• [28/11] exam en présentiel (you can use your notes, the slides, and the book “Geometric and Topological Inference”, all on your laptop)

2021-2022: The course consists of 8 lectures of 3h each, on Fridays at 12:45 in room 1004.

• [17/9] Warm up: 2D convex geometry . [MG] homework: 1st exercise of the exam from 2020-2021
• [24/9] . [MG]
• [8/10] . [MG]
• [15/10] . [MG]
• [22/10] Homology theory [CM] —- 0 Overview 1 Homology theory
• [5/11] Discrete Morse theory [CM] —- 2 Discrete Morse theory
• [12/11] Persistent homology [CM] —- 3 Persistent homology
• [19/11] Stability and topological inference [CM] —- 4 Topology inference
• [3/12] exam en présentiel (you can use your notes, the slides, and the book “Geometric and Topological Inference”, all on your laptop)

2020-2021: The course consists of 8 lectures of 3h each, on Wednesdays at 8:45 in room 1013.

• [16/9] Warm up: 2D convex geometry . [MG]
• [23/9] Comparing objects, polytopes . [MG]
• [30/9] Voronoi, Delaunay . [MG]
• [07/10] Homology theory [CM] —- 0 Overview 1 Homology theory
• [14/10] Higher dimensions . [MG] in room 1013
• [21/10] Discrete Morse theory [CM] —- 2 Discrete Morse theory
• [28/10] Persistent homology [CM] —- 3 Persistent homology
• [04/11] Stability and topological inference [CM] —- 4 Topology inference
• [02/12] exam (from home, send your copy by email) (you can use your notes, the slides, and the book “Geometric and Topological Inference”)

2019-2020: The course consists of 8 lectures of 3h each, on Thursdays at 12:45 in room 1013.

• [19/9] Warm up: 2D convex geometry . [MG]
• [26/9] Comparing objects, polytopes [MG]
• [3/10] Voronoi, Delaunay [MG]
• [10/10] [CM] Homology theory
• [24/10] [CM] Discrete Morse theory
• [31/10] [MG] Higher dimensions
• [7/11] [CM] Persistent homology
• [14/11] [CM] Stability and topological inference
• [28/11] exam (you can use your notes, the slides, and the book “Geometric and Topological Inference”, all on your laptop)

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

• [4/12] Warm up: 2D convex geometry . [MG]
• [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] WARNING: homework for 2021 is exercise 1 of the exam from 2020, not this one exam (you can use your notes, the slides, and the book “Geometric and Topological Inference”)

2017:

Introduction .

• 1. [11/09] Warm up: 2D convex geometry . [MG]

• 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

Extra slides: Nearest neighbors ., witness complex .

All fundamental notions will be introduced.

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.

* Algorithms and combinatorics for geometric graphs

* Computer Graphics and Scientific Visualization