Géométrie algorithmique
Michel Pocchiola, Ens-Paris, Cours (36H) et TD (18H).

Cours du 27 Février.
  • Introduction : Présentation du domaine de recherche et exemples de problèmes : Diagramme de Voronoi, Convexification d'un polygone simple, Recherche simpliciale; Support de Cours
  • Enveloppes convexes 2D : Orientation d'un triplet de points, chirotope d'une famille de points, CC-systèmes , Balayage de Graham, marche de Jarvis, algorithme de T. Chan, algorithme incrémental randomisé; Support de Cours
  • Relation d'Euler pour les graphes planaires, non planarité des graphes de Kuratowski, localisation dans une triangulation (Méthode de Kirkpatrick), borne inférieure sur le nombre de croisements d'un graphe géométrique en fonction du nombre de sommets et du nombre d'arêtes;

    • Cours du 5 Mars.
  • Enveloppes convexes 2D: Algorithme incrémental déterministe, fonction d'appui d'un convexe, env. conv. et enveloppes inférieures, séquences de Davenport-Schinzel;
  • Triangulations 2D: Démo CGAL sur les triangulations (Delaunay, contraint, conforme, maillage), Énumération (algorithme de Bespatmyatnikh). Support de Cours
  • Nombre d'incidences point-droite, nombre de k-arêtes;

    • Cours du 12 Mars.
  • Théorème du plongement barycentrique de Tutte, application au morphing 2D;
  • Pseudo-triangulations d'une collection de points;

    • Cours du 19 Mars.
  • Arrangements de droites : construction par balayage topologique, arbres d'horizon, théorème d'amortisation;
  • Graphes de visibilité de convexes : pseudo-triangulations, pseudo-triangulations gloutonnes, propriété du flip glouton. Support de Cours
  • Présentation des projets informatiques: calcul de plus courts chemins et algorithme de l'entonnoir, tests d'homotopie, espace des configurations d'un segment dans un envirronnement polygonal;

    • Cours du 26 Mars.
  • Correspondance de Maxwell-Cremona;
  • Complexes de visibilité, espace de configuration d'un segment dans un environnement polygonal;
  • Discussion des projets informatiques;

    • Cours du 02 Avril (Sortie).
  • Les étudiants sont invités à participer au colloque final du projet Européen "Effective Computational Geometry for Curves and Surfaces" ayant lieu en salle Dussane;

    • Cours du 9 Avril.
  • Recherche unidimensionnelle : arbre binaire de recherche aléatoire, borne de Chernoff pour les variables aléatoires harmoniques;
  • Recherche orthogonale : range trees, segment trees;
  • Recherche simpliciale : équipartitions 2D (algorithme de Nimrod Meggido), équipartitions 3D (existence via le théorème de Borsuk-Ulam), équipartitions dD; Support de Cours

    • Vacances de Pâques : 12 Avril au 26 Avril

    Cours du 30 Avril.
  • Hypergraphes géométriques, dimension de Vapnik-Chervonenkis, epsilon-nets, partitions aléatoires;

    • Cours du 7 Mai.
  • Cuttings, problème de Hopcroft, complexité de m cellules d'un arrangement de n droites,
  • Partitions simpliciales, recherche simpliciale;

    • Cours du 14 mai.
  • Convexité, polarité, théorèmes de séparation;
  • Cônes, polyèdres et polytopes, procédure d'élimination de Fourier-Motzkin, Lemmes de Farkas;
  • Théorème de dualité pour la programmation linéaire, progammation linéaire via la méthode du simplexe;

    • Cours du 21 mai.
  • Treillis des faces d'un polytope, polytopes simples et simpliciaux, polytopes cycliques;
  • Effeuillage d'un polytope, f-vecteur et h-vecteur d'un polytope simple;
  • Théorème de la borne supérieure.

    • Cours du 28 Mai (Examen sous forme d'exposé).
  • Bornes inférieures pour la recherche simpliciale;
  • Séquence de Davenport-Schinzel de paramètre 3;
  • Test de rigidité (the pebble game).

    • Last modified: Wed Jun 16 12:05:08 CEST 2004