Kürzeste Wege in Polygonen ========================== Wolfgang Mulzer gegeben: Ein einfaches Polygon P, zwei Punkte s, t in P. gesucht: Der kuerzeste Polygonzug von s nach t, der ganz in P liegt und keine ueberfluessigen Ecken hat. 1. Trianguliere P (ist nur einmal noetig). 2. Konstruiere den Aermel fuer P, s und t. Seien D1, D2, ..., Dk die Dreiecke des Aermels und d1, d2, ..., d(k-1) die gemeinsamen Diagonalen. Bezeichne mit d(l,i) und d(r,i) den linken bzw. rechten Endpunkt von di. Variablen: + Zwei doppelt verkettete Listen Z(l,i) und Z(r,i), der jeweils kuerzeste Weg von s zu dem linken bzw. rechten Endpunkt von di. Dabei sind Z(l,i) und Z(r,i) bis zu v identisch und verzweigen sich hinter v. + v, die Spitze des durch Z(l,i) und Z(r,i) definierten Trichters 3. v <- s 4. Z(l,1) <- (s, d(l,1)); Z(r,1) <- (s, d(r,1)); 5. for i := 2 to k-1 do 6. if d(i-1) und d(i) unterscheiden sich im Endpunkt d(l,i) then 7. w <- d(l,i-1) 8. while w != v && w ist nicht die Tangentialecke fuer d(l,i) an Z(l,i-1) do 9. w <- Vorgaenger von w auf Z(l,i-1) 10. if w ist die Tangentialecke fuer d(l,i) an Z(l, i-1) then 11. Z(l,i) <- Z(l,i-1)[s->w] ++ d(l,i) 12. else 13. w <- Nachfolger von v auf Z(r,i-1) 14. while w != d(r,i-1) && w ist nicht die Tangentialecke fuer d(l,i) an Z(r,i-1) do 15. w <- Nachfolger von w auf Z(r,i-1) 16. Z(l,i) <- Z(r,i-1)[s->w] ++ d(l,i) 17. v <- w 18. else 19. // Symmetrisch zum ersten Fall Laufzeitanalyse: Die Schritte 1-4 benoetigen O(n log n) Zeit (bzw. O(n)) Zeit, falls das Polygon bereits trianguliert ist oder ein schneller Triangulierungsalgorithmus zum Einsatz komm.t: Die for-Schleife in Schritt 5 wird O(n) mal durchlaufen. Jeder Durchlauf benoetigt O(1 + # inspizierter Ecken in den while-Schleifen). Alle inspizierten Ecken bis auf die letzte werden danach nie wieder betrachtet (d.h., sie werden vom Trichter geloescht). Da jede Ecke genau einmal auf den Trichter gesetzt wird, ist die Gesamtzahl der geloeschten Ecken O(n), und die Gesamtzeit fuer die for-Schleife ist linear.