This paper introduces compass routing on geometric networks, a local routing algorithm that uses the direction of edges to determine the next step in a path from a starting point to a destination. The algorithm works by selecting the edge with the closest slope to the line connecting the current vertex to the destination. It is designed for geometric graphs, where vertices represent street intersections and edges represent streets. The algorithm is local, meaning it only uses information about the current vertex and a small amount of stored data, without needing full knowledge of the network topology.
The paper studies compass routing on planar geometric networks, which are networks that can be drawn on a plane without edges crossing. It shows that Delaunay triangulations of point sets on the plane support compass routing. It also presents a geometric local routing algorithm that always finds a path between any two vertices of a connected geometric graph. The paper also investigates which planar graphs can be embedded in a way that compass routing produces the shortest path between any pair of vertices. It proves that trees always have such embeddings, but not all outerplanar graphs or planar graphs do.
The paper also discusses the limitations of compass routing. It shows that compass routing may not always find a path from one vertex to another, even in 3-connected geometric graphs with convex polygonal faces. The paper provides an example of such a graph and explains why compass routing fails in this case. It also notes that compass routing has been studied in the context of wireless communication networks, where the goal is to ensure that information reaches its destination, not necessarily to find the shortest path.This paper introduces compass routing on geometric networks, a local routing algorithm that uses the direction of edges to determine the next step in a path from a starting point to a destination. The algorithm works by selecting the edge with the closest slope to the line connecting the current vertex to the destination. It is designed for geometric graphs, where vertices represent street intersections and edges represent streets. The algorithm is local, meaning it only uses information about the current vertex and a small amount of stored data, without needing full knowledge of the network topology.
The paper studies compass routing on planar geometric networks, which are networks that can be drawn on a plane without edges crossing. It shows that Delaunay triangulations of point sets on the plane support compass routing. It also presents a geometric local routing algorithm that always finds a path between any two vertices of a connected geometric graph. The paper also investigates which planar graphs can be embedded in a way that compass routing produces the shortest path between any pair of vertices. It proves that trees always have such embeddings, but not all outerplanar graphs or planar graphs do.
The paper also discusses the limitations of compass routing. It shows that compass routing may not always find a path from one vertex to another, even in 3-connected geometric graphs with convex polygonal faces. The paper provides an example of such a graph and explains why compass routing fails in this case. It also notes that compass routing has been studied in the context of wireless communication networks, where the goal is to ensure that information reaches its destination, not necessarily to find the shortest path.