Gabriel Triangulations and Angle-Monotone Graphs: Local Routing and Recognition

Abstract

A geometric graph is angle-monotone if every pair of vertices has a path between them that—after some rotation—is x- and y-monotone. Angle-monotone graphs are $\sqrt{2}$-spanners and they are increasing-chord graphs. Dehkordi, Frati, and Gudmundsson introduced angle-monotone graphs in 2014 and proved that Gabriel triangulations are angle-monotone graphs. We give a polynomial time algorithm to recognize angle-monotone geometric graphs. We prove that every point set has a plane geometric graph that is generalized angle-monotone—specifically, we prove that the half-$\theta _6$-graph is generalized angle-monotone. We give a local routing algorithm for Gabriel triangulations that finds a path from any vertex s to any vertex t whose length is within $1 + \sqrt{2}$ times the Euclidean distance from s to t. Finally, we prove some lower bounds and limits on local routing algorithms on Gabriel triangulations.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

A geometric graph has vertices that are points in the plane, and edges that are drawn as straight-line segments, with the weight of an edge being its Euclidean length. A geometric graph need not be planar. Geometric graphs that have relatively short paths are relevant in many applications for routing and network design, and have been a subject of intense research. A main scenario is that we are given a point set and must construct a sparse geometric graph on that point set with good shortest path properties.

If the shortest path between every pair of points has length at most t times the Euclidean distance between the points, then the geometric graph is called a t-spanner, and the minimum such t is called the spanning ratio. Since their introduction by Paul Chew in 1986 [10], spanners have been heavily studied [18].

Besides the existence of short paths, another issue is routing—how to find short paths in a geometric graph. One goal is to find paths using local routing where the path is found one vertex at a time using only local information about the neighbours of the current vertex plus the coordinates of the destination. A main example of such a method is greedy routing: from the current vertex u take any edge to a vertex v that is closer (in Euclidean distance) to the destination than u is. The geometric graphs for which greedy routing succeeds in finding a path are called greedy drawings. These have received considerable attention because of their potential ability to replace routing tables for network routing, and because of the noted conjecture of Papadimitriou and Ratajczak [19] (proved in [5, 16]) that every 3-connected planar graph has a greedy drawing. One drawback is that a path found by greedy routing may be very long compared to the Euclidean distance between the endpoints. Of course this is inevitable if the geometric graph has large spanning ratio.

When a geometric graph is a t-spanner, we can ideally hope for a local routing algorithm that finds a path whose length is at most k times the Euclidean distance between the endpoints, for some k, where, of necessity, $k \ge t$. The maximum ratio, k, of path length to Euclidean distance is called the routing ratio. For example, the Delaunay triangulation, which is a t-spanner for $t \le 1.998$ [21], permits local routing with routing ratio $k \le 5.90$ [7]. It is an open question whether the spanning ratio and routing ratio are equal, though there is a provable gap for $L_1$-Delaunay triangulations [7] and TD-Delaunay triangulations [9].

Other “good” Paths. Recently, a number of other notions of “good” paths in geometric graphs have been investigated. Alamdari et al. [2] introduced self-approaching graphs, where any two vertices s and t are joined by a self-approaching path—a path such that a point moving continuously along the path from s to any intermediate destination r on the path always gets closer to r in Euclidean distance. In an increasing-chord graph, this property also holds for the reverse path from t to s. The self-approaching path property is stronger than the greedy path property in two ways: it applies to every intermediate destination r, and it requires that continuous motion (not just the vertices) along the path to r always gets closer to r. The significance of the stronger property is that self-approaching and increasing-chord graphs have bounded spanning ratios of 5.333 [15] and 2.094 [20], respectively. An important characterization is that a path is self-approaching if and only if at each point on the path, there is a $90^\circ$ wedge that contains the rest of the path [15].

Angelini et al. [4] introduced monotone drawings, where any two vertices s and t are joined by a path that is monotone in some direction. This is a natural desirable property, but not enough to guarantee a bounded spanning ratio.

Angle-Monotone Paths. In this paper we explore properties of another class of geometric graphs with good path properties. These are the angle-monotone graphs which were first introduced by Dehkordi, Frati, and Gudmundsson [12] as a tool to investigate increasing-chord graphs. (We note that Dehkordi et al. [12] did not give a name to their graph class.)

A polygonal path with vertices $v_0, v_1, \ldots , v_n$ is $\beta$ -monotone for some angle $\beta$ if the vector of every edge $(v_i, v_{i+1})$ lies in the closed $90^\circ$ wedge between $\beta - 45^\circ$ and $\beta + 45^\circ$. (In the terminology of Dehkordi et al. [12] this is a $\theta$ -path.) In particular, an x-y-monotone path (where x and y coordinates are both non-decreasing along the path) is a $\beta$-monotone path for $\beta = 45^\circ$ (measured from the positive x-axis). A path is angle-monotone if there is some angle $\beta$ for which it is $\beta$-monotone. To visualize this, note that a path is angle-monotone if and only if it can be rotated to be x-y-monotone. An angle-monotone path is a special case of a self-approaching path where the wedges containing the rest of the path all have the same orientation. See Fig. 1. This implies that an angle-monotone path is also angle-monotone when traversed in the other direction, and thus, has the increasing-chord property. Observe that angle-monotone paths have spanning ratio $\sqrt{2}$—this is because x-y-monotone paths do.

Fig. 1.

The difference between a self-approaching st path (left) with $90^\circ$ wedges each containing the rest of the path, and an angle-monotone path (right) where the $90^\circ$ wedges all have the same orientation $\beta$.

A geometric graph is angle-monotone if for every pair of vertices u, v, there is an angle-monotone path from u to v. Note that the angle $\beta$ may be different for different pairs u, v. Dehkhori et al. [12] introduced angle-monotone graphs, and proved that they include the class of Gabriel triangulations (triangulations with no obtuse angle). Their main goal was to prove that any set of n points in the plane has a planar increasing-chord graph with O(n) Steiner points and O(n) edges. Given their result that Gabriel graphs are increasing chord, this follows from a result of Bern et al. [6] that any point set can be augmented with O(n) points to a point set whose Delaunay triangulation is Gabriel.

The notion of angle-monotone graphs can be generalized to wedges of angle $\gamma$ different from $90^\circ$. (A precise definition is given below.) We call these angle-monotone graphs with width $\gamma$, or generalized angle-monotone graphs. For $\gamma < 180^\circ$, they still have bounded spanning ratios.

Results. The main themes we explore are: Which geometric graphs are angle-monotone? Can we create a sparse (generalized) angle-monotone graph on any given point set? Do angle-monotone graphs permit local routing?

Our first main result is a polynomial time algorithm to test if a geometric graph is angle-monotone. This is significant because it is not known whether increasing chord graphs can be recognized in polynomial time (or whether the problem is NP-hard). Our algorithm extends to generalized angle-monotone graphs for any width $\gamma < 180^\circ$.

Our next result is that for any point set in the plane, there is a plane geometric graph on that point set that is angle-monotone with width $120^\circ$. In particular, we prove that the half- ${\theta _6}$ -graph has this property. Width $90^\circ$ cannot always be achieved because it would imply spanning ratio $\sqrt{2}$ which is known to be impossible for some point sets, as discussed below under Further Background.

The rest of the paper is about local routing algorithms, where we concentrate on a subclass of angle-monotone graphs, namely the Gabriel triangulations. We give a local routing algorithm for Gabriel triangulations that achieves routing ratio $1 + \sqrt{2} \thickapprox 2.41$. This is better than the best known routing ratio for Delaunay triangulations of 5.90 [7]. Also, our algorithm is simpler. The algorithm succeeds, i.e. finds a path to the destination, for any triangulation, and we prove that the algorithm has a bounded routing ratio for triangulations with maximum angle less than $120^\circ$. For Delaunay triangulations, we prove a lower bound on the routing ratio of 5.07, but leave as an open question whether the algorithm ever does worse. Finally, we give some lower bounds on the routing ratio of local routing algorithms on Gabriel triangulations, and we prove that no local routing algorithm on Gabriel triangulations can find self-approaching paths.

As is clear from this outline, we leave many interesting open questions, some of which are listed in the Conclusions section.

Further Background. The standard Delaunay triangulation is not self-approaching in general [2], and therefore not angle-monotone.

The Gabriel graph of point set P is a graph in which for every edge (u, v) the circle with diameter uv contains no points of P. A Gabriel graph that is a triangulation is called a Gabriel triangulation. Any Gabriel triangulation is a Delaunay triangulation. Observe that a triangulation is Gabriel if and only if it has no obtuse angles. Not every point set has a Gabriel triangulation, e.g. three points forming an obtuse triangle.

There are several results on constructing self-approaching/increasing-chord graphs on a given set of points. Alamdari et al. [2] constructed an increasing chord network of linear size using Steiner points, and Dehkordi et al. [12] improved this to a plane network. It is an open question whether every point set admits a plane increasing-chord graph without adding Steiner points. However, for the more restrictive case of angle-monotone graphs, the answer is no: any angle-monotone graph has spanning ratio $\sqrt{2}$ but there is a point set (specifically, the vertices of a regular 23-gon) for which any planar geometric graph has spanning ratio at least 1.4308 [13]. An earlier example was given by Mulzer [17].

Preliminaries and Definitions. A polygonal path with vertices $v_0, v_1, \ldots , v_n$ is $\beta$ -monotone with width $\gamma$ for some angles $\beta$ and $\gamma$ with $\gamma < 180^\circ$ if the vector of every edge $(v_i, v_{i+1})$ lies in the closed wedge of angle $\gamma$ between $\beta - {\gamma \over 2}$ and $\beta + {\gamma \over 2}$. When we have no need to specify $\beta$, we say that the path is angle-monotone with width $\gamma$, or “generalized angle-monotone”. A path that is generalized angle-monotone is a generalized self-approaching path [1] and thus has bounded spanning ratio depending on $\gamma$ [1]. But in fact, we can do better:

Observation 1 [proof in long version]. The spanning ratio of an angle-monotone path with width $\gamma < 180^\circ$ is at most $1/\cos {\gamma \over 2}$.

A geometric graph is angle-monotone with width $\gamma$ if for every pair of vertices u, v, there is an angle-monotone path with width $\gamma$ from u to v. When we have no need to specify $\gamma$, we say that the graph is “generalized angle-monotone”.

Note that in an angle-monotone path (with width $90^\circ$) the distances from $v_0$ to later vertices form an increasing sequence. Furthermore, any $\beta$-monotone path from u to v lies in a rectangle with u and v at opposite corners and with two sides at angles $\beta \pm 45^\circ$, and the union of such rectangles over all $\beta \in [0,360^\circ )$ forms the disc with diameter uv. (See Figure in long version.) This implies:

Lemma 1

Any angle-monotone path from u to v lies inside the disc with diameter uv.

2 Recognizing Angle-Monotone Graphs

In this section we give an $O(n m^2)$ time algorithm to test if a geometric graph with n vertices and m edges is angle-monotone. The idea is to look for angle-monotone paths from a node s to all other nodes, and then repeat over all choices of s. For a given source vertex s, the algorithm explores nodes u in non-decreasing order of their distance from s. At each vertex u we store information to capture all the possible angles $\beta$ for which there is a $\beta$-monotone path from s to u. We show how to propagate this information along an edge from u to v.

We begin with some notation. We will measure angles counterclockwise from the positive x-axis, modulo $360^\circ$. To any ordered pair u, v of vertices (points) of our geometric graph we associate the vector $v-u$ and we denote its angle by $\alpha (u,v)$. If S is a set of angles that lie within a wedge of angle less than $180^\circ$, then we define the minimum of S to be the most clockwise angle, and the maximum of S to be the most counter-clockwise angle. More formally, $\alpha$ is the minimum of S if for any other $\beta \in S$, $\beta - \alpha \in [0,180^\circ )$, and similarly for maximum.

Although there may be exponentially many angle-monotone paths from s to u, each such path has two extreme edges. More precisely, if P is an angle-monotone path from s to u, then the angles, $\alpha (e), e \in P$, lie in a $90^\circ$ wedge, and so this set has a minimum and maximum that differ by at most $90^\circ$. We will store a list of all such min-max pairs with vertex u. Each pair defines a wedge of at most $90^\circ$. Since each pair is defined by two edges, there are at most $O(m^2)$ such pairs (though we will show below that we only need to store O(m) of them).

The algorithm starts off by looking at every edge (s, u) and adding the pair $(\alpha (s,u), \alpha (s,u))$ to u’s list. Then the algorithm explores vertices $u \ne s$ in non-decreasing order of their distance from s. To explore vertex u, consider each edge (u, v) and each pair $(\alpha (e), \alpha (f))$ stored with u, and update the list of pairs for vertex v as follows. If $\alpha (u,v)$ is within $90^\circ$ of $\alpha (e)$ and within $90^\circ$ of $\alpha (f)$ then add to v’s list the pair $(\min \{ \alpha (u,v), \alpha (e)\}, \max \{\alpha (u,v), \alpha (f)\})$.

If ever the algorithm tries to explore a vertex that has no pairs stored with it, then halt—the graph is not angle-monotone. To justify correctness we prove:

Lemma 2

When the algorithm has explored all the vertices closer to s than v, then there exists an angle-monotone path from s to v with extreme edges e and f if and only if the pair $(\alpha (e), \alpha (f))$ is in v’s list.

Proof

The proof is by induction on the distance from s to v.

For the “only if” direction, let P be an angle-monotone path from s to v with extreme edges e and f, and let u be the penultimate vertex of P. The subpath of P from s to u is an angle-monotone path. Suppose its extreme edges are $e'$ and $f'$ where $e=e'$ or $f=f'$ or both. Now, u is closer to s so by induction the pair $(\alpha (e'), \alpha (f'))$ is in u’s list. Because P is angle-monotone, $\alpha (u,v)$ is within $90^\circ$ of $\alpha (e')$ and $\alpha (f')$. Thus the update step applies. During the update step we add the angle $\alpha (u,v)$ to the pair $(\alpha (e'), \alpha (f'))$, which gives the pair $(\alpha (e), \alpha (f))$. Thus we add the pair $(\alpha (e), \alpha (f))$ to v’s list.

For the “if” direction, suppose that the pair $(\alpha (e), \alpha (f))$ is in v’s list. This pair was added to v’s list because of an update from some vertex u closer to s applied to some pair $(\alpha (e'), \alpha (f'))$ in u’s list. By induction, there exists an angle-monotone path P from s to u with extreme edges $e'$ and $f'$, and because the update is only performed when $\alpha (u,v)$ is within $90^\circ$ degrees of $\alpha (e')$ and $\alpha (f')$ therefore the edge (u, v) can be added to P to produce an angle-monotone path with extreme edges e and f.    $\square$

To improve the efficiency of the algorithm we observe that it is redundant to store at a vertex v a pair whose wedge contains the wedge of another pair. Therefore, we only need to store O(m) pairs at each vertex, at most one pair whose first element is $\alpha (e)$ for each edge e. We can simply keep with each vertex v a vector indexed by edges e, in which we store the minimal pair $(\alpha (e), \alpha (f))$ (if any) associated with v so far. Finally, observe that during the course of the algorithm, each edge (u, v) is handled once in an update step. With the refinement just mentioned, handling an edge costs O(m). Therefore the algorithm runs in time $O(m^2)$ for a single choice of s, and in time $O(n m^2)$ overall.

The algorithm can be generalized to recognize angle-monotone graphs of width $\gamma$ for fixed $\gamma < 180^\circ$. It is no longer legitimate to explore vertices in order of distance from s, since a generalized angle-monotone path will not necessarily respect this ordering. However, we can run the algorithm in phases, where phase i captures all the angle-monotone paths of width $\gamma$ that start at s and have at most i edges. Since no angle-monotone path can repeat a vertex, there are at most $n-1$ edges in any angle-monotone path. Thus we need $n-1$ phases. In each phase, for each directed edge (u, v) we update each pair $(\alpha (e), \alpha (f))$ stored at u as follows. If $\alpha (u,v)$ is within $\gamma$ of $\alpha (e)$ and within $\gamma$ of $\alpha (f)$ then add to v’s list the pair $(\min \{ \alpha (u,v), \alpha (e)\}, \max \{\alpha (u,v), \alpha (f)\})$. In this way, each of the $n - 1$ phases takes time $O(m^2)$, so the total run-time of the algorithm over all choices of s becomes $O(n^2 m^2)$.

3 A Class of Generalized Angle-Monotone Graphs

In this section we show that every point set in the plane has a plane geometric graph that is angle-monotone with width $120^\circ$. In particular, we will prove that the half- ${\theta _6}$ -graph has this property. As noted in the Introduction, there are point sets for which no plane graph is angle-monotone with width $90^\circ$. It is an open question to narrow this gap and find the minimum angle $\gamma$ for which every point set has a plane graph that is angle-monotone with width $\gamma$ (and thus spanning ratio $1/ \cos {\gamma \over 2}$).

We first define the half-$\theta _6$-graph. For each point $u \in P$, partition the plane into $60^\circ$ cones with apex u, with each cone defined by two rays at consecutive multiples of $60^\circ$ from the positive x-axis. Label the cones $C_0$, $C_1$, $C_2$, $C_3$, $C_4$, and $C_5$ in clockwise order around u, starting from the cone containing the positive y-axis. See Fig. 2(a).

For two vertices u and v the canonical triangle $T_{uv}$ is the triangle bounded by: the cone of u that contains v; and the line through v perpendicular to the bisector of that cone. See Fig. 2(b). Notice that if v is in an even cone of u, then u is in an odd cone of v. We build the half-$\theta _6$-graph as follows. For each vertex u and each even $i=0,2,4$, add the edge uv provided that v is in the $C_i$ cone of u and $T_{uv}$ is empty. We call v the $C_i$ -neighbour of u. For simplicity, we assume that no two points lie on a line parallel to a cone boundary, guaranteeing that each vertex connects to exactly one vertex in each even cone. Hence the graph has at most 3n edges in total. The half-$\theta _6$-graph is a type of Delaunay triangulation where the empty region is an equilateral triangle in a fixed orientation as opposed to a disk [8]. It can be computed in $O(n \log n)$ time [18].

Fig. 2.

(a) 6 cones originating from point u, (b) Canonical triangle $T_{uv}$, (c) path $\sigma _u$ (solid) with its empty canonical triangles shaded, path $\sigma _v$ (dashed) and their common vertex x.

To prove angle-monotonicity properties of the half-$\theta _6$-graph, we use an idea like the one used by Angelini [3]. His goal was to show that every abstract triangulation has an embedding that is monotone, i.e. angle-monotone with width $180^\circ$. (The same result was obtained in [14] with a different proof.) Angelini did this by showing that the Schnyder drawing of any triangulation is monotone, and in fact, upon careful reading, his proof shows that any Schnyder drawing is angle-monotone with the smaller width $120^\circ$. Schnyder drawings are a special case of half-$\theta _6$-graph s [8] so it is not surprising that Angelini’s proof idea extends to the half-$\theta _6$-graph in general.

Theorem 1

The half-$\theta _6$-graph is angle-monotone with width $120^\circ$.

Proof

We must prove that for any points u and v, there is an angle-monotone path from u to v of width $120^\circ$. Assume without loss of generality that v is in the $C_0$ cone of u. See Fig. 2(b).

Our path from u to v will be the union of two paths, each of which is angle-monotone of width $60^\circ$. We begin by constructing a path $\sigma _u$ from u in which each vertex is joined to its $C_0$ neighbour. This is a $\beta$-monotone path of width $60^\circ$ for $\beta = 90^\circ$. If the path contains v we are done, so assume otherwise. Let $u'$ be the last vertex of the path that lies in $T_{uv}$. Note that v cannot lie in the $C_0$ cone of $u'$. Let S be the subpath of $\sigma _u$ from u to $u'$, together with the $C_0$ cone of $u'$. Then S separates $T_{uv}$ into two parts. Suppose that v lies in the right-hand part (the other case is symmetric). See Fig. 2(c).

Next, construct a path $\sigma _v$ from v in which each vertex is joined to its $C_4$ neighbour. This is a $\beta$-monotone path of width $60^\circ$ for $\beta = 210^\circ$.

We now claim that $\sigma _u$ and $\sigma _v$ have a common vertex x. Then as our final path from u to v we take the portion of $\sigma _u$ from u to x followed by the portion of $\sigma _v$ backwards from x to v. Since the reverse of $\sigma _v$ is $\beta$-monotone with width $60^\circ$ for $\beta = 30^\circ$, the final path is $\beta$-monotone with width $120^\circ$ for $\beta = 60^\circ$.

It remains to prove that x exists. Let $v'$ be the last vertex of $\sigma _v$ that lies strictly to the right of S. Let $u''$ be the last vertex of $\sigma _u$ that lies below $v'$. We claim that $u''$ is the $C_4$ neighbour of $v'$, and thus that $u''$ provides our vertex x. Let T be the empty canonical triangle from $u''$ to its $C_0$-neighbour (or the empty $C_0$ cone of $u''$ in case $u''$ has no $C_0$-neighbour). First note that $u''$ is in the $C_4$ cone of $v'$—otherwise $v'$ would be in T. Next note that $T_{v'u''}$ is empty—otherwise v would have a $C_4$-neighbour that is in T or is to the right of S.    $\square$

Theorem 1 implies that the spanning ratio of the half-$\theta _6$-graph is 2, which was already known [11]. The best routing ratio achievable for the half-$\theta _6$-graph is $5/\sqrt{3} \approx 2.887$ [9]. (This was the first proved separation between spanning ratio and routing ratio.) Since angle-monotone paths of width $120^\circ$ have spanning ratio 2, this implies that no local routing algorithm can compute angle-monotone paths with width $120^\circ$ on the half-$\theta _6$-graph.

4 Local Routing in Gabriel Triangulations

In this section we give a simple local “angle” routing algorithm that finds a path from s to t in any triangulation. Like previous algorithms, the path walks only along edges of triangles that intersect the line segment st. The novelty is that the next edge of the path is chosen based on angles relative to the vector st.

The details of the algorithm are in Sect. 4.1. In Sect. 4.2 we prove that the algorithm has routing ratio $1 + \sqrt{2}$ on Gabriel graphs, and discuss its behaviour on Delaunay triangulations. In Sect. 4.3 we give lower bounds on the routing and competitive ratios of local routing algorithms on Gabriel graphs.

4.1 Local Angle Routing

Our algorithm is simple to describe: Suppose we want a route from s to t in a triangulation. Orient st horizontally, t to the right. Suppose we have reached vertex p. Consider the last (rightmost) triangle that is incident to p and intersects the line segment st. The triangle has two edges incident to p. Of these two edges, take the one that has the minimum angle to the horizontal ray from p to the right. See Fig. 3. Pseudo-code can be found below in Algorithm 1. Note that in the pseudo-code, the angle test is equivalently replaced by two tests, identifying steps of type A and B for easier case analysis. For an example of a path computed by the algorithm, see Fig. 4. Observe that the algorithm always succeeds in finding a route from s to t because it always advances rightward in the sequence of triangles that intersect line segment st.

Fig. 3.

Local routing from s to t. At vertex p, with pab being the rightmost triangle incident to p that intersects line segment st, we route from p to a because the (unsigned) angle apr is less than angle bpr. A step of type A is shown on the left and a step of type B on the right.

Fig. 4.

Example of route computed by Algorithm 1 (heavy blue path). In dotted red, a longer route obtained by replacing each segment of the route by the most extreme angle. Both routes are within $(1 + \sqrt{2} )$ of ||st||. (Color figure online)

4.2 Analysis of the Algorithm

In this section we will prove that the above algorithm has routing ratio exactly $1 + \sqrt{2}$ on Gabriel triangulations, which have maximum angle at most $90^\circ$. In the last part of the section we generalize the analysis to triangulations with a larger maximum angle, and we show that the routing ratio is at least 5.07 on Delaunay triangulations.

The intuition for bounding the routing ratio on Gabriel triangulations is to replace each segment of the route by the most extreme segment possible. See Fig. 4. Any step of type B is replaced by a $45^\circ$ segment plus a horizontal segment. Any step of type A is replaced by a vertical segment plus a horizontal segment. Vertical segments are the bad ones, but each vertical must be preceded by $45^\circ$ segments, which means that instead of travelling 1 unit horizontally (the optimum route) we have travelled $\sqrt{2}$ along a $45^\circ$ segment plus 1 vertically, giving us the $1 + \sqrt{2}$ ratio. We now give a more formal proof.

For each edge $e = (p_i, p_{i+1})$ of the path, let $d_x(e) = ||x(p_i)-x(q_{p+1})||$ and $d_y(e) = ||y(p_i)-y(p_{i+1})||$. Let A (resp. B) be the set of edges of the path where the algorithm makes a step of type A (resp. type B). (Context will distinguish edge sets from steps.) Let $x_B = \sum _{e\in B} d_x(e)$ and $x_A = \sum _{e \in A} d_x(e)$.

Lemma 3

On any Gabriel triangulation the path computed by Algorithm 1 is x-increasing.

Proof

Let us show that each step is x-increasing. Consider a step from p, with a and b as defined in Algorithm 1. Assume without loss of generality that p and a are above line st and b is below. Since T is the last triangle incident to p that intersects st, the clockwise ordering of T is pab. Refer to Fig. 3.

If the algorithm takes a step of type B then a is above p (in y coordinate) and b is below p. Since $\angle bpa \le 90^\circ$, thus x(a) and x(b) are greater than x(p). If the algorithm takes a step of type A then since b is below st and a is above st and $\angle bap \le 90^\circ$, thus x(a) is greater than x(p).    $\square$

Theorem 2

On any Gabriel triangulation, Algorithm 1 has a routing ratio of $1+\sqrt{2}$ and this bound is tight.

Proof

We first bound $\sum _{e \in B} ||e||$. Observe that each edge in B forms an angle with the horizontal line through p that is at most $45^\circ$. Thus $\sum _{e \in B} d_y(e) \le x_B$ and $\sum _{e \in B} ||e|| \le \sqrt{2} x_B$.

We next bound $\sum _{e \in A} ||e||$. Observe that edges in A move us closer to the line st, and must be balanced by previous steps (of type B) that moved us farther from the line st. This implies that $\sum _{e \in A} d_y(e) \le \sum _{e \in B} d_y(e) \le x_B$ (where the last step comes from the first observation). Since $||e|| \le d_x(e) + d_y(e)$, thus $\sum _{e \in A} ||e|| \le x_A + \sum _{e \in A} d_y(e) \le x_A + x_B$.

Putting these together, the length of the path is bounded by $\sum _{e \in A} ||e|| + \sum _{e \in B} ||e|| \le x_A + x_B + \sqrt{2} x_B \le (1 + \sqrt{2})(x_A + x_B)$. Finally, by Lemma 3, $x_A + x_B = ||st||$, so this proves that the routing ratio is at most $(1 + \sqrt{2})$.

An example to show that this analysis is tight is given in the full version.    $\square$

We conclude this section with two results on the behaviour of the routing algorithm on other triangulations. Proofs can be found in the full version.

Theorem 3

In a triangulation with maximum angle $\alpha < 120^\circ$ Algorithm 1 has a routing ratio of $(\sin \alpha + \sin {\alpha \over 2}) / \sin {{3 \alpha } \over 2}$ and this bound is tight.

Theorem 4

The routing ratio of Algorithm 1 on Delaunay triangulation is greater than 5.07.

We believe that the routing ratio of Algorithm 1 on Delaunay triangulations is close to 5.07, but leave that as an open question. We remark that Algorithm 1 is different from the generalization of Chew’s Routing Algorithm for Delaunay triangulations [10] (cf. the algorithm described in [7]).

4.3 Limits of Local Routing Algorithms on Gabriel Triangulations

In this section we prove some limits on local routing on Gabriel triangulations. Proofs are deferred to the full version.

A routing algorithm on a geometric graph G has a competitive ratio of c if the length of the path produced by the algorithm from any vertex s to any vertex t is at most c times the length of the shortest path from s to t in G, and c is the minimum such value. (Recall that the routing ratio compares the length of the path produced by the algorithm to the Euclidean distance between the endpoints. Thus the competitive ratio is less than or equal to the routing ratio).

A routing algorithm is k-local (for some integer constant $k>0$) if it makes forwarding decisions based on: (1) the k-neighborhood in G of the current position of the message; and (2) limited information stored in the message header.

Theorem 5

Any k-local routing algorithm on Gabriel triangulations has routing ratio at least 1.4966 and competitive ratio at least 1.2687.

Although Gabriel triangulations are angle-monotone [12], Theorem 5 shows that no local routing algorithm can compute angle-monotone paths since that would give routing ratio $\sqrt{2}$. The following theorem tells us that even less constrained paths cannot be computed locally:

Theorem 6

There is no k-local routing algorithm on Gabriel triangulations that always finds self-approaching paths.

5 Conclusions

We conclude this paper with some open questions.

• 1. What is the minimum angle $\gamma$ for which every point set has a plane geometric graph that is angle-monotone with width $\gamma$ (and thus has spanning ratio $1/ \cos {\gamma \over 2}$)? We proved $\gamma \le 120^\circ$, and it is known that $\gamma > 90^\circ$.

• 2. Is there a local routing algorithm with bounded routing ratio for any angle-monotone graph? Any increasing-chord graph?

• 3. We bounded the routing ratio of our local routing algorithm on triangulations based on the maximum angle in the triangulation, but how does this relate to the property of being generalized angle-monotone? If a triangulation has bounded maximum angle, is it generalized angle-monotone? The only thing known is that maximum angle $90^\circ$ implies angle-monotone with width $90^\circ$ [12].

• 4. Is the standard Delaunay triangulation generalized angle-monotone? In particular, proving that the Delaunay triangulation is angle-monotone with width strictly less than $120^\circ$ would provide a different proof that the Delaunay triangulation has spanning ratio less than 2 [21]. It is known that the Delaunay triangulation is not angle-monotone with width $90^\circ$ (see Sect. 1).

• 5. How does our local routing algorithm behave on standard Delaunay triangulations? We proved a lower bound of 5.07 on the routing ratio. We believe the routing ratio is close to this value, but have no upper bound.