Compass Routing on Geometric Networks
Evangelos Kranakis Harvinder Singh Jorge Urrutia
In the Proceedings of 11th Canadian Conference on Computational Geometry 1999, Vancouver, Canada.
Reviewed by: Rachna Vargiya
Compass routing on geometric network in its most elemental form yields an algorithm which states that suppose we want to travel from an initial vertex s to a destination vertex t, and that all the information available to us at any point in time is the coordinates of our destination, our current position and the directions of the edges incident with the vertex we are located at. Starting at s, we will in a recursive way choose and traverse the edge of our geometric graph incident to our current position with the closest slope to that of the line segment connecting the vertex we are standing at to t. Ties are broken randomly.
This paper studies local routing algorithms on geometric networks. A routing algorithm is called a local algorithm if it satisfies the following conditions:
- At each point in time, we know the coordinates of our starting position, as well as those of our destination.
- Upon arrival to a vertex v (starting at s), we can use local information stored in v regarding its neighbors, and the edges connecting v to them.
- We are not allowed to change the local information stored at v.
The last condition is because the authors don’t want to leave markers, or garbage at the vertices that have already been visited while trying to reach the destination. This makes the algorithm particularly desirable as it doesn’t leave garbage and is ecologically sound, thus not requiring extra memory at the nodes on the way. The assumption on having geometric network is necessary.
Other compact routing algorithms such as interval routing, Boolean routing at each node of a network a copy of distributed algorithm is stored. Such schemes however can be worst-case storage intensive in the sense that large amounts of information may be required to store per node in order to achieve all-pair shortest path routing. Also, a more serious drawback is that the topology of the network for which these algorithms have been developed are assumed to be of a specific type.
It is not true however that compass routing will always find a path from any starting point in a geometric graph to any other. A geometric graph G supports compass routing if for every pair of its vertices s and t, compass routing (starting at s) produces a path from s to t. The Delaunay triangulation D(Pn) of a set of n points Pn on the plane, is the partitioning of the convex hull of Pn ubti a set if triangles with disjoint interiors such that, the vertices of these triangles points in Pn and for each triangle in the triangulation the circle passing through its vertices contains no other point on Pn in its interior. The algorithm presented is based on the following theorem.
“Let Pn be a set of n points on the plane, then D(Pn) supports compass routing.”
In order to modify the algorithm so that it would work for arbitrary geometric models as well, the next theorem is used.
“There exist a local information routing algorithm on geometric graphs that guarantees that destination is reached. Also, a linear number of edges are traversed.”
The problem of deciding which planar graphs admit geometric embeddings for which compass routing produces the shortest path between any pair of vertices is interesting. The biggest advantage of their approach is that they develop routing algorithm that can be applied to existing communication networks whose only restriction is that they are planar. One disadvantage of the approach is that to keep in memory the coordinates storage is an issue.