# Constrained Theta-10 Routing Between Visible Vertices

by Jonathan Rodriguez

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

JRodriguezSummer-Scholars-PosterImagine
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*.

As a humanities nerd, I appreciate your effort to make this project understandable even to me. I look forward to when I can look at memes more efficiently because your work makes the internet faster 🙂

Thanks for the comment, Ethan! Nothing would make me happier than facilitating your meme-viewing. 🙂