Midpoint routing algorithms for Delaunay triangulations

摘要

Memoryless online routing (MOR) algorithms are important for the applications with only local information available to make routing decisions. This paper gives two new MOR algorithms for a class of geometric graphs called Delaunay triangulations (DTs): the Midpoint Routing algorithm and the Compass Midpoint algorithm. More meaningfully, the former is generalized into a set of MOR algorithms that use the Euclidean distance as the reference and work for DTs, and the latter is generalized into a set of MOR algorithms that use the direction as the reference and work for DTs. Many other existing MOR algorithms can also be covered by these two sets. Finally, the two new algorithms are e valuated and compared with other existing MOR algorithms, and the experimental results give new findings on the performances of these algorithms in average and general cases.