Keywords

1 Introduction

The Well-Separated Pair Decomposition (WSPD) of a set P of n points in \(\mathbf {R}^d\) is a versatile structure that has found many applications [12]. Among these applications is the ability to construct a \((1+\varepsilon )\)-spanner for any \(\varepsilon > 0\). A t-spanner in this context is a weighted graph whose vertex set is P, whose edges are weighted by the Euclidean distance between their endpoints and between every pair of points \(x, y \in P\), there exists a path in the graph whose weight is at most t times the length of the segment xy. This path is often referred to as a spanner path. Typically, a t-spanner has a linear number of edges and serves as an approximation of the complete graph.

A t-spanner guarantees the existence of a short path between any pair of vertices, but in most applications, the mere existence of a short path is not sufficient. One requires that the path actually be computed. There exist many algorithms to compute shortest paths in weighted graphs, such as Dijkstra’s algorithm [14]. However, Dijkstra’s algorithm requires full knowledge of the graph, in the sense that the routing algorithm needs to know the vertex set and edge set of the graph.

The problem offers different challenges in the online setting, where the routing algorithm has no knowledge of the graph at the outset. As such, the algorithm starts with the knowledge of the source and destination vertices and explores the graph while trying to reach the destination. A route or path is constructed incrementally. After each step, the algorithm acquires the information stored at each vertex, called the routing table. The routing table can store the neighbourhood of the vertex, and some additional bits of information.

If the only information that the algorithm uses to make its forwarding decision is the information stored at the current vertex and knowledge of the destination vertex, then the algorithm is called local. In addition, if the algorithm has no memory and each step is a local decision, then the algorithm is called memoryless. If no routing table is stored at a vertex, then an online local memoryless routing algorithm cannot identify a short path in general or any path for that matter [7]. An adversary can fool such an algorithm to cycle and never reach its destination. As such, the goal is to store as little information as possible in the routing tables to be able to compute a short path.

The ratio of the length of the path found by a routing algorithm and the Euclidean distance between the source and destination vertex is called the routing ratio. Note that the routing ratio is an upper bound on the spanning ratio. In the literature, online local memoryless (or O(1)-memory) routing algorithms have been designed for various families of geometric spanners such as \(\varTheta \)-graphs [13, 19], Yao-graphs [22, 25], or Delaunay Graphs [5, 6, 8, 10].

In this article, we focus on the design of an online local memoryless routing algorithm on a spanner obtained from a WSPD of a point set P of n points in \(\mathbf {R}^d\). Given a WSPD of P, one can construct many different \((1+\varepsilon )\)-spanners since there is some flexibility in the structure. Therefore, we present a specific construction of a \((1+\varepsilon )\)-spanner from a WSPD, which we call a Heavy-Path WSPD-spanner. We show that a Heavy-Path WSPD-spanner has spanning ratio \(1+2/s+2/(s-1)\) and \(O(s^dn)\) size, where \(s>2\) is the separation ratio. The larger the value of s, the closer \(\varepsilon \) is to zero. Our spanner also has the property that spanner paths have at most \(2\lg {n}+1\) edges.

Our main contribution is a memoryless local routing algorithm for heavy-path WSPD-spanners. The routing ratio is at most \(1+4/s+1/(s-1)\) and at least \(1+4/s\) which is close to the spanning ratio. Moreover, the number of edges on the path is also bounded by \(2\lg {n}+1\). Each vertex v of the graph stores \(O(\deg (v)\log {n})\) bits of information to aid the routing algorithm, where \(\deg (v)\) is the degree of v. This implies a total of \(O(s^dn\log n)\) bits in total.

Our result is a four-fold improvement on previous work in this area [4, 9, 11]. Our routing algorithm works on d-dimensional point sets whereas all previous results are focused on 2 dimensions. Our algorithm uses fewer bits in total for the routing tables. Our routing algorithm has the lowest routing ratio. Finally, our routing algorithm returns a spanner path that uses at most \(2\lg n +1\) edges. We also feel that our algorithm is simpler than the previous algorithms, however, it is difficult to quantify simplicity. See Table 1 for a comparison. A full and detailed description of these results appears in Tuttle’s masters thesis [24].

Table 1. Routing algorithms for WSPD spanners. B is the number of bits needed to store a bounding box, \(\varDelta \) is the ratio of the largest distance between two points to the smallest, and s is the separation ratio. An algorithm is k-local if it uses information about vertices at most k hops away to make routing decisions.
Full size table

Now, we will describe the data structures that are needed to construct the heavy path WSPD spanner. In particular we will define compressed quadtrees, which are used to construct a WSPD, and WSPDs themselves.

1.1 Compressed Quadtrees

A quadtree is a tree data structure for storing spatial data. Let S be a set of n points in \(\mathbf {R}^d\). If \(n = 1\), then the quadtree for S is a single node that stores the lone point of S. If \(n > 1\), to construct a quadtree for S we need a hypercube that contains S. Let C be a hypercube that contains S. We can assume that this is given to us, but if not it is simple to construct such a hypercube in time O(dn).

Subdivide C into \(2^d\) smaller hypercubes \(C_i, \dots C_{2^d}\) by bisecting it along each dimension. For each nonempty \(C_i\), recursively construct a quadtree on the points in \(C_i\). The root of the quadtree stores the hypercube C. Each of the recursively constructed quadtrees is a child of the root.

In a (uncompressed) quadtree, each node a is associated with a hypercube C(a) that contains all the points in the subtree of a. If a is at level i in the tree, then the side length of C(a) is \(2^{-i}L\), where L is the side length of hypercube associated to the root.

A quadtree is a tree with n leaves. Each internal node has at least one child, and at most \(2^d\) children. The fact that a node can have only a single child means the height of the tree can be unbounded. We can fix this in the following way. If a quadtree has a long chain of internal nodes with only one child, then compress them all into a single edge. The resulting structure is called a compressed quadtree, and the height is now linear with respect to the number of points in the worst case.

In a compressed quadtree, a node no longer corresponds to just one hypercube. Instead, each node a corresponds to two hypercubes. A node in a compressed quadtree might correspond to an entire path in the uncompressed quadtree. We store the hypercube \(C_L(a)\) that corresponds to the shallowest node on that path, and the hypercube \(C_S(a)\) that corresponds to the deepest node on that path. If p(a) denotes the parent of a, then \(C_L(a)\) is obtained by splitting \(C_S(p(a))\) along each dimension. Let S(a) denote the set of points stored in the leaves of the subtree rooted at a. For any compressed quadtree node, we have \(S(a) \subset C_S(a) \subseteq C_L(a)\). The two hypercubes \(C_S(a)\) and \(C_L(a)\) can be equal if the node a does not correspond to a compressed chain of nodes in the quadtree.

Theorem 1

([1, Section 19.2.5]). Let S be a set of n points in \(\mathbf {R}^d\). A compressed quadtree for S can be constructed in \(O(dn \log n)\) time.

See [1] for a tof different quadtree variants. For our application, we will need the following property of compressed quadtrees.

Lemma 1

Let T be a compressed quadtree, and let a be a non-root node of T. The node a corresponds to two hypercubes, \(C_L(a)\) and \(C_S(a)\). Let \(\ell (a)\) be the diagonal length of \(C_S(a)\). Note that this is an upper bound on the diameter of the points stored in the subtree of a. We have \(\ell (a) \le (1/2)\ell (p(a))\), where p(a) is the parent of a in T.

1.2 The Well-Separated Pair Decomposition

Let S and \(S'\) be two point sets in \(\mathbf {R}^d\). We say that S and \(S'\) are well-separated with respect to \(s > 2\) if \(d(S, S') \ge s \cdot \max \{\mathrm {diam}S, \mathrm {diam}S'\}\), where and \(\mathrm {diam}S\) is the diameter of S, the maximum distance between two points in S. The number s is called the separation ratio.

The following lemma [12] about well-separated pairs will make precise the idea that distances in one set are small compared to distances between sets.

Lemma 2

Let S and \(S'\) be well-separated point sets with respect to \(s > 2\). Then for any points \(p, p' \in S\) and \(q, q' \in S'\): , and .

A well-separated pair decomposition (WSPD) of S is a sequence \(\{A_1, B_1\},\) \(\dots , \{A_m, B_m\}\) of pairs of subsets of S such that (a) \(A_i \cap B_i = \varnothing \) for all i (b) for each pair p, q of points in S there is exactly one i such that \(p \in A_i\) and \(q \in B_i\) (or \(p \in B_i\) and \(q \in A_i\)) (c) \(A_i\) and \(B_i\) are s-well separated for all i.

Given a compressed quadtree T, we can construct a WSPD with a recursive algorithm [16, Section 3.1.1]. The following theorem summarizes the construction.

Theorem 2

([16, Theorem 3.10]). Given a set S of n points in \(\mathbf {R}^d\), a WSPD with separation ratio \(s > 2\) with \(O(s^dn)\) pairs can be constructed using a compressed quadtree in time \(O(d(n \log n + s^dn))\).

The WSPD that results from this algorithm has an important property that we will need in Sect. 2.1, so we will state it now.

Lemma 3

Let T be a compressed quadtree for some point set P, and let W be a WSPD computed using T. Every pair in W has the form \(\{S(a), S(b)\}\) for some nodes a, b of T. Let p, q be any two points of P and let \(\{S(a), S(b)\}\) be the pair that separates them. If c is a node that stores both p and q in its subtree, then a and b are both descendants of c.

In the construction of a WSPD, we used compressed quadtrees. There are alternative tree structures that have been used instead. For example, the fair split tree of Callahan and Kosaraju [12]. The reason compressed quadtrees are used is so that we can use Lemma 1. The diameter of the hypercube representing a compressed quadtree node is a constant fraction of the diameter of its parent. In a fair split tree this fraction depends on the dimension of the point set since a split is only done along one dimension, instead of along all dimensions simultaneously. This property of compressed quadtrees will be used in the analysis of the routing algorithm.

2 The Heavy Path WSPD Spanner

We now describe the heavy path decomposition of a tree. Let T be a rooted tree. If a is a node of T, then the size of a is the number of leaves in the subtree rooted at a. It is worth noting here that a node a is considered to be an ancestor and a descendant of itself. For each internal node a, choose one child of maximal size (breaking ties arbitrarily), and mark the edge from a to that child as heavy. The other edges are marked light. If b is a child of a and the edge from a to b is heavy, then we call b the heavy child of a. Otherwise b is a light child of a. What results is a decomposition of the tree into heavy paths, one for each leaf node. The heavy path decomposition of a tree with n leaves can be computed in O(n) time [23].

For an internal node a, let r(a) be the leaf node defined by following the unique heavy path down the tree starting from a. This leaf is called the representative of a. Let h(a) be the node defined by following the heavy path up the tree, again starting from a, until the edge to the parent is no longer heavy.

Lemma 4

([23, Lemma 1]). The number of light edges on any root-to-leaf path in a heavy path decomposition of a compressed quadtree is at most \(\lg n\), where n is the number of leaves in the compressed quadtree.

Lemma 5

Let T be a tree, and let a be an internal node of T. Compute a heavy path decomposition of T. Let r(a) be the representative of a. Then for every node b on the path from h(a) to r(a), we have \(r(b) = r(a)\).

2.1 Constructing a Heavy Path WSPD Spanner

Constructing a spanner graph given a WSPD is simple. For each pair in the WSPD, choose an arbitrary point from each set and add an edge between those two points. The result is a t-spanner for \(t = (s+4)/(s-4)\), where \(s > 4\) is the separation ratio of the WSPD [21]. Since we can choose these points in any manner, we are free to decide on a scheme that benefits our application. In this article, we will choose the points using a method based on the heavy path decomposition. The spanner that we construct will be called a heavy path WSPD spanner. This construction originally appeared in Arya et al. [2, 3] for the fair split tree. Here we present it for WSPDs built from a compressed quadtree.

Let T be the compressed quadtree used to compute the WSPD. Compute a heavy path decomposition of T. For each pair \(\{A, B\}\) in the WSPD, there is a corresponding pair \(\{a, b\}\) of nodes in T. The edge that we add to the graph will be between the points r(a) and r(b).

Now we will prove that this graph is a \((1 + 2/s + 2/(s-1))\)-spanner. To construct a path between two points p and q, consider Algorithm 1.1. Let \(\{S(a), S(b)\}\) be the WSPD pair that separates p from q. The algorithm adds an edge between r(a) and r(b), and recursively constructs a path from p to r(a) and from r(b) to q.

figure a

To analyze the spanning ratio, we will first consider a special case, where q is the representative of a node storing p. In other words, h(q) is an ancestor of h(p). In this case, in every call made to BuildPath that does not immediately return, at least one of the two recursive calls will be to the base case.

Lemma 6

Let S be a set of points in \(\mathbf {R}^d\), and let T be a compressed quadtree for the points of S. Construct a heavy path WSPD spanner for S. Let p and q be points stored in the leaves of T such that q is the representative of some node containing p. In a call to BuildPath(p, q), at most one edge is added at each level of recursion.

Consider an initial call to BuildPath(p, q), where q is not necessarily the representative of an ancestor of p. Two recursive calls are made, to BuildPath(p, r(a)) and BuildPath(r(b), q). Both of these calls satisfy the conditions for Lemma 6.

We can also bound the length of the edges being added to the path, as a function of the recursion depth.

Lemma 7

Let S be a set of points in \(\mathbf {R}^d\), and let T be a compressed quadtree for the points of S. Construct a heavy path WSPD spanner for S. Let p and q be points of S. Consider the series of recursive calls made during a call to BuildPath(p, q). If the level of recursion of some call is k, the length of the edge added during that call is at most .

Using these two lemmas, we can bound the spanning ratio of the path between p and q. Note that this implies the graph is connected.

Theorem 3

Let S be a set of n points in \(\mathbf {R}^d\). The heavy path WSPD spanner G for S has a spanning ratio of at most \(1 + 2/s + 2/(s - 1)\).

Proof

Let p and q be points of S. Algorithm 1.1 constructs a path from p to q. The edge added from r(a) to r(b) has length at most by Lemma 2. The length of the path from p to r(a) can be bounded using Lemma 6 and Lemma 7. There is at most one edge being added at each level of recursion, and the length of the edge being added at level k is at most . Let M be the maximum recursion depth. Therefore, the length of the path from p to r(a) is at most

The length of the path from r(b) to q can be bounded in the same way. Therefore the total length of the path is at most

In addition to bounding the length of the path, we can bound the number of edges on the path from p to q, using Lemma 4. This is because every edge on the spanner path “traverses” at least one light edge. The diameter of a spanner is the maximum number of edges over all the shortest paths between any pair of points in the spanner.

Lemma 8

For two points p and q in a heavy path WSPD spanner, the number of edges on the path from p to q found by BuildPath(p, q) is at most \(2\lg n + 1\). In other words, the heavy path WSPD spanner is a \((2\lg n + 1)\)-hop spanner.

Proof

Let \(\{S(a), S(b)\}\) be the WSPD pair that separates p from q. Consider the subpath \(p = p_1, p_2, \dots , p_k = r(a)\). For each edge \(p_ip_{i+1}\), we know that \(p_i\) is contained in the subtree of \(h(p_{i+1})\), where \(h(p_{i+1})\) is the shallowest node in the compressed quadtree that \(p_{i+1}\) is the representative of.

The sequence of nodes \(h(p_1), h(p_2), \dots , h(p_k)\) must then all lie on the same root-to-leaf path (that is, the path from p to the root). Since all of these nodes have different representatives, by Lemma 4 there can be at most \(\lg n\) of them.

The same is true for the subpath between r(b) and q, and then adding the edge between r(a) and r(b) gives an upper bound of \(2\lg n + 1\) edges on the spanner path.

We end this section with a theorem that summarizes the entire construction of a heavy path WSPD spanner and all its properties. Note that the BuildPath algorithm that finds a path between two points in a heavy path WSPD spanner is not a local algorithm since it requires knowing the pair \(\{S(a), S(b)\}\) from p.

Theorem 4

Let S be a set of n points in \(\mathbf {R}^d\), and let \(s > 2\). In \(O(d(n \log n + s^dn))\) time, we can construct a graph G called a heavy path WSPD spanner with the following properties:

  • The number of edges in G is \(O(s^dn)\).

  • G is a \((1 + 2/s + 2/(s - 1))\)-spanner.

  • G is a \((2\lg n + 1)\)-hop spanner.

Additionally, between any two points there is a single path (found by algorithm BuildPath) that achieves both the spanning and hop-spanning ratio.

3 Local Routing in Euclidean Space

In this section, we present a local routing algorithm for heavy path WSPD spanners. Let S be a set of points, T be a compressed quadtree for S, W be a WSPD computed using T, and G be a heavy path WSPD spanner constructed as described in the previous section. We now have all the tools to describe the routing algorithm. First, we will explain what we need to store at each vertex. Then, we can present the routing algorithm and analyze it.

3.1 Routing Tables

First, we describe a labelling scheme for the nodes of T. The vertices of G will store these labels. The message will only use the label of the destination to route. In other words, the algorithm is memoryless.

Each leaf will get a unique label in the range \(1, 2, \dots , n\). Perform a depth-first traversal of T, and label the leaves in the order that they are visited. The label of an internal node will be the set of all the labels in the leaves of that node’s subtree. We call this the DFS labelling scheme. The labelling scheme ensures that this set will be an interval.

Lemma 9

Let T be a tree, and label its leaves using a depth first search. Let a be a node of T. Let I be the set of labels of the leaves in the subtree rooted at a. The labels form a contiguous subset of \(\{1, 2, \dots , n\}\). That is, if i is the minimum label and j is the maximum label in I, then \(I = \{i, i+1, \dots , j-1, j\}\).

Since we only need to store the minimum and maximum labels of each interval, we only need \(2\lg n\) bits to store the label of an internal node.

In a depth-first search, the children of a node can be visited in any order. If we always visit the child with the largest subtree first (i.e., always follow the heavy edge), and then visit the other children in an arbitrary order, then we can save some memory as shown in the following lemma. We call this type of DFS labelling scheme a heavy path DFS labelling scheme.

Lemma 10

Let T be a compressed quadtree and let a be an internal node of T. In a heavy path DFS labelling of T, the label of r(a) is the minimum label of all the points stored in the subtree of a. That is, if the label of a is [x, y], then the label of r(a) is x.

We now describe the information that needs to be stored in the routing table of a vertex u. First, store the label of u. Second, for each neighbour v of u, let \(\{S(a_v), S(b_v)\}\) be the WSPD pair that generated the edge between u and v, where \(v \in S(b_v)\), i.e., v is the leaf in the subtree of \(b_v\) with minimum label. Store the labels (defined by the heavy path DFS labelling of T) of v, \(b_v\), and h(v). Recall that h(v) is the shallowest node in T for which v is a representative. Notice that the label of \(a_v\) is not stored, as it is never used by the routing algorithm.

Lemma 11

The total size of the routing tables is \(O(s^dn\log n)\).

Proof

The label of a point is a single integer in the range \(\{1, \dots , n\}\), and the label of an internal node is two integers in the same range, so in total we need to store \(5\lg n\) bits for each neighbour of u. This can be improved by applying Lemma 10. We know that v is the representative of \(b_v\), since the edge uv was generated by the pair \(\{a_v, b_v\}\). We also know that v is the representative of h(v), by the definition of h(v). So if x is the label of v, then the labels of \(b_v\) and h(v) are of the form [x, y] and [x, z], respectively. Since three of the integers being stored are equal, we actually only need \(3\lg n\) bits.

The total size of the routing table at a vertex u of G is \((3\deg (u) + 1)\lg n\), where \(\deg (u)\) is the number of neighbours of u in G. The total size of the routing tables stored in the entire graph is

$$\begin{aligned} \sum _{u \in P} (3\deg (u) + 1)\lg n = (6m + n)\lg n \end{aligned}$$

where m is the number of edges in the spanner. Since we know \(m = O(s^dn)\), the total size of the routing table is therefore \(O(s^dn\log n)\).

3.2 Routing in a Heavy Path WSPD Spanner

We now present the routing algorithm. Let p be the starting vertex, and let q be the destination vertex. We can assume that the label of the destination q is stored with the message. No other information needs to be stored with the message (that is, the algorithm is memoryless). The algorithm proceeds in two stages: the ascending stage and the descending stage. We first check if we are in the descending stage of the algorithm. If so, perform a descending step. If not, perform an ascending step. We will refer to this algorithm as the heavy path routing algorithm.

  1. 1.

    [Descending step] If u has a neighbour v (with WSPD pair \(\{a_v, b_v\}\)) such that \(q \in b_v\), then forward the message to v.

  2. 2.

    [Ascending step] Otherwise, find the representative of the parent of h(u), and forward the message to that vertex.

The proof that this routing algorithm guarantees delivery is split into two stages. Let \(\{S(a), S(b)\}\) be the WSPD pair separating p from q. First we will prove that the ascending step will be applied until the message reaches r(a). Then, we will prove that the descending step will be applied until the message reaches its destination. That is, the routing algorithm can be split into two “stages”: a series of ascending steps followed by a series of descending steps.

First we need to show that it is possible to implement an ascending step using only the information stored in the vertices of G.

Lemma 12

The representative of the parent of h(u) is a neighbour of u in G, and can be found using only the information in the routing table at u.

Another way of viewing Lemma 12 is that one application of the ascending step will move the message one light edge “up” in the quadtree.

The next two lemmas prove that, from p, the routing algorithm will repeatedly apply an ascending step until r(a) is reached. This part of the algorithm is called the ascending stage.

Lemma 13

Starting from p, repeated application of the ascending step will forward the message to r(a).

Lemma 14

The ascending step is always applied if u is in a, but not equal to r(a).

Once the message reaches r(a), the descending step will be applied until the destination is reached.

Lemma 15

If u is on the path constructed in Algorithm 1.1 and not in S(a), then the descending step is applied and will forward the message to the next point on the spanner path.

Putting the ascending and descending steps together will therefore successfully route a message from p to q.

Theorem 5

The heavy path routing algorithm will successfully route a message in a heavy path WSPD spanner, with information stored in each vertex as outlined in Sect. 3.1.

3.3 Analysis of the Local Routing Algorithm

In this section we will bound the routing ratio of the heavy path routing algorithm. First we will bound the length of the path found in the descending stage, as it is much easier to do.

Lemma 16

Let p and q be points in a heavy path WSPD spanner. The length of the path constructed during the descending stage of the heavy path routing algorithm is at most .

Proof

Lemma 15 implies that the descending stage finds a path from r(a) to q, where r(a) is the representative of the set containing p in the WSPD pair \(\{S(a), S(b)\}\) that separates p from q.

From Theorem 3, we know that the edge r(a)r(b) has length at most , and that the subpath constructed in Algorithm 1.1 from r(b) to q has length at most . Lemma 15 implies that the path from r(a) to q found by the heavy path routing algorithm is the same as the spanner path, so its length is at most \(1 + 2/s + 1/(s - 1)\) times , because that is the length of the spanner path from r(a) to q.

The only thing that remains to be bounded is the length of the path constructed during the ascending stage.

Lemma 17

Let \(p = p_1, p_2, \dots , p_k = r(a)\) be the points visited during the ascending stage. For any point \(p_i\), the points \(p_1\) through \(p_{i-1}\) are all stored in the subtree rooted at \(h(p_i)\).

We can bound the length of the path constructed during the ascending stage using the previous lemma.

Lemma 18

The length of the path constructed during the ascending stage of the algorithm is no more than .

Proof

First, note that if a is the parent of b in the quadtree, then \(\ell (a) \ge (1/2)\ell (b)\), by Lemma 1. The path from p to r(a) is contained in the subtree rooted at a, so the length of every edge on the path is at most \(\ell (a)\). That path, minus the last edge, is contained in the subtree rooted at one of the children of a by Lemma 17, so the length of all but the last edge is at most \((1/2)\ell (a)\).

Repeating this argument will show that the length of the entire path is not more than \(\ell (a) + (1/2)\ell (a) + (1/2)^2\ell (a) + \cdots = 2\ell (a)\). By the condition for checking well-separatedness in the WSPD construction algorithm, . Therefore, the length of the path from p to r(a) is at most .

Theorem 6

The routing ratio of the heavy path routing algorithm is at most \(1 + 4/s + 1/(s - 1)\).

Proof

By Lemma 18, the total length of the path constructed during the ascending stage is no more than . The path constructed during the descending step is equal to the spanner path from r(a) to q, and so we can use the bound on the spanning ratio to bound this part of the path. By Lemma 16 this is at most . Therefore the length of the path from p to q is

Theorem 7

The routing ratio of the heavy path routing algorithm is at least \(1 + 4/s\) in the worst case.

Similar to Lemma 8, we can bound the number of edges on the spanner path. In fact, the proof works almost identically to the proof of Lemma 8.

Lemma 19

Starting at a point p, a message can be forwarded to any other point q after forwarding only \(2\lg n + 1\) times.

Proof

Let \(\{S(a), S(b)\}\) be the WSPD pair that separates p from q. Consider the subpath \(p = p_0, p_1, \dots , p_k = r(a)\) found during the ascending stage. There will be one edge added to this path for each light edge on the path from p to a in the compressed quadtree. By Lemma 4, this is at most \(\lg n\).

Since the path constructed during the descending stage follows the spanner path, Lemma 8 implies that the number of forwards during the descending stage is at most \(\lg n + 1\). Therefore the number of forwards for the entire routing algorithm is at most \(2\lg n + 1\).

The results of this section are summarized in the following theorem.

Theorem 8

Let G be a heavy path WSPD spanner for a set S of points in \(\mathbf {R}^d\), and let p and q be points of S. There exists a local, memoryless routing algorithm that can find a path from p to q, such that:

  • The number of bits stored at each vertex u is \((3\deg (u) + 1)\lg n\)

  • The length of the path found from p to q is at most

  • The number of edges on the path is at most \(2\lg n + 1\)

4 Conclusions

We presented a spanner construction scheme based on the WSPD of a point set P of n points in \(\mathbf {R}^d\) that has spanning ratio \(1+2/s+2/(s-1)\), has spanning paths with at most \(2\lg {n}+1\) edges and \(O(s^dn)\) size, where \(s>2\) is the separation ratio. We call these spanners heavy-path WSPD-spanners. We then presented a memoryless local routing algorithm for heavy-path WSPD-spanners with routing ratio at most \(1+4/s+1/(s-1)\) and at least \(1+4/s\) which is close to the spanning ratio. The number of edges on the spanner path is bounded by \(2\lg {n}+1\) and a total of \(O(s^dn\log n)\) bits are used to store all the routing tables. These are currently the best known bounds for routing algorithms on WSPD-spanners.

The spanner construction and routing algorithm presented in this paper can be modified to work in a more general setting than d-dimensional Euclidean space. Specifically it is possible to show that a variant of the heavy-path WSPD-spanner can be constructed for metric spaces of bounded doubling dimension. Although the compressed quadtree cannot be constructed in this setting, the net tree of Har-Peled and Mendel [17] can be used instead. This construction is also amenable to a memoryless competitive online local routing algorithm, however, the algorithm is more complicated and the doubling dimension factors into all of the bounds for both the construction and routing algorithms. For details of this generalisation, refer to Tuttle [24].

Another avenue to explore is to consider other spanner constructions based on WSPDs to try to improve some of our bounds. The spanner construction that we presented is designed to allow for a fairly simple routing algorithm. Recall that given a WSPD of point set, one can construct many different \((1+\varepsilon )\)-spanners since there is some flexibility in the structure. There are various spanner construction schemes that can produce WSPD-spanners with other desirable properties such as bounded degree or \(o(\log n)\) hop distance. For details on the various constructions of spanners from WSPDs, see Narasimhan and Smid [21]. These different constructions may improve some of our bounds at the cost of a slightly more elaborate and complicated routing scheme.

Finally, WSPDs have been defined for the unit disk graph [15]. Using these WSPDs, local routing in the unit disk graph is possible as was shown by Kaplan et al. [18] and Mulzer & Willert [20]. Our algorithm routes on spanners constructed directly from a WSPD, as such, our result does not immediately transfer to this setting. We leave as an open problem to determine whether our routing scheme can be adapted to this setting and provide a better trade-off.