Lokale NetzstrukturenUbung 3

21.06.2017

Wiederholung: Spanner

Sei H = (V ,E ′ ⊆ E ) Teilgraph von G = (V ,E ) (schreiben dannauch H ⊆ G ). Bezeichne mit dH(u, v) die kurzeste Distanzzwischen u und v in H bzgl. der Metrik d(·, ·).

DefinitionH hat spanning ratio (stretch factor) t bzgl. G , falls gilt:

∀ u, v ∈ V : dG (u, v) ≤ t · dH(u, v)

Alternativ kann man schreiben:

DefinitionDie spanning ratio (stretch factor) von H bzgl. G ist definiert als:

maxu,v∈V

{dH(u, v)

dG (u, v)

}

Aufgabe 5 – a)

I Ein geometrischer Graph wird als zivilisiert bezeichnet, wennfur jede Kante uv im Graphen gilt, dass die EuklidischeDistanz zwischen u and v mindestens λ betragt, fur einbeliebig aber festes λ > 0.

Im Folgenden sei G = (V ,E ) ein zivilisierter geometrischer Graphund H = (V ,E ′) sei ein Subgraph von G .Beweisen oder widerlegen Sie: Falls H ein Euklidischer Spanner furG ist, dann folgt daraus dass H auch ein topologischer Spanner furG ist.

Aufgabe 5 – a) (cont’d)

G = (V ,E ) mit V = {w0,w1, ...,wn},wobei n = (π/2)·|uv |

λ + 1 undE = {uv} ∪ {vivi+1}0≤i<n

Sei H = (V ,E ′) mit E ′ = E \ {uv}Uberlegen zunachst das H tatsachlichEukl. Spanner fur G mit c ≤ π/2Außerdem gilt:

dhH(u, v)

dhG (u, v)

=n − 1

1

D.h. H ist Eukl. Spanner fur G aberkein topologischer Spanner. Aussagealso widerlegt.

Aufgabe 5 – b)

I Ein Graph wird weiterhin als reichweitenbeschranktbezeichnet, falls keine Kante uv im Graphen langer ist als einebeliebige aber feste Konstante r > 0 (bspw. gehort die Klasseder Unit Disk Graphen zur Klasse der reichweitenbeschranktenGraphen).

Im Folgenden sei G = (V ,E ) ein zivilisierter geometrischer Graphund H = (V ,E ′) sei ein Subgraph von G .Angenommen Graph G ware zusatzlich auch nochreichweitenbeschrankt mit r > λ > 0. Beweisen oder widerlegenSie: Falls H ein Euklidischer Spanner fur G ist, dann folgt darausdass H auch ein topologischer Spanner fur G ist.

Aufgabe 5 – b) (cont’d)

Bezeichne mit ΠH(u, v) und ΓH(u, v) den kurzesten Euklidischenbzw. topologischen Pfad von u nach v in H. Bezeichnen mit

||ΠH(u, v)|| die Euklidische Lange und mit |ΠH(u, v)| die hopLange eines Pfades.

Voronoi DiagrammVoronoi Region eines Knotens

Sei P ⊂ R2. Voronoi Region von u bzgl. P, VRP(u):

VRP(u) =⋂

v∈V \{u}

H(u, v)

Voronoi Diagramm (cont’d)

Voronoi Diagram uber P, VD(P):

VD(P) = {VRP(u1), ...,VRP(un)},P = {u1, ..., un}

Zusammenhang Voronoi Diagramm und DelaunayTriangulierung

Probleme: colinearity und cocircularity

Konvexe Hulle

Eine Teilmenge S ⊂ R2 heißt konvex genau dann wenn fur jedespaar von Punkten p, q ∈ S das Liniensegment pq vollstandig in Senthalten ist. Die Konvexe Hulle (Convex Hull) uber S , CH(S), istdie kleinste konvexe Menge die S enthalt. Formal: CH(S) ist dieSchnittmenge aller konvexen Mengen die S enthalten.

Aufgabe 1 – a)

Beweisen oder widerlegen Sie: Voronoi Diagramm VD(P) enthaltmindestens eine unbeschrankte Voronoi Region.

I Voruassetzung: P nicht colinear, nicht cocircular und |P| = nist endlich

I nach Def. teilt VD(P) den R2 in n Regionen.

I Da R2 unendlich ist, muss mindestens eine der n Flachen VRP

unendlich sein

Aufgabe 1 – a)

Beweisen oder widerlegen Sie: Voronoi Diagramm VD(P) enthaltmindestens eine unbeschrankte Voronoi Region.

I Voruassetzung: P nicht colinear, nicht cocircular und |P| = nist endlich

I nach Def. teilt VD(P) den R2 in n Regionen.

I Da R2 unendlich ist, muss mindestens eine der n Flachen VRP

unendlich sein

Aufgabe 1 – b)Beweisen Sie die folgende Aussage: Eine Voronoi Region VRP(pi )ist unbeschrankt genau dann wenn pi ein Punkt auf der konvexenHulle von P ist, d.h. pi ∈ CH(P).

Figure: Beweis- und Bildquelle: A. Okabe, B. Boots, K. Sugihara, and S.N. Chiu, Spatial Tessellations — Concepts and Applications of VoronoiDiagrams, 2nd Ed. Chichester: John Wiley & Sons, 1999, pp.58.

Aufgabe 1 – b)Beweisen Sie die folgende Aussage: Eine Voronoi Region VRP(pi )ist unbeschrankt genau dann wenn pi ein Punkt auf der konvexenHulle von P ist, d.h. pi ∈ CH(P).

Figure: Beweis- und Bildquelle: A. Okabe, B. Boots, K. Sugihara, and S.N. Chiu, Spatial Tessellations — Concepts and Applications of VoronoiDiagrams, 2nd Ed. Chichester: John Wiley & Sons, 1999, pp.58.

Aufgabe 1 – b) (cont’d)

“⇐”: Fur pi ∈ P im Inneren von CH(P) istdie Voronoi Region beschrankt.

I Da pi im inneren von CH(P) liegt und Pnicht colinear, ∃ Dreieck um drei Punktepi1, pi2, pi3 ∈ CH(P), sodass pi darinenthalten ist.

I Konstruieren Dreieck ausH(pi , pi1),H(pi , pi2), H(pi , pi3)(gestrichelt)

I Da pi ∈ 4pi1pi2pi3, ist das gestrichelteDreieck beschrankt, außerdem gilt:

H(pi , pi1) ∩ H(pi , pi2) ∩ H(pi , pi3) ⊇⋂

pj∈P\{pi}

H(pi , pj) = VR(pi ).

Aufgabe 1 – b) (cont’d)

“⇒”: Aus VRP(pi ) beschrankt folgtpi /∈ CH(P).

I Sei Ji ⊂ P die Menge der Punkte die eineVoronoi Kante mit pi teilen.

I Es gilt: pi ist im Inneren vonCH({pj , j ∈ Ji})

I Mit CH({pj , j ∈ Ji}) ⊂ CH(P) gilt zudem, dass pi nicht aufCH(P) liegt

Aufgabe 1 – c)Fur pi ∈ P sei pj der nachste Punkt aus der Menge P (bzgl. desEuklidischen Abstands). Beweisen Sie: Die Voronoi Regionen vonpi und pj teilen sich eine gemeinsame Kante im Voronoi DiagrammVD(P).

Figure: Beweis- und Bildquelle: A. Okabe, B. Boots, K. Sugihara, and S.N. Chiu, Spatial Tessellations — Concepts and Applications of VoronoiDiagrams, 2nd Ed. Chichester: John Wiley & Sons, 1999, pp.58.

Aufgabe 1 – c)Fur pi ∈ P sei pj der nachste Punkt aus der Menge P (bzgl. desEuklidischen Abstands). Beweisen Sie: Die Voronoi Regionen vonpi und pj teilen sich eine gemeinsame Kante im Voronoi DiagrammVD(P).

Figure: Beweis- und Bildquelle: A. Okabe, B. Boots, K. Sugihara, and S.N. Chiu, Spatial Tessellations — Concepts and Applications of VoronoiDiagrams, 2nd Ed. Chichester: John Wiley & Sons, 1999, pp.58.

Localized Delaunay Triangulation

k-localized Delaunay triangle

A triangle 4uvw satisfies k-localized Delaunay property if theinterior of the circumcircle C (u, v ,w) does not contain any nodeof V which is a k-hop-neighbor of u,v ,or w ; and all edges of thetriangle 4uvw have length no more than one unit.

k-localized Delaunay graph

The k-localized Delaunay graph over a node set V , denoted byLDel (k)(V ), has exactly all Gabriel edges and edges of allk-localized Delaunay triangles.

Localized Delaunay Triangulation (con’d)

Aufgabe 2 – a)Es ist aus der Vorlesung bereits bekannt, dass die 1-lokale DelaunayTriangulierung LDel (1)(V ) uber einer Knotenmenge V nicht planarist, da ein 1-lokales Delaunay Dreieck von einer Gabriel GraphKante geschnitten werden kann. Geben Sie nun ein Beispiel fureinen Unit Disk Graphen an in dem ein 1-lokales Delaunay Dreieckdurch ein weiteres 1-lokales Delaunay Dreieck geschnitten wird.

Aufgabe 2 – a) (cont’d)

Beweisquelle: Li, X.-Y., Calinescu, G., Wan, P., Wang, Y.:Localized Delaunay triangulation with application in ad hocwireless networks. IEEE Transactions on Parallel and DistributedSystems 14(10), pp.1035–1047, 2003. (Kapitel 3.2)

Aufgabe 2 – b)Sei 4(uvw) ein k-lokales Delaunay Dreieck in UDG (V ) und sei(x , y) eine Kante in UDG (V ). Beweisen Sie: Falls die Kante (x , y)das Dreieck 4(uvw) schneidet, dann konnen nicht beide Knoten xund y im Kreis C (uvw) enthalten sein.

Aufgabe 2 – b) (cont’d)

I Annahme: x , y ∈ C (uvw) und xy schneidet4(uvw).

I Kreis C (uvw) wird durch 4(u, v ,w) in 4 Teilegeteilt. Nach Annahme (es ex. Schnitt) kannweder x noch y im Dreick 4(uvw) liegen.

I O.B.d.A. liege x unterhalb von uv und yoberhalb von vw .

I Mit Winkelsummensatz muss gelten:∠(uwv) ≤ π/2 oder ∠(vuw) ≤ π/2. Darausfolgt: Einer der Winkel ∠(uxv), ∠(vyw) istmindestens π/2.

I Damit gilt entweder vy ≤ vw ≤ R odervx ≤ vu ≤ R.

I D.h. C (uvw) enthalt Knoten aus N1(v).Widerspruch zu “4(uvw) ist lokales DelaunayDreieck”.

Aufgabe 2 – c)

Aus der Vorlesung ist bekannt, dass LDel (k)(V ) fur k ≥ 2 einplanarer Euklidischer Spanner fur den Unit Disk Graphen ist.Beschreiben Sie einen 2-lokalen Algorithmus zur Konstruktion vonLDel (2)(V ) in UDG.Genauer: Ausgefuhrt auf einem beliebigen Netzknoten v eines UDGsoll ihr Algorithmus die Kanten von v in LDel (2)(V ) berechnen.

Aufgabe 2 – c) (cont’d)

1. Every node u collects N2(u) and computes the Delaunaytriangulation Del(N2(u)) of its 2-neighborhood, includingitself.

2. For each edge uv of Del(N2(u)), let 4uvw and 4uvz be twotriangles incident on uv . Edge uv is a GG edge if both angles∠uwv and ∠uzv are less than π/2 and uv ≤ 1. Node u addsall GG edges to its set of incident edges.

3. Each node u finds all triangles 4uvw from Del(N2(u)) suchthat all three edges of 4uvw have length at most one unit.Node u broadcasts a message proposal(u, v ,w) to N1(u) toform a localized Delaunay triangle 4uvw in LDel (2)(V ), andlistens to the messages from its neighboring nodes.

Aufgabe 2 – c) (cont’d)

1. Every node u collects N2(u) and computes the Delaunaytriangulation Del(N2(u)) of its 2-neighborhood, includingitself.

2. For each edge uv of Del(N2(u)), let 4uvw and 4uvz be twotriangles incident on uv . Edge uv is a GG edge if both angles∠uwv and ∠uzv are less than π/2 and uv ≤ 1. Node u addsall GG edges to its set of incident edges.

3. Each node u finds all triangles 4uvw from Del(N2(u)) suchthat all three edges of 4uvw have length at most one unit.Node u broadcasts a message proposal(u, v ,w) to N1(u) toform a localized Delaunay triangle 4uvw in LDel (2)(V ), andlistens to the messages from its neighboring nodes.

Aufgabe 2 – c) (cont’d)

1. Every node u collects N2(u) and computes the Delaunaytriangulation Del(N2(u)) of its 2-neighborhood, includingitself.

2. For each edge uv of Del(N2(u)), let 4uvw and 4uvz be twotriangles incident on uv . Edge uv is a GG edge if both angles∠uwv and ∠uzv are less than π/2 and uv ≤ 1. Node u addsall GG edges to its set of incident edges.

3. Each node u finds all triangles 4uvw from Del(N2(u)) suchthat all three edges of 4uvw have length at most one unit.Node u broadcasts a message proposal(u, v ,w) to N1(u) toform a localized Delaunay triangle 4uvw in LDel (2)(V ), andlistens to the messages from its neighboring nodes.

Aufgabe 2 – c) (cont’d)

4. When a node u receives a message proposal(u, v ,w), uaccepts the proposal of constructing 4uvw if it belongs toDel(N2(u)) by broadcasting accept(u, v ,w) to N1(u);otherwise, it rejects the proposal by broadcastingreject(u, v ,w) to N1(u).

5. A node u adds the edges uv and uw to its set of incidentedges if the triangle 4uvw is in Del(N2(u)) and both v andw have sent either accept(u, v ,w) or proposal(u, v ,w).

Aufgabe 2 – c) (cont’d)

4. When a node u receives a message proposal(u, v ,w), uaccepts the proposal of constructing 4uvw if it belongs toDel(N2(u)) by broadcasting accept(u, v ,w) to N1(u);otherwise, it rejects the proposal by broadcastingreject(u, v ,w) to N1(u).

5. A node u adds the edges uv and uw to its set of incidentedges if the triangle 4uvw is in Del(N2(u)) and both v andw have sent either accept(u, v ,w) or proposal(u, v ,w).

Quellen zum nachlesen

1. A. Okabe, B. Boots, K. Sugihara, and S. N. Chiu, SpatialTessellations – Concepts and Applications of VoronoiDiagrams, 2nd Ed. Chichester: John Wiley & Sons, 1999,pp.59.

2. Li, X.-Y., Calinescu, G., Wan, P., Wang, Y.: LocalizedDelaunay triangulation with application in ad hoc wirelessnetworks. IEEE Transactions on Parallel and DistributedSystems 14(10), pp.1035–1047, 2003. (Kapitel 3.2)

3. Li, X.-Y., Calinescu, G., Wan, P., Wang, Y.: Distributedconstruction of a planar spanner and routing for ad hocwireless networks. Proceedings of the 21th Annual JointConference of the IEEE Computer and CommunicationsSocieties (INFOCOM), pp.1268–1277, 2002. (Lemma 8)