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 Slides|
|(Monday 12 November - MP)||Triangulations in non-Euclidean spaces. Slides|
|(Monday 10 December 8:30)||Presentations (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: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: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
Basic background about algorithms and complexity (sorting algorithms, binary search trees, graphs,...).
Thanks to Monique Teillaud for her contribution to this course.