GeoNet Seminar Theta-Graph. Strukturen Motivation Definition von Theta-Graph Beispiel nach der Definition Eingenschafen von Theta-Graph Implemetierungsalgorithmus

GeoNet Seminar

Theta-Graph

Strukturen • Motivation• Definition von Theta-Graph• Beispiel nach der Definition• Eingenschafen von Theta-Graph• Implemetierungsalgorithmus von Theta-Graph • Beispiel nach des Algorithmus• Definition des Spanners• Theta-Graph ist Spanner• Beweis• Folgerung

Motivation

•Realisierung Spanner (approximativ vollständiger Graph)

•Entwicklung der Approximationsalgorithmen oder in der Heuristik

Definition von Theta-Graph• Theta-Graph In Fläche um jeden Knote in Sektoren von

Koordinatesystem mit dem örtlichfestgelegten Winkel und schließen den Knote an den nächsten Nachbar in jedem Sektor

Beispiel nach der Definition























Eingenschafen von Theta-Graph

• = ,wobei k ist eine Ganzzahl(k > 8) • Jeder Knoten hat höchsten k Kanten • Im allgemeinen hat ein Knoten Typ i Kanten wobei 1<=i<=k und

der winkel von eine kante und x-coordinate ist.

2k

2 ( 1) 2i ik k

Implemetierungsalgorithmus von Theta-Graph

• Methode Man findet alle Kanten nach Typ i (zuerste ist

Typ1 , dann ist Typ2 , usw.) für jede Knote.• Defintion Drei Ordnungen : In jeder Ordnung

werden die Knoten durch die Einrichtung ihrer Projektionen auf die orientierte Linie georgernet,die durch den Nullpunkt einen Winkel von mit der X-Achse bildet.

, ,

Ordnung :

Ordnung :

Ordnung :


2 ( 1)ik

2 ( 1)2

ik

22

ik

• ImplemetierungsAlgrorithmus 1) Insert point p into table T. 2) If p has a predecessor q in T then report that pq is a type i edge. 3) Repeat Forver If p has a successor r in T then If (r) > (p) then delete r from T else exit loop

Bemerkung: 1) Abtastung in unaufsteigender Ordnung 2) Am Anfang ist Tablle T leer 3) Nach Ordnung stecketet die neue Knote ein


Beispiel Nach Implemetierungsalgorithmus


= {e,b,a,j,d,f,h,c,i,g}



= {e,b,a,j,d,f,h,c,i,g} = {a,c,b,d,g,e,f,h,i,j}


= {e,b,a,j,d,f,h,c,i,g} = {a,c,b,d,g,e,f,h,i,j} = {i,g,h,j,c,f,d,e,b,a}



Knoten Kanten(Typ 1)

a




a




a




c a




c a




c a




c b a




c b a bc,




c b (a) bc,




c d b (a) bc,




c d b (a) bc,dc,




c d b (a) bc,dc,




g c d b (a) bc,dc,




g c d b (a) bc,dc,




g c d b (a) bc,dc,




g c d e b (a) bc,dc,




g c d e b (a) bc,dc,ed




g c d e (b) (a) bc,dc,ed




g c f d e (b) (a) bc,dc,ed




g c f d e (b) (a) bc,dc,ed,fc




g c f d e (b) (a) bc,dc,ed,fc




g h c f d e (b) (a) bc,dc,ed,fc




g h c f d e (b) (a) bc,dc,ed,fc,hg




g h (c) f d e (b) (a) bc,dc,ed,fc,hg




i g h (c) f d e (b) (a) bc,dc,ed,fc,hg




i g h (c) f d e (b) (a) bc,dc,ed,fc,hg




i (g) h (c) f d e (b) (a) bc,dc,ed,fc,hg




i (g) h j (c) f d e (b) (a) bc,dc,ed,fc,hg




i (g) h j (c) f d e (b) (a) bc,dc,ed,fc,hg,jh



i (g) h j (c) (f) (d) e (b) (a) bc,dc,ed,fc,hg,jh



Vergleichen

Definition des Spanners

• Difintion p,q= zwei beliebige konten in graph G d(p,q)=euklidische distanz G(p,q)=länge eines kürzesten wegs in graph G• Spanner Spanner ist ein Subgraph von G und im Spanner ist

der Maximalwert des Verhältnisse G(p,q) / d(p,q) in konstantem Rahmen.

Theta-Graph ist Spanner

• Definiton : Länge eines kürzesten Wegs von p bis q in theta-

graph m: die Anzahl von Knoten in d(p,q) : euklidische distanz• Lemma Wenn es ein kürzesten Weg von p bis q in Theta-graph ,

(k ist eine Ganzzahl und k > 8 ) gibt, und der

Weg fährt über m Knoten durch,dann

( , )p q

2k

( , )p q

( , ) 1 tan 1 tan( , ) cos tan 1

mmp q

d p q

Beweis des Lemmas

• Methode durch Induktionsbeweis• Definition : n-te Knoten im Weg von p bis q in theta-

graph ( 0<=i<=m ),davon : Länge eines kürzesten Wegs von p bis

q in theta-graph

: Länge eines Wegs p bis q in theta-graph mit solche Beschränkung:

ns

( , )p q0s p

/ ( , )p q

Beschränkung für : Wenn der Winkel von und x-achse ist d.h ist ein Kanten von Typ i ,dann ist die Kanten von auch Typ i

Offenbar:

Beweis des Lemmas

/ ( , )p q

ns q 2 ( 1) 2i i

k k

ns q

1n ns s

/( , ) ( , )q qp p

/ ( , )p q( , )p q

( , )d p q

Falls wir

bewiesen haben , dann gilt auch

Beweis des Lemmas

( , ) 1 tan 1 tan( , ) cos tan 1

mmp q

d p q

/ ( , )p q( , )p q

( , )d p q

/ ( , ) 1 tan 1 tan( , ) cos tan 1

mmp q

d p q

1) Wenn m=0 ist , dann ist ;

2)Annahme: ist richtig

Claim: Verhältnis hat Maximumswert,genau

dann wenn (a) q im x-achse ist (b) der Winkel von und x-achse maximal ( ) hat

Beweis des Lemmas

/ ( , ) ( , )p q d p q

/ 11( , ) 1 tan 1 tan

( , ) cos tan 1

mmp q

d p q

/ ( , )( , )p q

d p q

1ps

20k

Setzt in p ein =>

=> und

=>

Beweis des Claims

1/ 1

1 11 tan 1( , ) ( , ) tan

cos tan 1

mms q d s q

/ 11( , ) 1 tan 1 tan

( , ) cos tan 1

mmp q

d p q

/ 111

1

( , ) 1 tan 1 tan( , ) cos tan 1

mms q

d s q

1s

/ / /1 1( , ) ( , ) ( , )p q p s s q /

1 1( , ) ( , )p s d p s

1/ 1

1 11 tan 1( , ) ( , ) ( , ) tan

cos tan 1

mmp q d p s d s q

( , )p q/ ( , )p q( , )d p q

q und werden sich im beschränkte Rahmen

( )beweget,aber die Verhältnis wird nicht weniger ,d.h. und werden nicht weniger ,und

wird sich nicht erhöht.

Beweis des Claims1

/ 11 1

1 tan 1( , ) ( , ) ( , ) tancos tan 1

mmp q d p s d s q

1s/ ( , )( , )p q

d p q

1( , )d p s 1( , )d s q

20k

( , )d p q

Falls < ist ,dann müssen wir und umtauschen ,dann werden und nicht weniger ,und wird sich nicht erhöht,wenn q sich um ins x-achse dreht.

=>

Beweis des Claims

1( , )d p s 1( , )d s q( , )d p q

1s

1( , )d s q

/ ( , )p q

( , )d p q

1( , )neu d s q1( , )alt d s q

1( , )neu d p s1( , )alt d p s

( , )neu d p q( , )alt d p q

(a) q ist im x-achse

Beweis des Claims

wenn q sich um ins x-achse dreht, ändern und nicht,und > => wird sich nicht erhöht. D.h wenn q im x-achse ist,dann ist minimal .

1( , )d p s

1( , )d s q

( , )d p q

( , )d p q

1s1( , )neu d s q

1( , )alt d s q1( , )neu d p s

1( , )alt d p s( , )neu d p q

( , )alt d p q

(b) der Winkel von und x-achse maximal ( ) hat

Beweis des Claims

20k

Wenn sich entlang y-coordinate beweget ,dann wird vergrössert

aber , und werden sich erhöht,aber ändert nicht D.h.wenn ist ,dann ist

maximal.

1s

20k

( , )d p q1( , )d s q

1( , )d p s

2k

1( , )d p s




=>

Nach Claim,ist und ist

minimal und ist maximal.=>

Beweis des Lemmas

1( , )0 ( , )cosd p qd p s

( , )d p q

1( , )d p s

1( , ) ( , ) tand s q d p q







3)

Setzt und ein

=>

=>

=>

Beweis des Lemmas1

/ 11 1

1 tan 1( , ) ( , ) ( , ) tancos tan 1

mmp q d p s d s q

1( , )0 ( , )cosd p qd p s

1( , ) ( , ) tand s q d p q

1/ 1( , ) 1 tan 1( , ) ( , ) tan tan

cos cos tan 1

mmd p qp q d p q

/ 11( , ) 1 1 tan 1tan tan

( , ) cos cos tan 1

mmp q

d p q

/ 1

1( , ) 1 1 tan 1tan tan( , ) cos cos tan 1

mmp q

d p q

=>

=>=>

=>

=>

Beweis des Lemmas/ ( , ) 1 tan tan tan( , ) cos cos (tan 1)

mmp q

d p q

/ ( , ) (tan 1) tan tan tan( , ) cos (tan 1) cos (tan 1)

mmp q

d p q

/ ( , ) tan 1 tan tan tan( , ) cos (tan 1)

mmp q

d p q

/ ( , ) tan 1 tan( , ) cos (tan 1)

mmp q

d p q

/ ( , ) 1 tan 1 tan( , ) cos tan 1

mmp q

d p q

Folgerung

Wenn im theta-graph ist und k>8 , dann ist

,deshalb ist Verhältnisse

=B

( , ) 1 1( , ) cos 1 tanp q

d p q

m

tan 1

k B10 4.52

15 1.97

20 1.56

25 1.39

30 1.30

35 1.24

40 1.20

GeoNet Seminar

Schönen Dank

Documents

GeoNet Seminar Theta-Graph. Strukturen Motivation Definition von Theta-Graph Beispiel nach der Definition Eingenschafen von Theta-Graph Implemetierungsalgorithmus