v2.11.0 (5380)

PA - C1B' - INF562 : Géométrie algorithmique : de la théorie aux applications

Domaine > Informatique.

Descriptif

La géométrie algorithmique est une jeune discipline de l'informatique qui étudie d'un point de vue combinatoire et algorithmique les propriétés d'objets géométriques tels que nuages de points, arrangements, graphes géométriques, ou encore triangulations.

Ce cours propose une promenade au sein de cette discipline afin d'en illustrer la richesse sur le plan théorique et applicatif. Dans ce contexte, nous introduirons un éventail de problèmes issus du domaine, des plus classiques comme le calcul d'enveloppes convexes ou de triangulations de Delaunay, aux plus récents comme la reconstruction à partir de nuages de points, l'approximation de problèmes géométriques NP-difficiles, ou la localisation éfficace de points en grandes dimensions.

L'objectif du cours sera double : d'une part, mettre en relief l'élégance et la validité théorique des solutions proposées ; d'autre part, montrer leur potentiel au travers d'applications issues de domaines tels que l'informatique graphique, la robotique, l'apprentissage ou le traitement d'images.

Niveau requis : aucun (INF555 est conseillé)

Modalités d'évaluation : Examen écrit + mini-projet (non-obligatoire, en binômes)

Mini-projets (international programming contests): en 2019-20 et 2020-21 le but était de concevoir et implanter des solutions algorithmiques efficaces pour la solution de problèmes d'optimisation géométrique proposés par deux compétitions internationales: le CG:SHOP Competition (in conjuction with the Annual Symp. on Computational Geometry) et le Graph Drawing Live Challenge (programming contest organized during the annual Symp. on Graph Drawing and Network Visualization).

Langue du cours : anglais

Credits ECTS : 4

Format des notes

Numérique sur 20

Littérale/grade réduit

Pour les étudiants du diplôme M2 IGD - Interaction, Graphic and Design

Le rattrapage est autorisé (Note de rattrapage conservée)
    L'UE est acquise si note finale transposée >= C
    • Crédits ECTS acquis : 5 ECTS

    Pour les étudiants du diplôme M1 IGD - Interaction, Graphic and Design

    Le rattrapage est autorisé (Note de rattrapage conservée)
      L'UE est acquise si note finale transposée >= C
      • Crédits ECTS acquis : 5 ECTS

      Pour les étudiants du diplôme Artificial Intelligence and Advanced Visual Computing

      Le rattrapage est autorisé (Note de rattrapage conservée)
        L'UE est acquise si note finale transposée >= C
        • Crédits ECTS acquis : 4 ECTS

        La note obtenue rentre dans le calcul de votre GPA.

        Pour les étudiants du diplôme M1 MPRI - Foudations of Computer Science

        Le rattrapage est autorisé (Note de rattrapage conservée)
          L'UE est acquise si note finale transposée >= C
          • Crédits ECTS acquis : 5 ECTS

          Pour les étudiants du diplôme Diplôme d'ingénieur de l'Ecole polytechnique

          Le rattrapage est autorisé (Note de rattrapage conservée)
            L'UE est acquise si note finale transposée >= C
            • Crédits ECTS acquis : 5 ECTS

            La note obtenue rentre dans le calcul de votre GPA.

            Pour les étudiants du diplôme Echanges PEI

            Le rattrapage est autorisé (Note de rattrapage conservée)
              L'UE est acquise si note finale transposée >= C
              • Crédits ECTS acquis : 5 ECTS

              Programme détaillé

              Ce cours propose une promenade au sein de la Géométrie Algorithmique afin d'en illustrer la richesse sur le plan théorique et applicatif. Nous introduirons un éventail de problèmes et techniques issus du domaine, des plus classiques jusqu'au plus récentes:

              • le calcul d'enveloppes convexes
              • le calcul des triangulations de Delaunay et diagrammes de Voronoi,
              • l'implémentation efficace de requêtes de proximité géométrique (e.g. nearest neighbors)
              • le calcul de dessins de graphes planaires (Tutte barycentric method, force-directed layouts, Schnyder drawing, ...)
              • le calcul des petits séparateurs et leurs applications à la solution de problèmes algorithmiques pour les graphes planaires
              • la reconstruction 3D à partir de nuages de points,
              • l'approximation de problèmes géométriques NP-difficiles (e.g. Euclidean TSP),
              • la localisation efficace de points en grandes dimensions.

              Overview and course organization: Introduction to Computational Geometry (slides)

              Veuillez patienter