Midpoint Routing Algorithms for Delaunay Triangulations
Source: University of Sydney
Oblivious Online Routing (OOR) algorithms are important for the applications with only local information available to make routing decisions. This paper gives two new OOR algorithms for a class of geometric graphs called Delaunay Triangulations (DTs): the Midpoint Routing algorithm and the Compass Midpoint algorithm. Moreover, the former is generalized into a set of OOR algorithms that use the Euclidean distance as the reference and work for DTs, and the latter is generalized into a set of OOR algorithms that use the direction as the reference and work for DTs.