Upload
others
View
0
Download
0
Embed Size (px)
Citation preview
1
1Christian Knauer
Distanzprobleme in der Ebene
(Literatur: deBerg et al., Kapitel 7,9)
2Distanzprobleme in der Ebene - Christian Knauer
Motivation: Alle nächsten Nachbarn
§ Gegeben: Eine Menge von Punkten P in der Ebene§ Berechne: Zu jedem Punkt aus P alle seine nächsten
Nachbarn
2
3Distanzprobleme in der Ebene - Christian Knauer
Motivation: Minimaler aufspannender Baum
§ Gegeben: Eine Menge von Punkten P in der Ebene§ Berechne: Einen aufspannenden Baum von P der unter allen
aufspannenden Bäumen von P die Summe der Kantenlängen minimiert („minimaler aufspannender Baum“ – MST)
4Distanzprobleme in der Ebene - Christian Knauer
Motivation: Nächster-Nachbar Anfragen
§ Gegeben: Eine Menge von Punkten P in der Ebene§ Berechne: Eine Datenstruktur, mit der man zu einem
Anfragepunkt q?R2 die Menge N(q) aller Punkte aus P finden kann, die näher an q liegen, als alle Punkte aus P\N(q) (Nächster-Nachbar Anfrage)
3
5Distanzprobleme in der Ebene - Christian Knauer
Motivation: Postamtproblem
§ Gegeben: Eine Menge von n Punkten P={p1,…,pn} in der Ebene§ Berechne: Die Unterteilung der Ebene in Regionen N1,…,Nn,
so dass Ni = {p?R2|für alle 1=j=n: d2(p,pi)=d2(p,pj)} (inkl. einer Datenstruktur, mit der man Punktlokalisierungsanfragen für diese Unterteilung beantworten kann)
6Distanzprobleme in der Ebene - Christian Knauer
Definition des Voronoi-Diagramms
§ Def.: Sei P={p1,…,pn}?R2 eine Menge von Punkten, sowie p,q?R2
§ B(p,q) := {x?R2|d2(x,p) = d2(x,q)} bezeichnet die Menge der Punkte in der Ebene, die von p und q den gleichen Abstand haben, den Bisektor von p und q
§ N(p,P) := {x?R2|für alle 1=j=n : d2(x,p) = d2(x,pj)} bezeichnet die Menge der Punkte in der Ebene, die näher an p als an allen Punkten aus P liegen, die Voronoi-Region von p bezüglich P
§ VD(P) := {x?R2|es gibt 1=i<j=n: x?N(pi,P) und x?N(pj,P)} bezeichnet die Menge der Punkte in der Ebene, die an mindestens zwei Voronoi-Regionen beteiligt sind, das Voronoi-Diagram von P
§ Voronoi-Knoten: Punkt, der an mindestens drei Voronoi-Regionenbeteiligt ist
§ Voronoi-Kante: maximal zusammenhängende Menge von Punkten, die an genau zwei Voronoi-Regionen beteiligt sind
4
7Distanzprobleme in der Ebene - Christian Knauer
Elementare Eigenschaften (n=2)
§ Bem.: § B(p,q) ist die Mittelsenkrechte auf der Strecke pq§ N(p,q) ist die von B(p,q) begrenzte Halbebene§ B(p,q) = B(q,p) = VD({p,q})
p
q
B(p,q)N(p,q)
N(q,p)
8Distanzprobleme in der Ebene - Christian Knauer
Eigenschaften des Voronoi-Diagramms
§ Lemma§ Voronoi-Regionen sind konvex§ Voronoi-Kanten sind Strecken oder Strahlen (ohne
Endpunkte), deren Endpunkte Voronoi-Knoten sind(Geraden treten genau dann als Voronoi-Kanten auf, wenn
alle Punkte aus P auf einer Geraden liegen)§ Beweisidee§ N(p,P) = q?P\{p}N(p,q)§ N(p,q) ist eine Halbebene
U
5
9Distanzprobleme in der Ebene - Christian Knauer
Charakterisierung von Punkten
§ Lemma: Betrachte zu einem Punkt x?R2 einen Kreis C(x) mit dem Mittelpunkt x, dessen Radius (der anfangs Null ist) sich langsam vergrössert. Zu einem gewissen Zeitpunkt wird C(x) zum ersten Mal auf einen (oder mehrere) Punkte aus P treffen. Dabei gilt§ C(x) trifft zuerst nur auf p?P gdw.
x liegt in der Voronoi-Region von p§ C(x) trifft zuerst nur auf p,q?P gdw.
x liegt auf der Voronoi-Kante zwischen den Voronoi-Regionen von p und q
§ C(x) trifft zuerst nur auf p1,…,pk?P mit k>2 gdw.x ist ein Voronoi-Knoten, an den die Voronoi-Regionen von p1,…,pk angrenzen
§ Bew. à Übung
10Distanzprobleme in der Ebene - Christian Knauer
Komplexität des Voronoi-Diagramms
§ Satz: |Voronoi-Knoten|+|Voronoi-Kanten|+|Voronoi-Regionen|=O(n)
§ Beweis: VD(P) kann als planarer Graph G=(V,E) mit Knoten-menge V={Voronoi-Knoten}?{v8 } und Kantenmenge E={Voronoi-Kanten} betrachtet werden
(v8 ist ein zusätzlicher, „unendlich ferner“ Knoten, der zu allen unbeschränkten Voronoi-Kanten inzident ist).
Die Behauptung folgt dann mit der Euler-Formel.
v8
6
11Distanzprobleme in der Ebene - Christian Knauer
Einschub: Dualität planarer Graphen
§ Def. Sei G ein planarer Graph. Der duale Graph G* hat als Knoten die Facetten von G und für jede Kante e von G die zwei Facetten f und g trennt gibt es in G* eine Kante e* zwischen den Knoten f* und g*.
G*
G
12Distanzprobleme in der Ebene - Christian Knauer
Eigenschaften der Dualität
§ Satz (ohne Beweis). Für einen zusammenhängenden, planaren Graphen G gilt:§ G* ist planar und zusammenhängend§ G** ist isomorph zu G
7
13Distanzprobleme in der Ebene - Christian Knauer
Definition der Delaunay-Triangulierung
§ Def.: Sei P?R2 eine Menge von Punkten § DT(P) := VD(P)* bezeichnet den dualen Graphen des Voronoi-
Diagramms von P, die Delaunay-Triangulierung von P§ Bem.: DT(P) hat eine natürliche planare Einbettung:§ die Einbettung einer Ecke v=N(p,P) von DT(P) - also einer
Voronoi-Region von VD(P) - ist der Punkt p§ die Einbettung einer Kante e={u,v} von DT(P) ist die Ver-
bindungsstrecke zwischen den Einbettungen von u und v
14Distanzprobleme in der Ebene - Christian Knauer
Triangulierungen von Punktmengen
§ Def.: Eine Triangulierung einer Menge von Punkten P?R2 ist ein planarer Graph mit den Punkten von P als Knoten, bei dem die innere Facetten alle Dreiecke sind, und dessen äussere Facette von den Kanten der konvexen Hülle von P beschränkt wird§ Bem.: Eine planarer Graph G mit den Punkten von P als
Knoten ist genau dann eine Triangulierug von P, wenn keine Kante in G eingefügt werden kann, ohne die Planarität von G zu zerstören („maximal planarer Graph“)§ Bem.: DT(P) ist eine Triangulierung von P gdw. es in P nicht
mehr als drei Punkte gibt, die auf einem leeren Kreis liegen („allgemeine Lage“)
8
15Distanzprobleme in der Ebene - Christian Knauer
Delaunay ßà Voronoi
§ Lemma: Sei P?R2 eine Menge von n Punkten. Dann sind VD(P) und DT(P) in O(n) Zeit auseinander konstruierbar.§ Beweis: à Übung
16Distanzprobleme in der Ebene - Christian Knauer
Anwendungen der Delaunay-Triangulierung
§ Lemma.: Sei P?R2 eine Menge von Punkten und p,q?P. Falls der Kreis (inklusive Rand) mit pq als Durchmesser keine weiteren Punkte von P enthält, dann ist pq eine Kante von DT(P).§ Bew.: Sei m der Mittelpunkt des leeren Kreises C(m) mit pq
als Durchmesser. Aus obiger Charakterisierung von Punkten bezüglich des Voronoi-Diagramms folgt, dass m auf der Voronoi-Kante zwischen den Voronoi-Regionen von p und q liegt, also p und q in DT(P) durch eine Kante verbunden werden.
9
17Distanzprobleme in der Ebene - Christian Knauer
Anwendung: Alle nächsten Nachbarn …
§ Satz.: Sei P?R2 eine Menge von Punkten. Jeder Punkt aus P ist mit seinen nächsten Nachbarn in DT(P) durch eine Kante verbunden.§ Bew.: Sei p?P und q ein nächster
Nachbar von p der in DT(P) nicht mit p verbunden ist. Betrachten wir den Kreis C mit Durchmesser pq. Nach obigem Lemma liegt auf dem Rand oder im Inneren von C mindestens ein Punkt r. Damit ist d2(p,r) < d2(p,q), also q kein nächster Nachbar von p, im Widerspruch zur Annahme.
p qr
C
18Distanzprobleme in der Ebene - Christian Knauer
… Anwendung: Alle nächsten Nachbarn
§ Satz: Kennt man die Delaunay-Triangulierung DT(P) einer Menge von n Punkten P in der Ebene, dann kann man in O(n) Zeit für jeden Punkt aus P alle seine nächsten Nachbarn berechnen.§ Bew.: Um zu p?P alle seine nächsten Nachbarn zu finden,
genügt es nach dem Lemma, die Nachbarn von p in DT(P) zu betrachten. Die Anzahl der insgesamt berechneten Abstände ist somit O(n).
10
19Distanzprobleme in der Ebene - Christian Knauer
Anwendung: Minimaler aufspannender Baum …
§ Satz.: Sei P?R2 eine Menge von Punkten. Die Kanten jedes minimalen aufspannenden Baumes (MST) von P sind Kanten in DT(P).§ Bew.: Angenommen, e={p,q} ist eine Kante in
einem MST S von P, die nicht in DT(P) ist. Nach dem Lemma liegt auf dem Rand oder im Inneren des Kreises C mit Durchmesser pq ein Punkt r, für den damit max(d2(p,r), d2(q,r)) < d2(p,q). Wird e aus S entfernt, so entstehen zwei Bäume T, U die zusammen P aufspannen. Falls r?U (r?T), entsteht durch einfügen der Kante pr (qr) ein aufspannender Baum S‘ mit |S‘| < |S|, im Widerspruch zur Minimalität von S.
p q
r
C
e
T U
20Distanzprobleme in der Ebene - Christian Knauer
… Anwendung: Minimaler aufspannender Baum
§ Satz: Kennt man die Delaunay-Triangulierung DT(P) einer Menge von n Punkten P in der Ebene, kann man in O(n log n) Zeit einen minimalen aufspannenden Baum von P berechnen.§ Bew.: Die Laufzeit des Algorithmus von Prim angewendet auf
die Delaunay-Triangulierung DT(P) ist O(n log n).
11
21Distanzprobleme in der Ebene - Christian Knauer
Berechnung des Voronoi-Diagramms
§ Gegeben: Eine Menge von n Punkten P in der Ebene§ Berechne:§ Das Voronoi-Diagramm VD(P)
(als ebene Unterteilung oder planaren Graphen)§ Eine Datenstruktur, die effizient Punktlokalisierungsanfragen
in VD(P) beantworten kann
22Distanzprobleme in der Ebene - Christian Knauer
Berechnung der Delaunay-Triangulierung
§ Gegeben: Eine Menge von n Punkten P in der Ebene§ Berechne:§ Die Delaunay-Triangulierung DT(P)
(als ebene Unterteilung)§ Eine Datenstruktur, die effizient Punktlokalisierungsanfragen
in DT(P) beantworten kann
12
23Distanzprobleme in der Ebene - Christian Knauer
Untere Schranken
§ Lemma: Die Voronoi-Region eines Punktes p?P ist genau dann unbeschränkt, wenn p auf dem Rand der konvexen Hülle von P liegt.§ Beweis: à Übung§ Folgerung: § aus VD(P) kann in O(n) Zeit die konvexe Hülle von P
konstruiert werden à jeder vergleichsbasierte Algorithmus zur Berechnung von VD(P) benötigt ? (n log n) Schritte § aus DT(P) kann in O(n) Zeit VD(P) konstruiert à jeder
vergleichsbasierte Algorithmus zur Berechnung von DT(P) benötigt ? (n log n) Schritte
24Distanzprobleme in der Ebene - Christian Knauer
Charakterisierung von Delaunay-Dreiecken …
§ Lemma: Seien p,q,r?P und ? das von diesen drei Punkten aufgespannte Dreieck. Dann sind folgende Aussagen äquivalent:1) Das Dreieck ? gehört zu DT(P) („ist ein Delaunay-Dreieck“)2) Der Umkreismittelpunkt von ? ist ein Knoten von VD(P)3) Der Umkreis von ? enthält keinen Punkt von P
§ Beweis …: § (2) ó (3): vgl. Charakterisierung von Punkten im Voronoi-
Diagramm
13
25Distanzprobleme in der Ebene - Christian Knauer
… Charakterisierung von Delaunay-Dreiecken
§ … Beweis: § (1) ó (3): „<=“ Falls der Umkreis von ? leer
ist, so ist der Um-kreismittelpunkt m von ? ein Knoten von VD(P) (wg. der Äquivalenz (2) ó (3)). m ist der Schnittpunkt der Bisektoren von pq,qr,pr (Mittelsenkrechten), so dass in einer Umgebung von m diese Bisektoren als Voronoi-Kanten in VD(P) existieren. Damit gehört ? zu DT(P).„=>“ Angenommen im Umkreis C von ? gibt es einen weiteren Punkt s?P. Falls s??, dann gehört ? nicht zu DT(P). Falls s?C\? (o.B.d.A.) zwischen p und q liegt, dann ist jedes x?B(p,q) entweder näher zu s als zu p und q, oder näher zu r als zu p und q. Damit gibt es keine Voronoi-Kante zwischen den Voronoi-Regionen von p und q und die Kante pq(und damit ?) gehört nicht zu DT(P)
p q
rC
s
B(p,q)
26Distanzprobleme in der Ebene - Christian Knauer
Charakterisierung Delaunay-Triangulierung 1
§ Lemma: Sei T eine Triangulierung einer Menge von n Punkten P in der Ebene. Dann ist T=DT(P) gdw. der Umkreis jedes Dreiecks aus T leer ist.§ Bew.: Folgt unmittelbar aus der Charakterisierung von
Delaunay-Dreiecken.
14
27Distanzprobleme in der Ebene - Christian Knauer
Lokal zulässige Dreiecke
§ Def.: Sei T eine Triangulierung einer Menge von n Punkten P in der Ebene. Ein Dreieck ? von T heisst lokal zulässig, falls die Ecken der zu ? benachbarten Dreiecke nicht im Umkreis von ? liegen. T heisst lokal zulässig, wenn in T alle Dreiecke lokal zulässig sind.
28Distanzprobleme in der Ebene - Christian Knauer
Charakterisierung Delaunay-Triangulierung 2
§ Lemma (ohne Beweis): Sei T eine Triangulierung einer Menge von n Punkten P in der Ebene. § T=DT(P) gdw. T lokal zulässig ist.§ T=DT(P) gdw. T den kleinsten Innenwinkel maximiert.
15
29Distanzprobleme in der Ebene - Christian Knauer
Lokal zulässige Vierecke
§ Def.: Sei T eine Triangulierung einer Menge von Punkten P in der Ebene. Ein Viereck ? von P ist ein Paar von be-nachbarten Dreiecken ? =? (p,q,r) und ? *=? (p,q,s) von P (p,q,r,s?P). Das Viereck ? heisst lokal zulässig, wenn s nicht im Umkreis von ? liegt (und damit r nicht im Umkreis von ? * liegt)
30Distanzprobleme in der Ebene - Christian Knauer
Charakterisierung Delaunay-Triangulierung 3
§ Lemma: Sei T eine Triangulierung einer Menge von n Punkten P in der Ebene. Dann ist T=DT(P) gdw. jedes Viereck in T lokal zulässig ist.§ Bew.: Sei ? ein Dreieck von T. ? bildet zusammen mit allen
benachbarten Dreiecken ? * lokal zulässige Vierecke. Damit ist auch ? lokal zulässig und T=DT(P).
16
31Distanzprobleme in der Ebene - Christian Knauer
Lawson-Flip
§ Def.: Sei T eine Triangulierung einer Menge von Punkten in der Ebene und ? ein lokal unzulässiges Dreieck von T. Sei ? * ein zu ? benachbartes Dreieck, dessen Ecke nicht im Umkreis von ? liegt. Die Operation, bei der wir in dem von ? und ? * gebildetem konvexen Viereck ? die gemeinsameKante e von ? und ? * durch die andere Diagonale von ? ersetzen heisst Lawson-Flip in ? .
?? *
? ?
e
32Distanzprobleme in der Ebene - Christian Knauer
Eigenschaften des Lawson-Flip
§ Lemma: Sei T eine Triangulierung einer Menge von Punkten in der Ebene und ? ein lokal unzulässiges konvexes Viereck in T. Nach einem Lawson-Flip in ? ist dieses Viereck lokal zulässig. § Beweis: à Übung
17
33Distanzprobleme in der Ebene - Christian Knauer
Algorithmus zur Berechnung von DT(P)
Eingabe: eine Triangulierung T einer Menge P von n Punkten in der Ebene
Ausgabe: die Delaunay-Triangulierung DT(P) von P
while T enthält ein lokal unzulässiges konvexes Viereck ? doführe den Lawson-Flip in ? durch
§ Bem.:§ Man kann zeigen, dass eine geflippte Kante nie wieder
erscheint. Daher ist die Delaunay-Triangulierung nach O(n2) Lawson-Flips erreicht.§ Man kann je zwei Triangulierungen T, T* durch O(n2)
Lawson-Flips ineinander überführen