* Arrangements d'hyperplans
- Complexité
- Algorithme incrémental et complexité
* Arrangements de segments
- Algorithme de Bentley-Ottmann et complexité
- Problèmes de précision et variantes du balayage
- Décomposition verticale (carte des trapèzes) et décomposition cylindrique algébrique, complexité
- Prédicats et constructions pour le balayage
* Enveloppe inférieure et suites de Davenport-Schinzel
Transparents - arrangements et enveloppes inférieures (merci à Olivier Devillers ) - ne pas imprimer (animations, 230 pages !)
* La bibliothèque CGAL
* Introduction à la résolution des problèmes de robustesse en géométrie (prédicats et constructions)
Transparents - CGAL et robustesse
* Zoom sur les prédicats et constructions
cas des segments et des arcs de courbes de petits degrés
- degré algébrique
- variantes (intersections, arrangements, carte des trapèzes)
Transparents - prédicats
A propos d'un noyau courbe CGAL
* Aperçu de la dimension 3
- arrangements de sphères, de quadriques
- décomposition spatiale...
Transparents - arrangements de quadriques
Bibliographie
- Micha Sharir, Pankaj K. Agarwal, Davenport-Schinzel Sequences and their Geometric Applications, 1995, Cambridge University Press.
- (Distribué en cours) Dan Halperin, Arrangements, Handbook of Discrete and Computational Geometry, Chapitre 21, Jacob E. Goodman and Joseph O'Rourke, 1997, CRC Press LLC.
- (Pour en savoir plus sur un autre aspect de la robustesse dans CGAL, le traitement des cas dégénérés, très rapidement mentionné en cours)
Olivier Devillers and Monique Teillaud. Perturbations and Vertex Removal in a 3D Delaunay Triangulation. In Proc. 14th ACM-SIAM Symposium on Discrete Algorithms, pages 313-319, 2003.
Transparents
- et bien sûr
Jean-Daniel Boissonnat, Mariette Yvinec, Géométrie Algorithmique, 1995, Ediscience international.
Jean-Daniel Boissonnat, Mariette Yvinec, Algorithmic Geometry, 1998, Cambridge University Press.