Table of Contents
## Computational Geometry and Topology : (3 ECTS)Contact : Marc Glisse . ## Teachers## News- [22/09/2023] The Exam page is now up, please check it out here.
## GoalsThis 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? ## LanguageThe course will be given in English, except if all participants speak French fluently. All material is in English. ## Course planning2023-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:
- 1. [11/09] Warm up: 2D convex geometry . [MG]
- 3. [25/09] Robustness and practical Delaunay computation [MG]
- 4. [02/10] Good meshes . [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 ## PrerequisiteAll fundamental notions will be introduced. ## Bibliography
- J-D. Boissonnat, F. Chazal and M. Yvinec, - 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.
- 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. ## Relevant courses## Pedagogic teamMarc Glisse Clément Maria Steve Oudot |