Konvexe Hülle

Konvexe Hülle
Definition konvexe Menge:
Für je zwei beliebige Punkte, die zur Menge gehören, liegt auch stets
deren Verbindungsstrecke ganz in der Menge.
Abbildung:
[Wikipedia]:
Nicht-konvexe Menge (links), konvexe Menge (rechts)
KIT – Institut für Theoretische Informatik
510
Konvexe Hülle
Definition konvexe Menge:
Für je zwei beliebige Punkte, die zur Menge gehören, liegt auch stets
deren Verbindungsstrecke ganz in der Menge.
Abbildung:
[Wikipedia]:
Nicht-konvexe Menge (links), konvexe Menge (rechts)
Definition konvexe Hülle CH(S):
Kleinste konvexe Menge, die S enthält.
KIT – Institut für Theoretische Informatik
510
Obere konvexe Hülle
Entwurfsprinzip: Teile und herrsche (divide and conquer)
I
I
Gegeben: Punktmenge S = {p1 , . . . , pn } ⇢ R2
Gesucht: Konvexe Hülle von S
CH(S) = Bereich,
der von blauen Kanten
umschlossen ist
KIT – Institut für Theoretische Informatik
511
Obere konvexe Hülle
Annahmen
Annahmen oBdA:
I
Sortieren geht mit EREW-PRAM in
T (n) = O(log n) und W (n) = O(n log n)
I
Vereinfachung: n = 2k für k 2 N, Koordinaten sind eindeutig
KIT – Institut für Theoretische Informatik
512
Obere konvexe Hülle
Algorithmische Idee
I
Punkte p und q mit minimaler/maximaler x-Koordinate
sind Teil der CH
I
p und q partitionieren CH in UCH und LCH (lower convex hull)
I
OBdA: Betrachten Upper Convex Hull (UCH)
KIT – Institut für Theoretische Informatik
513
Obere konvexe Hülle
Algorithmische Idee
I
Punkte p und q mit minimaler/maximaler x-Koordinate
sind Teil der CH
I
p und q partitionieren CH in UCH und LCH (lower convex hull)
I
OBdA: Betrachten Upper Convex Hull (UCH)
Vorgehen: Teile und herrsche (divide and conquer)
I
Sortiere Punkte aufsteigend nach x-Koordinate
I
Seien S1 = {p1 , . . . , pn/2 } und S2 = {pn/2+1 , . . . , pn }
KIT – Institut für Theoretische Informatik
513
Obere konvexe Hülle
Algorithmische Idee
I
Punkte p und q mit minimaler/maximaler x-Koordinate
sind Teil der CH
I
p und q partitionieren CH in UCH und LCH (lower convex hull)
I
OBdA: Betrachten Upper Convex Hull (UCH)
Vorgehen: Teile und herrsche (divide and conquer)
I
Sortiere Punkte aufsteigend nach x-Koordinate
I
Seien S1 = {p1 , . . . , pn/2 } und S2 = {pn/2+1 , . . . , pn }
I
I
Angenommen, UCH(S1 ) und UCH(S2 ) sind bekannt
Dann: Brauchen obere gemeinsame Tangente (Stützgerade)
von UCH(S1 ) und UCH(S2 )
KIT – Institut für Theoretische Informatik
513
p
pn
1
Obere konvexe Hülle
Veranschaulichung der oberen gemeinsamen Tangente
Upper common tangent
S2
S1
http://www.cs.yale.edu/homes/arvind/cs424/readings/pram.pdf, 06.07.2015
Figure 5: Determining the convex hull of a set of points.
KIT – Institut für Theoretische Informatik
514
Obere gemeinsame Tangente
I
Bestimmung geht sequentiell in O(log n) Zeit
I
Verfahren: Binäre Suche auf beiden Seiten,
jeweils 9 Fälle testen
KIT – Institut für Theoretische Informatik
515
Obere gemeinsame Tangente
I
Bestimmung geht sequentiell in O(log n) Zeit
I
Verfahren: Binäre Suche auf beiden Seiten,
jeweils 9 Fälle testen
Schraﬃert:
Für binäre Suche
uninteressant
KIT – Institut für Theoretische Informatik
515
Algorithmus UCH
Pseudocode
Eingabe: Menge S von n Punkten in der Ebene (mit obigen Annahmen)
Ausgabe: Obere konvexe Hülle von S
assert x(p1 ) < x(p2 ) < · · · < x(pn )
if n  4 then
1) Brute Force zur Bestimmung von u , der oberen konvexen Hülle von S
else
2a) Teile S in S1 = (p1 , . . . , pn/2 ) und S2 = (pn/2 , . . . , pn )
2b) Parallel: u1 := UCH(S1 ) und u2 := UCH(S2 )
3a) Berechne sequentiell uct (obere gemeinsame Tangente) von u1 und u2
3b) Bestimme u, die obere konvexe Hülle von S, mit Hilfe von uct
return u
KIT – Institut für Theoretische Informatik
516
Algorithmus UCH
Beispiel
Siehe Animation!
KIT – Institut für Theoretische Informatik
517
Algorithmus UCH
PRAM-Analyse
Rekurrenz für T (n):
1. T (n) = O(1), W (n) = O(1)
2. T (n) = T (n/2) + c, W (n) = 2W (n/2)
3. Sequentiell O(log n) Zeit für Bestimmung der oberen Tangente,
dazu T (n) = O(1) und W (n) = O(n) fürs Kombinieren der beiden
oberen Hüllen
KIT – Institut für Theoretische Informatik
518
Algorithmus UCH
PRAM-Analyse
Rekurrenz für T (n):
1. T (n) = O(1), W (n) = O(1)
2. T (n) = T (n/2) + c, W (n) = 2W (n/2)
3. Sequentiell O(log n) Zeit für Bestimmung der oberen Tangente,
dazu T (n) = O(1) und W (n) = O(n) fürs Kombinieren der beiden
oberen Hüllen
Also (für Konstanten a, b, c):
T (n)  T (n/2) + a log n + c
W (n)  2W (n/2) + bn
2 O(log2 n)
2 O(n log n)
KIT – Institut für Theoretische Informatik
518
Algorithmus UCH
PRAM-Analyse
Rekurrenz für T (n):
1. T (n) = O(1), W (n) = O(1)
2. T (n) = T (n/2) + c, W (n) = 2W (n/2)
3. Sequentiell O(log n) Zeit für Bestimmung der oberen Tangente,
dazu T (n) = O(1) und W (n) = O(n) fürs Kombinieren der beiden
oberen Hüllen
Also (für Konstanten a, b, c):
T (n)  T (n/2) + a log n + c
W (n)  2W (n/2) + bn
2 O(log2 n)
2 O(n log n)
Achtung: T (n) ist hier nicht optimal, W (n) schon!
KIT – Institut für Theoretische Informatik
518
Algorithmus UCH
PRAM-Analyse
Rekurrenz für T (n):
1. T (n) = O(1), W (n) = O(1)
2. T (n) = T (n/2) + c, W (n) = 2W (n/2)
3. Sequentiell O(log n) Zeit für Bestimmung der oberen Tangente,
dazu T (n) = O(1) und W (n) = O(n) fürs Kombinieren der beiden
oberen Hüllen
Also (für Konstanten a, b, c):
T (n)  T (n/2) + a log n + c
W (n)  2W (n/2) + bn
2 O(log2 n)
2 O(n log n)
Achtung: T (n) ist hier nicht optimal, W (n) schon!
Brauchen für optimales T (n) schnelleres Conquer!
KIT – Institut für Theoretische Informatik
518
Zusammenfassung
I
Parallele Algorithmen sind nützlich
I
PRAM: Abstraktes Shared-Memory-Modell
I
Work-Time-Prinzip
KIT – Institut für Theoretische Informatik
519
Zusammenfassung
I
Parallele Algorithmen sind nützlich
I
PRAM: Abstraktes Shared-Memory-Modell
I
Work-Time-Prinzip
I
Parallele Entwurfskonzepte:
I
I
I
Baumparadigma
Teile und herrsche
... (! Vorlesung Parallele Algorithmen von Prof. Sanders)
KIT – Institut für Theoretische Informatik
519
Kap. 14: Zusammenfassung
I
Datenstrukturen
I
Algorithmen
I
Entwurfstechniken
I
Analysetechniken
KIT – Institut für Theoretische Informatik
520
Zusammenfassung – Datenstrukturen
I
(doppelt) verkettete Listen, unbeschränkte (zyklische) Felder,
Stapel, FIFOs, deques
I
(beschränktes) Hashing: verketten (universell) / lin. Suche
I
sortiertes Feld
I
Prioritätslisten (binärer Heap) (addressierbar)
I
Implizite Repräsentation vollständiger Bäume
I
Suchbäume: binär, (a, b)-Baum
I
Graphen: Adjazenzfeld / Listen / Matrix
I
Union-Find
KIT – Institut für Theoretische Informatik
521
Zusammenfassung – Algorithmen
I
Langzahlmultiplikation
I
Insertion-, Merge-, Quick-, Heap-, Bucket-, Radix-sort, Selektion
I
BFS, DFS, topologisches Sortieren
I
Kürzeste Wege: Dijkstra, Bellman-Ford
I
MST: Jarník-Prim, Kruskal
I
Parallele Summe
I
Konvexe Hülle auf der PRAM
KIT – Institut für Theoretische Informatik
522
Zusammenfassung – Entwurfstechniken I
I
Iteration/Induktion/Schleifen, Teile-und-Herrsche
I
Schleifen- und Datenstruktur-Invarianten
I
Randomisierung (universelles Hashing, Quicksort,. . . )
I
Graphenmodelle
I
Trennung Mathe $ Funktionalität $ Repräsentation $
Algorithmus $ Implementierung
I
Sonderfälle vermeiden
I
Zeigerdatenstrukturen
I
Datenstrukturen augmentieren (z.B. Teilbaumgrößen)
I
Datenstrukturen unbeschränkt machen
I
Implizite Datenstrukturen (z.B. Intervallgraphen)
KIT – Institut für Theoretische Informatik
523
Zusammenfassung – Entwurfstechniken II
I
Algebra
(Karatsuba, univ. Hashfkt., Matrixmultiplikation für Graphen)
I
Algorithmenschemata (z.B. DFS, lokale Suche)
I
Verwendung abstrakter Problemeigenschaften
(z.B. Schnitt/Kreis-Eigenschaft bei MST)
I
Black-Box-Löser (z.B. lineare Programmierung)
I
Greedy
I
Dynamische Programmierung
I
Systematische Suche
I
Metaheuristiken (z.B. Lokale Suche)
I
Parallelität
KIT – Institut für Theoretische Informatik
524
Zusammenfassung – Analysetechniken
I
Summen, Rekurrenzen, Induktion, Master-Theorem, Abschätzung
I
Asymptotik (O(·), . . . , w(·)), einfache Modelle
I
Analyse im Mittel
I
Amortisierung (z.B. unbeschränkte Felder)
I
Linearität des Erwartungswertes, Indikatorzufallsvariablen
I
Kombinatorik (⇡ Zählen): univ. Hashfunktionen,
untere Sortierschranken (Informationsmenge)
I
Integrale als Summenabschätzung
I
Schleifen/Datenstruktur-(In)varianten
(z.B. (a, b)-Baum, Union-by-rank)
KIT – Institut für Theoretische Informatik
525
Zusammenfassung – weitere Techniken
I
Algorithm Engineering
I
Parameter-Tuning (z.B. Basisfallgröße)
I
High-Level-Pseudocode
I
Dummys und Sentinels (Listen, insertion sort,. . . )
I
Speicherverwaltung
KIT – Institut für Theoretische Informatik
526

Download Report