moteur de recherche

Séminaire Algo - Vincent Despré
Séminaire Algo - Vincent Despré
21-mars-2017 14:30
Il y a: 34 days





Vincent Despré

Un algorithme de routage pour les triangulations de Delaunay

Salle de séminaire (4B05R) - Bâtiment Copernic

La triangulation de Delaunay d'un nuage de points du plan est l'unique triangulation telle qu'aucun point n'est à l'intérieur du cercle circonscrit de l'un des triangles. Un algorithme de routage est un algorithme qui calcule un chemin entre deux points de la triangulation en n'utilisant que des informations locales. L'étirement d'un algorithme de routage est le rapport entre la longueur du chemin calculé et la longueur euclidienne entre les extrémités du chemin. Nous proposons un algorithme très simple dont l'étirement est inférieur à 4.08 améliorant l'ancienne borne de 5.90.








<- retour: