Dans ce cours d'introduction aux objets, techniques et applications de la géométrie algorithmique nous développons plus particulièrement l'étude des arrangements d'hyperplans et des polyèdres convexes, la recherche simpliciale, et la programmation linéaire.

Cours des 17, 24 Février et 3 Mars

polyèdres et arrangements d'hyperplans support de cours

Cours des 10, 17 et 24 Mars

Construction d'un arrangement de droites par balayage support de cours

Arrangement de pseudodroites, chirotopes, théorème de Folkman-Lawrence

Algorithmes d'enveloppe convexes 2D, backward analysis, séquences de Davenport-Schinzel support de cours

Cours du 31 mars : partiel

Cours des 7 et 28 Avril

Théorème de Steinitz via le théorème du plongement barycentrique de Tutte

Triangulations, triangulation de Delaunay (construction incrémentale randomisée), localisation dans une triangulation, énumération

Pseudo-triangulations, pseudo-triangulations gloutonnes, propriété du flip glouton, graphes de visibilité, énumération support de cours

Cours des 5, 12, 19 Mai

Recherche géométrique, recherche orthogonale, recherche simpliciale: équipartitions, partitions randomisés

Théorie des epsilon-nets, cuttings et partitions simpliciales (existence) support de cours

Surfaces combinatoires, classification des surfaces combinatoires.

Cours du 02 Juin : examen.

---

Last modified: Fri May 19 12:57:47 CEST 2006