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.
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.