The algorithmic techniques will be presented on a specific
problem: constructing triangulations of a point set.
Applications such as reconstruction algorithms and meshing will be
sketched.
Finally, recent developments about computational geometry in
non-Euclidean spaces will be presented.
Bibliography (updated Nov 26)
Outline (7 lectures of 3 hours + exam)
| (Monday 9 October - OD) | Introduction. Slides
Convex hull: definitions, classical algorithms. Slides Exercises - Correction |
|
| (Friday 10 November - OD) | Delaunay triangulation: definitions, motivations, properties, classical algorithms.
Slides
Exercises - Correction |
|
| (Monday 13 November - OD) | Probabilistic analyses: randomized algorithms, evenly distributed points.
Slides
Exercises - Correction |
|
| (Friday 17 November - MT) | Robustness issues: numerical issues, degenerate cases.
Slides
Exercises - Correction |
|
| (Monday 20 November - MT) | Triangulations in the CGAL library. Slides | |
| (Friday 24 November - OD) | Applications: reconstruction, meshing. Slides | |
| (Monday 27 November - MT) | Triangulations in non-Euclidean spaces. Slides | |
| (Monday 18 December) | Presentations (Evaluation). |
Evaluation
(Continuous assessment) and (CGAL project or presentation of a paper). More details (updated Nov 9)
Projects and papers (updated Nov 13).
File data.zip for project "3D alpha shapes".
-->
Prerequisites
Basic background about algorithms and complexity
(sorting algorithms, binary search trees, graphs,...).