Computational Geometry

ENS de Lyon - Master 2 - CR02

Lecturers: Olivier Devillers and Monique Teillaud

The page has moved - Please follow this link

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.

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