Computational Geometry
ENS de Lyon - Master 2 - CR02
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.
Prerequisites
Basic background about algorithms and complexity
(sorting algorithms, binary search trees, graphs,...).