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
nonEuclidean 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 nonEuclidean 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,...).