L’étude des structures géométriques discrètes fondamentales comme les polyèdres convexes, les diagrammes de Voronoï ou les triangulations de Delaunay est l’un des sujets centraux de la géométrie algorithmique. On établit une correspondance très utile entre diagrammes de Voronoï, triangulations de Delaunay et polyèdres convexes. Le théorème de McMullen qui majore le nombre de faces d’un polyèdre convexe permet alors de borner la complexité combinatoire des diagrammes de Voronoï et des triangulations de Delaunay.
Au-delà de l’analyse des structures géométriques, le but de la géométrie algorithmique est de concevoir des algorithmes permettant de construire ces structures et de les représenter sous la forme de programmes informatiques. Le cours présente un premier algorithme simple qui permet de construire l’enveloppe convexe d’un ensemble fini de points dans un espace de dimension quelconque. Des résultats analogues se déduisent pour les diagrammes de Voronoï et les triangulations de Delaunay et permettent de traiter des questions connexes comme le calcul d’une union de boules ou des diagrammes de Voronoï pour différentes métriques.
