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

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