Constrained Theta-10 Routing Between Visible Vertices

by Jonathan Rodriguez

Mentor: Diane Souvaine, Computer Science; funding source: NSF TRIPODS

Imagine a network of devices communicating wirelessly. These devices can be part of a massive network, and this network could change regularly, so if we want to send a message in the network, it would not be viable for each device to know the whole network. Thus, in order to send a message, we need a way to efficiently route in a network that is unknown to each device. One way to construct a graph locally is by using a Theta-m graph. For some number m, a Theta-m graph is formed by radially splitting the plane into m cones at each vertex and tracing an edge to the closest vertex in each cone. If we do this for every vertex, we get a full graph, but most importantly we can quickly and easily find the edges at each vertex. However, this graph alone isn’t enough to simulate real-life routing. We might have to worry about real-world obstacles, such as mountains or buildings, through which it is impossible to send a message. For these cases, we model the obstacles as constraints, which are just edges that are not allowed to be crossed by other edges. With this we can now formalize my research problem.

              The goal of my project is to develop an algorithm for routing in the constrained Theta-10 graph. That is, given a set of vertices and constraints, we want to use the Theta-10 graph to route from a source vertex s to a target vertex t, without crossing any constraints. The constrained Theta-6 graph has been studied previously and there exists an efficient algorithm for routing in it. However, the properties that led to this algorithm are unique to Theta-6; it is not generalizable to other Theta-graphs. Having more cones better approximates the visibility graph, in which all edges that do not cross constraints are drawn, and a better approximation of the visibility graph could lead to better approximations of the shortest path in the visibility graph, which implies faster delivery of messages. This is why it is worthwhile to find a routing algorithm for the Theta-10 graph.

              The key to our algorithm is to define what we call a witness line. This witness line starts off as the line segment st and gets modified after each step of the algorithm, becoming more like a chain of line segments ending at t. The point of the witness line is to restrict our search at each cone and keep the distance traveled from extending infinitely. The witness line has limited crossings by constraints, so if we “hug” the line by staying as close as we can to it, we can route around any constraints that could prove to be problematic. Another use of the witness line is to show that the algorithm does, in fact, terminate. If we show that after each step the witness line shrinks, we can prove that the algorithm will lead us to t every time.

              Although we have an algorithm that we believe works, we have not yet proven that it is efficient, or even that it is guaranteed to reach the target. This is the subject of ongoing investigation. Once we prove that it always works, we want to show that the distance of the path that we take in the algorithm is not more than a constant factor of the distance between s and t. Then of course, we don’t want to stop with the Theta-10 graph. We believe that the algorithm would work just as well with Theta-14, Theta-18, and in general any Theta-(4k+2) graph, since the properties we use are found in all these graphs. We want to generalize the algorithm with the hope of achieving an even tighter bound on the ratio between the distance we would have to travel and the direct distance between s and t.