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 stetsderen 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

Konvexe Hülle

Definition konvexe Menge:Für je zwei beliebige Punkte, die zur Menge gehören, liegt auch stetsderen 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 511

Obere konvexe HülleEntwurfsprinzip: Teile und herrsche (divide and conquer)

I Gegeben: Punktmenge S = {p1, . . . ,pn}⇢ R2

I Gesucht: Konvexe Hülle von S

CH(S) = Bereich,der von blauen Kanten

umschlossen ist

KIT – Institut für Theoretische Informatik 512

Obere konvexe HülleAnnahmen

Annahmen oBdA:I Sortieren geht mit EREW-PRAM in

T (n) = O(logn) und W (n) = O(n logn)I Vereinfachung: n = 2k für k 2 N, Koordinaten sind eindeutig

KIT – Institut für Theoretische Informatik 513

Obere konvexe HülleAlgorithmische Idee

I Punkte p und q mit minimaler/maximaler x-Koordinatesind 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-KoordinateI Seien S1 = {p1, . . . ,pn/2} und S2 = {pn/2+1, . . . ,pn}I Angenommen, UCH(S1) und UCH(S2) sind bekanntI Dann: Brauchen obere gemeinsame Tangente (Stützgerade)

von UCH(S1) und UCH(S2)

KIT – Institut für Theoretische Informatik 513

Obere konvexe HülleAlgorithmische Idee

I Punkte p und q mit minimaler/maximaler x-Koordinatesind 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-KoordinateI Seien S1 = {p1, . . . ,pn/2} und S2 = {pn/2+1, . . . ,pn}

I Angenommen, UCH(S1) und UCH(S2) sind bekanntI Dann: Brauchen obere gemeinsame Tangente (Stützgerade)

von UCH(S1) und UCH(S2)

KIT – Institut für Theoretische Informatik 513

Obere konvexe HülleAlgorithmische Idee

I Punkte p und q mit minimaler/maximaler x-Koordinatesind 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-KoordinateI Seien S1 = {p1, . . . ,pn/2} und S2 = {pn/2+1, . . . ,pn}I Angenommen, UCH(S1) und UCH(S2) sind bekanntI Dann: Brauchen obere gemeinsame Tangente (Stützgerade)

von UCH(S1) und UCH(S2)

KIT – Institut für Theoretische Informatik 514

Obere konvexe HülleVeranschaulichung der oberen gemeinsamen Tangente

14 Copyright c Siddhartha Chatterjee, Jan Prins 1997–2002

2

5

4

3

1 2 2 1 1

7

8

9

6 6 6

6

1

25 6

7 8 93 4

Figure 4: Building the Euler tour representation of a tree from a pointer-based representation.

p1 p

n

UH(S)

Upper common tangent

S1S2

Figure 5: Determining the convex hull of a set of points.http://www.cs.yale.edu/homes/arvind/cs424/readings/pram.pdf, 06.07.2015

KIT – Institut für Theoretische Informatik 515

Obere gemeinsame Tangente

I Bestimmung geht sequentiell in O(logn) ZeitI Verfahren: Binäre Suche auf beiden Seiten,

jeweils 9 Fälle testen

Schraffiert:Für binäre Suche

uninteressant

KIT – Institut für Theoretische Informatik 515

Obere gemeinsame Tangente

I Bestimmung geht sequentiell in O(logn) ZeitI Verfahren: Binäre Suche auf beiden Seiten,

jeweils 9 Fälle testen

Schraffiert:Für binäre Suche

uninteressant

KIT – Institut für Theoretische Informatik 516

Algorithmus UCHPseudocode

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

else2a) 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 u23b) Bestimme u, die obere konvexe Hülle von S , mit Hilfe von uct

return u

KIT – Institut für Theoretische Informatik 517

Algorithmus UCHBeispiel

Siehe Animation!

KIT – Institut für Theoretische Informatik 518

Algorithmus UCHPRAM-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(logn) Zeit für Bestimmung der oberen Tangente,

dazu T (n) = O(1) und W (n) = O(n) fürs Kombinieren der beidenoberen Hüllen

Also (für Konstanten a,b,c):

T (n) T (n/2)+a logn+ c 2 O(log2 n)

W (n) 2W (n/2)+bn 2 O(n logn)

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

Algorithmus UCHPRAM-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(logn) Zeit für Bestimmung der oberen Tangente,

dazu T (n) = O(1) und W (n) = O(n) fürs Kombinieren der beidenoberen Hüllen

Also (für Konstanten a,b,c):

T (n) T (n/2)+a logn+ c 2 O(log2 n)

W (n) 2W (n/2)+bn 2 O(n logn)

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

Algorithmus UCHPRAM-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(logn) Zeit für Bestimmung der oberen Tangente,

dazu T (n) = O(1) und W (n) = O(n) fürs Kombinieren der beidenoberen Hüllen

Also (für Konstanten a,b,c):

T (n) T (n/2)+a logn+ c 2 O(log2 n)

W (n) 2W (n/2)+bn 2 O(n logn)

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

Algorithmus UCHPRAM-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(logn) Zeit für Bestimmung der oberen Tangente,

dazu T (n) = O(1) und W (n) = O(n) fürs Kombinieren der beidenoberen Hüllen

Also (für Konstanten a,b,c):

T (n) T (n/2)+a logn+ c 2 O(log2 n)

W (n) 2W (n/2)+bn 2 O(n logn)

Achtung: T (n) ist hier nicht optimal, W (n) schon!

Brauchen für optimales T (n) schnelleres Conquer!

KIT – Institut für Theoretische Informatik 519

Zusammenfassung

I Parallele Algorithmen sind nützlichI PRAM: Abstraktes Shared-Memory-ModellI Work-Time-Prinzip

I Parallele Entwurfskonzepte:I BaumparadigmaI Teile und herrscheI ... (! Vorlesung Parallele Algorithmen von Prof. Sanders)

KIT – Institut für Theoretische Informatik 519

Zusammenfassung

I Parallele Algorithmen sind nützlichI PRAM: Abstraktes Shared-Memory-ModellI Work-Time-Prinzip

I Parallele Entwurfskonzepte:I BaumparadigmaI Teile und herrscheI ... (! Vorlesung Parallele Algorithmen von Prof. Sanders)

KIT – Institut für Theoretische Informatik 520

Kap. 14: Zusammenfassung

I DatenstrukturenI AlgorithmenI EntwurfstechnikenI Analysetechniken

KIT – Institut für Theoretische Informatik 521

Zusammenfassung – Datenstrukturen

I (doppelt) verkettete Listen, unbeschränkte (zyklische) Felder,Stapel, FIFOs, deques

I (beschränktes) Hashing: verketten (universell) / lin. SucheI sortiertes FeldI Prioritätslisten (binärer Heap) (addressierbar)I Implizite Repräsentation vollständiger BäumeI Suchbäume: binär, (a,b)-BaumI Graphen: Adjazenzfeld / Listen / MatrixI Union-Find

KIT – Institut für Theoretische Informatik 522

Zusammenfassung – Algorithmen

I LangzahlmultiplikationI Insertion-, Merge-, Quick-, Heap-, Bucket-, Radix-sort, SelektionI BFS, DFS, topologisches SortierenI Kürzeste Wege: Dijkstra, Bellman-FordI MST: Jarník-Prim, KruskalI Parallele SummeI Konvexe Hülle auf der PRAM

KIT – Institut für Theoretische Informatik 523

Zusammenfassung – Entwurfstechniken I

I Iteration/Induktion/Schleifen, Teile-und-HerrscheI Schleifen- und Datenstruktur-InvariantenI Randomisierung (universelles Hashing, Quicksort,. . . )I GraphenmodelleI Trennung Mathe $ Funktionalität $ Repräsentation $

Algorithmus $ ImplementierungI Sonderfälle vermeidenI ZeigerdatenstrukturenI Datenstrukturen augmentieren (z.B. Teilbaumgrößen)I Datenstrukturen unbeschränkt machenI Implizite Datenstrukturen (z.B. Intervallgraphen)

KIT – Institut für Theoretische Informatik 524

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 GreedyI Dynamische ProgrammierungI Systematische SucheI Metaheuristiken (z.B. Lokale Suche)I Parallelität

KIT – Institut für Theoretische Informatik 525

Zusammenfassung – Analysetechniken

I Summen, Rekurrenzen, Induktion, Master-Theorem, AbschätzungI Asymptotik (O(·), . . . , w(·)), einfache ModelleI Analyse im MittelI Amortisierung (z.B. unbeschränkte Felder)I Linearität des Erwartungswertes, IndikatorzufallsvariablenI Kombinatorik (⇡ Zählen): univ. Hashfunktionen,

untere Sortierschranken (Informationsmenge)I Integrale als SummenabschätzungI Schleifen/Datenstruktur-(In)varianten

(z.B. (a,b)-Baum, Union-by-rank)

KIT – Institut für Theoretische Informatik 526

Zusammenfassung – weitere Techniken

I Algorithm EngineeringI Parameter-Tuning (z.B. Basisfallgröße)I High-Level-PseudocodeI Dummys und Sentinels (Listen, insertion sort,. . . )I Speicherverwaltung