ENS de Lyon - Master 2 - CR02
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
The course will review solutions used to address these
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
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,...).