Abstract. We consider online routing algorithms for routing between the vertices of embedded planar straight line graphs. Our results include (1) two deterministic memoryless routing algorithms, one that works for all Delaunay triangulations and the other that works for all regular triangulations, (2) a randomized memoryless algorithm that works for all triangulations, (3) an O(1) memory algorithm that works for all convex subdivisions, (4) an O(1) memory algorithm that approximates the shortest path in Delaunay triangulations, and (5) theoretical and experimental results on the competitiveness of these algorithms. Key words. Routing, Online algorithms, Delaunay triangulations, shortest path, spanning path 1. Introduction. Path finding, or routing, is central to a number of fields including geographic information systems, urban planning, robotics, and communication networks. In many cases, knowledge about the environment in which routing takes place is not available beforehand, and the vehicle/robot/packet must learn this information through exploration. Algorithms for routing in these types of environments are referred to as online [3] routing algorithms. In this paper we consider online routing in the following abstract setting: The environment is a planar straight line graph [17] , T , with n vertices, whose edges are weighted by the Euclidean distance between their endpoints, the source v src and destination v dst are vertices of T , and a packet can only move on edges of T . Initially, a packet only knows v src , v dst , and N (v src ), where N (v ) denotes the set of vertices adjacent to v. We classify online routing algorithms based on their use of memory and/or randomization. Define v cur as the vertex at which the packet is currently stored. A routing algorithm is called memoryless if the next step taken by a packet depends only on v cur , v dst , and N (v cur ). An algorithm is randomized if the next step taken by a packet is chosen randomly from N (v cur ). A randomized algorithm is memoryless if the distribution used to choose from N (v cur ) is a function only of v cur , v dst , and N (v cur ). The justification for studying the memory requirements of routing algorithms comes from communication networks, in which memory used by an algorithm results in header information that travels with a packet. Since this information is only used for routing purposes and is of no use to the sender or receiver, it effectively produces a decrease in communication bandwidth. For an algorithm A we say that a graph defeats A if there is a source/destination pair such that a packet never reaches the destination when beginning at the source. If A finds a path P from v src to v dst we call P the A path from v src to v dst . Here we use the term path in an intuitive sense rather than a strict graph theoretic sense, since P may visit the same vertex more than once. In this paper we also consider, as a special case, a class of "well-behaved" triangulations. The Voronoi diagram [16] of S is a partitioning of space into cells such that all points within a Voronoi cell are closer to the same element p ∈ S than any other point in S. The Delaunay triangulation is the straight-line face dual of the
As an exception, it was shown that on Delaunay triangulations there is an algorithm which is competitive compared with the shortest path between the source and the destination REF .
Online Routing in Triangulations
in Proc. of the 10 th Annual Int. Symp. on Algorithms and Computation ISAAC
Computer Science Mathematics