Computational Geometry

ENS de Lyon - Master 2 - CR02

Lecturers: Olivier Devillers and Marc Pouget


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.


Bibliography


Internships in Gamble team (slides)


Outline 2018-19 (7 lectures of 3 hours + exam, Monday 9:00 or Friday 13:30, room B1)
(Friday 21 September - OD)   Introduction. Slides
Convex hull: definitions, classical algorithms. Slides -     Exercises - Correction
(Monday 24 September - OD)   Delaunay triangulation: definitions, motivations, properties, classical algorithms. Slides -     Exercises - Correction
(Friday 5 October - OD)   Probabilistic analyses: randomized algorithms, evenly distributed points. Slides -     Exercises - Correction
(Monday 8 October - OD)   Robustness issues: numerical issues, degenerate cases. Slides -     Exercises - Correction
(Friday 19 October - OD)   Applications: reconstruction, meshing. Slides
(Friday 9 November - MP)   Triangulations in the CGAL library. Slides
(Monday 12 November - MP)   Triangulations in non-Euclidean spaces. Slides
(Monday 10 December 8:30)   Presentations (Evaluation).

Evaluation
Continuous assessment and presentation of a paper.
Papers (updated Oct 5).
Affectation des sujets:
08:00 C. Brosse: Rounding arrangements dynamically (Guibas & Marimount)
08:20 G. Coiffier: Star splaying (Shewchuk)
08:40 L. Gayral: Stable snap rounding (Hersheberger)
09:00 break
09:10 X. H. La: The ultimate planar convex hull algorithm (Kirkpatrick & Seidel)
09:30 P. Nidhi: Sorting Helps for Voronoi (Chew & Fortune)
09:50 P.-E.Polet: Shewchuk predicates
10:10 D. H. Ta: Triangulating simple polygon (Seidel)
10:20 break
10:40 M. Vavrille: upper enveloppe (Hersheberger)
11:00 L. Bethune: Projet crust
11:20 J. Felderhoff: Projet moving points
11:40L. Valque: Projet Poisson Delaunay simulations


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


Acknowledgements
Thanks to Monique Teillaud for her contribution to this course.