WikiMPRI

Contact : Steve Oudot .

Steve Oudot, INRIA Saclay - .

Pooran Memari, LIX/Polytechnique - .

In the past 20 years, the field of computational geometry has undergone a vast expansion, including new topics such as high-dimensional geometry, low-dimensional topology, or topological data analysis. This course is an introduction to the field of computational geometry, with a balance between classic and new topics. On the classic side we cover polytopes and convex geometry, Voronoi diagrams and Delaunay triangulations. On the new side we cover manifold reconstruction and learning, nearest neighbor search in high dimensions, geometric methods for clustering, and persistent homology.

]

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

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

• [22/9] Warm up: 2D convex geometry [PM]
• [29/9] Comparing objects, polytopes [PM]
• [6/10] Voronoi, Delaunay [PM]
• [13/10] Reconstruction in higher dimensions [PM]
• [20/10] Nearest neighbor search [SO]
• [3/11] Clustering [SO]
• [10/11] Homology and persistent homology [SO]
• [17/11] Stability of persistent homology - homology inference [SO]
• [1/12] Written exam in class (you can use your notes, the slides, and the book “Geometric and Topological Inference”, all on your laptop)

A background in algorithms design and analysis, as well as in Euclidean geometry and linear algebra. The other required notions will be introduced in the course.

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

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 .