文章基本信息

标题：Improved Routing on the Delaunay Triangulation
本地全文：下载
作者：Nicolas Bonichon ; Prosenjit Bose ; Jean-Lou De Carufel 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2018
卷号：112
页码：1-13
DOI：10.4230/LIPIcs.ESA.2018.22
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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|.
关键词：Delaunay; local routing; geometric; graph