Computational Geometry

ENS de Lyon - Master 2 - CR02

Lecturers: Olivier Devillers and Monique Teillaud

The goal of this class is to present classical computational geometry and its limitations: worst-case optimal algorithms are too complex, degenerate inputs are not well handled, floating-point computations create inconsistencies.
The course will review solutions used to address these limitations: randomization, probabilistic analysis, exact computation paradigm.

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

(Continuous assessment) and (CGAL project or presentation of a paper). More details (updated Nov 9)
Projects and papers (updated Nov 13).
File for project "3D alpha shapes".

Basic background about algorithms and complexity (sorting algorithms, binary search trees, graphs,...).