Midpoint Routing Algorithms for Delaunay Triangulations

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.