Comment construire un réseau routier qui relie efficacement les villes d’un pays sans construire de ponts ?


Dans cet exposé interactif, nous nous intéressons à des problèmes de construction de graphes couvrants géométriques. Après une présentation des triangulations de Delaunay, les participants seront invités à construire à la main un autre graphe couvrant rivalisant avec les fameuses triangulations de Delaunay.


Notions présentées :

Triangulations de Delaunay, étirement d’un graphe, algorithme distribué.