15/ 19 4. Erweiterung – beliebige Polygone Bezeichnungen/ Definitionen : w(s,p)  : Länge des tatsächlich zurückgelegten Wegs von s nach p d(s,p)  : Länge des kürzesten Wegs von s nach p Beweis der Kompetitivität Wir wissen : v liegt auf dem Weg von s nach t, somit ergibt sich d(s,t) = d(s,v) + |vt| Wegen    (  ,   ) (  ,   ) d s v     w s v £ ergibt sich folgendes Weglängenverhältnis: (  ,  ) (  ,  ) (  ,  ) 2 1 (  ,  ) (  ,  ) (  ,  ) w s v     vt w s t w s v em d s t d s v     vt     d s v + = £ < + + (Beweis analog zum Beweis ab Seite 6) D.h. wir können einen kompetitiven Faktor erreichen, der linear von m (Anzahl der Blätter von SPT in s) abhängt.