Improved Routing on the Delaunay Triangulation

Nicolas Bonichon (1) , Prosenjit Bose (2) , Jean-Lou de Carufel (3) , Vincent Despré (4) , Darryl Hill (2) , Michiel Smid (2)

1 LaBRI - Laboratoire Bordelais de Recherche en Informatique
2 Carleton University
3 uOttawa - Université d'Ottawa [Ontario]
4 GAMBLE - Geometric Algorithms and Models Beyond the Linear and Euclidean realm

A geometric graph G = (P,E) is a set of points in the plane and edges between pairs of points, where the weight of the edge is equal to the Euclidean distance between the points. In k-local routing we find a path through G from a source vertex s to a destination vertex t, using only knowledge of the present location, the locations of s and t, and the k-neighbourhood of the current vertex. We present an algorithm for 1-local routing on the Delaunay triangulation, and show that it finds a path between a source vertex s and a target vertex t that is not longer than 3.56|st|, improving the previous bound of 5.9.

Mots clés: local routing; geometric; graph

Domaines: Géométrie algorithmique [cs.CG]; Mathématique discrète [cs.DM]

Nicolas Bonichon, Prosenjit Bose, Jean-Lou de Carufel, Vincent Despré, Darryl Hill, et al.. Improved Routing on the Delaunay Triangulation. ESA 2018 - 26th Annual European Symposium on Algorithms, Aug 2018, Helsinki, Finland. ⟨10.4230/LIPIcs.ESA.2018.22⟩. ⟨hal-01881280⟩