 |
|
|
|
|
The dilation of a graph specifies how much greater the shortest-path distance of two points of the graph over their euclidean distance can be. If C(p, q) denotes the shortest-path distance of two points p and q of a graph G = (V, E) and |pq| their euclidean distance, then the detour of p and q is defined as
detour(p, q) = C(p, q) / |pq|.The geometric dilation is then defined as
D(G) = max {detour(p, q); (p, q in e) & (e in E) & (p != q)}If we only consider the vertices of G, we get the graph-theoretic dilation
S(G) = max {detour(p, q); (p, q in V) & (p != q)}
Dilation plays an important role, for example, in analyzing online routing algorithms. If we consider the graph as a network of highways, then the dilation specifies the maximum increase in driving distance, when driving an automobile (along the shortest paths) instead of travelling by air.
The applet below computes the geometric dilation of a graph G = (V, E) in running time O(|V|4). As for simple polygonal paths, algorithms computing a (1+e)-approximation in O(n log n) [1] and computing the exact geometric dilation in expected O(n log n) [2] are known.
The algorithm computes the geometric dilation by determining a vertex-edge-cut and a separation pair with the greatest detour. A vertex-edge-cut is a tuple of two points of which at least one is on a vertex, whereas a separation pair is a tuple of two points which cut in half the shortest cycle of the graph connecting the two points.
The vertex-edge-cut is computed by considering every combination of a vertex and an edge: For each vertex-edge-pair (p, s2s1) the algorithm calculates the shortest paths from the vertex p to the ends of the edge s2s1. With Dijkstra, this amounts to a total of O(|V|3) time.
Using the following facts, the algorithm computes in constant time O(1) for each vertex-edge-pair the point q(t) on the edge s2s1, which, combined with p, makes up the greatest detour (see figure 1):
fig.
1
detour(p, q(t)) = C(p, q(t)) / |pq(t)| = (t + |C(p, s2)|) / sqrt( t2 + |ps2|2 - 2t|ps2|cos(beta) )
d(detour(p, q(t))/dt = 0 <=> t = |ps2| * ( |ps2| + C(p, s2) * cos(beta) ) / ( |ps2| * cos(beta) + C(p, s2) )
If t is too great or too small, then the algorithm, respectively, lowers or increases it until q(t) is in s2s1 again.
Altogether, computing the vertex-edge-cut takes O(|V|3) time.
In order to compute the separation pair, the algorithm considers every combination of two edges: For each pair of edges ab and cd it first computes the four shortest paths b->c, d->a and b->d, c->a. If none of them contains ab or cd then we have two shortest cycles ab->cd->a and ab->dc->a.
First the algorithm considers the cycle ab->cd->a. Intuitively, two points p, q have to be chosen such that the lengths of paths p->q and q->p on the cycle are the same. These two points are then moved around the cycle with the same speed until they are in a position of having the smallest euclidean distance, i. e. having the greatest detour.
The same is done in case of ab->dc->a.
Given two edges ab, cd and the smallest cycle ab->cd->a the algorithm computes in O(1) the distance t to be covered by p, q so that they reach their desired positions (see figure 2):
fig.
2
dist := cycle.length/2 - ab.length - (b->c).length
t = [ (cos(cd.orientation) - cos(ab.orientation)) * (a.x - c.x - dist*cos(cd.orientation))
+ (sin(cd.orientation) - sin(ab.orientation)) * (a.y - c.y -dist*sin(cd.orientation))]
/ [(cos(ab.orientation) - cos(cd.orientation))2 + (sin(ab.orientation) - sin(cd.orientation))2]
(Explaining how to get to this equation would go beyond the scope of this demonstration.)
Again, the algorithm secures that t would be great or
small enough to keep p, q on ab or cd,
respectively.
But one more thing has to be assured: the shortest paths
pb->dq, qd->bp,
pa->cq, qc->ap from p to
q passing b->d, d->b,
a->c, c->a, respectively, must
not exceed cycle.length/2.
Since for two edges the algorithm needs only O(1) in order to compute a separation pair on them with the greatest detour, this part of the algorithm takes O(|E|2) = O(|V|4) running time.
Again using Dijkstra, calculating the shortest paths from each vertex as starting point takes O(|V|3) time.
Altogether the running time of calculating the separation pair with the greatest detour by this algorithm is O(|V|4).
O(|V|4) is also the total running time of this algorithm.
By [1] we know that a dilation pair of points needs to be covisible. But the shortest path connecting these two points does not have to be on the border of their area (see figure 3).
fig.
3
fig.
3
[1] Ebbers-Baumann, Klein, Langetepe, Lingas. A Fast Algorithm for Approximating the Detour of a Polygonal Chain. Proceedings of the 9th Annual European Symposium on Algorithms, 2001.
[2] Langerman, Morin, Soss. Computing the Maximum Detour and Spanning Ratio of Planar Paths, Trees and Cycles. STACS 2002.
