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 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.
Outline (12 lectures of 2 hours)
and CGAL project or presentation of a paper