Competitive online routing in geometric graphs

摘要: We consider online routing algorithms for finding paths between the vertices of plane graphs. Although it has been shown in Bose et al. (Internat. J. Comput. Geom. 12(4) (2002) 283) that there exists no competitive scheme works on all triangulations, we show a simple O(1)-memory c-competitive strategy approximates shortest path triangulations possessing diamond property, i.e., total distance travelled by algorithm to route message two is at most constant c times path. Our results imply certain classical such as Delaunay, greedy, or minimum-weight triangulation, since they possess property. then generalize our graphs both property and good convex polygon