2018-08-01
Improved routing on the delaunay triangulation
Publication
Publication
Presented at the
26th European Symposium on Algorithms, ESA 2018 (August 2018), Helsinki
A geometric graph G = (P,E) is a set of points in the plane and edges between pairs of points, where the weight of an edge is equal to the Euclidean distance between its two endpoints. In local routing we find a path through G from a source vertex s to a destination vertex t, using only knowledge of the current vertex, its incident edges, and the locations of s and t. We present an algorithm for 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|st|.
| Additional Metadata | |
|---|---|
| Keywords | Delaunay, Geometric, Graph, Local routing |
| Persistent URL | dx.doi.org/10.4230/LIPIcs.ESA.2018.22 |
| Conference | 26th European Symposium on Algorithms, ESA 2018 |
| Citation |
Bonichon, N. (Nicolas), Bose, P, De Carufel, J.-L. (Jean-Lou), Despré, V. (Vincent), Hill, D. (Darryl), & Smid, M. (2018). Improved routing on the delaunay triangulation. In Leibniz International Proceedings in Informatics, LIPIcs. doi:10.4230/LIPIcs.ESA.2018.22
|