Ellipse and Arc Routing Algorithms for Delaunay Triangulations

Oblivious Online Routing (OOR) algorithms are suitable when applications only have local information available to make routing decisions. This paper presents two new OOR algorithms for Delaunay triangulations: the Ellipse Routing algorithm and the Arc Routing algorithm. Both of their names come from the shapes of their searching areas for the next-hop neighbor. This paper also evaluates and compares the presented algorithms with three existing OOR algorithms in terms of link distances and Euclidean distances.