Improved Routing Ratio for the $L^2$ Delaunay Triangulation
Darryl Hill

The $k$-neighbourhood of a vertex in a graph refers to the neighbours within $k$ hops from that vertex. Online routing algorithms navigate a graph using only information about the $k$-neighbourhood of the current position, as well as limited information in the header. An algorithm has a routing ratio of $c$ if the path it finds between any two vertices $s$ and $t$ is at most $c$ times the Euclidean distance between them.

Seminal work by Chew provided an online routing algorithm for the Delaunay triangulation in the $L^1$ and $L^\infty$ metrics. This algorithm achieved a routing and spanning ratio of approximately 3.16 on the above graphs using knowledge of the start and target vertex and the 1-neighbourhood of the current position. Recently Bonichon et al. cleverly generalized Chew's routing algorithm, applying it to the $L^2$ Delaunay triangulation. They achieved a routing ratio of 5.9, which is the best known routing ratio on the $L^2$ Delaunay triangulation.

We present a new online routing algorithm for the $L^2$ Delaunay triangulation that improves the routing ratio to less than 4.13. It uses knowledge of the position of the start and target vertices as well as knowledge of the 1-neighbourhood of the current position.