Date/heure
10 janvier 2023
16:30 - 17:30
Lieu
Salle de conférences Nancy
Oratrice ou orateur
Olivier Devillers (LORIA)
Catégorie d'évènement Colloquium
Résumé
La géométrie algorithmique classique étudie la complexité des problèmes dans le cas
le pire. Il en résulte souvent des choses assez compliquées pour être capable de couvrir
des cas peu réalistes voire franchement pathologiques. Nos amis probabilistes étudient
parfois ces complexités pour des distributions de points de données qui elles aussi peuvent
s’avérer peu réalistes.
Je parlerai de trois résultats:
– L’analyse lissée permet de faire une interpolation entre l’aléatoire et le cas le pire en
étudiant des objets perturbés de manière aléatoire. On s’intéressera à la taille de l’enveloppe
convexe de points dans ce modèle.
– Il existe de nombreuses stratégies pour marcher de sommet en sommet en suivant
les arêtes de la triangulation de Delaunay. On donnera quelques analyses de la longueur de
différents chemins.
– La triangulation de Delaunay 3D a une taille entre linéaire et quadratique. On regardera le
cas où les points sont distribués sur une surface.
Pour tous ces problèmes il reste pas mal de questions ouvertes.