Algorithmique des courbes et surfaces II

Monique Teillaud

• Plan du cours

  2 février 2005	Introduction - à la résolution des problèmes de robustesse en géométrie (prédicats et contructions) - à la bibliothèque CGAL	Transparents
  9 février 2005	* 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	Transparents (merci à Olivier Devillers ) - à éviter d'imprimer (animations, 130 pages !)
  23 février 2005	* 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) * Enveloppe inférieure et suites de Davenport-Schinzel	- Transparents prédicats - Transparents enveloppe inférieure (merci à Olivier Devillers ) - éviter d'imprimer (animations, 95 pages !)

• Exercices
  sujets et indications

• Bibliographie
  Jean-Daniel Boissonnat, Mariette Yvinec, Géométrie Algorithmique, 1995, Ediscience international.
  Jean-Daniel Boissonnat, Mariette Yvinec, Algorithmic Geometry, 1998, Cambridge University Press.
  Micha Sharir, Pankaj K. Agarwal, Davenport-Schinzel Sequences and their Geometric Applications, 1995, Cambridge University Press.
  Herbert Edelsbrunner, Algorithms in Combinatorial Geometry, 1987, Springer Verlag.
  (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.