Local Routing on Ordered $𝚯$-Graphs

A geometric network $G=(V,E)$ is a weighted graph where each vertex $v\in V$ is a point in the Euclidean plane ${ℝ}^2$ and each edge $(u,v)\in E$ is a straight line segment, connecting $u\in V$ and $v\in V$, weighted by the Euclidean distance $|uv|$. We define the weighted distance ${\delta }_G(u,v)$ between two vertices $u$ and $v$ on $G$ to be the sum of the weights of the edges along the weighted shortest path from $u$ to $v$ in $G$.

A subgraph $H=(V,E^{\prime })$ of a geometric network $G=(V,E)$ is called a $c$-spanner of $G$, if, for every pair of vertices $s,t\in V$, we have ${\delta }_H(s,t)\le c\cdot {\delta }_G(s,t)$, where $c\in {ℝ}_{\ge 1}$. Here, $G$ is called the underlying network of $H$. The smallest constant $c$ such that $H$ is a $c$-spanner of $G$ is called the spanning ratio or stretch factor of $H$. We consider the situation where the underlying network $G$ is the complete Euclidean graph of $V$ – i.e., a $c$-spanner $H$ of $G$ approximates the Euclidean distance $|st|={\delta }_G(s,t)$ between any pair of points $s,t\in V$ by a constant factor $c$. The spanning ratio of a class of spanners $𝒢$ is the spanning ratio of the worst-case instance $G\in 𝒢$ maximizing the spanning ratio. See the textbook by Narasimhan and Smid [15] and the survey by Bose and Smid [9] for a comprehensive overview of spanners and their open problems.

The study of geometric spanners is closely related to the design and analysis of efficient routing algorithms that forward a message between a pair of vertices. Given a source vertex $s$ and a target vertex $t$ on a graph $G$, a routing algorithm aims to find a short path from $s$ to $t$. If the information of the entire graph can be known and kept track during routing, several classical path-finding algorithms, including Dijkstra’s algorithm [11] and the Bellman-Ford-Moore algorithm [14], can be used on spanners to find a short path. However, when we have restricted knowledge of the graph and limited memory, the routing problem becomes more challenging.

A routing algorithm is called $h$-local if it only knows the $h$-neighbourhood of the current vertex $u$ and the information of the destination $t$, where the $h$-neighbourhood of $u$ is the set of vertices that can be reached from $u$ by taking at most $h$ distinct edges in the graph. A routing algorithm is called $m$-memory if a memory of size $m$ is stored with the message of routing.¹¹1In this paper, we use the standard real RAM model of computation used in computational geometry. In this model, each machine word holds a real number or a $O(\log n)$-bit integer (such as a pointer or an index), and we assume that arithmetic operations (excluding the floor and ceiling functions for real numbers) on machine words take $O(1)$ time. Consequently, a $O(1)$-memory routing algorithm may store $O(\log n)$ bits.

Two major classes of local routing algorithms have been actively researched in the literature: (1) deterministic $1$-local memoryless routing algorithms and (2) deterministic $1$-local $O(1)$-memory routing algorithms. Borrowing the notation used by Bose et al. [2], these two classes of local routing algorithms can be formalised as follows:

• $\mathrm{■}$

  A deterministic $1$-local memoryless routing algorithm on a graph $G=(V,E)$ is a routing function $f:V\times V\times 𝒫(V)\to V$, where $𝒫(\cdot )$ denotes the power set. We express the parameters of the function as $f(u,t,N(u))$, where $u\in V$ is the “current” vertex during routing (i.e., $u$ currently holds the message we want to route from the source to the destination), $t\in V$ is the destination vertex, and $N(u)\subseteq V$ is the $1$-neighbourhood of $u$ (which simply means the set of immediate neighbours of $u$). The output of the routing function with the given parameters, $v=f(u,t,N(u))\in N(u)$, is the neighbour of $u$ to which the message is forwarded.

• $\mathrm{■}$

  A deterministic $1$-local $O(1)$-memory routing algorithm on a graph $G=(V,E)$ is a routing function $g:V\times V\times 𝒫(V)\times ℐ\to V$, which is similar to the routing function $f$ above, except the parameters of the function $g(u,t,N(u),i)$ has an additional parameter $i\in ℐ$, modelling some information stored in the constant-sized memory of $g$ that can be used to make routing decisions.

A routing algorithm performed on a graph $H$ is called $c$-competitive with respect to the underlying network $G$ if the total weight of the path traveled by the routing algorithm between any pair of vertices in $H$ is at most $c$ times the total weight of the shortest path in $G$ [4]. The minimum possible value $c$ for which the given routing algorithm is $c$-competitive with respect to $G$ is called the routing ratio of the routing algorithm in $H$.

The $\mathrm{\Theta }$-graph, introduced independently by Clarkson [10] and Keil [13], is a geometric network studied extensively in the literature. Given a point set $V\subset {ℝ}^2$, the ${\mathrm{\Theta }}_k$-graph $G=(V,E)$ is defined and constructed as follows: For each vertex $u\in V$, we let equally spaced $k$ rays emerge from $u$, resulting in $k$ cones, each with the aperture $\theta =\frac{2\pi }{k}$. For each cone of every vertex $u$, we add an edge from $u$ to the nearest neighbour $v$ within that cone, with distance measured along the bisector of the cone (see Figure 1).

It is known that ${\mathrm{\Theta }}_k$-graphs are spanners (see Table 1 for a summary). In addition, various local routing algorithms with good routing ratios have been developed for ${\mathrm{\Theta }}_k$-graphs. A prime example is $\mathrm{\Theta }$-routing, also known as cone-routing. $\mathrm{\Theta }$-routing from $s$ to $t$ on a ${\mathrm{\Theta }}_k$-graph is defined as follows: Let $u$ be the current vertex visited during the routing from $s$ to $t$. If there exists a direct edge from $u$ to $t$, follow this edge. Otherwise, follow the edge to the closest vertex in the cone of $u$ containing $t$. This is repeated until the destination is reached.

$\mathrm{\Theta }$-routing is known to be competitive when used on ${\mathrm{\Theta }}_k$-graphs for $k\ge 7$. In addition to $\mathrm{\Theta }$-routing, various local routing algorithms with good routing ratios have been developed for $\mathrm{\Theta }$-graphs with smaller numbers of cones (see Table 1 for a summary).

Unfortunately, the $\mathrm{\Theta }$-graph has a number of undesirable properties, including potentially a high maximum degree and a large diameter. The ordered $\mathrm{\Theta }$-graph alleviated these issues. It was introduced by Bose et al. [6] in 2004 to achieve logarithmic maximum degree and logarithmic diameter, in addition to the spanner property. An ordered ${\mathrm{\Theta }}_k$-graph is constructed by inserting the vertices one by one and connecting each vertex to the “closest” previously inserted vertex in each of the $k$ cones.

However, achieving these additional properties comes at a price. For example, ordered $\mathrm{\Theta }$-graphs with $4$, $5$, or $6$ cones are not spanners [8], despite the fact that their unordered counterparts are. In addition, ordered $\mathrm{\Theta }$-graphs have worse spanning ratios compared to $\mathrm{\Theta }$-graphs. The best known upper bounds and lower bounds on the spanning ratio of ordered ${\mathrm{\Theta }}_k$-graphs are summarized in Table 2.

Although we have good local routing algorithms for the $\mathrm{\Theta }$-graph, no local routing algorithm is known for the ordered $\mathrm{\Theta }$-graph. A major obstacle is that even if there are vertices in a cone, there may still not be any edges, due to the insertion order (see Figure 2). This makes the ordered $\mathrm{\Theta }$-graph much more challenging to route on than the $\mathrm{\Theta }$-graph – for example, $\mathrm{\Theta }$-routing fails on the ordered $\mathrm{\Theta }$-graph.

Our contribution is twofold: First, we show why so far no deterministic memoryless $h$-local routing algorithms have been found. Specifically, we prove that there does not exist a deterministic memoryless $h$-local routing algorithm on the ordered ${\mathrm{\Theta }}_k$-graph, for $h\ge 1$ and $k\ge 2$. We construct two ordered ${\mathrm{\Theta }}_k$-graphs $L_h^k$ and $R_h^k$ that cannot be distinguished in this routing model, which implies that any such algorithm fails on one of $L_h^k$ and $R_h^k$. By doing so, we obtain the following theorem.

We then present a deterministic $O(1)$-memory $1$-local routing algorithm $𝒜$ and prove that it converges to the destination in $O(n)$ hops (i.e., taking at most $O(n)$ edges). Our algorithm $𝒜(s,t)$ works in two phases: The first routes from the source $s$ to the first inserted vertex $v_1$ by repeatedly moving to a neighbour with a smaller order. In the second phase, our algorithm routes from $v_1$ to the destination $t$ by systematically exploring vertices that might lead to $t$. By exploring “candidate” vertices in a systematic way, we ensure that we do not need to keep track of the path. Instead, we can use a simple memoryless $1$-local routing algorithm we call ordered $\mathrm{\Theta }$-routing, which allows us to implicitly keep track of the vertices we need to backtrack to by utilizing the geometric property of the ordered $\mathrm{\Theta }$-graph.

To prove that our algorithm $𝒜(s,t)$ converges, we consider the path $P$ travelled by ordered $\mathrm{\Theta }$-routing from $t$ to $v_1$ and show that our algorithm explores this path in the reverse direction. By arguing that any vertex is explored at most once and backtracked from at most once, we conclude that our algorithm reaches the destination in at most $O(n)$ hops and $O(kn)$ time. Consequently, we obtain the following theorem.

Given a set of vertices $V\subset {ℝ}^2$ in the Euclidean plane, the ordered ${\mathrm{\Theta }}_k$-graph $G=(V,E)$ is a geometric network, with edges being undirected straight line segments, constructed as follows. For each vertex $u\in V$, we define $\rho (u)$ to be the order of insertion of $u$ – i.e., if $v_i$ is the $i$-th vertex inserted into $G$, for some positive integer $i\le n$, where $n=|V|$, we let $\rho (v_i)=i$. We incrementally insert the vertices from the first to the last according to the pre-defined order $\rho$. Upon inserting each vertex $u\in V$, we partition the plane around $u$ into $k$ disjoint regions, by projecting $k$ equally spaced rays from $u$, such that the angle between each pair of consecutive rays is $\theta =\frac{2\pi }{k}$ (see Figure 3(a)). We define a cone $C^u$ of $u$ to be a region in the plane between two consecutive rays originating from $u$. We orient the $k$ cones such that the bisector of one of them coincides with the vertical half-line through $u$ lying above $u$. Let the cone with such a bisector be $C_0^u$, from which we start numbering the cones in clockwise order around $u$. For the insertion of every other vertex $v\in V$, we orient and number the cones around $v$ in the same way. We write $C_i^v$ to denote the $i$-th cone of $v$, for . We say that $v$ is the apex of $C_i^v$. We also define $C^v(w)$ to be the cone of $v$ containing a vertex $w$.

Upon the insertion of each vertex $u\in V$, an edge is created to the “closest” previously inserted vertex in each cone $C_i^u$ of $u$ (see Figure 3(b)). More formally, an edge is created from $u$ to $v$ if (1) $u$ is the apex of the cone that contains $v$ such that and (2) for every vertex $w$ within the cone such that , $|u{v}^{\prime }|\le |u{w}^{\prime }|$, where $x^{\prime }$ denotes the orthogonal projection of a vertex $x$ onto the bisector of the cone of $u$ that contains $x$. The canonical triangle $\mathrm{\Delta }uv$ corresponding to an edge created from $u$ to $v$ is defined by the boundary of the cone of $u$ containing $v$ and the line through $v$ and its orthogonal projection onto the bisector. It is important to note that only the vertices inserted before $u$ are considered for the edge creation process. This is why different orderings of vertex insertions result in different ordered ${\mathrm{\Theta }}_k$-graphs, even if the vertex set is the same.

For the insertion of each vertex $u\in V$, we store its order $\rho (u)$ on the vertex, in addition to the $x$- and $y$-coordinates of $u$. Since $1\le \rho (u)\le n$ (where $n=|V|$), storing the order $\rho (u)$ requires at most $\lceil \log n\rceil$ extra bits per vertex, fitting in a single machine word.

It is important to note that a canonical triangle of the ordered $\mathrm{\Theta }$-graph is not necessarily empty, despite the fact that any canonical triangle in the $\mathrm{\Theta }$-graph is always empty of vertices in its interior. This is because the vertices are inserted incrementally and we can always insert a vertex in a canonical triangle between a pair of vertices previously inserted: Suppose, during the construction of an ordered $\mathrm{\Theta }$-graph, we have just inserted a vertex $v\in V$ with order $\rho (v)=k$. Let $v^{\prime }$ with order be the closest neighbour of a cone of $v$. At this stage, the canonical triangle $\mathrm{\Delta }v{v}^{\prime }$ is empty. However, we can insert the next vertex $v^{\prime \prime }$ with order $\rho (v^{\prime \prime })=k+1$ into the interior of $\mathrm{\Delta }v{v}^{\prime }$, making the canonical triangle non-empty.

For simplicity, in order to avoid tie-breaking for edge creation, we assume that $V$ is in general position. Specifically, we will assume that, upon inserting each vertex during the construction of the ordered $\mathrm{\Theta }$-graph, it is clear which vertices lie in which cone (i.e., no previously inserted vertex lies on a boundary of a cone of the currently inserted vertex) and it is clear which vertex is the “closest” in each cone of a vertex (i.e., no vertex $w$ lies on the boundary of the canonical triangle $\mathrm{\Delta }uv$ of the current vertex $u$ and a neighboring vertex $v$, where $w\ne u$ and $w\ne v$). This assumption can be removed using standard techniques.

In this section, we will show that no deterministic memoryless local routing algorithm is guaranteed to reach the destination on the ordered ${\mathrm{\Theta }}_k$-graph, for any integer $k\ge 2$ (Section 4.1). As this motivates us to allow a small amount of memory, we will then present a deterministic $O(1)$-memory local routing algorithm that is guaranteed to reach the destination (Section 4.2).

We first define an important operation used by local routing algorithms.

In this paper, we addressed the following problem with a positive result: Does there exist a local routing algorithm that works on the ordered $\mathrm{\Theta }$-graph? We first proved there does not exist a deterministic memoryless $h$-local routing on the ordered ${\mathrm{\Theta }}_k$-graph for any integers $h\ge 1$ and $k\ge 2$. Then, we presented a deterministic $O(1)$-memory local routing algorithm that is guaranteed to reach the destination in $O(n)$ hops and $O(kn)$ time on the ordered ${\mathrm{\Theta }}_k$-graph for any $k\ge 2$. To the best of our knowledge, the algorithm we provided is the first local routing strategy that is successful on the ordered ${\mathrm{\Theta }}_k$-graph.

Although our local routing algorithm $𝒜(s,t)$ can route between any source and destination, we remark that the total routing path length can be arbitrarily high, which means our local routing algorithm is not $c$-competitive.

Therefore, one natural open question is whether there exists a $c$-competitive local routing algorithm using a small amount of memory on the ordered $\mathrm{\Theta }$-graph. Things that make finding such an algorithm difficult include the fact that ordered $\mathrm{\Theta }$-graphs are generally not plane, the proofs used to bound the spanning ratio by Bose et al. [8] and Bose et al. [6] are highly non-local, and the commonly used properties (such as empty canonical triangles) do not hold for these graphs.