Geometrische Dilation eines Graphen


 

Einführung und Definitionen

Die Dilation eines Graphen gibt an um wieviel größer die Distanz des kürzesten Weges zweier Punkt des Graphen im Vergleich ihrer euklidischen Distanz ist. Sei C(p, q) die Distanz des kürzesten der Punkte Weges p und q des Graphen G = (V, E) und sei |pq| ihre euklidische Distanz, dann ist der Umweg (detour) von p und q definiert als

detour(p, q) = C(p, q) / |pq|.
Die geometrische Dilation ist dann definiert durch
D(G) = max {detour(p, q); (p, q in e) & (e in E) & (p != q)}
Betrachten wir nur die Ecken von G, so erhalten wir die graptherotische Dilation
S(G) = max {detour(p, q); (p, q in V) & (p != q)}

Anwendung

Dilationen spielen eine wichtige Rolle, zum Beispiel bei der Analysierung von online routing Algorithmen. Wenn wir uns den Graphen als ein Netzwerk von Autobahnen vorstellen, dann ist die Dilation die maximal mögliche Strecke (entlang des kürzesten Weges) die wir in einem Auto im Vergleich zu einem Flugzeug in Kauf nehmen müssen

Applet

Das Applet berechnet die geometrische Dilation eines Graphen G = (V, E) in einer Zeit von O(|V|4). Für simple polygonale Pfade existieren Algorithmen, die eine(1+e)-Approximation in O(n log n) [1], und die exakte geometrische Dilation in erwarteten O(n log n) [2] berechnen.

[Applet cannot be started]

Algorithmus

Der Algorithmus berechnet die geometische Dilation indem er ein vertex-edge-cut und ein separation pair mit dem größten Umweg bestimmt. Ein vertex-edge-cut ist ein Tupel von zwei Punkten, von denen mindestens einer auf einem Knoten des Graphen liegen muss. Ein separation pair ist ein Tupel von zwei Punkten, wenn man sie verbindet, den kürzesten Zyklus des Graphen in zwei Hälften teilt.

Vertex-Edge-Cut

Der vertex-edge-cut wird berechnet durch die Betrachtung aller Kombinationen von einem Knoten und einer Kante: Für jedes Paar (p, s2s1) wird der kürzeste Weg von Knoten p zum Ende der Kante s2 s1 berechnet. Mit Dijkstra, brauchen wir dafür insgesamt O(|V|3).

Mit den folgenden Fakten berechnet der Algorithmus in konstanter Zeit O(1) für jedes vertex-edge-pair den Punkt q(t) auf der Kante i>s2s1, der zusammen mit p, den größten Umweg bildet (siehe fig.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) )

Wenn t zu groß oder zu klein ist, wird der Algirthmus den Wert dementsprechend senken oder erhöhen, bis q(t) wieder in s2s1 liegt.

Insgesamt liegt die Berechnung in O(|V|3).

Separation Pair

Zur Berechnung des speration pair betrachtet der Algorithmus alle Kombinationen zweier Kanten: Für jedes Kantenpaar ab und cd wird zunächst die vier kürzesten Wege b->c, d->a und b->d, c->a berechnet. Falls in keinen von ihnen ab oder cd liegt, haben wir zwei kürzeste Zyklen ab->cd->a und ab->dc->a.

Zuerst wird der Zyklus ab->cd->a betrachtet. Man erkennt, das die Punkte p und q in der Art ausgewählt werden müssen, dass die Länge der Wege p->q und q->p auf dem Zyklus dieselben sind. Diese beiden Punkte werden dann mit gleicher Geschwindigkeit um den Zyklus bewegt, bis sie in einer Position sind, in der sie den kleinsten euklidischen Abstand haben, respektive den größten Umweg bilden.

Der Fall ab->dc->a wird analog berechnet.

Mit den zwei Kanten ab, cd, und dem kleinsten Zyklus ab->cd->a berechnet der Algorithmus in O(1) die Distanz um in p,q enthalten zu sein, so dass diese ihre gewünschte Positionen erreichen siehe fig.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]

(Eine genauere Erklärung hierzu würde im Rahmen dieser Demonstration zu weit führen.)

Wie gesagt, der Algorithmus stellt sicher das t groß oder klein genug ist um p, q auf ab bzw cd zu halten. Allerdings muss noch eine weiter Sache sichergestellt werden: Die kürzesten Wege pb->dq, qd->bp, pa->cq, qc->ap von p zu q über dementsprechend b->d, d->b, a->c, c->a dürfen cycle.length/2 nicht überschreiten.

Da der Algorithmus für zwei Ecken nur O(1) zur Berechnung eines seperation pairs mit größtem Umweg braucht, dauert dieser Teil des Algorithmus O(|E|2) = O(|V|4).

Durch Benutzung von Dijkstra dauert die Berechnung des kürzesten Weges von jedem Knoten als Startpunkt O(|V|3).

Insgesamt braucht der Berechnung des seperation pairs mit dem größten Umweg O(|V|4).

Totale Laufzeit

O(|V|4) ist gleichzeitig die totale Laufzeit des Algorithmus.

Bemerkung

Durch [1] wissen wir das ein Punktepaar einer Dilation covisible sein muss. Allerdings muss der kürzeste Weg der diese beiden Punkte verbindet nicht auf am Rand dieser Fläche liegen (siehe fig.3).

fig. 3

Referenzen

Literatur:

[1]:bbers-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.