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
nonEuclidean spaces will be presented.
Internships in
Gamble team
(slides)
Outline 201819 (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 nonEuclidean 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.