Algorithmes géométriques et géométrie discrète

Vous êtes ici :

Algorithmes géométriques et géométrie discrèteCode de l'UE : HMIN214

Présentation

Le sujet du cours est l’étude algorithmique et combinatoire d’objet géométrique
(principalement du plan). Les chapitres principaux sont :
- calcul de l’enveloppe convexe d’un ensemble de points,
- manipulation de polygones,
- graphes planaires, objets géométriques discrets (droites, cercles...)
- triangulations,
- triangulation de Delaunay et diagramme de Voronoï.
Ces notions seront appliquées/illustrés sur les problèmes suivants :
encodage compact des graphes planaires, localisation dans une carte planaire, reconnaissance
de formes (alpha-shape et alpha-complexe), intersections de polygones (sommes de
Minkowski), visualisation de scène (algorithme du peintre), arbre euclidien minimum, plus
courts chemins dans un polygone, tracé de droites discrètes...

Objectifs

Le sujet du cours est l’étude algorithmique et combinatoire d’objet géométrique
(principalement du plan). Les chapitres principaux sont :
- calcul de l’enveloppe convexe d’un ensemble de points,
- manipulation de polygones,
- graphes planaires, objets géométriques discrets (droites, cercles...)
- triangulations,
- triangulation de Delaunay et diagramme de Voronoï.
Ces notions seront appliquées/illustrés sur les problèmes suivants :
encodage compact des graphes planaires, localisation dans une carte planaire, reconnaissance
de formes (alpha-shape et alpha-complexe), intersections de polygones (sommes de
Minkowski), visualisation de scène (algorithme du peintre), arbre euclidien minimum, plus
courts chemins dans un polygone, tracé de droites discrètes...

Volume horaire

  • CM : 16.5
  • TD : 16.5
  • TP : 16.5
Diplômes intégrant cette UE

En bref

Crédits ECTS 5

Période de l'année
secondSemestre

Langue d'enseignement
fr