Computational Geometry


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.

Outline (12 lectures of 2 hours)

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

Proposed evaluation:
written exam
and CGAL project or presentation of a paper