Local Routing in Spanners Based on WSPD's
Frédérik Paradis

Let $S \subseteq \mathbb{R}^d$ be a set of points. From this point set, we construct a graph such that the path between any pair of points $p, q \in S$ has a length of at most $t|pq|$, where $|pq|$ is the Euclidean distance between $p$ and $q$ and $t$ is a constant called the stretch factor. Such graphs are called $t$-spanners (or just spanners, for short). One interesting topic about spanners is how to do routing in them. Since we have the knowledge of the existence of paths with certain lengths, a routing algorithm on spanners should guarantee some length for the found paths. The general goal should be to approach the bound on the length given by $t|pq|$. A specialization of routing would be local routing in which the routing is done using only local information from each point in the path.

It is possible to construct a $t$-spanner for $S$ with a well-separated pair decomposition of $S$. A well-separated pair decomposition (WSPD) of $S$ is an approximation of the $O(n^2)$ pairs of points of $S$. There are many ways to construct a WSPD. In this paper we assume that the WSPD is constructed using a split tree. A split tree is a data structure that represents the idea of recursively splitting in two the bounding box of our point set.

In this paper, we present a local-routing algorithm for spanners constructed using WSPD’s. We prove the correctness of the algorithm and find its routing ratio.