Bonjour à tous,

Le prochain séminaire Graphes@Lyon aura lieu ce vendredi 9 juin. Nous aurons le plaisir d’écouter Vincent Despré (LIP) en salle C5 du Nautibus, à 10h.
L’exposé est ouvert à tous !

Titre: A Routing Algorithm for Delaunay Triangulations.

Résumé: Delaunay Triangulations are graphs defined on sets of points in the plane. They are very classical since their construction is natural and they have strong geometric properties. One of the more classical study about those triangulations is the calculation of the worst possible stretch for a pair of points . The stretch of a pair is defined by the worst length of a shortest path between those points divided by the Euclidian distance between them. Computing this shortest path is generally considered as efficient but it is not the case for very big triangulations. It becomes interesting to only consider local information at each step while routing from one vertex to the other. Our work consists in designing an algorithm with this restriction that outputs a path with a reasonable stretch.

En espérant vous voir nombreux,

Aline