WEBVTT

00:00.540 --> 00:01.600
So, schönen guten Tag.

00:01.740 --> 00:06.840
Ich begrüße Sie zur vorletzten Veranstaltung Effiziente Algorithmen.

00:07.900 --> 00:08.980
Letztes Mal bzw.

00:10.080 --> 00:13.980
neulich hat mir Herr Schukla erzählt, dass viele von Ihnen

00:13.980 --> 00:17.620
Schwierigkeiten haben mit der parallelen Variante des Warschall

00:17.620 --> 00:20.240
-Algorithmus, bei den Graph-Algorithmen.

00:21.400 --> 00:23.700
Ich weiß nicht, ob das bei Ihnen, die jetzt hier sitzen, der Fall ist.

00:24.300 --> 00:26.640
Aber ich dachte, es ist vielleicht ganz hilfreich, wenn ich das

00:26.640 --> 00:30.580
nochmal versuche, einmal kurz zu erläutern, was da eigentlich abläuft.

00:31.640 --> 00:34.840
Und da müssen wir einmal kurz hier die richtige Stelle finden.

00:34.960 --> 00:37.720
Ich weiß gar nicht, wo das genau...

00:38.540 --> 00:41.680
Genau, auf dem Schlag die richtige Folie gefunden.

00:42.580 --> 00:45.160
Also, das war hier...

00:45.160 --> 00:46.780
Das war...

00:46.780 --> 00:50.540
Das ist der Warschall-Algorithmus.

00:50.680 --> 00:52.500
Beziehungsweise, wenn wir hier nochmal eine Folie weiter

00:52.500 --> 00:53.880
zurückgehen...

00:53.880 --> 00:55.700
Sie erinnern sich, worum es geht.

00:55.700 --> 00:58.600
Ich habe jetzt hier die Annotationen nicht weggewischt.

01:00.240 --> 01:03.720
Sie erinnern sich daran, dass beim Warschall-Algorithmus es darum

01:03.720 --> 01:07.060
geht, die transitive Hülle eines Graphen zu berechnen.

01:07.400 --> 01:11.140
Also, ich muss feststellen, ob es Wege gibt.

01:11.200 --> 01:14.580
Ich muss alle Wege zwischen irgendwelchen zwei Punkten feststellen.

01:14.720 --> 01:16.800
Also, ich will feststellen, welche Punkte sind von welchen anderen

01:16.800 --> 01:17.380
erreichbar.

01:18.180 --> 01:21.120
Istgleichberechnung der transitiven Hülle eines Graphen.

01:21.160 --> 01:22.460
Oder einer Adjacenzmatrix.

01:22.460 --> 01:28.220
Sie erinnern sich, dass man hier dabei dieses schöne Bild hat.

01:28.620 --> 01:30.680
Bei diesem schönen Algorithmus.

01:31.180 --> 01:32.980
Dreifach geschachtelte Schleife.

01:33.700 --> 01:37.580
Ich habe letztes Mal in der Wiederholung noch kurz darauf hingewiesen.

01:38.020 --> 01:38.940
Eigentlich ganz ähnlich.

01:39.040 --> 01:40.780
Auf den ersten Blick sieht es genauso aus wie eine Matrix

01:40.780 --> 01:41.520
-Modifikation.

01:42.280 --> 01:43.620
Es steht hier so schön drin.

01:43.740 --> 01:45.240
AIJ gleich AIJ.

01:46.120 --> 01:47.260
Das kennen wir.

01:47.260 --> 01:55.480
Bei der Matrix-Modifikation stand CIJ gleich CIJ plus AIK mal BKJ.

01:56.360 --> 01:59.260
Hier steht jetzt AIK und AKJ.

01:59.400 --> 02:02.420
Oder AIJ oder AIK und AKJ.

02:02.500 --> 02:03.420
Das ist aber ganz ähnlich.

02:04.740 --> 02:07.260
So ähnlich, als wenn man eine Matrix mit sich selbst modifiziert.

02:08.840 --> 02:11.420
Matrix-Modifikation macht einmal mit sich selbst modifiziert.

02:11.500 --> 02:12.740
Aber das ist etwas anderes, was hier steht.

02:12.740 --> 02:18.740
Der Unterschied ist eben, dass wir hier da oben das K stehen haben.

02:18.820 --> 02:19.820
Richtig eingekringelt.

02:20.380 --> 02:21.740
Und dann kommen erst die I und J.

02:22.560 --> 02:25.260
Das K war bei der Matrix-Modifikation die innerste Schleife.

02:26.280 --> 02:30.400
Das ändert für die Komplexität des Algorithmus zunächst mal gar

02:30.400 --> 02:30.580
nichts.

02:30.640 --> 02:32.640
Anzahl der Operationen, wenn Sie sich das hier anschauen.

02:33.020 --> 02:34.880
Dreifach geschachtelte Schleife, Aufwand Nr.

02:34.900 --> 02:35.240
3.

02:35.560 --> 02:37.440
Man kann das ein bisschen genauer analysieren.

02:37.440 --> 02:43.700
Hier ist alles das, worauf ich bei der Matrix-Modifikation mit

02:43.700 --> 02:49.180
aufpassen, dass man nicht unnötig Zugriffe macht auf Matrix-Elemente

02:49.180 --> 02:49.840
und ähnliche Dinge.

02:50.120 --> 02:51.680
Das ist hier alles nicht berücksichtigt.

02:52.280 --> 02:53.740
Das muss man natürlich alles noch mit einbauen.

02:53.900 --> 02:56.620
Man wird das niemals so schreiben wie hier, sondern wird das versuchen

02:56.620 --> 03:00.300
ein bisschen anders zu machen, um ein bisschen Aufwand einzusparen.

03:00.380 --> 03:01.440
Aber das ist alles so Kleinkram.

03:02.320 --> 03:04.420
Dass man versucht, das effizienter zu machen.

03:04.500 --> 03:06.720
Da hatte ich Ihnen genügend Methoden zu erzählen.

03:06.720 --> 03:10.760
Das Wesentliche ist zu sehen, ich habe hier auf einmal die beiden IJ

03:10.760 --> 03:13.700
-Schleifen innen drin und außen die K-Schleife.

03:14.300 --> 03:16.220
Und ich kann das nicht einfach umdrehen.

03:16.740 --> 03:18.480
Das verändert die Struktur des Algorithmus.

03:18.900 --> 03:22.920
Ich mache erst etwas für K gleich 1 und das für alle IJ, dann etwas

03:22.920 --> 03:26.520
für K gleich 2 und das für alle IJ und so weiter.

03:26.640 --> 03:33.000
Und das Problem ist eben, wenn ich mir das anschaue, dass ich, anders

03:33.000 --> 03:36.480
als bei der Matrix-Modifikation, wenn ich versuche, das jetzt parallel

03:36.480 --> 03:37.020
zu machen.

03:37.760 --> 03:40.620
Also jetzt haben wir hier die parallele Variante.

03:41.480 --> 03:44.220
Bei der Matrix-Modifikation konnte ich schön die Elemente so

03:44.220 --> 03:47.380
durchschieben durch die Matrix und hatte da immer die richtigen

03:47.380 --> 03:50.180
Elemente, die ich brauchte, genau an der richtigen Stelle.

03:50.580 --> 03:54.840
Ich konnte das sehr schön mit dem Mapping-Ansatz machen.

03:54.940 --> 03:58.600
Ich kann hier auch einen Mapping-Ansatz machen, aber da sind die

03:58.600 --> 04:00.200
Distanzen nicht alle so schön homogen.

04:00.400 --> 04:04.060
Also das, was da innen drin steht, das passt nicht so gut.

04:04.060 --> 04:05.560
Es sieht alles ein bisschen anders aus.

04:06.740 --> 04:10.000
Also über den Mapping-Ansatz das abzubilden, ist etwas schwieriger.

04:10.560 --> 04:12.880
Kann man sich auch nochmal angucken, will ich jetzt aber gar nicht

04:12.880 --> 04:13.120
machen.

04:13.920 --> 04:17.540
Und die Idee bei dieser Parallelen, also das, was hier aufgemalt war,

04:17.840 --> 04:22.480
wenn ich zum Beispiel für dieses Element A3-2, die ganzen

04:22.480 --> 04:25.860
Kombinationen der Elemente, die ich mir anschaue, die ich für K gleich

04:25.860 --> 04:31.020
1 alle mir angucken muss, da muss ich eben auf A1-2 zugreifen, das

04:31.020 --> 04:36.680
sitzt hier oben und auf A3-1, die beiden muss ich irgendwie

04:36.680 --> 04:36.960
kombinieren.

04:38.800 --> 04:43.600
Oder ich muss eben auch hier dieses A, was haben wir denn hier noch,

04:44.100 --> 04:49.020
A1 -2, ich muss die richtigen Elemente jedenfalls kombinieren hier

04:49.020 --> 04:49.220
drin.

04:49.660 --> 04:54.040
Und das ist alles etwas anders.

04:54.640 --> 04:58.860
Und die Idee war, dass man eben hier folgendes macht, dass man die

04:58.860 --> 05:03.060
erste Zeile, weil ich weiß, ich brauche die erste, für K gleich 1

05:03.060 --> 05:09.760
brauche ich die Information aus der ersten Zeile, alle A1j-Elemente,

05:09.900 --> 05:14.000
die brauche ich hier in der Zeile 3 zum Beispiel.

05:14.420 --> 05:16.660
Ich brauche die auch in der Zeile 2, ich brauche die auch in der Zeile

05:16.660 --> 05:17.040
4.

05:17.820 --> 05:23.180
Dieses A1-2 brauche ich in jeder Zeile, die unten drunter steht.

05:23.300 --> 05:26.960
Das A1-1 oder A1-3 brauche ich in jeder Zeile, die unten drunter

05:26.960 --> 05:27.280
steht.

05:28.020 --> 05:29.300
Für K gleich 1.

05:30.660 --> 05:34.920
Ich brauche aber auch jedes Element, das hier in der ersten Spalte

05:34.920 --> 05:35.280
steht.

05:35.960 --> 05:38.380
Das brauche ich auch in allen anderen Elementen.

05:38.720 --> 05:43.400
Weil hier steht A irgendein I und dann 1.

05:44.100 --> 05:47.640
Und für K gleich 1 brauche ich also diese Elemente in allen anderen,

05:48.360 --> 05:50.880
in denen ich jetzt diese Berechnung mache, die hier nochmal

05:50.880 --> 05:55.360
eingekringelt ist, Aij gleich Aij oder Aik und Akj.

05:55.520 --> 06:01.080
Für K gleich 1 brauche ich also an jeder Position IJ ein Element aus

06:01.080 --> 06:03.580
der ersten Zeile und eins aus der ersten Spalte.

06:05.900 --> 06:08.760
Wenn ich das parallel machen will, muss ich dafür sorgen, dass die

06:08.760 --> 06:09.760
irgendwie dahin kommen.

06:10.740 --> 06:15.420
Das Problem ist, wenn ich eben an irgendeiner Position ein Element aus

06:15.420 --> 06:17.980
der ersten Zeile und ersten Spalte brauche, dann muss ich die da

06:17.980 --> 06:19.880
irgendwie hinbringen, das ist lange Distanz.

06:19.880 --> 06:22.780
Lange Distanz heißt, das dauert eine Weile, bis die da hinkommen.

06:25.120 --> 06:28.780
Aber wir gucken uns trotzdem an, wie man die Elemente dort hinbringen

06:28.780 --> 06:29.080
kann.

06:29.300 --> 06:34.260
Da war die Idee, dass ich einfach alle Informationen aus der ersten

06:34.260 --> 06:37.180
Zeile einfach über das Feld verteile.

06:38.280 --> 06:42.580
Und alle Informationen aus der ersten Spalte über das Feld verteile.

06:44.320 --> 06:48.900
Und zwar so, das ist noch ein besonderer Trick dabei, dass

06:48.900 --> 06:55.860
anschließend die erste Zeile unten steht und die anderen eins nach

06:55.860 --> 06:56.660
oben gerutscht sind.

06:57.120 --> 07:00.440
Das heißt, ich schiebe nicht einfach nur die erste Zeile nach unten

07:00.440 --> 07:04.740
durch, die Informationen darüber, sondern ich vertausche im Prinzip

07:04.740 --> 07:10.120
die erste Zeile mit der zweiten, dann die erste Zeile mit der dritten,

07:10.420 --> 07:14.260
mit der vierten usw., bis die erste Zeile ganz unten steht und alle

07:14.260 --> 07:16.460
anderen sind bei diesem Vertauschen eins nach oben gerutscht.

07:19.080 --> 07:23.240
Und dadurch habe ich also anschließend hier die erste Zeile unten und

07:23.240 --> 07:25.820
hier oben steht dann die zweite Zeile.

07:27.700 --> 07:29.540
Das gleiche mache ich mit der ersten Spalte.

07:30.260 --> 07:34.020
Die schiebe ich eben einfach ganz rüber über das Feld nach rechts und

07:34.020 --> 07:38.420
vertausche aber jeweils mit der nächsten Spalte.

07:39.020 --> 07:42.360
Und habe anschließend die erste Spalte rechts und die Spalten zwei,

07:42.540 --> 07:44.960
drei bis N eins nach links verschoben.

07:45.660 --> 07:47.540
Und das können wir uns jetzt genauer angucken.

07:48.440 --> 07:49.140
Also hier steht es nochmal.

07:50.200 --> 07:52.620
Das schauen wir uns hier nochmal an, was da genau passiert.

07:53.620 --> 07:55.200
Das ist das, was wir machen wollen.

07:56.200 --> 07:59.460
Erste Zeile nach unten, erste Spalte nach rechts verschieben.

08:00.560 --> 08:03.560
Das ist unsere Ausgangsmatrix, das ist also unsere

08:03.560 --> 08:08.020
Erreichbarkeitsmatrix, beziehungsweise die Adjacenzmatrix zu Anfang.

08:08.900 --> 08:11.180
Das ist unsere Adjacenzmatrix, das Graph.

08:12.960 --> 08:14.960
So, da stehen die ganzen Elemente drin.

08:15.080 --> 08:20.440
Jetzt will ich das, was in der ersten Zeile steht, hier nach unten

08:20.440 --> 08:20.840
schieben.

08:21.400 --> 08:28.980
Das heißt, in jede einzelne Zeile rein, schreibe ich A11 in jedes

08:28.980 --> 08:29.920
Element hier unten runter.

08:30.080 --> 08:34.420
Hier habe ich also A11, A11, A11, da steht auch A11.

08:35.060 --> 08:37.420
Das eigentliche Element, das so stand, ist aber eines nach oben

08:37.420 --> 08:37.940
gerutscht.

08:38.420 --> 08:43.400
Das heißt, hier steht jetzt A21 drin, da steht A31 drin und da steht

08:43.400 --> 08:43.800
A41.

08:44.720 --> 08:45.940
Außerdem das A11.

08:47.980 --> 08:53.060
Und das, was vorher die erste Spalte war, diese Zeile ist

08:53.060 --> 08:54.400
runtergerutscht in die ganz unten.

08:54.920 --> 08:59.420
Das heißt, ich habe jetzt hier unten drin stehen die Elemente, ganz

08:59.420 --> 09:01.760
unten habe ich die erste Zeile im Prinzip zweimal drin stehen.

09:02.920 --> 09:07.480
Und oben drüber steht halt A41, A42, A43, A44.

09:07.640 --> 09:10.860
Das sind also die Elemente hier der vorher vierten Zeile.

09:11.580 --> 09:14.900
Und dazu steht noch die Information aus der ersten Zeile.

09:17.580 --> 09:22.860
Und jetzt mache ich das Gleiche mit dieser Matrix, indem ich diese

09:22.860 --> 09:25.760
erste Spalte jetzt nach rechts rüberschiebe.

09:25.760 --> 09:35.140
Natürlich nur die Elemente A21, A31, A41, A11.

09:36.380 --> 09:38.080
Jetzt schiebe ich die nach rechts rüber.

09:39.240 --> 09:42.700
Und lasse die dort jeweils liegen, schiebe das, was da rechts daneben

09:42.700 --> 09:43.520
stand, nach links rüber.

09:43.640 --> 09:47.420
Also diese A22 wandert als anschließend hier vorne in der linken

09:47.420 --> 09:47.920
Spalte.

09:48.680 --> 09:50.400
Und dazu habe ich das A21 noch stehen.

09:51.280 --> 09:52.000
Das Element.

09:52.880 --> 09:57.100
Und entsprechend steht A21 jetzt hier in jedem Element in der ersten

09:57.100 --> 09:59.360
Zeile.

10:00.080 --> 10:04.860
Das A31 steht in jedem Element der zweiten Zeile und so weiter.

10:05.080 --> 10:09.780
Und das A11, äh Quatsch, ja doch, das A11 steht jetzt hier unten.

10:10.320 --> 10:14.260
Das A11 war ja hier hergerutscht durch das Verschieben aus den ersten

10:14.260 --> 10:14.780
Vorgangen.

10:14.840 --> 10:18.820
Jetzt habe ich also anschließend genau das, was hier beschrieben war.

10:18.820 --> 10:26.940
Der Prozessor I-1, J-1 enthält AIJ, AI1 und A1J.

10:27.220 --> 10:37.080
Also der Prozessor I1, das ist unser Prozessor I1, der enthält AIJ,

10:38.900 --> 10:40.060
also A22.

10:41.080 --> 10:41.800
Das ist das hier.

10:42.900 --> 10:49.600
Wenn das I-1, I-1 und J-1 ist, habe ich also hier A22 drin stehen.

10:49.720 --> 10:51.060
Das ist dieses AIJ.

10:51.760 --> 10:53.000
Der hält AI1.

10:54.260 --> 10:56.260
Das ist unser A21.

10:57.420 --> 10:59.400
Und der enthält A1J.

11:00.400 --> 11:02.060
Das ist das hier oben, das A12.

11:02.940 --> 11:08.260
Und jetzt kann ich, das gilt für jeden Prozessor hier drin, der

11:08.260 --> 11:12.180
enthält genau die Elemente, die er braucht, um diese Berechnung

11:12.180 --> 11:14.900
auszuführen für K gleich 1.

11:16.060 --> 11:21.360
Und jedem Prozessor kann ich ausführen AIJ gleich AIJ, also A34 zum

11:21.360 --> 11:28.440
Beispiel gleich A34 oder A31 und A14.

11:30.280 --> 11:34.320
Das heißt, jetzt habe ich genau in jedem Prozessor genau die richtigen

11:34.320 --> 11:34.900
Elemente drin.

11:36.260 --> 11:38.980
Das ist also erstmal das Prinzip, das man sich überlebt.

11:40.100 --> 11:44.520
Ich muss alle Elemente aus der ersten Zeile über die Spalten verteilen

11:44.520 --> 11:47.780
und alle aus der ersten Spalte über die Zeilen verteilen.

11:47.920 --> 11:49.780
Dann habe ich genau die Informationen in jeder Zelle.

11:50.780 --> 11:53.520
Ich kann also, egal wo ich hingucke, da sind die richtigen Elemente

11:53.520 --> 11:55.380
zusammen, jetzt kann ich etwas tun.

11:56.220 --> 12:03.400
Der Aufwand dafür ist natürlich sehr hoch, weil dieses Rüberschieben,

12:03.920 --> 12:05.480
das ist lineare Aufwand.

12:05.540 --> 12:11.620
Also Aufwand N für das Verschieben nach unten, Aufwand N für das

12:11.620 --> 12:12.500
Verschieben nach rechts.

12:12.980 --> 12:14.780
Die Operation ist konstanter Aufwand.

12:16.000 --> 12:18.180
Nochmal zwei Operationen, und und dann oder.

12:19.320 --> 12:22.080
Das ist also nicht weiter schlimm, aber ich habe einen linearen

12:22.080 --> 12:23.560
Aufwand jeweils.

12:23.560 --> 12:26.480
Und jetzt ist eben die Idee, dass man sich anguckt, welche Operationen

12:26.480 --> 12:27.460
führe ich eigentlich aus?

12:27.540 --> 12:29.120
Kann ich das irgendwie anders organisieren?

12:30.860 --> 12:33.860
Ja, und da ist eben die Idee, was wir hier machen, ist eigentlich,

12:34.580 --> 12:37.680
dass wir im ersten Prozessor...

12:37.680 --> 12:41.480
Also um, wenn wir uns angucken, ich mische das mal weg.

12:42.060 --> 12:45.280
Wenn wir uns angucken, was hier im ersten Prozessor passiert, wie sind

12:45.280 --> 12:46.560
die Elemente dort hingekommen?

12:49.890 --> 12:57.810
Es hat doch der Prozessor, das A22 hat er von unten gelesen.

12:59.550 --> 13:01.450
Beziehungsweise ich kann das auch hier aufmalen.

13:01.770 --> 13:04.330
Der liest, nein, es ist so.

13:05.130 --> 13:08.210
Er liest dieses Element von unten,

13:11.820 --> 13:17.160
dann der rechts daneben liest das Element, schiebt das rüber.

13:17.160 --> 13:27.740
Außerdem wird das A1 und das A12 wandern auch darüber und das A11

13:27.740 --> 13:28.980
wandert auch darunter.

13:32.090 --> 13:34.290
Das heißt, ich muss diese beiden Operationen machen.

13:39.130 --> 13:44.960
Und damit das A22 dahin wandert...

13:46.320 --> 13:49.060
Ich muss ja das irgendwie da hochkriegen.

13:49.660 --> 13:56.720
Muss ich hier entsprechend einmal das von dort gelesen haben.

13:57.700 --> 14:00.360
Und es muss dann eben auch da hinwandern.

14:01.660 --> 14:09.000
Das sind eine Reihe von Elementaroperationen, die ich machen muss.

14:09.180 --> 14:11.920
Das ist nicht mit einer Operation zu machen, das sind mehrere Takte,

14:12.000 --> 14:12.860
die ich hier ausführen muss.

14:12.860 --> 14:16.120
Aber das sind alles lokale Operationen, durch die ich dafür sorge,

14:17.000 --> 14:20.080
dass Elemente, also solche Wege laufen können.

14:20.220 --> 14:24.960
Erstmal nach links, also diesen Weg hier darüber und dann so hoch muss

14:24.960 --> 14:25.680
das laufen können.

14:27.420 --> 14:29.940
Das sind zwei Operationen, die ich machen muss.

14:30.560 --> 14:32.360
Lokale Operationen.

14:32.360 --> 14:38.140
Also wenn ich jetzt auf der nächsten Folie, das war das, was jetzt

14:38.140 --> 14:42.160
hier steht, um das so in Berechnungswellen zu machen.

14:43.640 --> 14:52.140
Ich muss also das, was auf der Folie 8 gerade entstand, ich muss das

14:52.140 --> 14:56.440
nicht so machen, dass ich diese ganze Zeile so runterschiebe und die

14:56.440 --> 15:01.180
ganze Spalte so rüberschiebe, sondern ich kann das eben auch in

15:01.180 --> 15:02.480
Diagonalen laufen lassen.

15:04.200 --> 15:06.880
Ich kann die Operation, ich kann das so sukzessive, ich kann praktisch

15:06.880 --> 15:10.300
anfangen, diese Zeile darunter zu schieben und ich kann anfangen, die

15:10.300 --> 15:11.420
Spalte darüber zu schieben.

15:11.580 --> 15:13.660
Man muss mir das praktisch so wieder vorstellen als diagonal

15:13.660 --> 15:14.400
verschränkt.

15:15.060 --> 15:18.820
Also wenn ich diese Elemente da so durchschiebe und dann läuft das

15:18.820 --> 15:22.360
genauso ab, dann habe ich aber, wie ich sagte, die Anzahl der

15:22.360 --> 15:28.000
Operationen, die ich tatsächlich machen muss, das ist nicht nur eine

15:28.000 --> 15:32.480
Diagonale, also ein Befehl, den ich da mache, um dieses Verschieben

15:32.480 --> 15:36.700
der Elemente dort zu simulieren, sondern das sind mehrere Operationen,

15:36.740 --> 15:40.720
die ich machen muss, bis ich tatsächlich die richtigen Elemente dort

15:40.720 --> 15:42.380
nach oben hinbekommen habe.

15:42.500 --> 15:45.960
Also nacheinander muss ich das simulieren, dass ich ein Element nach

15:45.960 --> 15:50.320
unten schiebe und dieses Verschieben der ersten Spalte und der ersten

15:50.320 --> 15:53.780
Zeile, das muss ich hier durch mehrere lokale Operationen machen.

15:55.020 --> 16:00.980
Und das ist auch in der Variante, die hier steht, natürlich so, dass

16:00.980 --> 16:03.320
ich das durch lokale Operationen machen muss, aber das ist einfach

16:03.320 --> 16:04.180
eine andere Anordnung.

16:06.100 --> 16:10.660
Und dann stelle ich eben fest, ich kann einfach das zeitlich

16:10.660 --> 16:11.100
verändern.

16:11.100 --> 16:16.340
Ich mache das nicht gleichzeitig, wenn ich also hier mir anschaue, was

16:16.340 --> 16:21.060
hier passiert, ich mache diese Operation nicht gleichzeitig, dass ich

16:21.060 --> 16:26.600
hier rüberlese, da rüberlese und gleichzeitig das hier mache, sondern

16:26.600 --> 16:27.640
das mache ich zeitlich versetzt.

16:29.280 --> 16:33.040
Wenn ich das zeitlich versetzt mache, dann bin ich eben da oben in der

16:33.040 --> 16:38.100
Ecke schon fertig und kann dann dort die nächste Operation machen.

16:38.100 --> 16:41.320
Ich kann also, weil ich ja anschließend hier das Element A22 stehen

16:41.320 --> 16:45.520
habe, kann ich anschließend den gleichen Prozess nochmal loslaufen

16:45.520 --> 16:45.820
lassen.

16:47.700 --> 16:51.960
Während in dem Rest, das ist jetzt eben auf der Folie 9 alles drauf,

16:52.460 --> 16:55.880
kann eben alles erledigen, was hier oben in der Ecke erforderlich ist,

16:57.120 --> 17:02.620
kann in dem Bereich hier noch zu tun haben mit der davorliegenden

17:02.620 --> 17:06.560
Verschiebung und hier genauso, das kann so diagonal durchlaufen.

17:07.300 --> 17:13.780
Das ist einfach nur ein Umgruppieren der Befehle und diejenigen, die

17:13.780 --> 17:16.820
nicht logisch voneinander abhängig sind, die kann ich halt

17:16.820 --> 17:21.320
gleichzeitig laufen lassen.

17:23.180 --> 17:27.620
Und dadurch spare ich Zeit, weil der Aufwand, die Anzahl der

17:27.620 --> 17:32.240
Diagonalen, die ich brauche, um die Elemente geeignet zu verschieben,

17:32.240 --> 17:37.820
der ist konstant, das sind so Größenordnung 4, 5 Befehle, die ich

17:37.820 --> 17:40.800
machen muss und dann bin ich damit durch.

17:41.500 --> 17:44.400
Und dann kann ich eben in den Diagonalen die nächsten Berechnungen

17:44.400 --> 17:44.960
laufen lassen.

17:45.640 --> 17:50.380
Das habe ich jetzt hier nicht nochmal aufgedrüselt, welche konkreten

17:50.380 --> 17:51.660
Befehle ich jetzt hier aufsuche.

17:51.760 --> 17:56.340
Im Prinzip sind das genau die Befehle, die ich hier machen muss, um

17:56.340 --> 17:57.560
diese Verschiebung hinzubekommen.

17:57.560 --> 18:11.320
Und um diesen Schritt zu machen, da muss ich halt nur dafür sorgen,

18:11.480 --> 18:15.980
dass ich das Element nach unten schiebe und das nach oben schiebe.

18:16.220 --> 18:17.780
Und das mache ich in allen gleichzeitig.

18:19.760 --> 18:21.880
Die muss ich im Prinzip vertauschen.

18:23.760 --> 18:32.180
Schiebe das 2,1 nach oben, das 1,1 nach unten und kann das im Prinzip

18:32.180 --> 18:34.380
auf allen Elementen machen.

18:37.640 --> 18:43.880
Dadurch habe ich dann diese Operation erstmal nur hier in der...

18:45.540 --> 18:49.940
nur diese Operation, wo nur Elemente in den Spalten jeweils verbunden

18:49.940 --> 18:50.320
sind.

18:50.680 --> 18:54.660
Um von dort nach dort zu kommen, muss ich entsprechend diese Operation

18:54.660 --> 18:58.560
machen, dass ich hier etwas verschiebe und so weiter.

19:00.100 --> 19:01.960
Und das in diesen...so.

19:04.120 --> 19:08.340
Wenn ich das Ganze...ups, nee, da nicht, sondern auf dem anderen ist

19:08.340 --> 19:08.640
egal.

19:08.940 --> 19:12.000
Also ich muss das nicht da machen, sondern ich muss das natürlich hier

19:12.000 --> 19:12.560
auf diesem machen.

19:12.680 --> 19:15.520
Da würde ich es ja verschieben, da muss ich die Operation ausführen.

19:16.740 --> 19:17.180
So.

19:17.620 --> 19:22.740
Und das, was ich eben hier mache, erst die ganzen senkrechten

19:22.740 --> 19:27.040
Operationen, dann die ganzen horizontalen Operationen, das bringt mir

19:27.040 --> 19:28.860
dann diese Endmatrix, die ich hier habe.

19:29.580 --> 19:32.340
Und ich sage eben einfach, ich mache nicht erst alle senkrechten und

19:32.340 --> 19:36.080
dann alle horizontalen, sondern ich verknüpfe das, ich mache erst hier

19:36.080 --> 19:40.640
eben nur das, was sich auf dieses bezieht, diese Operation, die

19:40.640 --> 19:46.240
Operation und kriege dadurch genau die richtigen Informationen

19:46.240 --> 19:46.620
darüber.

19:48.340 --> 19:49.640
Ja, das ist der ganze Trick.

19:52.360 --> 19:55.080
Also, ich hoffe, dass es dadurch klarer geworden ist.

19:56.760 --> 19:57.820
Sie gucken immer noch so rum, die Leute.

19:59.700 --> 20:00.300
Immer noch Fragen?

20:03.360 --> 20:04.760
Sie können nicht so richtig fragen.

20:05.580 --> 20:05.960
Klar,

20:14.550 --> 20:16.630
aber im Prinzip ist das...

20:16.630 --> 20:19.750
Also wir müssen einfach die entsprechend umordnen.

20:20.650 --> 20:24.490
Ich könnte Ihnen auch ein, das jetzt als Befehlshistorisches Feld

20:24.490 --> 20:27.070
hinschreiben und die Folge der Befehle, die man dort ausführen muss,

20:27.130 --> 20:28.410
könnte ich Ihnen auch noch dazu aufmalen.

20:28.470 --> 20:31.210
Das habe ich jetzt nicht gemacht, aber das ist wirklich nur eine

20:31.210 --> 20:33.830
Umgruppierung in der zeitlichen Reihenfolge.

20:34.190 --> 20:36.270
Das sind genau die Befehle, die man hier aufmacht.

20:36.990 --> 20:37.090
Ja?

20:38.230 --> 20:38.510
Gut.

20:38.510 --> 20:42.690
Das also noch mal zu diesem Warschall-Algorithmus und dann will ich

20:42.690 --> 20:44.690
hier mal damit mal aufhören.

20:45.690 --> 20:47.970
Und es ist, das Wesentliche ist eben einfach, dass man hier sieht, ich

20:47.970 --> 20:51.870
habe eine algorithmische Struktur und das war eben dieses, ich hoffe,

20:51.990 --> 20:56.190
das war es auf der Folie 7, nein, auf der Folie 6, das ist eben

20:56.190 --> 20:59.270
einfach das Wesentliche, das ist das interessante Erkenntnis gewesen,

20:59.550 --> 21:04.690
dass man hier eine algorithmische Struktur hat, die man bei einer

21:04.690 --> 21:07.890
ganzen Reihe von Problemen in Graphen wiederfindet.

21:08.510 --> 21:11.190
Und deswegen hat man mit dieser einen Überlegung, wie ich den

21:11.190 --> 21:17.670
Warschall -Algorithmus parallelisiere, eine parallele Variante für

21:17.670 --> 21:21.890
viele Graph-Probleme erzeugt, mit der man also viele Graph-Probleme

21:21.890 --> 21:23.090
sinnvoll bearbeiten kann.

21:24.170 --> 21:29.190
Und also eine ganze Reihe von Algorithmen, die man also auf Graphen

21:29.190 --> 21:33.150
macht, sind also entweder von diesem Typ oder von dem Typ Matrix

21:33.150 --> 21:33.870
-Modifikation.

21:36.550 --> 21:39.530
Und das heißt, die haben zwar unterschiedliche Namen, der eine heißt

21:39.530 --> 21:41.930
dann Floyd, der andere heißt Dijkstra, der andere heißt noch wieder

21:41.930 --> 21:44.730
irgendwie anders, aber das sind im Prinzip alles die gleichen

21:44.730 --> 21:48.370
Strukturen, da ist nur die innerste Zeile leicht verändert.

21:49.090 --> 21:49.630
Das ist alles.

21:50.830 --> 21:55.850
Ja, das ist ein ganz klarer Entwurfsprinzip für Algorithmen.

21:56.670 --> 22:04.170
Gut, jetzt zurück zu unserem eigentlichen Thema, bei dem wir jetzt

22:04.170 --> 22:04.510
sind.

22:05.450 --> 22:11.270
Nämlich zu dem Thema der algorithmischen Geometrie.

22:12.730 --> 22:16.670
Und da habe ich letztes Mal Ihnen schon einiges darüber erzählt, über

22:16.670 --> 22:21.130
Motivation, dass man in solchen schönen zig verschiedenen Gebilden

22:21.130 --> 22:23.530
irgendwelche Operationen machen will, dass man es mit geometrischen

22:23.530 --> 22:24.350
Problemen zu tun hat.

22:24.410 --> 22:27.010
Und das Interessante ist eben erst mal zu überlegen, was für Arten von

22:27.010 --> 22:29.150
geometrischen Problemen muss man eigentlich mit dem Rechner

22:29.150 --> 22:29.650
bearbeiten.

22:30.390 --> 22:33.470
Und da gibt es halt eine Vielfalt verschiedener und wir haben uns dann

22:33.470 --> 22:35.450
ein paar ganz einfache rausgenommen.

22:36.150 --> 22:38.430
Wir haben uns zunächst mal angeguckt, was gibt es für geometrische

22:38.430 --> 22:39.870
Objekte, die uns interessieren.

22:40.750 --> 22:43.870
Und haben die dann weiter...

22:46.670 --> 22:48.690
Wie kann man die darstellen?

22:49.450 --> 22:55.310
Die Datenstruktur spielt nicht eine Rolle.

22:56.530 --> 23:00.230
Das war alles nicht so wahnsinnig interessant.

23:00.470 --> 23:01.710
Alles relativ naheliegend.

23:02.270 --> 23:04.110
Und dann haben wir uns hier mit...

23:04.110 --> 23:06.150
Klar, Zeitaufwand, Platzaufwand spielt eine Rolle.

23:06.150 --> 23:09.490
Es sind arithmetisch logische Operationen hier im Wesentlichen dabei.

23:10.130 --> 23:12.150
Zum Teil auch ein paar Vergleichsoperationen.

23:13.830 --> 23:17.910
Aber es ist nicht so einfach wie bei den algebraischen Problemen und

23:17.910 --> 23:20.590
bei den Sortierproblemen, dass ich sagen kann, ich gucke mir nur

23:20.590 --> 23:22.330
Vergleiche an oder nur arithmetische Operationen.

23:22.690 --> 23:24.530
Hier muss ich mir schon beides angucken.

23:25.850 --> 23:29.290
Und das Interessante ist, dass ich hier auf einmal über

23:29.290 --> 23:32.430
Vorbereitungsmaßnahmen den Aufwand für die eigentlichen Operationen

23:32.430 --> 23:33.570
drastisch reduzieren kann.

23:33.570 --> 23:37.710
Hier war das erste Beispiel gewesen, festzustellen, wie viele Punkte

23:37.710 --> 23:38.970
innerhalb eines Rechtecks liegen.

23:39.070 --> 23:43.430
Da hatten wir gesehen, wenn wir das naiv machen, haben wir Aufwand der

23:43.430 --> 23:44.730
Linearsen, der Anzahl der Punkte.

23:45.190 --> 23:49.990
Wenn wir es geschickt machen, dann kam man darauf, dass man durch eine

23:49.990 --> 23:56.590
gewisse Vorbereitung, bei der man für jedes solche Rechteck, das durch

23:56.590 --> 23:59.550
die Koordinatlinien aufgespannt wird, da im Prinzip zunächst mal

23:59.550 --> 24:04.810
berechnet, wie viele Punkte kleinergleich diesem jeweiligen Rechteck

24:04.810 --> 24:10.210
sind, dann kann man durch vier solche Punktanfragen die Antwort finden

24:10.210 --> 24:13.290
darauf, wie viele Punkte in einem Rechteck liegen.

24:13.450 --> 24:17.490
Und das war dann jeweils Aufwandblock N, weil man die geeignet

24:17.490 --> 24:22.110
angeordnet hat und konnte also hier durch binäre Suche im Prinzip

24:22.110 --> 24:26.990
jeweils das Rechteck bestimmen und dann die ermittelte Zahl angeben.

24:27.330 --> 24:32.510
Das war dann logarithmischer Aufwand für diese Anzahl der Punkte in

24:32.510 --> 24:32.930
einem Rechteck.

24:33.530 --> 24:35.770
Und dann haben wir als nächstes angeguckt, Polygone.

24:36.610 --> 24:37.610
Da waren wir noch mittendrin.

24:37.970 --> 24:42.770
Wir haben das Problem, dass wir für ein einfaches Polygon, das also

24:42.770 --> 24:46.690
eine Ebene in zwei disjunkte Flächen teilt, einmal das innere und das

24:46.690 --> 24:49.490
äußere Sein des Polygons, dass wir feststellen wollen, ob ein

24:49.490 --> 24:52.430
beliebiger Punkt im Inneren oder im Äußeren liegt.

24:52.430 --> 24:57.250
Das ist ein Problem, das man durchaus in verschiedensten Situationen

24:57.250 --> 24:57.710
haben kann.

24:57.810 --> 25:01.570
Ich habe Ihnen so ein paar aus dem praktischen Leben vorgestellt, aber

25:01.570 --> 25:04.590
es gibt auch am Rechner einige, die aus dem praktischen Leben zu tun

25:04.590 --> 25:08.030
haben, aber dort ein bisschen formaler sind, dass Sie also irgendein

25:08.030 --> 25:12.150
Element auswählen wollen und Sie klicken drauf und müssen sehen, habe

25:12.150 --> 25:15.350
ich das Element ausgewählt oder habe ich die Umgebung ausgewählt.

25:16.190 --> 25:18.330
Solche Dinge muss man halt richtig erkennen können.

25:18.330 --> 25:21.510
Und hier hatten wir festgestellt, hier können wir auch mit

25:21.510 --> 25:22.710
Vorbereitung nichts machen.

25:22.810 --> 25:29.750
Der Aufwand, um für ein beliebiges Polygon festzustellen, ist ein

25:29.750 --> 25:33.770
Punkt drin oder draußen, der war linear in der Anzahl der Punkte des

25:33.770 --> 25:35.470
Polygons oder in der Anzahl der Kanten.

25:35.630 --> 25:39.450
Wir mussten feststellen, wie viele Kanten des Polygons geschnitten

25:39.450 --> 25:42.070
werden auf dem Weg von dem Punkt nach außen.

25:42.810 --> 25:46.010
Wenn wir einen sicheren Punkt haben, der außen liegt, brauchen wir nur

25:46.010 --> 25:49.950
die Anzahl der Punkte zwischen dem Punkt, von dem wir es wissen wollen

25:49.950 --> 25:53.290
und dem, der sicher außen ist oder einer, der sicher innen ist,

25:54.490 --> 25:59.430
feststellen, Anzahl der Schnittpunkte mit Kanten, wenn die gerade ist,

26:00.110 --> 26:05.290
dann wissen wir, wenn wir Verbindung zu einem äußeren Punkt haben, wir

26:05.290 --> 26:07.270
haben eine gerade Zahl von Schnittpunkten, dann ist der andere Punkt

26:07.270 --> 26:07.790
auch draußen.

26:08.230 --> 26:12.570
Wenn es eine ungerade Anzahl von Schnitten ist, dann haben wir einen

26:12.570 --> 26:13.290
anderen Punkt drin.

26:14.370 --> 26:23.090
Und dann kam diese Frage, wenn wir jetzt ein konvexes Polygon haben,

26:23.290 --> 26:26.190
dort sieht das anders aus.

26:26.250 --> 26:29.270
Da können wir etwas mehr machen und das war die letzte Folie beim

26:29.270 --> 26:29.930
letzten Mal.

26:30.770 --> 26:37.910
Also wir haben ein konvexes Polygon, außerdem einfach, also in dem

26:37.910 --> 26:42.110
Fall sollte es schon einfach sein, ansonsten hätten Sie nicht

26:42.110 --> 26:44.010
unbedingt ein konvexes Polygon.

26:45.730 --> 26:51.290
Also konvex heißt eben, ist klar, je zwei Punkte im Inneren dieses

26:51.290 --> 26:55.790
Polygons liegen, oder die Verbindungslinie von je zwei Punkten liegt

26:55.790 --> 26:57.030
immer vollständig innen drin.

26:57.710 --> 27:00.870
Das ist die übliche Definition und nicht konvex wäre eben ein

27:00.870 --> 27:02.970
Beispiel, das hier rechts dann angegeben ist.

27:03.530 --> 27:08.630
Da wären Punkte durch eine gerade Linie verbunden, die halt zum Teil

27:08.630 --> 27:09.270
außen liegt.

27:10.510 --> 27:16.550
Und für jedes konvexe Polygon wissen wir halt, dass jeder Punkt im

27:16.550 --> 27:22.350
Inneren eines solchen Polygons, da muss ich erstmal umschalten, jeder

27:22.350 --> 27:28.510
Punkt im Inneren, wenn wir von dem aus ein Strahl nach außen schicken,

27:28.970 --> 27:33.170
dann schneidet der nur eine Kante, genau eine Kante des Polygons.

27:33.750 --> 27:34.890
Ansonsten würde er nicht innen sein.

27:35.690 --> 27:38.270
Dadurch, dass es konvex ist, wissen wir halt, es kann nur ein

27:38.270 --> 27:38.930
Schnittpunkt liegen.

27:40.630 --> 27:41.050
So.

27:41.670 --> 27:45.510
Und jetzt wollen wir feststellen, ob ein Punkt tatsächlich im Inneren

27:45.510 --> 27:46.210
liegt oder außen.

27:47.330 --> 27:53.330
Und dazu machen wir jetzt folgendes, hier ist unser Punkt Q, von dem

27:53.330 --> 27:55.170
wir wissen wollen, liegt er innen oder außen.

27:56.850 --> 28:00.150
Und wir bestimmen einfach irgendeinen Punkt im Inneren von P, den

28:00.150 --> 28:05.470
können wir uns einfach ermitteln, indem wir zwei nicht benachbarte

28:05.470 --> 28:08.510
Punkte des Polygons nehmen und irgendeinen Punkt zwischen diesen

28:08.510 --> 28:08.870
beiden.

28:09.210 --> 28:10.590
Dann haben wir einen, der im Inneren liegt.

28:11.610 --> 28:13.310
Wie Sie den Punkt im Inneren finden, ist völlig egal.

28:13.430 --> 28:21.770
Sie nehmen sich irgendeinen her und jetzt teilen wir das Polygon durch

28:21.770 --> 28:31.670
Strahlen von dem Punkt R aus zu den Eckpunkten unseres Polygons in N

28:31.670 --> 28:32.830
Sektoren auf.

28:35.050 --> 28:38.570
Ich kann hier einen Strahl schicken, jeweils von dem Punkt R aus zu

28:38.570 --> 28:39.510
den ganzen Eckpunkten.

28:41.570 --> 28:45.950
Ich habe ein Polygon gegeben durch eine Folge von Punkten.

28:45.950 --> 28:53.110
Also, der Polygon ist gegeben durch eine Folge von Punkten P1, P2, P3

28:53.110 --> 28:55.510
und so weiter bis PN.

28:57.310 --> 28:59.950
Das heißt, es fängt irgendwo an, meinetwegen hier, wenn das 1 ist,

29:00.030 --> 29:03.590
dann habe ich hier 2, 3, 4, 5 und so weiter.

29:05.590 --> 29:11.310
Das heißt, ich habe eine Anordnung dieser Strahlen und damit eine

29:11.310 --> 29:12.570
Anordnung der Sektoren.

29:14.270 --> 29:21.130
Und jetzt will ich wissen, für irgendeinen beliebigen Punkt Q liegt

29:21.130 --> 29:23.310
der im Polygon oder außerhalb des Polygons.

29:24.290 --> 29:29.590
Und dazu will ich einfach feststellen durch binäre Suche, ich habe

29:29.590 --> 29:33.370
eine sortierte Folge von Sektoren, in welchem Sektor liegt Q.

29:35.710 --> 29:38.310
Was ist jetzt eine binäre Suche auf solchen Sektoren?

29:39.350 --> 29:42.870
Normalerweise binäre Suche, sagt sich das in der sortierten Folge, ich

29:42.870 --> 29:47.850
gehe in die Mitte, ist das Element kleiner oder größer, dann gehe ich

29:47.850 --> 29:51.550
vielleicht hier wieder in die Mitte und so weiter, da vielleicht

29:51.550 --> 29:56.710
wieder in die Mitte, bis ich irgendwo den Bereich gefunden habe, wo

29:56.710 --> 29:57.990
das Element tatsächlich liegt.

29:58.650 --> 29:59.890
Das ist binäre Suche.

30:00.530 --> 30:02.690
Wie mache ich das bei so einem... Was heißt das?

30:02.690 --> 30:08.730
Ich fange hier in der Mitte an, also wenn ich N solche Sektoren habe,

30:08.830 --> 30:14.050
fange ich also bei dem Strahl von R nach P in halbe an und schaue

30:14.050 --> 30:21.650
nach, liegt, wenn das meinetwegen hier in halbe ist, liegt das Q, ist

30:21.650 --> 30:22.970
das kleiner oder größer?

30:23.150 --> 30:25.650
Also liegt das in einem kleineren Sektor oder in einem größeren

30:25.650 --> 30:26.110
Sektor?

30:26.110 --> 30:31.450
Dazu muss ich aber wissen, ob dieses Q links oder rechts von einer

30:31.450 --> 30:32.170
Geraden liegt.

30:34.090 --> 30:35.550
Wie kann ich das denn feststellen?

30:36.350 --> 30:38.750
Ob der Punkt oberhalb oder unterhalb liegt?

30:38.870 --> 30:43.190
Also wenn der da liegt oder so, liegt der jetzt unterhalb, oberhalb

30:43.190 --> 30:44.090
oder hier?

30:44.650 --> 30:45.530
Wie kann ich das feststellen?

30:45.610 --> 30:46.830
Was brauche ich hier für Operationen?

30:48.710 --> 30:53.210
Man kann irgendwie Winkel vergleichen oder Radialkoordinaten

30:53.210 --> 30:54.950
bestimmen, versuchen das zu vergleichen.

30:55.830 --> 30:59.470
Das Wesentliche ist, ich muss wissen, ob ein Punkt Q, der mich

30:59.470 --> 31:03.050
interessiert, ob der links oder rechts von einer Geraden ist.

31:04.090 --> 31:08.590
Wenn ich weiß, der liegt links, wenn ich so von hier gucke, da in die

31:08.590 --> 31:14.990
Richtung wäre jetzt links, gucke in die Richtung, dann weiß ich, ich

31:14.990 --> 31:19.290
muss entsprechend bei der binären Suche in der oberen Hälfte gucken.

31:20.410 --> 31:22.350
Die Frage ist, wie mache ich das?

31:24.230 --> 31:30.150
Und dazu muss man sich überlegen, wenn ich also den Winkel betrachte,

31:30.350 --> 31:32.550
Q, R, P, I.

31:33.650 --> 31:36.990
Auch hier Q, R, P, I.

31:37.710 --> 31:46.110
Das eine Mal ist dieser Winkel eine Linksdrehung, das ist hier der

31:46.110 --> 31:46.390
Fall.

31:47.550 --> 31:51.730
Ich drehe mich an diesem Punkt nach links und hier Q, R, P, I, da

31:51.730 --> 31:52.630
drehe ich mich nach rechts.

31:54.270 --> 31:54.750
Okay.

31:55.350 --> 31:56.710
Man kann verschiedene Sachen sich überlegen.

31:57.490 --> 31:59.130
Ich kann mir auch dieses Bild hier aufmalen.

32:00.390 --> 32:01.610
Ich stelle folgendes fest.

32:02.430 --> 32:05.830
Ich habe hier gewisse Flächen schraffiert.

32:07.490 --> 32:16.290
Und wenn der Punkt Q links liegt von dieser Gerade, die durch R und P,

32:16.330 --> 32:23.090
I geht, dann ist diese Fläche hier, also diese Fläche liegt dann dort

32:23.090 --> 32:27.310
oberhalb von diesem Trapez, das da unten drunter ist.

32:27.310 --> 32:32.410
Und wenn der rechts liegt, wenn er auf der anderen Seite liegt, dann

32:32.410 --> 32:36.970
würde diese Fläche hier, die hier angedeutet ist, Fläche dieses

32:36.970 --> 32:39.170
Dreiecks, würde innerhalb dieses Trapezes liegen.

32:40.270 --> 32:43.990
Jetzt versuche ich zunächst mal, die Fläche dieses Dreiecks zu

32:43.990 --> 32:44.310
bestimmen.

32:46.110 --> 32:47.410
Und das mache ich so.

32:48.810 --> 32:51.130
Hier steht es gleich da, wie kann man das machen?

32:51.330 --> 32:54.350
Ich bestimme einfach die verschiedenen Flächen.

32:55.350 --> 33:00.210
Ich bestimme hier eine Fläche eines Trapezes.

33:00.330 --> 33:01.090
Welches Trapez?

33:01.850 --> 33:03.550
YI plus Y halbe.

33:03.670 --> 33:05.630
YI ist diese Strecke.

33:06.010 --> 33:06.810
Das ist YI.

33:07.490 --> 33:09.510
Y ist diese Strecke.

33:10.590 --> 33:16.890
Das heißt, ich gucke mir zunächst mal dieses große Trapez an.

33:18.310 --> 33:24.550
Die Fläche dieses Trapez hier unten ist genau XI minus X.

33:27.610 --> 33:32.750
Das heißt, ich habe hier Fläche dieses Trapezes, wissen wir, YI plus Y

33:32.750 --> 33:35.230
halbe mal XI minus X.

33:36.110 --> 33:44.490
Produkt der beiden Baslinien hier mal Höhe.

33:44.530 --> 33:45.790
Durch zwei.

33:46.330 --> 33:49.190
Dann ist das nächste auch wieder Fläche eines Trapezes.

33:49.790 --> 33:52.550
Und da habe ich jetzt Y und T und X minus S stehen.

33:52.670 --> 33:54.890
Das hier ist X minus S.

33:57.670 --> 34:01.050
Und dann habe ich hier T und Y, also hier haben wir T.

34:01.890 --> 34:02.610
Noch ein Trapez.

34:03.450 --> 34:06.870
Jetzt habe ich also dieses Trapez, ich habe dieses Trapez mir

34:06.870 --> 34:07.470
angeguckt.

34:07.470 --> 34:14.310
Und das dritte, davon ziehe ich jetzt ab, das Trapez, das hier durch

34:14.310 --> 34:16.750
die Punkte P, I und R aufgespannt wird.

34:17.190 --> 34:20.730
Da habe ich also YI und T halbe mal XI minus S.

34:21.430 --> 34:25.190
Das ist also hier die gesamte Linie.

34:25.710 --> 34:32.610
Wenn ich das abziehe, dann bleibt doch genau hier dieses Dreieck

34:32.610 --> 34:32.930
übrig.

34:34.730 --> 34:37.870
Ich habe die beiden erst addiert, dann habe ich das abgezogen, bleibt

34:37.870 --> 34:38.290
die Fläche übrig.

34:38.370 --> 34:39.910
Das ist also genau die Fläche dieses Dreiecks.

34:41.170 --> 34:44.750
Wenn ich mir das genauer angucke, was ich hier berechne, dann ist das

34:44.750 --> 34:51.410
gerade der halbe Wert der Determinanten, die hier aufgeschrieben ist,

34:52.350 --> 34:52.970
dieser Matrix.

34:53.910 --> 35:00.570
Ich habe die drei Punkte Q, R und PI aufgeschrieben, jeweils noch eine

35:00.570 --> 35:01.470
1 rechts daneben.

35:01.470 --> 35:05.390
Wenn ich hier die Determinante ausrechne und durch zwei dividiere,

35:05.490 --> 35:07.110
kommt genau dieser Term raus.

35:10.910 --> 35:13.570
Jetzt wissen wir, wie groß die Fläche ist.

35:13.790 --> 35:15.210
Wir wollten noch gar keine Fläche bestimmen.

35:15.930 --> 35:20.810
Wir wollten wissen, liegt das Q links von R, PI oder liegt das rechts

35:20.810 --> 35:21.450
von R, PI.

35:22.610 --> 35:24.330
Ich stelle mir aber eines fest.

35:25.070 --> 35:30.610
Wenn das Q rechts von R, PI liegt, dann ist der Wert, der hier steht,

35:31.970 --> 35:33.950
kleiner.

35:34.990 --> 35:39.710
Dann wäre der negativ, weil dann ja der Punkt, wenn der da gelegen

35:39.710 --> 35:43.930
hätte, dann wäre ja die Summe der beiden Trapeze eine kleinere Fläche

35:43.930 --> 35:47.790
gewesen, als das Trapez, das durch R und PI aufgespart wird.

35:48.550 --> 35:50.150
Dann wäre der Wert, den wir rauskriegen, negativ.

35:51.690 --> 35:54.970
Also ich hätte eigentlich, die Fläche des Dreiecks ist nicht genau

35:54.970 --> 35:56.970
das, was hier steht, sondern der Betrag davon.

36:01.310 --> 36:05.230
Und wenn das Q links von R, PI liegt, dann ist der Wert dieser

36:05.230 --> 36:06.690
Determinante tatsächlich größer geworden.

36:07.930 --> 36:10.770
Das heißt, was mich interessiert, ist nicht der Wert, also der

36:10.770 --> 36:11.950
absolute Wert dieser Fläche.

36:12.070 --> 36:14.850
Was interessiert mich nur, ist das, was da rauskommt, größer 0 oder

36:14.850 --> 36:15.450
kleiner 0.

36:16.730 --> 36:18.930
Das heißt, ich brauche gar nicht, mich zweizudividieren, das

36:18.930 --> 36:19.890
interessiert mich überhaupt nicht.

36:20.470 --> 36:23.310
Ich muss nur herausfinden, hat diese Determinante einen Wert, der

36:23.310 --> 36:24.750
größer 0 ist oder kleiner 0 ist.

36:25.390 --> 36:27.550
Ich brauche mich also nicht um irgendwelche Winkel zu kümmern,

36:27.650 --> 36:29.910
Winkelberechnungen, ich brauche keine trigonometrischen Funktionen und

36:29.910 --> 36:30.410
ähnliches.

36:30.410 --> 36:37.430
Ich brauche nur diese einfache Determinante hier auszurechnen und zu

36:37.430 --> 36:40.650
sehen, ist der Wert, der da rauskommt, größer 0 oder kleiner 0.

36:41.050 --> 36:46.710
Und dann weiß ich, ob der Punkt Q links oder rechts der gerade liegt,

36:46.810 --> 36:49.190
die durch R und PI bestimmt ist.

36:51.290 --> 36:55.470
Und das ist also eine wichtige Erkenntnis, wie man das einfach

36:55.470 --> 36:56.070
ausrechnet.

36:56.510 --> 36:59.210
Das hätte ich auch kürzer machen können, wenn Sie Experten sind in

36:59.210 --> 37:01.790
Geometrie, hätten Sie das alles gewusst, dass man das sofort so

37:01.790 --> 37:02.450
ausrechnen kann.

37:03.290 --> 37:06.090
Immer, an dass Sie das nicht so direkt gewusst haben, dass das so der

37:06.090 --> 37:06.450
Fall ist.

37:07.090 --> 37:09.070
Wer hat das gewusst, von vornherein, von Ihnen?

37:10.370 --> 37:11.850
Ne, okay, dann war das das Neueste.

37:12.930 --> 37:14.730
Also, das ist jetzt hier nochmal aufgeschrieben.

37:16.070 --> 37:21.190
Diese Determinante ist also größer 0, wenn das Q links liegt und

37:21.190 --> 37:26.210
kleiner 0, wenn das rechts liegt.

37:27.850 --> 37:32.250
Und das heißt, wir haben genau diese Erkenntnis gewonnen und können

37:32.250 --> 37:37.450
damit einfach feststellen, durch ein paar Operationen, wie dieser

37:37.450 --> 37:38.390
Vergleich aussieht.

37:38.490 --> 37:39.610
Liegt das links oder rechts?

37:40.070 --> 37:43.790
Das ist also der Vergleich, den wir ansonsten bei binärer Suche

37:43.790 --> 37:43.930
machen.

37:44.050 --> 37:45.730
Wir machen nur einen Größenvergleich von zwei Werten.

37:46.090 --> 37:48.650
Hier gucken wir, ist ein Wert kleiner 0 oder größer 0?

37:49.550 --> 37:51.190
Und damit haben wir den Aufschluss.

37:51.250 --> 37:54.270
Dann wissen wir, wie wir diese Vergleiche machen bei der binären

37:54.270 --> 37:54.730
Suche.

37:55.490 --> 38:00.990
Dann wissen wir, in welchem Sektor, also am Ende der binären Suche

38:00.990 --> 38:03.470
wissen wir, in welchem Sektor der Punkt Q liegt.

38:03.470 --> 38:07.550
Und dann müssen wir nur noch feststellen, liegt dieser Punkt Q jetzt

38:07.550 --> 38:13.550
links oder rechts von der Polygonkante, die diesen Sektor hier

38:13.550 --> 38:14.190
festlegt.

38:16.170 --> 38:19.410
Und das ist wieder so ein Vergleich und dann bin ich fertig.

38:20.530 --> 38:23.450
Das ist wieder so ein einfacher Vergleich links oder rechts von einer

38:23.450 --> 38:23.690
Kante.

38:25.570 --> 38:31.170
Und das heißt, damit habe ich sehr einfach festgestellt, ich habe

38:31.170 --> 38:32.490
welchen Aufwand.

38:33.090 --> 38:37.610
Ich muss zunächst mal die Reihenfolge der Sektoren haben.

38:39.090 --> 38:40.110
Die habe ich aber sowieso.

38:40.830 --> 38:44.090
Mein Polygon ist ja gegeben als eine Folge von Punkten.

38:45.350 --> 38:48.770
Und ich brauche ja diese Strahlen alle gar nicht zu berechnen.

38:49.250 --> 38:50.810
Ich habe also die sortierte Reihenfolge.

38:50.810 --> 38:54.710
Ich muss nur in der sortierten Reihenfolge meiner Punkte, bzw.

38:54.790 --> 38:57.690
ich muss einmal diesen Punkt R suchen, den brauche ich natürlich.

38:57.950 --> 38:59.890
Einen Punkt R im Inneren.

39:00.110 --> 39:01.410
So ein konstanter Aufwand.

39:02.390 --> 39:06.270
Und dann muss ich einfach nur diese binäre Suche machen auf einer

39:06.270 --> 39:07.070
sortierten Folge.

39:07.350 --> 39:09.250
Binäre Suche ist jeweils Aufwandlog N.

39:09.870 --> 39:12.330
Und dann nochmal den Vergleich, wenn ich den Sektor bestimmt habe,

39:12.770 --> 39:14.830
links oder rechts von der entsprechenden Polygonkante.

39:15.590 --> 39:16.710
Konstanter Aufwand dazu.

39:17.430 --> 39:24.210
Und das heißt, der Vorbereitungsaufwand steht hier, ist O von N.

39:26.470 --> 39:28.610
Aber eigentlich habe ich gar nicht viel vorbereitet.

39:28.710 --> 39:32.390
Ich musste mir nur einmal die Folge angucken, die einmal aufschreiben.

39:32.470 --> 39:33.430
Die ist aber eigentlich gegeben.

39:33.890 --> 39:36.150
Also das würde ich mal hier in Klammern setzen.

39:36.690 --> 39:38.310
Und ich musste eigentlich gar nichts vorbereiten.

39:38.390 --> 39:41.370
Das, was ich hier auf der vorigen Folie gesagt habe.

39:42.890 --> 39:44.150
Noch ein weiter vorne.

39:44.150 --> 39:45.930
Das war der Algorithmus.

39:48.250 --> 39:48.710
Vorbereitung.

39:48.830 --> 39:54.430
Bestimme einen Punkt Rst im Inneren von P. Der Aufwand ist O von 1.

39:55.630 --> 39:59.130
Dann steht hier, teile das Polygon und die Ebene durch die Eckpunkte

39:59.130 --> 40:00.470
von P in N Sektoren.

40:01.150 --> 40:03.150
Das sieht aus, als wäre das Aufwand N.

40:03.930 --> 40:05.350
Aber den brauche ich gar nicht zu treiben.

40:06.010 --> 40:07.610
Diesen Punkt kann ich mir eigentlich sparen.

40:08.070 --> 40:09.030
Man lernt nie aus.

40:09.850 --> 40:15.030
Das ist ja schon gegeben durch die Folge meiner Polygon-Punkte.

40:15.650 --> 40:19.850
Und ich muss ja im weiteren Verlauf dann nur entsprechend dieser

40:19.850 --> 40:31.530
Operation machen.

40:31.930 --> 40:33.910
Und diese Koordinaten sind mir alle gegeben.

40:34.070 --> 40:36.970
Die einzelnen Punkte P, I, die stehen hier unten.

40:36.970 --> 40:38.410
Das ist jeweils P, I.

40:38.870 --> 40:39.950
Das hier ist der Punkt R.

40:40.430 --> 40:41.530
Und das ist der Punkt Q.

40:42.030 --> 40:44.750
Ich muss also immer nur entsprechend das hier ausrechnen.

40:44.970 --> 40:45.450
Das ist alles.

40:47.910 --> 40:54.590
Insofern ist der Aufwand dann für diese Suche tatsächlich Log N.

40:57.150 --> 40:57.290
Bitte?

40:59.550 --> 41:00.030
Okay.

41:00.530 --> 41:00.970
Gut.

41:01.510 --> 41:07.250
Das habe ich vorher nie bemerkt, dass das gar kein Aufwand ist, den

41:07.250 --> 41:07.790
ich dort treibe.

41:08.250 --> 41:12.150
Wenn ich es tatsächlich malen möchte, muss ich für jeden Punkt das

41:12.150 --> 41:12.730
hinmalen.

41:13.450 --> 41:18.410
Aber durch dieses P1 bis PN ist ja bereits meine Eingabe.

41:19.130 --> 41:21.230
Und damit ist der Punkt eigentlich schon erledigt.

41:21.870 --> 41:22.950
Das ist bereits sortiert.

41:22.950 --> 41:27.050
Und damit habe ich hier Aufwand Log N.

41:27.710 --> 41:28.450
Sehr einfach zu machen.

41:30.210 --> 41:31.350
Kommen wir zum nächsten Problem.

41:32.290 --> 41:33.090
Ich habe ein Polygon.

41:33.990 --> 41:37.470
Wir hatten gerade eben gesehen, wichtig ist, dass ein Polygon konvex

41:37.470 --> 41:37.890
ist.

41:39.130 --> 41:40.230
Das kann wichtig sein.

41:40.350 --> 41:41.470
Aber dafür muss ich ein bisschen auf das einfach.

41:41.570 --> 41:45.370
Also wenn ich mal angucke, ich könnte ja gucken, ich gucke einfach,

41:45.470 --> 41:48.790
sind das hier jeweils Rechtsdrehungen, wenn ich so durch das Polygon

41:48.790 --> 41:49.430
durchlaufe.

41:53.150 --> 41:58.010
Nur einfach ein Polygon, bei dem jeder Winkel eine Rechtsdrehung ist,

41:58.090 --> 41:59.490
ist aber nicht notwendigerweise einfach.

41:59.650 --> 42:01.730
Da kann man sich leicht überlegen, dass dafür Gegenbeispiele gibt.

42:03.070 --> 42:06.530
Ich möchte manchmal eben einfach wissen, ist das Polygon zunächst

42:06.530 --> 42:07.290
einmal einfach?

42:08.370 --> 42:11.690
Das war ja bei dem anderen Punkt auch schon, also bei dem ersten

42:11.690 --> 42:15.070
Problem, das wir angeguckt haben, auch schon wichtige Eigenschaft.

42:15.710 --> 42:17.470
Also die Frage, wie kann ich das überprüfen?

42:17.470 --> 42:20.170
Dazu muss ich überprüfen, ob sich irgendwelche Kanten schneiden.

42:22.250 --> 42:24.510
Jetzt weiß ich natürlich nicht, welche das sind.

42:24.690 --> 42:27.990
Es könnte ja beliebig viele, könnten sich hier schneiden, könnte hier

42:27.990 --> 42:29.230
ein sehr komplexes Gebilde sein.

42:29.310 --> 42:30.470
Hier schneiden sich gerade zwei.

42:31.110 --> 42:33.630
Ich könnte ein anderes Polygon mir aufmalen, wo sich durchaus mehrere

42:33.630 --> 42:35.070
Überschneidungen ergeben können.

42:35.830 --> 42:37.910
Es kann ja beliebig kompliziert aussehen.

42:39.370 --> 42:44.030
Und ich muss also, wenn ich das naiv mache, für alle Kantenpaare

42:44.030 --> 42:46.630
gucken, ob die sich schneiden.

42:47.710 --> 42:49.890
Der Aufwand ist quadratisch.

42:51.350 --> 42:54.270
Und der Platz ist natürlich linear, das ist klar.

42:55.130 --> 42:56.010
Vorbereitung ist null.

42:57.050 --> 43:01.190
Mit quadratischem Aufwand könnte ich hier überprüfen, alle Paare von

43:01.190 --> 43:03.930
Kanten schaue ich mir an, überprüfe jeweils, überschneiden die sich

43:03.930 --> 43:09.270
oder überschneiden die sich nicht und habe dann das rausgefunden.

43:10.130 --> 43:11.590
Jetzt kann man das besser machen.

43:12.470 --> 43:15.830
Und das ist ein Verfahren, das ist wesentlich in der algorithmischen

43:15.830 --> 43:16.190
Geometrie.

43:16.290 --> 43:21.610
Das ist nämlich eine Idee, eine algorithmische Idee, die man sehr

43:21.610 --> 43:24.390
hilfreich einsetzen kann an vielen verschiedenen Stellen.

43:25.670 --> 43:31.250
Und die wesentliche Idee ist, dass ich ein zweidimensionales Problem

43:31.250 --> 43:32.950
auf ein eindimensionales Problem setze.

43:33.650 --> 43:36.270
Wir haben hier ein zweidimensionales Problem.

43:38.010 --> 43:40.270
Punkte, ein Polygon in der Ebene.

43:40.430 --> 43:41.670
Wir wollen feststellen, dass wir nicht überschneiden, wir schneiden

43:41.670 --> 43:42.610
sich irgendwelche Kanten.

43:44.130 --> 43:50.830
Das reduzieren wir auf ein eindimensionales Problem, in dem wir ein

43:50.830 --> 43:56.690
eindimensionales Problem wäre eine lineare Anordnung von Punkten.

43:59.490 --> 44:04.070
Dieses eindimensionale Problem schieben wir durch das zweidimensionale

44:04.070 --> 44:04.450
hindurch.

44:04.750 --> 44:09.130
Beziehungsweise wir betrachten an einer Reihe von Punkten und zwar

44:09.130 --> 44:22.230
immer gerade an den Polygonpunkten und so weiter betrachten wir ein

44:22.230 --> 44:23.410
eindimensionales Problem.

44:25.590 --> 44:31.330
Und das eindimensionale Problem ist ein Problem, bei dem es darum

44:31.330 --> 44:35.510
geht, ob sich Intervalle auf einer Geraden überschneiden.

44:36.890 --> 44:38.790
Schauen wir uns das jeweils nur an.

44:39.470 --> 44:44.150
Ich habe an jedem Haltepunkt hier, für mein eindimensionales Problem,

44:45.570 --> 44:51.370
da laufen irgendwelche, hier zum Beispiel, oder hier, an diesem Punkt,

44:51.470 --> 44:55.310
laufen zwei Kanten los.

44:55.550 --> 44:57.050
Von dahinten kam noch eine andere.

44:58.170 --> 45:00.410
Hier, da bin ich vorher gewesen.

45:01.710 --> 45:06.350
Wenn ich mir angucke, dann sind die Endpunkte dieser Kante, das sind

45:06.350 --> 45:10.550
die beiden, und die Endpunkte dieser Kante, das sind die beiden.

45:10.630 --> 45:20.130
Wenn das hier A und B sind, dann sind von der Kante habe ich hier Y

45:20.710 --> 45:24.330
und da oben, das wäre hier irgendein Punkt X.

45:24.970 --> 45:28.290
Dann stellen Sie fest, das Intervall XY überschneidet sich mit dem

45:28.290 --> 45:33.610
Intervall AB auf der Kante, die ich, oder auf der Geraden, die ich

45:33.610 --> 45:37.390
hier betrachte, wenn ich in diesem Haltepunkt hier oben gerade bin.

45:40.330 --> 45:46.030
Dann stelle ich fest, dadurch, dass die Paare von Anfangs und Endpunkt

45:46.030 --> 45:50.830
der benachbarten Kanten, Bezug auf diese Gerade, dadurch, dass die

45:50.830 --> 45:54.210
sich überschneiden, weiß ich, dann überschneiden sich die beiden

45:54.210 --> 45:54.570
Kanten.

45:57.690 --> 45:58.510
Sie schütteln den Kopf.

46:01.030 --> 46:02.110
Ja, tut mir leid.

46:02.330 --> 46:06.290
Es geht gleich, ist etwas kompliziert geworden, vielleicht.

46:06.490 --> 46:09.170
Sie sehen das gleich noch besser auf der nächsten Folie.

46:09.290 --> 46:12.950
Aber die wesentliche Idee ist, dass sich ein zweidimensionales Problem

46:12.950 --> 46:16.490
überschneiden sich irgendwelche Linien in der Ebene, reduziere auf ein

46:17.050 --> 46:19.370
eindimensionales, bei dem ich nur noch gucke, ob sich Intervalle

46:19.370 --> 46:19.890
überschneiden.

46:22.030 --> 46:25.950
Und ein eindimensionales Problem ist tendenziell einfacher als ein

46:25.950 --> 46:27.070
zweidimensionales Problem.

46:28.310 --> 46:31.490
Und das ist eigentlich die wesentliche Idee, das nennt man also diesen

46:31.490 --> 46:32.290
Plane Suite.

46:32.990 --> 46:37.190
Ich fahre mit einem Besen über die Ebene rüber und gucke mir an jedem

46:37.190 --> 46:40.470
Zeitpunkt an, was für Probleme habe ich an diesem Besen zu lösen.

46:42.550 --> 46:46.690
Und sammle also im Prinzip gerade die Information auf, die mir auf

46:46.690 --> 46:47.950
diesem Besen zur Verfügung steht.

46:48.790 --> 46:49.930
Alles andere interessiert mich nicht.

46:49.990 --> 46:52.850
Wenn ich an dieser Stelle hier bin, wenn ich hier diese Kante

46:52.850 --> 46:57.210
betrachte, interessiert mich überhaupt nicht, was irgendwo in dem

46:57.210 --> 46:58.570
Bereich hier hinten los ist.

46:59.730 --> 47:03.190
Sondern es interessiert mich nur, dass hier eine Kante in der Richtung

47:03.190 --> 47:03.790
losläuft.

47:03.910 --> 47:05.670
Die Kante, die dahinter liegt, die kann ich vergessen.

47:06.250 --> 47:06.970
Die ist abgehakt.

47:08.170 --> 47:11.350
Die Kante hier ist relevant und die Kante ist dort relevant.

47:12.210 --> 47:12.590
Hier unten.

47:13.490 --> 47:17.710
Und diese Kante und die Kante, die sind völlig unabhängig voneinander.

47:18.330 --> 47:21.230
Da habe ich einen Intervall, da oben habe ich einen Intervall.

47:21.330 --> 47:22.690
Die beiden sind schön weit auseinander.

47:23.530 --> 47:24.270
Kein Überschneiden.

47:25.030 --> 47:26.850
Das kann ich an dieser Stelle erzählen.

47:29.370 --> 47:33.930
Und an jedem Haltepunkt vergesse ich ein paar Kanten, die dort enden.

47:34.390 --> 47:35.270
Maximal zwei.

47:36.330 --> 47:39.590
Und es fangen maximal zwei an.

47:40.590 --> 47:42.550
Also wenn zwei geendet haben, fängt keine neu an.

47:43.210 --> 47:45.910
Wenn eine geendet hat, kann eine wieder anfangen.

47:46.350 --> 47:47.430
Oder wird eine weiterlaufen.

47:47.990 --> 47:51.630
Wenn keine geendet hatte, wie an diesem Punkt hier, an dem Punkt da

47:51.630 --> 47:55.070
unten, dann fangen zwei Kanten an.

47:56.490 --> 47:58.810
Die können sich mit den darüber oder runterliegenden Kanten eventuell

47:58.810 --> 47:59.190
schneiden.

48:00.870 --> 48:04.730
Das ist übrigens hier noch, ich habe den Namen dazugefügt, Bentley

48:04.730 --> 48:05.810
-Ottmann -Algorithmus.

48:06.370 --> 48:08.990
Das ist in einem Artikel von den beiden veröffentlicht worden.

48:09.070 --> 48:12.070
Herr Ottmann war mein Vorgänger auf dieser Stelle, vor vielen Jahren.

48:12.530 --> 48:15.710
Und ist jetzt schon emeritiert in Freiburg.

48:16.350 --> 48:19.830
Und das ist eine der am häufigsten zitierten Arbeiten, die im Format

48:19.830 --> 48:21.990
die Arbeit, in der dieser Algorithmus vorgestellt wurde.

48:23.370 --> 48:29.270
Das ist auch ein wichtiges Prinzip, das man da sich ausgedacht hat.

48:30.710 --> 48:35.830
Dieses Reduktion eines Problems von N-Dimensionen auf N-1-Dimensionen.

48:36.790 --> 48:40.510
Und natürlich muss ich dann eine Menge solcher N-1-Dimensionalen

48:40.510 --> 48:41.250
Probleme lösen.

48:41.850 --> 48:47.070
Aber die Anzahl oder die Summe der Aufwände für die N-1-Dimensionalen

48:47.070 --> 48:50.490
Probleme kann halt einfacher sein oder kleiner sein als der Aufwand

48:50.490 --> 48:51.850
für das N-Dimensionale Problem.

48:52.550 --> 48:53.890
Und das ist der wesentliche Punkt dabei.

48:54.570 --> 48:56.910
Hier ist das Intervallüberschreitungsproblem gegeben.

48:57.250 --> 48:57.770
Da oben.

48:58.350 --> 48:59.730
Ich habe eine Reihe von Intervallen.

49:01.510 --> 49:03.530
x1, y1 bis xn, yn.

49:04.730 --> 49:06.170
Das ist hier angedeutet.

49:06.670 --> 49:09.050
Das wäre also zum Beispiel ein solches Intervall.

49:10.870 --> 49:15.050
Das Intervall x2, y2 geht also hier in dem Fall von da nach da.

49:15.050 --> 49:19.350
Das Intervall x3, y3 geht von da nach da und da haben wir schon eine

49:19.350 --> 49:19.970
Überschneidung.

49:21.050 --> 49:21.930
Zwischen diesen beiden.

49:23.330 --> 49:29.890
Und wenn man sich anguckt, x4, y4 geht darüber, überschneidet sich mit

49:29.890 --> 49:31.610
dem Intervall y3.

49:33.950 --> 49:39.750
Und ich sage, das Problem Überschneidung von Kanten zu finden,

49:40.230 --> 49:42.710
reduziere ich auf ein Intervallüberschneidungsproblem.

49:42.710 --> 49:47.150
Dieses Problem hier kann ich einfach bearbeiten.

49:49.790 --> 49:53.330
Beziehungsweise das Problem, das ich beim Planesweep lösen muss, sieht

49:53.330 --> 50:00.230
so aus, dass ich mir irgendeinen Punkt habe, hier drin, also

50:00.230 --> 50:07.030
irgendeinen Anfangspunkt eines Intervalls und ich muss nur sehen,

50:07.090 --> 50:10.950
überschneidet sich das mit den Intervallen, die links oder rechts

50:10.950 --> 50:11.610
davon sind.

50:13.410 --> 50:14.570
Ja, die schon drauf sind.

50:15.150 --> 50:15.630
Auf der Kante.

50:16.530 --> 50:19.490
Ich muss sehen, an welcher Stelle befinde ich mich, wenn ich also hier

50:19.490 --> 50:21.130
an solch einem Punkt anlange.

50:21.510 --> 50:24.410
Das sind meine Haltepunkte für meinen Planesweep.

50:25.690 --> 50:28.830
Da kann ich ein Intervall vergessen, das für diese Kante kann ich

50:28.830 --> 50:32.710
vergessen, ein neues Intervall muss ich dazufügen und ich habe

50:32.710 --> 50:35.830
abgespeichert das Intervall für diese Kante da oben.

50:36.550 --> 50:40.130
Dann muss ich überprüfen, überschneiden sich diese beiden Intervalle,

50:40.170 --> 50:42.970
überschneidet sich das Intervall, das ich neu dazufüge, mit dem

50:42.970 --> 50:46.390
Intervall, das direkt oben drüber liegt oder dem, das direkt unten

50:46.390 --> 50:46.850
drunter liegt.

50:49.330 --> 50:51.350
Und in diesem Fall überschneidet es sich nicht.

50:52.750 --> 50:55.690
Ja, aber insofern habe ich hier keinen Schnittpunkt festgestellt und

50:55.690 --> 50:56.510
ich kann weiterlaufen.

50:56.970 --> 51:01.770
Ich habe diese Information dann drauf abgespeichert auf meinem Besen,

51:03.450 --> 51:04.790
das von links nach rechts rüber läuft.

51:05.730 --> 51:09.890
Ich muss also ich habe also ein lokales

51:09.890 --> 51:11.890
Intervallüberschneidungsproblem zu lösen hierbei.

51:11.970 --> 51:15.590
Ich muss nur erst mal den Punkt finden auf meiner Geraden.

51:16.370 --> 51:19.390
Das zu finden, den richtigen Punkt, ist ein Suchproblem.

51:20.350 --> 51:21.410
An welcher Stelle bin ich?

51:21.850 --> 51:24.290
Suchproblem können wir in logarithmischer Zeit lösen.

51:25.230 --> 51:27.650
Das ist ein einfacher Suchbaum im Prinzip als Datenstruktur.

51:29.070 --> 51:32.090
Und dann muss ich dort ein lokales Problem lösen.

51:32.190 --> 51:34.510
Dieses lokale Problem kann ich mit konstantem Aufwand lösen.

51:35.190 --> 51:39.950
Ich muss dort eventuell ein bis zwei Intervalle rauslöschen und

51:40.690 --> 51:43.690
eventuell ein oder zwei Intervalle neu eintragen.

51:44.370 --> 51:46.910
Und dann überprüfen, habe ich dadurch Schnittpunkte erzeugt oder

51:46.910 --> 51:47.150
nicht.

51:48.870 --> 51:53.250
Also, was ich machen muss, die Haltepunkte sind die Anfangs- und

51:53.250 --> 51:54.930
Endpunkte der Kanten des Polygons.

51:56.310 --> 51:58.610
Und jetzt muss ich mir überlegen, was sind die Haltepunkte?

52:01.410 --> 52:05.590
Die Haltepunkte sind natürlich, das sind hier jeweils die Haltepunkte,

52:05.650 --> 52:09.350
wenn ich mir das so aufmale, da muss ich also die x-Koordinaten mir

52:09.350 --> 52:12.170
hernehmen, der Punkte des Polygons.

52:13.370 --> 52:17.170
Mein Polygon ist gegeben als Folge von Punkten, die so sukzessive

52:17.170 --> 52:18.730
miteinander verbunden sind.

52:19.230 --> 52:27.470
Also da steht drin P1, P2, P3, P4, P5, P6, P7, P8, P9, P10.

52:29.110 --> 52:31.650
Das gibt mir nicht die Reihenfolge der x-Koordinaten.

52:32.090 --> 52:32.970
Ich muss die erst mal sortieren.

52:34.790 --> 52:36.050
Das ist also erst mal ein Aufwand.

52:36.410 --> 52:38.310
Ich sortiere die nach ihren x-Koordinaten.

52:39.710 --> 52:40.830
Oder sonst irgendwie.

52:41.050 --> 52:43.590
Jedenfalls muss ich da eine Reihenfolge reinbekommen.

52:43.850 --> 52:46.250
Dann habe ich die Richtung des Plane-Streaks festgelegt.

52:46.330 --> 52:48.930
Ich könnte auch die y-Koordinaten nehmen, dann würde ich halt von

52:48.930 --> 52:49.790
unten nach oben laufen.

52:50.070 --> 52:50.830
Das ist völlig egal.

52:51.870 --> 52:52.750
Das ist symmetrisch.

52:54.190 --> 52:56.930
Und dann muss ich sehen, was mache ich an den einzelnen Haltepunkten.

52:57.790 --> 53:00.110
Und da habe ich je nachdem, wo ich gerade bin, unterschiedliche

53:00.110 --> 53:00.670
Aufgaben.

53:01.570 --> 53:08.930
Das erste ist, ich lösche zunächst mal alle... ich bin also an einem

53:08.930 --> 53:09.910
Haltepunkt angelangt.

53:09.950 --> 53:13.550
Den Haltepunkt bestimme ich durch entsprechende Suche in der

53:13.550 --> 53:15.310
Datenstruktur Aufwand-Login.

53:15.770 --> 53:18.210
Jetzt bin ich an dem Haltepunkt da, ich weiß, wo ich bin.

53:19.250 --> 53:23.450
In dem Punkt hätte ich also auf der Lokal an der Stelle etwas zu tun

53:23.450 --> 53:27.030
oder ich hätte an der Stelle etwas zu tun oder ich hätte sonst

53:27.030 --> 53:27.970
irgendwo etwas zu tun.

53:28.630 --> 53:29.410
Hier an der Stelle.

53:31.190 --> 53:35.350
Und da habe ich jetzt diese, wenn ich mir die drei Punkte angucke, A,

53:35.510 --> 53:39.890
B und C, da habe ich drei verschiedene Situationen.

53:40.170 --> 53:47.130
Das eine Mal muss ich eine Kante löschen, die dahinter liegt, die hier

53:47.130 --> 53:47.810
geendet hat.

53:48.510 --> 53:51.930
Das ist diese Kante, hatte ich vorhin schon gesagt, und ich muss eine

53:51.930 --> 53:55.410
neue Kante, also wenn ich die lösche, muss ich noch etwas tun.

53:56.530 --> 53:59.830
Ich habe hier jeweils nur geprüft, ob direkt benachbarte Kanten sich

53:59.830 --> 54:00.390
überschneiden.

54:02.630 --> 54:06.410
Wird also eine Kante gelöscht, überprüfe ich, ob die Kanten direkt da

54:06.410 --> 54:11.090
drüber und direkt da drunter sich schneiden.

54:13.770 --> 54:23.910
Also, so ein Fall tritt hier da, da, da, da, da, sehe ich jetzt nicht.

54:25.210 --> 54:25.970
Ist egal.

54:26.370 --> 54:27.910
Also zum Beispiel, wenn ich

54:32.460 --> 54:35.720
jedenfalls muss ich gucken, wenn ich die lösche, muss ich gucken, hier

54:35.720 --> 54:36.800
habe ich zu wenig drauf.

54:37.120 --> 54:38.320
Das kann komplizierter aussehen.

54:38.840 --> 54:41.200
Ich prüfe immer nur, ob eine Kante sich mit der direkt drüber

54:41.200 --> 54:42.700
liegenden und direkt runterliegenden schneidet.

54:43.320 --> 54:44.380
Das ist meine lokale Operation.

54:45.080 --> 54:48.840
Wenn ich also eine Kante rauslösche, dann gibt es neue

54:48.840 --> 54:50.180
Nachbarschaften.

54:50.400 --> 54:51.680
Weil ja eine rausgelöscht wurde.

54:52.300 --> 54:56.120
Und dann muss ich sehen, ob auf der Sleepline die jetzt direkt unter

54:56.120 --> 54:58.100
drüberliegenden Kanten sich schneiden.

54:59.420 --> 55:01.800
Und das ist also dieser Punkt, den ich hier machen muss.

55:02.260 --> 55:05.840
Und dann muss ich eine Kante eintragen, dass wir in diesem Fall diese

55:05.840 --> 55:08.080
Kante, die muss ich eintragen.

55:09.840 --> 55:11.360
Wird von PH nach rechts.

55:13.760 --> 55:19.500
Und jetzt überprüfe ich, ob sich diese Kante überschneidet mit der

55:19.500 --> 55:22.880
Kante direkt oben drüber oder mit der direkt unten drunter.

55:23.320 --> 55:24.400
Unten drunter gibt es keine.

55:24.560 --> 55:26.240
Oben drüber gibt es eine.

55:26.360 --> 55:27.500
Das ist diese Kante hier.

55:28.540 --> 55:29.560
Die überschneiden sich aber nicht.

55:33.060 --> 55:38.680
Und wenn ich also jetzt in einem dieser beiden Punkte, eins oder zwei,

55:38.800 --> 55:41.100
eine Kantenverschneidung festgestellt habe, bin ich fertig.

55:41.100 --> 55:44.560
Ich habe festgestellt, dass Polygon nicht einfach ist.

55:44.980 --> 55:46.020
Ansonsten mache ich weiter.

55:50.220 --> 55:51.800
Und damit bin ich eigentlich schon fertig.

55:51.980 --> 55:52.820
Das ist der ganze Algorithmus.

55:54.100 --> 55:57.160
Wenn ich diesen Fall betrachte, da muss ich nichts löschen.

55:57.520 --> 56:00.340
Da habe ich also nur zwei neue Kanten, die eingetragen werden.

56:01.260 --> 56:04.820
Ich muss also dann für jede Kante, die ich dort neu eintrage,

56:05.220 --> 56:07.900
feststellen, ob die sich mit der drüberliegenden oder drunterliegenden

56:07.900 --> 56:08.460
schneidet.

56:09.860 --> 56:11.180
Ja, das war der Punkt.

56:11.840 --> 56:17.260
Für jede Kante, die neu eingetragen wird, muss ich das überprüfen.

56:20.260 --> 56:20.760
Bleibt vorbei.

56:22.760 --> 56:23.280
Gut.

56:24.120 --> 56:26.200
Und jetzt mache ich das eben so, dass ich dafür eine effiziente

56:26.200 --> 56:30.080
Datenstruktur habe, also einen balancierten Suchbaum auf meinem Wesen,

56:31.720 --> 56:33.160
dem Planesweep-Wesen.

56:33.700 --> 56:35.700
Und dann habe ich dort jeweils Aufwandlog n.

56:36.240 --> 56:37.980
Der lokale Vergleich ist konstant.

56:38.900 --> 56:42.820
Und jede Kante wird natürlich einmal eingefügt, wenn ich an dem

56:42.820 --> 56:45.920
Anfangspunkt bin, und wieder gelöscht, wenn ich an dem Endpunkt

56:45.920 --> 56:46.400
ankomme.

56:46.560 --> 56:50.640
Das heißt, ich habe sie nur einmal einzutragen, einmal zu löschen.

56:51.800 --> 56:57.640
Das heißt, insgesamt muss ich n-mal an jedem Haltepunkt so eine Suche

56:57.640 --> 56:57.920
machen.

56:59.000 --> 57:01.000
Ich habe n-log-n Aufwand.

57:01.060 --> 57:03.780
Ich habe auch n-mal Log-n Aufwand für das Sortieren.

57:04.400 --> 57:09.580
Das heißt, die Summe der Aufwände an den einzelnen Haltepunkten ist in

57:09.580 --> 57:11.920
der gleichen Größenordnung wie der Aufwand für das Sortieren.

57:12.880 --> 57:18.120
Und damit bin ich also in der Zeit n-log-n insgesamt.

57:18.840 --> 57:20.560
Und der Platz ist linear.

57:21.140 --> 57:25.500
Ich muss halt nur meine einzelnen Elemente abspeichern, die Elemente

57:25.500 --> 57:26.300
des Polygons.

57:26.880 --> 57:30.620
Ich muss die Elemente auf der Sweep-Line abspeichern.

57:30.740 --> 57:34.640
Die Sweep-Line hat maximal n Kanten drauf, oder Größenordnung n

57:34.640 --> 57:35.040
Kanten.

57:35.740 --> 57:37.980
Das ist also auch nicht weiter schlimm.

57:39.080 --> 57:41.740
Ich habe hier also ein relativ einfaches Problem.

57:42.140 --> 57:44.440
Reduktion von n² auf n-log-n.

57:45.080 --> 57:46.620
Und das ist eben dieser Algorithmus.

57:46.680 --> 57:51.660
Und das Wesentliche ist diese Idee, dass man ein n-dimensionales

57:51.660 --> 57:55.160
Problem auf ein n-1-dimensionales reduziert, bzw.

57:55.480 --> 57:57.400
2-dimensionales auf ein 1-dimensionales.

57:57.500 --> 58:00.700
Ich habe eine Reihe von Problemen 1-dimensional zu lösen.

58:01.120 --> 58:03.260
Und das geht in jeweils einem Zeitlog n.

58:03.900 --> 58:05.980
Und das nur n-mal, damit habe ich Aufwand n-log-n.

58:07.100 --> 58:10.200
Das ist also ein ganz wichtiger Algorithmus.

58:11.340 --> 58:15.920
Und wir können schon zum nächsten Problem in der Antwort überlegen,

58:15.980 --> 58:17.960
wie kann man das parallelisieren.

58:18.420 --> 58:22.080
Ich muss gestehen, dass ich mich mit Parallelisierung dieses Problems

58:22.080 --> 58:23.200
noch nicht beschäftigt habe.

58:23.900 --> 58:26.200
Wir haben ein bisschen Zeit, deswegen dachte ich, überlegen wir doch

58:26.200 --> 58:30.420
mal, wie das wäre, wenn man dieses Problem parallelisieren will.

58:32.040 --> 58:33.320
Das Kantenüberschneidungsproblem.

58:34.660 --> 58:41.160
Ich kann natürlich, wenn ich mir das naiv anschaue, wenn Sie haben

58:41.160 --> 58:44.180
beliebige Parallelität zur Verfügung, wie wäre Ihr Aufwand für

58:44.180 --> 58:47.000
Überprüfung von Polygon 1?

58:48.820 --> 58:50.700
Sie haben beliebige Position zur Verfügung.

58:53.460 --> 58:55.440
Was hätten Sie für ein Aufwand?

59:04.020 --> 59:05.220
Richtig, genau.

59:05.580 --> 59:05.920
Konstant.

59:06.900 --> 59:13.800
Also parallel wäre das so, dass wir, wenn wir beliebige PRAM zur

59:13.800 --> 59:17.640
Verfügung hatten, dann hätten wir Aufwand O von 1.

59:18.420 --> 59:19.660
O von 1 Schritte.

59:22.640 --> 59:25.500
Wenn Sie nicht beliebig viele haben, wenn Sie die brauchten, bräuchten

59:25.500 --> 59:27.120
Sie N² Prozessoren.

59:29.580 --> 59:39.700
Ansonsten wenn Sie nicht N² haben, wenn Sie haben meinetwegen nur N

59:39.700 --> 59:41.520
Prozessoren, wie würde man das dann machen?

59:43.120 --> 59:43.660
Das hier parallel?

59:49.560 --> 59:50.180
Ja,

59:57.300 --> 59:58.100
bräuchte im Prinzip.

01:00:00.400 --> 01:00:05.060
Ich muss natürlich wissen, welche Informationen liegen auf so einer

01:00:05.060 --> 01:00:05.780
Kante drauf.

01:00:07.700 --> 01:00:12.400
Und es kann natürlich passieren, Sie sehen jetzt also hier ist ein

01:00:12.400 --> 01:00:13.160
Haltepunkt.

01:00:14.580 --> 01:00:16.680
Nehmen wir uns mal diesen Haltepunkt hier her.

01:00:18.000 --> 01:00:21.420
Bei dem Haltepunkt, woher weiß ich, welche Informationen ich dort

01:00:21.420 --> 01:00:21.840
brauche?

01:00:24.940 --> 01:00:25.200
Ja?

01:00:26.040 --> 01:00:26.880
Woher weiß ich das?

01:00:27.760 --> 01:00:30.660
Ich muss ja dafür eine Reihe von...

01:00:30.660 --> 01:00:33.680
Ich muss wissen, welche Kanten gehen, in dem unser Haltepunkt hieß.

01:00:34.060 --> 01:00:37.700
Da endet eine Kante oder es beginnt mindestens eine Kante.

01:00:38.420 --> 01:00:40.420
Es können aber noch Kanten geben, Sie wollen was sagen.

01:00:47.450 --> 01:00:52.650
Ich muss halt alle Kanten erstmal kennen, die dort liegen.

01:00:54.610 --> 01:00:58.590
Ich muss natürlich gucken, was sind die Kanten, die oben rüber und

01:00:58.590 --> 01:00:59.310
unten drunter liegen.

01:00:59.670 --> 01:01:04.350
Ich muss ja nur die Probleme, das, was ich hier sage, das will ich

01:01:04.350 --> 01:01:05.190
jetzt parallel machen.

01:01:06.190 --> 01:01:09.770
Dazu muss ich aber die Informationen haben, was sind die Kanten, die

01:01:09.770 --> 01:01:11.630
direkt da drüber oder direkt da drunter liegen.

01:01:14.370 --> 01:01:17.090
Ja, und ich muss zunächst auch mal, eigentlich brauche ich schon die

01:01:17.090 --> 01:01:17.990
ganze...

01:01:18.450 --> 01:01:21.710
die Informationen, die ansonsten sequenziell hier erzeugt worden

01:01:21.710 --> 01:01:22.090
wären.

01:01:23.370 --> 01:01:26.610
Und das Problem ist, es kann natürlich sein, dass hier irgendwelche

01:01:26.610 --> 01:01:33.510
Kanten beliebig durchlaufen von irgendwelchen anderen Polygonpunkten,

01:01:33.630 --> 01:01:36.290
die weit links lagen oder weit rechts.

01:01:37.750 --> 01:01:38.790
Und die muss ich erstmal kennen.

01:01:39.410 --> 01:01:43.090
Ich muss wissen, welche Punkte gehören eigentlich alle auf meine Kante

01:01:43.090 --> 01:01:43.510
drauf.

01:01:44.370 --> 01:01:48.890
Also der Aufwand, man wird das natürlich auch in...

01:01:48.890 --> 01:01:52.810
ich nehme schon an, dass man das in logarithmischer Zeit hinbekommt.

01:01:53.630 --> 01:01:56.170
Aber das Verfahren ist mir jetzt nicht so plausibel, wie man das

01:01:56.170 --> 01:01:56.410
macht.

01:01:57.370 --> 01:01:58.370
Muss man sich mal anschauen.

01:01:58.590 --> 01:02:00.270
Wäre ja mal interessant, sich anzugucken.

01:02:00.910 --> 01:02:02.170
Ich werde mal suchen, ob ich da was finde.

01:02:02.690 --> 01:02:03.930
Können wir nächste Woche nochmal drüber reden.

01:02:05.770 --> 01:02:10.470
Aber das ist im Augenblick nicht so offensichtlich, wie man das macht,

01:02:10.570 --> 01:02:13.210
weil dieser Planesweep natürlich zunächst mal ein inhärent

01:02:13.210 --> 01:02:15.090
sequenzieller Prozess ist.

01:02:15.850 --> 01:02:17.650
Ich laufe von links nach rechts da durch.

01:02:18.570 --> 01:02:22.810
Und das ist keineswegs trivial, sich zu überlegen, kann man diesen

01:02:22.810 --> 01:02:27.090
inhärent sequenziellen Prozess kann man das auch parallel machen,

01:02:27.210 --> 01:02:28.030
unabhängig voneinander.

01:02:28.330 --> 01:02:30.510
Oder muss man das so linear durchlaufen lassen.

01:02:31.290 --> 01:02:33.790
Wenn es linear durchlaufen lassen muss, hätte ich auf jeden Fall

01:02:33.790 --> 01:02:35.490
Aufwand in Schritte.

01:02:36.370 --> 01:02:37.150
Das wäre schlecht.

01:02:38.950 --> 01:02:43.070
Ja, also das, ich habe mir das nicht angeguckt, aber das sollte ich

01:02:43.070 --> 01:02:44.670
mal demnächst mal machen.

01:02:45.630 --> 01:02:48.510
Gehen wir zum nächsten Punkt.

01:02:49.950 --> 01:02:50.610
Nächstes Problem.

01:02:50.610 --> 01:02:52.610
Sie haben noch eine Frage.

01:02:56.770 --> 01:02:57.090
Ja.

01:03:00.430 --> 01:03:00.750
Ja.

01:03:04.550 --> 01:03:04.730
Ja.

01:03:05.570 --> 01:03:05.810
Ja.

01:03:05.810 --> 01:03:05.890
Ja.

01:03:08.730 --> 01:03:11.130
Da habe ich hier, wenn ich das so sortiere, dann auch von nlogn.

01:03:12.670 --> 01:03:14.410
Parallel können wir in Zeit nlogn sortieren.

01:03:18.680 --> 01:03:19.840
Ich habe es aber nur sortiert.

01:03:19.960 --> 01:03:22.840
Ich habe noch nicht die Informationen an den einzelnen Punkten

01:03:22.840 --> 01:03:23.320
erzeugt.

01:03:23.580 --> 01:03:26.720
Der erste Schritt ist natürlich, dass ich die Reihenfolge der

01:03:26.720 --> 01:03:27.820
Haltepunkte überlegen muss.

01:03:31.720 --> 01:03:32.520
Macht ja nichts.

01:03:33.300 --> 01:03:35.160
Nur über Denkfehler kommt man zu den richtigen Ideen.

01:03:36.480 --> 01:03:38.720
Also insofern können Sie auch mal nachdenken, wie Sie das machen

01:03:38.720 --> 01:03:39.080
würden.

01:03:40.200 --> 01:03:40.440
Gut.

01:03:40.900 --> 01:03:42.080
Gehen wir mal jetzt zum nächsten Problem.

01:03:44.160 --> 01:03:47.340
Sie wollen die konvexe Hülle von einer Menge von Punkten bestimmen.

01:03:47.800 --> 01:03:50.380
Das hatte ich Ihnen auch schon mal vorgestellt, ganz zu Anfang.

01:03:50.560 --> 01:03:53.380
Das ist ein relevantes Problem bei der algorithmischen Geometrie.

01:03:55.780 --> 01:03:59.360
Wir interessieren uns also für die konvexe Hülle einer Menge von

01:03:59.360 --> 01:03:59.700
Punkten.

01:03:59.760 --> 01:04:00.960
Das ist unsere Menge von Punkten.

01:04:01.540 --> 01:04:07.160
Und wir wollen die Extrempunkte haben, beziehungsweise die kleinste

01:04:08.560 --> 01:04:13.900
Menge, Teilmenge des E2, des zweidimensionalen klinischen Raumes, die

01:04:13.900 --> 01:04:16.000
alle Punkte dieser Menge M enthält.

01:04:17.080 --> 01:04:20.280
Da sehen wir schon, das sind unterschiedliche Aufgaben, die man hier

01:04:20.280 --> 01:04:20.940
angucken kann.

01:04:21.640 --> 01:04:25.100
Eine Aufgabe wäre, nur die Extrempunkte zu finden.

01:04:26.780 --> 01:04:30.600
Dann habe ich also, kenne ich alle Extrempunkte und weiß, alle anderen

01:04:30.600 --> 01:04:32.920
liegen irgendwo im Inneren.

01:04:33.040 --> 01:04:34.220
Ich kann die also irgendwie verbinden.

01:04:35.200 --> 01:04:38.060
Nur die Extrempunkte zu haben, reicht mir aber noch nicht.

01:04:38.760 --> 01:04:42.080
Ich brauche ja auch in irgendeiner Folge die Reihenfolge der

01:04:43.400 --> 01:04:48.200
Extrempunkte, um das umschließende Polygon tatsächlich angeben zu

01:04:48.200 --> 01:04:48.480
können.

01:04:50.260 --> 01:04:54.580
Ja, das ist also noch eine Aufgabe, das richtig anzuordnen.

01:04:55.020 --> 01:04:59.080
Das wäre eine radiale Sortierung der Punkte, die ich dort mache, die

01:04:59.080 --> 01:05:00.700
ich als Extrempunkte gefunden habe.

01:05:02.200 --> 01:05:05.900
Also das eine Problem ist, Extrempunkte zu finden und dann die

01:05:05.900 --> 01:05:08.980
richtige Reihenfolge, sodass ich tatsächlich die konvexe Hülle habe.

01:05:10.160 --> 01:05:14.500
Und dann ist es eben so, hier sage ich, es ist die kleinste, konvexe

01:05:14.500 --> 01:05:16.000
Teilmenge von E2.

01:05:16.740 --> 01:05:19.720
Das, was ich Ihnen hier aufgemalt habe, ist aber eher ein konvexes

01:05:19.720 --> 01:05:24.260
Polygon, das die Extrempunkte verbindet.

01:05:24.600 --> 01:05:28.360
Also den Rand der konvexen Hülle bildet.

01:05:28.760 --> 01:05:31.880
Insofern habe ich hier verschiedene Aufgaben, die ich mir angucken

01:05:31.880 --> 01:05:32.140
muss.

01:05:33.020 --> 01:05:35.320
Und ich werde Ihnen jetzt mehrere solcher Algorithmen zeigen, mit

01:05:35.320 --> 01:05:37.940
denen man die konvexe Hülle einer Menge von Punkten finden kann.

01:05:38.760 --> 01:05:41.620
Und auch da werde ich mich bemühen, so ein bisschen Ideen

01:05:41.620 --> 01:05:44.940
rüberzubringen, die man dort zugrunde legt, um auf diese Algorithmen

01:05:44.940 --> 01:05:45.380
zu kommen.

01:05:47.480 --> 01:05:50.000
Also es werden dort unterschiedliche Eigenschaften konvexer Mengen

01:05:50.000 --> 01:05:50.880
ausgenutzt bzw.

01:05:51.160 --> 01:05:51.920
von Polygonen.

01:05:53.200 --> 01:05:57.800
Der erste Ansatz ist folgende Idee.

01:05:59.760 --> 01:06:01.040
Wenn ich

01:06:04.920 --> 01:06:09.880
drei Punkte habe, x, und ich habe hier drei andere Punkte, wenn der

01:06:09.880 --> 01:06:19.360
Punkt x in einem Dreieck liegt, aus drei anderen Punkten, dann ist das

01:06:19.360 --> 01:06:20.740
x sicherlich kein Extrempunkt.

01:06:22.680 --> 01:06:23.620
Das ist offensichtlich.

01:06:24.900 --> 01:06:29.860
Ich brauche also nur, wenn ich diese Eigenschaft ausnutze, brauche ich

01:06:29.860 --> 01:06:36.180
nur festzustellen, liegt ein Punkt aus M, irgend beliebiger Punkt M,

01:06:36.840 --> 01:06:40.660
in einem Dreieck aus drei anderen Punkten meiner Menge.

01:06:42.600 --> 01:06:45.720
Also übernehme ich mir einfach alle möglichen Dreiecke, alle möglichen

01:06:46.960 --> 01:06:52.040
Teilmengen der Größe 3, und stelle jeweils fest, liegt das x innerhalb

01:06:52.040 --> 01:06:55.020
des Dreiecks, das von diesen drei Punkten gebildet wird.

01:06:57.820 --> 01:07:01.760
Das ist eine Idee, die man sich überlegen kann.

01:07:05.620 --> 01:07:06.900
Da war das ja auch gemacht.

01:07:08.680 --> 01:07:10.740
Der Algorithmus ist also ganz einfach.

01:07:10.880 --> 01:07:13.200
Ich prüfe für jeden Punkt, ob er in einem Dreieck liegt.

01:07:13.800 --> 01:07:16.700
Das Problem ist, ich habe natürlich sehr viele solche Dreiecke, wenn

01:07:16.700 --> 01:07:19.060
nur drei verschiedene Möglichkeiten dafür.

01:07:20.520 --> 01:07:23.300
Ich habe dann aber insgesamt h Extrempunkt.

01:07:24.740 --> 01:07:26.460
Und dann habe ich nur die Extrempunkte.

01:07:26.520 --> 01:07:28.000
Jetzt muss ich die noch geeignet anordnen.

01:07:28.160 --> 01:07:29.720
Ich muss eine geeignete Anordnung machen.

01:07:30.200 --> 01:07:33.500
Das kann ich wieder machen, indem ich also irgendeinen Punkt im

01:07:33.500 --> 01:07:35.460
Inneren von M nehme als Ursprung.

01:07:35.940 --> 01:07:37.460
Da brauche ich nur zwei Punkte zu verbinden.

01:07:38.360 --> 01:07:40.420
Irgendeinen Punkt auf der Verbindungslinie zu nehmen.

01:07:41.200 --> 01:07:44.200
Dann kann ich die anderen alle radial anordnen.

01:07:44.400 --> 01:07:45.980
Oder ich nehme drei Punkte, nehme einen in der Mitte, nehme den

01:07:45.980 --> 01:07:49.460
Mittelpunkt und kann dann insgesamt eine radiale Anordnung machen.

01:07:50.500 --> 01:07:54.800
Und kann die sortieren bezüglich ihres Winkels mit der x-Achse.

01:07:55.860 --> 01:07:57.640
Das ist also, wir wissen, wie man das macht.

01:07:57.960 --> 01:08:00.020
Da brauche ich nicht den Winkel zu berechnen, sondern muss nur sehen,

01:08:00.460 --> 01:08:02.900
liegt der rechts oder links von irgendeiner anderen Gerade.

01:08:03.540 --> 01:08:04.640
Das kann man alles machen.

01:08:05.900 --> 01:08:07.200
Der Aufwand ist nicht groß.

01:08:07.960 --> 01:08:12.680
Hier ist es angegeben, das wäre jeweils der Winkel mit der x-Achse.

01:08:13.660 --> 01:08:17.500
Und da brauche ich nur entsprechend die Determinanten zu berechnen.

01:08:19.420 --> 01:08:27.000
das heißt, ich muss für jeden Punkt von M ein Problem der

01:08:27.000 --> 01:08:28.840
Größenordnung n hoch 3 lösen.

01:08:28.940 --> 01:08:30.180
Das ist Aufwand n hoch 4.

01:08:31.900 --> 01:08:32.380
Riesenaufwand.

01:08:33.240 --> 01:08:35.080
Und dann muss ich noch meine Punkte sortieren.

01:08:35.860 --> 01:08:39.520
Das ist Aufwand h mal log h, wobei h die Anzahl der Extrempunkte ist.

01:08:42.540 --> 01:08:46.300
Und das heißt, der Gesamtaufwand hier ist n hoch 4, sehr groß.

01:08:46.960 --> 01:08:49.660
Der Vorteil ist, wenn ich das hier parallelisieren will, geht das sehr

01:08:49.660 --> 01:08:50.040
einfach.

01:08:51.980 --> 01:08:56.560
Ich muss ja nur für jeweils drei Punkte so ein Dreieck bestimmen,

01:08:56.680 --> 01:08:58.420
feststellen, liegt der Punkt im Inneren oder nicht.

01:08:58.520 --> 01:09:01.280
Das kann ich für alle diese Dreiecke parallel machen.

01:09:02.480 --> 01:09:06.780
Das ist also etwas, das kann ich alles parallel ausführen, allerdings

01:09:06.780 --> 01:09:07.860
mit sehr viel Aufwand.

01:09:08.360 --> 01:09:09.960
Ich brauche n hoch 3 Prozessoren dafür.

01:09:11.260 --> 01:09:16.240
Und kann aber im Prinzip das dann hier mit konstantem Aufwand

01:09:16.240 --> 01:09:16.860
feststellen.

01:09:17.380 --> 01:09:18.900
Mit konstanter Zeit, das ist ein Schritt.

01:09:19.940 --> 01:09:22.440
Und dann muss ich noch sortieren.

01:09:22.600 --> 01:09:24.140
Das wissen wir, geht in Zeit log n.

01:09:24.840 --> 01:09:28.740
Und dann habe ich also insgesamt, also parallel in Zeit log n, dann

01:09:28.740 --> 01:09:30.380
habe ich insgesamt Aufwand log n.

01:09:30.800 --> 01:09:33.200
Aber nur für das Sortieren meiner Extrempunkte.

01:09:33.640 --> 01:09:36.960
Und bin dann relativ schnell fertig mit der Parallelvariante.

01:09:38.240 --> 01:09:40.340
Was ich hier hingeschrieben hatte, hatte ich nicht hingeschrieben.

01:09:43.940 --> 01:09:49.380
Parallel in Zeit o von log n.

01:09:49.480 --> 01:09:54.220
Und das liegt daran, dass das hier, wenn ich hier tp hinschreibe, dann

01:09:54.220 --> 01:09:58.680
wäre das hier in o von log n.

01:09:59.000 --> 01:10:03.300
Und hier wäre tp aus o von 1.

01:10:04.860 --> 01:10:07.640
Das kann man nicht richtig lesen hier, aus o von 1.

01:10:12.880 --> 01:10:16.580
Also das wäre der erste Punkt, der konstante Aufwand, der nächste

01:10:16.580 --> 01:10:18.240
logarithmische Aufwand parallel.

01:10:18.960 --> 01:10:21.160
Das wäre also relativ einfach.

01:10:21.260 --> 01:10:23.480
Schön parallelisierbar, aber ein wahnsinns Aufwand.

01:10:24.660 --> 01:10:26.420
Jetzt müssen wir sehen, wie kann man das einfacher machen.

01:10:27.400 --> 01:10:29.540
Und da gibt es eine Reihe klassischer Algorithmen.

01:10:30.500 --> 01:10:32.600
Es gibt den sogenannten Graham-Scan.

01:10:33.920 --> 01:10:35.180
Der ist hier angedeutet.

01:10:36.320 --> 01:10:39.780
Graham hat folgendes gemacht.

01:10:41.000 --> 01:10:42.760
Der nimmt sich alle Punkte her

01:10:46.980 --> 01:10:49.620
und sortiert die nach ihren Polarkoordinaten.

01:10:50.560 --> 01:10:55.520
Das heißt, der nimmt sich irgendeinen Punkt r her und jetzt sortiert

01:10:55.520 --> 01:10:59.100
er alle Punkte der Menge m nach ihren Polarkoordinaten.

01:10:59.220 --> 01:11:04.520
Da, da, ein, da, da, da, da und so weiter.

01:11:04.940 --> 01:11:07.760
Das sind sehr viele Punkte.

01:11:08.300 --> 01:11:10.360
Sehr viele solche Endstücke.

01:11:11.620 --> 01:11:13.400
Ich habe n solche Strahlen.

01:11:13.560 --> 01:11:15.700
Die sortiere ich einfach jetzt nach ihren Polarkoordinaten.

01:11:15.800 --> 01:11:19.540
Ich nehme mal an, das sind so einige Annahmen, dass niemals zwei

01:11:19.540 --> 01:11:21.040
Punkte aus dem gleichen Strahlen liegen.

01:11:21.120 --> 01:11:23.200
Dass die also nicht die gleiche Polarkoordinaten haben.

01:11:23.880 --> 01:11:27.280
Man kann das aber durchaus, man kann sagen, wenn ich also zwei Punkte

01:11:27.280 --> 01:11:30.620
habe, zum Beispiel hier, die beiden liegen auf der gleichen

01:11:31.600 --> 01:11:34.460
Polarkoordinate, dann weiß ich aber, dass der erste Punkt hier

01:11:34.460 --> 01:11:37.740
garantiert kein Extrempunkt ist, den kann ich gleich rausstreichen.

01:11:38.040 --> 01:11:40.900
Insofern, wenn ich die sortiere und ich habe zwei, die die gleiche

01:11:41.560 --> 01:11:44.540
Polarkoordinate haben, dann nehme ich den, der weiter weg ist, weil

01:11:44.540 --> 01:11:46.440
das der potenzielle Extrempunkt ist.

01:11:46.440 --> 01:11:50.660
Insofern habe ich am Ende hier eine Reihe, eine Folge von solchen

01:11:50.660 --> 01:11:58.160
Strahlen, die eventuell sehr dicht nebeneinander liegen, ja, aber

01:11:58.160 --> 01:12:03.800
trotzdem schön so aufgeteilt, alle irgendwie radial angeordnet.

01:12:05.120 --> 01:12:09.500
Und jetzt gehe ich der Reihe nach diese Punkte durch.

01:12:10.120 --> 01:12:13.260
Ich fange bei irgendeinem an, zum Beispiel bei dem, der hier unten

01:12:13.260 --> 01:12:13.580
ist.

01:12:15.200 --> 01:12:18.980
Ich habe die Linie ja angeordnet, durch meine Sortierung.

01:12:19.480 --> 01:12:22.820
Ich nehme mal an, dass ich die in dieser Reihenfolge sortiert habe.

01:12:23.980 --> 01:12:29.300
Jetzt fange ich also bei irgendeinem Punkt P1 an und gehe zum Punkt P2

01:12:29.300 --> 01:12:31.280
und zum Punkt P3.

01:12:31.540 --> 01:12:33.240
Betrachte drei aufeinanderfolgende Punkte.

01:12:35.000 --> 01:12:41.940
Bei drei aufeinanderfolgenden Punkten habe ich folgende Situation, das

01:12:41.940 --> 01:12:47.720
ist entweder eine Linksdrehung, das wäre konvex, das wäre der Winkel,

01:12:48.600 --> 01:12:51.420
den ich, also dieser Winkel, das wäre dann hier Linksdrehung, das

01:12:51.420 --> 01:12:52.820
heißt, ich habe einen konvexen Winkel.

01:12:53.580 --> 01:12:59.420
Oder, wenn es eine Rechtsdrehung ist, dann weiß ich, der Punkt P2 ist

01:12:59.420 --> 01:13:00.940
garantiert kein Extrempunkt.

01:13:01.580 --> 01:13:08.280
Wenn ich eine Linksdrehung habe, dann könnte P2 ein Extrempunkt sein.

01:13:08.800 --> 01:13:10.700
Potenziell ist jeder Punkt ein Extrempunkt.

01:13:11.940 --> 01:13:13.380
P1, P2 und P3.

01:13:15.420 --> 01:13:19.280
Und ich fange also mit einem sicheren Extrempunkt an, zum Beispiel mit

01:13:19.280 --> 01:13:19.960
dem hier unten.

01:13:20.440 --> 01:13:23.520
Wenn ich mit dem anfange, dann würde ich also zunächst mal dorthin

01:13:23.520 --> 01:13:28.340
laufen und dann dorthin und hätte in dem Fall eine Rechtsdrehung und

01:13:28.340 --> 01:13:30.000
wüsste, der nächste Punkt ist kein Extrempunkt.

01:13:30.120 --> 01:13:31.160
Wir kommen gleich zu dieser Situation.

01:13:32.500 --> 01:13:37.580
Wenn es eine Linksdrehung ist, wie gesagt, dann, wir wissen, P1 ist

01:13:37.580 --> 01:13:39.080
ein Extrempunkt, ein sicherer.

01:13:40.020 --> 01:13:44.640
Dann ist P2 ein Kandidat, auch ein Extrempunkt zu sein.

01:13:46.340 --> 01:13:47.440
Da könnte einer sein.

01:13:48.480 --> 01:13:51.380
P3, der nächste, von dem weiß ich noch nichts.

01:13:52.520 --> 01:13:55.680
Und dann mache ich anschließend mit P2, P3, P4 weiter.

01:13:56.860 --> 01:13:59.920
Wenn also der nächste Punkt hier liegt, dann hätte ich hier nochmal

01:13:59.920 --> 01:14:05.320
die Situation, dann wären P2 und P3 Kandidaten für einen Extrempunkt.

01:14:05.320 --> 01:14:09.400
Und wenn aber der nächste dann irgendwo hier oben liegt, hätte ich

01:14:09.400 --> 01:14:13.900
diesen Winkel und dann hätte ich auf einmal festgestellt, hier habe

01:14:13.900 --> 01:14:14.800
ich eine Linksdrehung.

01:14:15.920 --> 01:14:17.040
Eine Rechtsdrehung.

01:14:17.560 --> 01:14:19.800
Dann wäre der Punkt hier unten kein Extrempunkt.

01:14:20.540 --> 01:14:23.880
Dann muss ich aber nochmal wieder zurücklaufen und muss gucken, was

01:14:23.880 --> 01:14:27.720
ist denn mit jetzt mit diesem Winkel.

01:14:28.660 --> 01:14:30.320
Der ist auch eine Rechtsdrehung.

01:14:30.860 --> 01:14:33.060
Dann wäre dieser P3 auch kein Extrempunkt.

01:14:33.720 --> 01:14:34.760
Das muss ich erkennen.

01:14:35.880 --> 01:14:37.280
Also, Linksdrehung ist das eine.

01:14:38.000 --> 01:14:40.260
Dann mache ich mit P2, P3, P4 weiter.

01:14:42.320 --> 01:14:44.020
Falls wir nicht schon am Ende sind.

01:14:44.560 --> 01:14:47.340
Also wir beginnen hier bei P. Das hier heißt P3 und gleich P. Das

01:14:47.340 --> 01:14:48.480
heißt, wir sind noch nicht am Ende.

01:14:50.240 --> 01:15:00.000
Und wenn wir feststellen, der Inhalt unseres Dreiecks ist 0, dann

01:15:00.000 --> 01:15:01.420
wissen wir diesen Kollinear.

01:15:01.580 --> 01:15:03.100
Das heißt, wir liegen auf einer Linie.

01:15:03.600 --> 01:15:04.840
Dann kann ich P2 vergessen.

01:15:06.080 --> 01:15:08.340
Und mache weiter mit P1, P3, P4.

01:15:08.460 --> 01:15:09.240
Mit dem nächsten Punkt.

01:15:09.660 --> 01:15:11.840
Sagen wir hier P4.

01:15:14.760 --> 01:15:14.980
So.

01:15:15.880 --> 01:15:23.660
Und jetzt habe ich also die Situation P1, P2, P3 ist eine

01:15:23.660 --> 01:15:24.440
Rechtsdrehung.

01:15:25.280 --> 01:15:29.320
Und in dem Fall, muss ich aufpassen, dann weiß ich, der Winkel ist

01:15:29.320 --> 01:15:30.020
konkav.

01:15:32.700 --> 01:15:34.840
P2 garantiert keinen Extrempunkt.

01:15:36.360 --> 01:15:40.760
Dann muss ich aber nicht weitermachen mit P2, P3, P4, sondern in dem

01:15:40.760 --> 01:15:45.320
Fall muss ich mit P1, P3, P4 weitermachen.

01:15:46.300 --> 01:15:47.660
Ich habe ja den Punkt vergessen.

01:15:47.800 --> 01:15:48.660
Den lasse ich raus.

01:15:49.300 --> 01:15:54.840
Das jetzt mache ich hier mit P1, P3 und irgendeinem P4 weiter.

01:15:57.960 --> 01:15:58.520
Falls

01:16:01.980 --> 01:16:06.300
P1 gleich P ist, dann weiß ich nämlich, dann ist P1 ein sicherer

01:16:06.300 --> 01:16:07.040
Extrempunkt.

01:16:08.300 --> 01:16:13.020
Wenn aber dass P1 noch kein sicherer Extrempunkt war, sondern nur ein

01:16:13.020 --> 01:16:16.800
Kandidat für einen Extrempunkt, wie zum Beispiel hier dieser Punkt P2

01:16:16.800 --> 01:16:17.260
hier oben.

01:16:18.080 --> 01:16:24.880
Wenn ich da P2, P3 und P4 angucke, oder irgendwie einen später, dann

01:16:24.880 --> 01:16:29.620
muss ich erstmal sehen, wie sieht das aus mit dem Winkel P0, P1, P3.

01:16:31.200 --> 01:16:33.140
P0, P1, P3.

01:16:34.620 --> 01:16:40.900
Der Winkel könnte nämlich, je nach Lage von dem P3, auch eventuell

01:16:40.900 --> 01:16:41.880
Konkav sein.

01:16:42.840 --> 01:16:45.200
Das heißt, dann wäre P1 kein Extrempunkt.

01:16:45.280 --> 01:16:50.240
Wenn also das P3 irgendwo hier hinten liegen würde, dann hätten wir

01:16:50.240 --> 01:16:55.540
einen solchen Winkel und wir hätten hier auf einmal, müssten dann P1

01:16:55.540 --> 01:16:57.020
auch vergessen.

01:16:57.480 --> 01:16:58.960
Wäre auch kein Extrempunkt.

01:16:59.500 --> 01:17:03.500
Das können wir aber erst dadurch erkennen, dass wir hier den Punkt P2

01:17:03.500 --> 01:17:08.260
ausgeschlossen haben, zu P3 gelaufen sind und dann nochmal gucken

01:17:08.260 --> 01:17:12.460
müssen, zurückgehen müssen einen Schritt und sehen, ist jetzt P1

01:17:12.460 --> 01:17:13.780
vielleicht doch kein Extrempunkt.

01:17:14.960 --> 01:17:19.500
Also das sind diese beiden Alternativen, je nachdem ob ich bei einem

01:17:19.500 --> 01:17:23.540
sicheren Extrempunkt gestartet habe, wenn das P1 ein sicherer

01:17:23.540 --> 01:17:27.520
Extrempunkt ist, dann kann ich mit P1, P3, P4 weitermachen.

01:17:27.980 --> 01:17:33.280
Ansonsten muss ich einen Schritt zurückgehen und mach dann mit P0, P1,

01:17:33.360 --> 01:17:34.000
P3 weiter.

01:17:34.680 --> 01:17:40.420
Und es ist klar, wenn jetzt P0, P1, P3 Konkave Winkel ist, dann muss

01:17:40.420 --> 01:17:42.780
ich entsprechend wieder einen Schritt zurückgehen.

01:17:44.300 --> 01:17:46.580
Ja, und muss eventuell wieder einen Punkt vergessen.

01:17:49.140 --> 01:17:51.800
Wie ist der Aufwand dafür, insgesamt?

01:17:53.700 --> 01:17:56.320
Ich muss zunächst mal alle Punkte sortieren hier oben.

01:17:57.180 --> 01:18:00.640
Das ist O von n mal log n.

01:18:03.300 --> 01:18:07.760
Ja, das sind meine n Polarkoordinaten, die ich dort bestimme.

01:18:07.880 --> 01:18:09.240
Das sind die Reihenfolge der Punkte.

01:18:10.860 --> 01:18:15.580
Und dann habe ich hier den sicheren Extrempunkt P zu wählen.

01:18:16.260 --> 01:18:25.540
Das ist der mit dem minimalen Y-Wert und außerdem unter dem mit

01:18:25.540 --> 01:18:32.320
minimalem Y-Wert, der mit dem meinetwegen größten X-Wert.

01:18:34.080 --> 01:18:34.240
Ja?

01:18:34.720 --> 01:18:36.060
Wie bestimme ich denn den Punkt?

01:18:36.300 --> 01:18:41.380
Sie nehmen sich drei Punkte her.

01:18:41.380 --> 01:18:42.820
Okay, sind ja mindestens drei Punkte drin.

01:18:42.880 --> 01:18:44.460
Wenn ich nur zwei Punkte habe, ist es trivial.

01:18:45.100 --> 01:18:46.480
Wenn ich drei Punkte habe, ist es auch trivial.

01:18:47.280 --> 01:18:51.080
Ich nehme also irgendwelche drei Punkte raus, bestimme einen Punkt im

01:18:51.080 --> 01:18:55.440
Inneren und bezüglich dieses Punktes mache ich dann meine Anordnung.

01:18:57.840 --> 01:18:58.280
Ja.

01:19:01.220 --> 01:19:01.660
Genau.

01:19:02.380 --> 01:19:05.520
Also ich muss einen Punkt im Inneren finden und den finde ich ganz

01:19:05.520 --> 01:19:08.800
einfach, indem ich einfach irgendeinen Punkt im Inneren eines Dreiecks

01:19:08.800 --> 01:19:10.820
nehme aus drei beliebigen Punkten meiner Menge.

01:19:13.040 --> 01:19:13.340
So.

01:19:14.220 --> 01:19:18.420
Jetzt habe ich also hier insgesamt den Algorithmus NlogN für das

01:19:18.420 --> 01:19:23.120
Sortieren der Punkte und an jedem, wenn ich jetzt drei nach da

01:19:23.120 --> 01:19:27.560
durchgehe, habe ich also, ich gucke mir jetzt jeden Punkt einmal an.

01:19:29.080 --> 01:19:33.880
Wenn ich einen, den ersten Fall habe hier, Linksdrehung, dann mache

01:19:33.880 --> 01:19:35.440
ich weiter, dann bleibt er drin.

01:19:37.820 --> 01:19:38.440
Dann

01:19:41.480 --> 01:19:43.820
habe ich das konstante Aufwand.

01:19:44.200 --> 01:19:46.840
Wissen wir, Linksdrehung, Rechtsdrehung kann ich über unsere

01:19:46.840 --> 01:19:47.960
Determinantenberechnung machen.

01:19:49.360 --> 01:19:54.360
Wenn ich Kolumnia habe, dann kann ich einen Punkt vergessen, den habe

01:19:54.360 --> 01:19:56.280
ich also gar nicht erst aufgenommen, den Punkt P2.

01:19:58.080 --> 01:20:03.900
Und wenn ich eine Rechtsdrehung habe, vergesse ich einen Punkt und

01:20:03.900 --> 01:20:06.780
muss aber nochmal zurückgehen.

01:20:08.640 --> 01:20:11.520
Das heißt, ich muss eventuell einen Punkt noch, dann habe ich also

01:20:11.520 --> 01:20:14.320
einen Punkt rausgelassen, muss aber eventuell dafür nochmal einen

01:20:14.320 --> 01:20:18.180
zurückgehen und muss eventuell den Punkt, den ich vorher als

01:20:18.180 --> 01:20:19.640
Kandidaten hatte, noch streichen.

01:20:21.740 --> 01:20:25.120
Ich muss aber für jedes einmal zurückgehen, lösche ich einen Punkt

01:20:25.120 --> 01:20:31.760
raus und das heißt, dass insgesamt ein Punkt nicht beliebig oft

01:20:31.760 --> 01:20:32.880
angeguckt werden kann.

01:20:33.340 --> 01:20:39.560
Der Aufwand insgesamt ist konstant für jeden dieser Vergleiche und ich

01:20:39.560 --> 01:20:42.820
habe insgesamt bei B einen linearen Aufwand.

01:20:44.720 --> 01:20:50.520
Also für dieses Durchlaufen durch meine Folge von Punkten, das sind N

01:20:50.520 --> 01:20:52.200
solche Punkte, die ich betrachten muss.

01:20:52.780 --> 01:20:57.680
Ich muss jeden Punkt einmal aufnehmen oder gleich löschen und wenn ich

01:20:57.680 --> 01:21:00.000
einen Punkt gelöscht habe, kann es sein, dass ich nochmal zurücklaufen

01:21:00.000 --> 01:21:02.440
muss an einen bereits aufgenommenen Punkt, eventuell löschen muss.

01:21:03.760 --> 01:21:08.660
Aber das ist insgesamt ein Aufwand, der bleibt linear und der Platz

01:21:08.660 --> 01:21:09.400
ist natürlich auch linear.

01:21:10.580 --> 01:21:13.960
Damit habe ich insgesamt einen Aufwand von N log N im Vergleich mit

01:21:13.960 --> 01:21:17.800
einem Aufwand, den wir beim ersten Algorithmus hatten, der war N hoch

01:21:17.800 --> 01:21:18.060
4.

01:21:18.640 --> 01:21:21.880
War aber auch sehr gut parallelisierbar.

01:21:22.580 --> 01:21:25.000
Mag ein Vorteil sein, aber der Aufwand war sehr hoch und hat eine

01:21:25.000 --> 01:21:26.480
völlig andere Idee, die man dort hatte.

01:21:27.160 --> 01:21:30.460
Und hier ist halt die Idee, dass ich mir nur angucke, sind das

01:21:30.460 --> 01:21:32.740
Rechtsdrehungen oder Linksdrehungen, beziehungsweise sind die

01:21:32.740 --> 01:21:38.900
Innenwinkel konkav oder konvex und ich weiß, dass die Innenwinkel bei

01:21:38.900 --> 01:21:42.660
der konvexen Hülle alle konvex sein müssen, deswegen ist das die Idee,

01:21:42.780 --> 01:21:43.580
die man hier anguckt.

01:21:45.720 --> 01:21:47.560
Ich gehe einfach durch die benachbarten Punkte.

01:21:48.200 --> 01:21:49.840
Jetzt habe ich hier aber ein Problem.

01:21:51.060 --> 01:21:58.180
Wenn ich mir so zwei Punkte anschaue, ich habe hier mal mal hier zwei

01:21:58.180 --> 01:22:03.900
Sachen, wenn ich hier so zwei Strahlen habe, diese Punkte hier liegen

01:22:03.900 --> 01:22:05.840
ganz klar weit voneinander entfernt.

01:22:06.120 --> 01:22:09.220
Wenn ich hier den dritten Punkt habe, das kann ich ganz klar

01:22:09.220 --> 01:22:13.040
feststellen, ist das eine Linksdrehung oder eine Rechtsdrehung.

01:22:14.520 --> 01:22:18.140
Wenn ich jetzt, nehmen wir mal diese Situation hier an,

01:22:21.900 --> 01:22:26.720
die Koordinaten sind ja üblicherweise, können ja beliebige Koordinaten

01:22:26.720 --> 01:22:28.820
sein, das sind reelle Zahlen.

01:22:30.640 --> 01:22:34.360
Jetzt habe ich hier zum Beispiel gesagt, dass wenn das gleich 0 ist,

01:22:36.400 --> 01:22:39.320
dann ist das Koordinaten, kann ich P2 vergessen.

01:22:40.840 --> 01:22:45.900
Oder ich habe hier zwei solche Punkte, die liegen sehr eng

01:22:45.900 --> 01:22:46.460
beieinander.

01:22:46.660 --> 01:22:49.100
Dann habe ich also hier eine solche Gerade und da habe ich eine solche

01:22:49.100 --> 01:22:49.520
Gerade.

01:22:51.100 --> 01:22:52.900
Liegt der jetzt rechts davon oder links davon?

01:22:55.820 --> 01:22:59.440
Und wenn ich reelle Zahlen habe, wenn ich mir das genauer angucke,

01:22:59.540 --> 01:23:01.820
dann habe ich gewisse Unsicherheiten, Ungenauigkeiten drin.

01:23:01.920 --> 01:23:06.240
Sie wissen das, dass reelle Zahlen, die genau dargestellt sind, sind

01:23:06.240 --> 01:23:08.340
nur innerhalb einer gewissen Genauigkeit.

01:23:09.060 --> 01:23:14.180
Und dann kann es sein, dass sich diese Situation hier, dass Punkte

01:23:14.180 --> 01:23:17.500
sehr eng beieinander liegen, nicht richtig entscheiden.

01:23:19.560 --> 01:23:23.260
Und das ist in der konkreten Anwendung durchaus ein Problem.

01:23:23.820 --> 01:23:29.560
Wenn ich alle Punkte der Menge betrachte, dann kann es passieren, dass

01:23:29.560 --> 01:23:34.120
die Koordinaten gerade so ungünstig liegen, dass ich bei der

01:23:34.120 --> 01:23:40.200
Entscheidung, ob ein Punkt jetzt rechts liegt, auf der Seite oder auf

01:23:40.200 --> 01:23:42.460
der Seite liegt, dass ich da Fehler mache.

01:23:44.140 --> 01:23:47.480
Weil die einfach zu nah beieinander liegen in Bezug auf diese

01:23:49.280 --> 01:23:49.720
Polarkoordinaten.

01:23:51.040 --> 01:23:56.760
Und auf einmal, wenn ich mich hier falsch entschieden habe, dann ist

01:23:56.760 --> 01:23:59.920
natürlich eines klar, dann sind diese Entscheidungen, die ich hier

01:23:59.920 --> 01:24:01.660
mache, auf einmal fehlerhaft.

01:24:03.240 --> 01:24:05.760
Und dann bekomme ich nicht mehr die komplexe Hülle raus, sondern ich

01:24:05.760 --> 01:24:09.200
habe eine andere Reihenfolge von Punkten auf einmal gefunden und gucke

01:24:09.200 --> 01:24:12.580
mir die falsch an und habe deswegen auf einmal die falschen Punkte

01:24:12.580 --> 01:24:13.060
rausgegeben.

01:24:13.500 --> 01:24:17.600
Das ist in der Praxis, wenn man dieses Verfahren implementiert, für

01:24:17.600 --> 01:24:21.000
beliebige Mengen von Punkten und dort die komplexe Hülle bestimmen

01:24:21.000 --> 01:24:24.900
möchte, also zum Beispiel irgendwie die äußere Kontur eines

01:24:24.900 --> 01:24:28.520
Werkstückes, das man baut und muss wissen, wo liegen dort die

01:24:28.520 --> 01:24:32.740
Extrempunkte, also die Oberfläche genau, wie wird die beschrieben, da

01:24:32.740 --> 01:24:33.840
kann das Probleme geben.

01:24:34.480 --> 01:24:36.880
Und da stürzen viele Verfahren einfach ab.

01:24:38.140 --> 01:24:40.780
Und deswegen hat man sich Gedanken gemacht, wie kann man das

01:24:40.780 --> 01:24:44.120
hinbekommen, dass solche Situationen erkannt werden.

01:24:44.720 --> 01:24:48.560
Es gibt interessante Ideen, wie man das machen kann, indem man einfach

01:24:48.560 --> 01:24:55.180
die Punktmenge ein bisschen verrüttelt, also die ein bisschen zufällig

01:24:55.180 --> 01:24:55.820
verdreht.

01:24:56.520 --> 01:25:01.540
Wenn ich die zufällig verdrehe, dann werden solche Situationen gerade

01:25:01.540 --> 01:25:04.260
so verändert, dass ich die anders machen kann.

01:25:04.380 --> 01:25:07.920
Das heißt, ich mache so zufällige Veränderungen meiner Punktmenge,

01:25:08.540 --> 01:25:13.740
gewisse Störungen baue ich da ein, ich drehe die so ein bisschen

01:25:13.740 --> 01:25:16.840
stochastisch und dann kriege ich das wieder besser hin.

01:25:16.900 --> 01:25:18.120
Und das Ganze macht man effizient.

01:25:18.980 --> 01:25:23.060
Und das sind Arbeiten, die hat sehr interessante Arbeiten von Herrn

01:25:23.060 --> 01:25:28.220
Mehlhorn, der in diesem ganzen Bereich algorithmische Geometrie einer

01:25:28.220 --> 01:25:31.840
der wesentlichen Wissenschaftler ist, der da sehr viel gemacht hat.

01:25:32.740 --> 01:25:37.360
Der hat sich mit der Problematik sehr intensiv beschäftigt, was sind

01:25:37.360 --> 01:25:41.980
eigentlich, wenn ich mir konkrete Mengen anschaue, mit solchen

01:25:41.980 --> 01:25:46.260
Randsituationen, wie kann ich die eigentlich so bearbeiten, dass ich

01:25:46.260 --> 01:25:50.040
noch ein robustes Verfahren habe, bei dem die Ergebnisse tatsächlich

01:25:50.040 --> 01:25:54.400
mit der Realität übereinstimmen und ich nicht durch solche Fehler

01:25:54.400 --> 01:25:57.160
aufgrund von Ungenauigkeiten in der Dachstellung der reellen Zahlen

01:25:57.160 --> 01:25:59.160
auf einmal falsche Ergebnisse kriege.

01:26:00.380 --> 01:26:01.360
Das war es für heute.

01:26:01.900 --> 01:26:03.560
Kontext der Hülle mache ich nächstes Mal noch fertig.

01:26:04.760 --> 01:26:08.600
Und dann noch eine Zusammenfassung, können wir nochmal über Inhalte

01:26:08.600 --> 01:26:09.840
der Vorlesung diskutieren.

01:26:10.680 --> 01:26:11.740
Also dann bis nächste Woche.

01:26:11.900 --> 01:26:12.440
Vielen Dank für heute.