Herzlich willkommen zurück zur Vorlesung effizienter Algorithmen.
Ich vertrete heute Professor Schmeck.
Professor Schmeck ist in Berlin, hat leider keine Zeit.
Deshalb ist heute die drittletzte Vorlesung.
Wir schauen uns heute nochmal algorithmische Geometrie an.
Und im nächsten Kapitel gehen wir auf verteilte Algorithmen ein.
Noch kurz der Hinweis hier, die Klausuranmeldung ist noch bis 6.
Juli freigeschaltet.
Falls ihr das noch nicht gemacht habt, meldet euch unbedingt an.
Denn nachträglich könnt ihr euch nicht mehr anmelden für die Klausur.
Ganz wichtig, bis zum 6.
Juli meldet euch für die Klausur an.
Wir haben letzte Woche angefangen, uns mit dem Thema algorithmische
Geometrie zu beschäftigen.
Ganz konkret, worum geht es hier eigentlich?
Wir beschäftigen uns mit typischen Problemen aus der Geometrie.
Allerdings nicht so, wie man das in der Schule gemacht hat.
Wir konstruieren hier nicht mit Zirkel und Lineal, sondern wir
versuchen diese Probleme durch Rammstückfragen oder mit medischen,
logischen Funktionen zu lösen.
Also so typische Objekte, mit denen man sich in der algorithmischen
Geometrie beschäftigt, das sind immer Punkte, Geraden, Linien,
Überebene und Polygone.
Wir haben uns letzte Woche auch schon...
Das erste Problem, mit dem wir uns beschäftigt haben, das war, wir
hatten eine Menge an Punkten in der Ebene.
Und wir wollten ermitteln, je nachdem, welches Rechteck da aufgespannt
wird, wie viele Punkte sich in diesem Rechteck befinden, von dieser
Punktemenge.
Dann haben wir gesehen, wenn man das naiv löst, hat man einen relativ
hohen Aufwand, aber durch geschickte Vorbereitung kann man das Ganze
auf einen konstanten Aufwand herunterbrechen.
Als nächstes haben wir uns dann angeschaut, wie kann man denn
ermitteln, ob ein Polygon einfach ist.
Also ein Polygon ist genau dann einfach, wenn sich keine...
Das kam erst später, wir haben zuerst ermittelt, wir haben ein
einfaches Polygon gegeben, also ein Polygon als Kantenzweig in der
Ebene und wir haben irgendeinen beliebigen Punkt und möchten jetzt
ermitteln, ob dieser Punkt in dem Polygon liegt oder außerhalb.
Als Beispiel wurde zum Beispiel angeführt, wenn man sich irgendwo in
der freien Natur befindet und ein Bauer hat zum Beispiel seine Weide
eingezäunt und es jetzt keine Ebene ist, sondern irgendwie über eine
bergige Landschaft geht, dann ist es vielleicht manchmal nicht mehr so
leicht zu ermitteln, wo denn der Zaun verläuft.
Dann könnte man zum Beispiel diese Strahlmethode, die hier vorgestellt
wurde, herausfinden, ob man sich denn gerade innerhalb der Weide
bewegt oder außerhalb.
Und dann sind wir nämlich zum dritten Problem gekommen und da ging es
darum, wir wollen ermitteln, ob ein Polygon gegeben ist, ob es einfach
ist.
Das heißt, ob sich irgendwelche Kanten dieses Polygons überschneiden.
An der Stelle werde ich jetzt auch weitermachen.
Also wir haben hier ein Polygon gegeben mit N-Ecken, also jeweils als
Kantenzug gegeben.
Das heißt, wir wissen in welcher Reihenfolge diese Ecken liegen, damit
sie sich zu einem Polygonzug zusammenfügen.
Und die Frage ist, ob dieses Polygon eben einfach ist.
Und dieses Problem eigentlich, ob ein Polygon einfach ist, ist das
Äquivalent zu einem anderen Problem, und zwar ob sich, wenn wir jetzt
N -geraden Segmenten haben, ob die sich überschneiden.
Das heißt, wenn wir dieses äquivalente Problem lösen können, dann
können wir auch dieses Problem lösen, herauszufinden, ob ein Polygon
einfach ist.
Jetzt ist es so, wenn man das Ganze naiv lösen würde, dann würde man
einfach alle Kantenpaare miteinander vergleichen.
Das heißt, wenn wir N-Kantenpaare haben, dann hätten wir hier
quadratischen Aufwand.
Da wir jedes Kantenpaar miteinander einmal vergleichen müssten.
Stattdessen kann man hier allerdings auch ein sogenanntes Planesweep
-Verfahren anwenden.
Das ist der sogenannte Bentley-Ottman-Algorithmus.
Und zwar, da wird folgendermaßen vorgegangen, man reduziert dieses
zweidimensionale Problem auf ein eindimensionales Problem.
Also wie gesagt, eigentlich ein Intervall-Überschneidungsproblem.
Und durch diese Reduktion kann man dadurch eine erhebliche
Laufzeitverbesserung bewirken.
Wie genau das funktioniert, schauen wir uns jetzt an.
Also ganz zu Beginn noch, was ist eigentlich ein Intervall
-Überschneidungsproblem?
Also wir haben hier
n Intervalle gegeben, die einmal durch einen Startpunkt x und einen
Endpunkt y definiert sind.
Und wir wollen ermitteln, ob sich diese Intervalle irgendwie
überschneiden, wie es hier rechts angegeben ist.
Also wie geht man da vor?
Nehmen wir an, wir haben jetzt diese Intervalle irgendwie gegeben in
der Liste.
Wir sortieren die zuerst nach den Endpunkten.
Also zwei Endpunkte hier, weil hier wird jetzt x und y beide als
Endpunkte betrachtet.
Also die Intervalle ändern ja links und rechts.
Um es ein bisschen anschaulicher zu halten, sage ich jetzt für x, dass
das ein Anfangspunkt ist und für y ein Endpunkt.
Wie gehen wir dann vor?
Also wir sortieren die gemäß ihrer Größe, diese Intervalle, nach den
Endpunkten.
Und dann muss ich ja nur überprüfen, ob in dieser sortierten Folge ein
xi, also ein Startpunkt, vor einem Endpunkt auftritt.
Wobei der Index für den Endpunkt, der muss kleiner sein als für den
Startpunkt.
Das heißt, wenn wir uns das mal in diesem Beispiel hier anschauen,
dann sehen wir hier das erste Intervall 1.
Das ist hier, hier finden keine Überschneidungen statt.
Wenn wir uns dann das nächste Intervall anschauen, x2, also das I2,
das zweite Intervall, sehen wir, dass hier an der Stelle bereits das
dritte Intervall beginnt.
Das heißt, hier findet eine Überschneidung statt, zwischen dem zweiten
und dem dritten Intervall.
Wenn wir da noch ein Stückchen weiter nach rechts gehen, sehen wir
auch, dass bereits das vierte Intervall beginnt, bevor das dritte
endet.
Also hier an der Stelle.
Und insgesamt können wir dann festhalten, dass x2 und x3 sich
überschneiden und sowohl x3 und x4 auch.
Der beste Aufwand für so ein Verfahren ist einfach nlogn.
Warum?
Weil das Sortieren des Erfolge erfordert insgesamt nlogn, einfach mit
einem effizienten Sortierverfahren.
Und dieser Aufwand, dieses Überprüfen der Überschneidung auf der
sortierten Liste, der ist am Ende linear, weil er die Liste einmal von
Anfang bis Ende durchtransferieren kann.
Okay.
Wie lässt sich jetzt das Ganze hier auf dieses Polygon, auf dieses
Überschneidungsproblem in der Ebene übertragen?
Das heißt, wir haben hier, also wir bedenken uns einen Besen, plane
sweep, sweep von englisch fegen, der über dieses Polygon, also von
links nach rechts, drüber fegt.
Und an diesen einzelnen Punkten, an den Ecken des Polygons, bestimmte
Operationen durchführt.
Diese Anfangs- und Endpunkte der Kanten dieses Polygons sind
sogenannte Haltepunkte.
Das heißt, wie gehen wir hier vor?
Wir sortieren auch erstmal die Haltepunkte nach ihren X-Koordinaten.
Das ist ja vorher auch ein Aufwand von nlogn.
Alternativ könnte man hier auch einen direkten binären Slew aufbauen.
Damit würde man sogar auch die lineare Laufzeit herunterbauen.
Das Entscheidende ist jetzt,
welche Operationen an diesen Haltepunkten durchgeführt werden.
Das schauen wir uns auf der nächsten Folie an.
Also wir haben hier eine Sweepline, eine Sweepline L, die speichert
Kanteninformationen.
Also die speichert Kanteninformationen ist die Punkte, die gerade von
der Sweepline, oder die Kanten, die von der Sweepline gerade
traversiert werden, wo die gerade drüber geht, die werden in der
Sweepline L gespeichert.
Das heißt, wenn ich jetzt an irgendeinem Punkt ankomme, nehmen wir zum
Beispiel hier für den ersten Fall mal den Punkt hier oben.
Ja, dann lösche ich in dem Moment, genau das ist dieser Punkt PH
jetzt, im ersten Fall.
Dann lösche ich erstmal alle Kanten, die sich gerade in der Sweepline
befinden, also die in der Sweepline gespeichert sind, die in PH enden,
also in diesem Punkt enden und links von der Sweepline liegen.
Also die Sweepline befindet sich ja dann genau an dem Punkt hier.
Mal noch so einzeichnen, das ist ja unsere Sweepline.
Das heißt zum Beispiel, wir würden diese Kante hier löschen, diese
löschen, weil die endet in PH.
Das heißt für jede Kante, die gelöscht wird, überprüfe ich, ob die
Kante, die sich direkt darüber befindet, also entsprechend nach den Y
-Koordinaten, und die Kante, die sich direkt darunter befindet, ob die
sich überschneiden.
An der Stelle befinden sich jetzt keine weiteren Kanten, wir haben nur
die hier unten, die sich noch darin befindet.
Aber das heißt, wir haben nur eine einzige weitere Kante in der
Sweepline.
Und das heißt, wir können ja auch keine Überschneidungen prüfen.
Anders würde es zum Beispiel aussehen, wenn wir uns hier befinden
würden.
Dann wären jetzt zu dem Zeitpunkt die Kante hier oben und die Kante
hier unten in der Sweepline.
Das heißt, wir würden zu dem Zeitpunkt, also wenn wir uns hier an
diesem Punkt befinden würden, würden wir überprüfen, ob sich die Kante
hier oben, also es ist hier KO oder es ist KO, ob die sich
überschneiden.
Nachdem wir diesen ersten Schritt abgearbeitet haben, kommen wir zum
zweiten Schritt.
Das heißt, im zweiten Schritt tragen wir für jede Kante, die in PH
startet, den Endpunkt PJ ein.
Das heißt, wir fügen die Kante dieser Sweepline hinzu.
Außerdem überprüfen wir, ob die Kante, die wir gerade eingetragen
haben, ob die sich eben auch mit dieser Kante KO oder KO
überschneidet.
Also wenn wir zum Beispiel im zweiten Fall hier wären, also wenn das
unser PH wäre, dann würden wir einmal diese Kante hier eintragen, weil
die beginnt ja in PH, und diese Kante hier, die würden wir auch
eintragen.
In dem Moment, wo wir beide Kanten eintragen, überprüfen wir auch, ob
die sich hier mit dieser Kante oben, also KO, auch mit dieser Kante
unten hier, KO.
Ich habe leider nicht mehr Farben zur Verfügung, sonst würde ich das
noch entsprechend besser kennzeichnen.
Aber ich hoffe, das wird klar.
Also diese Kante hier unten, das ist KO, und die Kante hier oben, das
ist KO.
In dem Moment, wo wir uns an diesem Punkt befinden, fügen wir diese
Kanten hier, also die von diesem PH abgehen, einmal hier nach rechts
oben und einmal nach rechts unten, und überprüfen im gleichen Moment,
ob die sich jeweils mit der oberen und der unteren Kante
überschneiden.
Dann würden wir hier herausfinden, dass sich diese Kante mit der Kante
hier unten überschneidet.
Und werden entsprechend ermittelt, dass das Polygon nicht einfach ist.
Das bringt uns auch schon zum dritten Punkt, nämlich falls eine
Kantenüberschneidung festgestellt wird, dann ist der zu Ende der
Algorithmus einfach und gibt zurück, dass der Punkt nicht einfach ist.
Andernfalls wandert die Sweep Line weiter zum nächsten Haltepunkt.
Das müsste dann hier sein, an der Stelle.
Dann wird dieses Prozedere wiederholt.
Und wenn der letzte Haltepunkt abgearbeitet wurde und keine
Überschneidung festgestellt wurde, dann ist das Polygon einfach.
Jetzt die Frage natürlich, wie kann man denn dieses Verfahren
möglichst effizient implementieren.
Und zwar die Kanten, die in dieser Sweep Line gespeichert werden, die
werden in einem balancierten Suchbaum hinterlegt.
Im Grunde ist es einfach, also wenn man sich vorstellt, wenn es jetzt
nicht so ein einfaches Polygon ist wie hier, wo wir immer nur eine
Handvoll Kanten haben, sondern wenn es viele sind.
Gerade wenn wir dieses andere Problem betrachten, dass wir ermitteln
wollen, ob sich in einer Menge von Geraden, ob sich da irgendwelche
überschneiden, dann kann es ja sein, dass wir mehrere Hundert oder
Tausende Kanteninformationen gerade in der Sweep Line gespeichert
haben.
Das heißt, wir verwenden hierfür einen balancierten Suchbaum, indem
wir die Kanteninformationen hinterlegen.
Und durch den balancierten Suchbaum können wir sicherstellen, dass wir
insgesamt logarithmische Laufzeit bei den Einfüge- und
Löschoperationen erreichen.
Was lässt sich noch weiter über die Laufzeit sagen?
Na ja, insgesamt wird ja jede Kante einmal in diese Sweep Line
eingefügt und einmal wieder gelöscht.
Das heißt, wir erhalten dadurch insgesamt eine Laufzeit von n log n.
Das ist nämlich nur für die Sortierung.
Und diese Sweep Line selbst, also dieser Vorgang, diese Operation an
den Haltepunkten, das benötigt insgesamt eine lineare Laufzeit.
Da werde ich jede Kante nur einmal aufbearbeiten.
Und diese ganzen Operationen hier, die können in konstanter Zeit
ausgeführt werden.
Platz ist auch maximal linear.
Im schlimmsten Fall haben wir n Linien oder Kanteninformationen in der
Sweep Line gespeichert.
Das war auch schon das dritte Problem.
Jetzt beschäftigen wir uns mit dem vierten und letzten Problem für
dieses Kapitel.
Und zwar geht es hier um die konvexe Hülle.
Also wir haben eine Menge von m, von m Punkten.
Zur Vereinfachung betrachten wir die nur in der Ebene.
Aber es gibt auch die Verfahren, die ich gleich vorstellen werde.
Dafür lassen sich auch äquivalente Verfahren in höherer Dimension
erarbeiten.
Also wir wollen die konvexe Hülle dieser Punkte m bestimmen.
Jetzt stelle ich die Frage, was ist denn eigentlich die konvexe Hülle
überhaupt?
Die konvexe Hülle ist die kleinste Teilmenge dieser Ebene, die m
enthält.
Das heißt, diese konvexe Teilmenge soll keine anderen Elemente der
Ebene enthalten.
Und die Frage ist natürlich, wenn wir eine Punktemenge haben, welche
Punkte dieser Menge formen denn den Rand der konvexen Hülle von m.
Um das Ganze nochmal ein bisschen anschaulicher darzustellen, haben
wir hier diese folgende Punktmenge.
Also das ist unsere Punktmenge m und die konvexe Hülle.
Das wäre hier zum Beispiel,
wenn man diese Randpunkte
miteinander verbindet.
Also wenn diese Powerpointfolie unsere Ebene ist, E2 hier oben, dann
ist die konvexe Hülle dieser Punktemenge m hier.
Also das ist unser m.
Dann ist eben hier dieser Kantenzug, dieses Polygon, die kleinste
Teilmenge von dieser Ebene, von dieser Powerpointpräsentation, die nur
Punkte aus m enthält.
Und das sind nämlich die konvexe Hülle, die wir durch diese
Extrempunkte definiert, also die Punkte, die am Rand dieser Menge
liegen.
Und wenn man diese ganzen Extrempunkte miteinander verbindet, dann
erhält man den Kantenzug des Polygons, das diese konvexe Hülle
definiert.
Und wenn wir die konvexe Hülle ermitteln wollen, von der Punktemenge,
dann wollen wir nicht nur die Extrempunkte haben, sondern wir wollen
auch wissen, in welcher Reihenfolge die angeordnet werden müssen, also
den Kantenzug, den diese konvexe Hülle definiert.
Ja, im Folgenden werde ich insgesamt vier Verfahren vorstellen.
Und die nutzen alle verschiedene Eigenschaften aus, die in konvexe
Mengen bzw.
Polygone zugrunde liegen.
Der erste Ansatz ist erstmal ein naiver Ansatz, den wir hier
betrachten.
Und da nutzt er folgende Eigenschaft.
Also wenn ein beliebiger Punkt, also wir betrachten einen beliebigen
Punkt X, wenn es möglich ist, diesen Punkt in ein Dreieck
einzuschreiben aus drei anderen Punkten dieser Menge M, also PQR,
diese anderen drei Punkte, und keiner dieser drei Punkte, also X,
entspricht, dann wissen wir, dass X kein Extrempunkt ist.
Ja, um das Ganze mal ein bisschen deutlicher zu machen, nehmen wir an,
hier sehen wir uns eine Menge N mit vielen Punkten, und wir greifen
uns jetzt einen Punkt hier X raus, und wir sehen, also es gibt andere
Punkte in dieser Menge, der sich X in ein Dreieck einschreiben lässt,
dann wissen wir, dass X kein Extrempunkt ist.
Diese Eigenschaft können wir nutzen, um den Algorithmus zu definieren.
Und zwar läuft es folgendermaßen ab, wir überprüfen für jeden
einzelnen Punkt in dieser Menge, ob er sich in so ein Dreieck
einzwängen lassen kann.
Das heißt, wenn wir das durchführen, das heißt, wir betrachten jeden
einzelnen Punkt, das heißt, wir haben insgesamt probischen Aufwand pro
Punkt.
Es gibt ja hier, wir müssen ja theoretisch alle Punktekombinationen
überprüfen, also alle Punktekombinationen aus drei Punkten, die sich
in dieser Menge befinden.
Also nicht nur PQR, sondern auch diese ganzen anderen Punkte, die sich
eingezeichnet haben.
Und das kann man sich ja leicht ausreichen, das ist dann im Endeffekt
ein Binomialkoeffizient, und wenn man den auflöst, hat man dann eben
einen probischen Aufwand.
Wenn ich dieses Verfahren für jeden einzelnen Punkt durchgeführt habe,
habe ich dann am Ende H-Extrempunkte.
Wenn ich die Extrempunkte habe, weiß ich aber noch nicht den
Kantenzug.
Also ich weiß da, welche Punkte meine konvexe Hülle definieren, aber
ich weiß nicht, in welcher Reihenfolge ich sie anordnen muss, um
daraus das resultierende Polygon zu ermitteln.
Und die Frage ist, wie gehe ich denn da vor, um die korrekte
Reihenfolge zu ermitteln?
Und zwar das Ganze kann ich mithilfe von radialer Sortierung machen.
Also ich habe ja meine H-Extrempunkte.
Und dann wähle ich einen beliebigen Punkt R im Inneren, also von dem
ich weiß, dass es ein innerer Punkt dieser Menge M ist.
Und dann sortiere ich die Extrempunkte jeweils bezüglich ihres Winkels
mit der X-Achse.
Also das ist hier unser Punkt R.
Und dann berechne ich die Winkel, die diese Dreiecke im Endeffekt
aufspannen.
Wenn das unser R ist, dann lege ich hier eine waagrechte Linie rein.
Und auf Basis dieser waagrechten Linie kann ich dann den Winkel zu P
berechnen, also im Endeffekt dieser Winkel, der hier aufgespannt wird.
Einmal von der waagrechten Linie, also der Linie, die R durch die X
-Achse beschreibt, mit P. Und das kann ich für jeden einzelnen
Extrempunkt machen.
Und danach habe ich im Endeffekt Polarkoordinaten.
Und diese Koordinaten kann ich dann radial sortieren, also
entsprechend dem Winkel.
Das heißt, der Winkel wird ja dann, wenn ich in diese Richtung gehe,
immer größer.
Und durch diese radiale Sortierung ergibt sich dann eine eindeutige
Darstellung des Kammzugs.
Also ist ja klar, dass die einzelnen Punkte, die entsprechen den
Winkeln, die sind aufeinanderfolgend.
Also zuerst der kleinste Winkel, dann der zweitkleinste.
Diese Winkelberechnung, also anstatt hier irgendwelche Winkel zu
berechnen, kann ich auch die Determinante verwenden, nach dem
Verfahren, das wir schon letzte Woche kennengelernt haben.
Die Determinante gibt ja im Endeffekt an, wie, wenn ein Tunnel zum
Beispiel links dieser Linie vorliegt, wie weit links er liegt.
Also wie stark die Quantifizierung dieses Abstandes ist.
Okay, wenn wir uns den Aufwand für dieses Verfahren anschauen, dann
sehen wir, dass wir insgesamt...
Also der Aufwand, der hier entsteht, insgesamt haben wir sogar einen
Aufwand von n hoch 4.
Denn diese Punktprobe, die wir durchführen in Schritt A, wird ja für
jeden einzelnen Punkt durchgeführt.
Also n mal den Aufwand von n hoch 3 gibt insgesamt den Aufwand von n
hoch 4.
Das ist der Aufwand, der in Schritt A entsteht.
Und in Schritt B erhalten wir den Aufwand von h mal Logarithmus von h,
denn wir haben ja h Extrempunkte.
Und die Sortierung von h Extrempunkten, ja, können wir durch ein
effizientes Verfahren in superlinearer Laufzeit bewerkstelligen.
Das heißt, der Aufwand von o von n hoch 4 ist natürlich wesentlich
größer, als der Aufwand für die radiale Sortierung.
Also diese Punktproben hier in A durchzuführen ist wesentlich
aufwendiger als die Sortierung der Extrempunkte.
Das heißt, wir haben insgesamt Aufwand von o von n hoch 4.
Der Platz, den wir insgesamt benötigen, ist auch maximal linear, denn
im schlimmsten Fall sind ja alle Punkte der Menge m Extrempunkte.
Dann der zweite Ansatz, den wir betrachten, das ist der sogenannte
Graham -Scan.
Hier führen wir jetzt direkt eine radiale Sortierung der einzelnen
Koordinaten aus.
Also wie in diesem vorherigen Schritt in 1b, wo wir die Extrempunkte
radial sortiert haben, entsprechend ihren Polarkoordinaten, machen wir
das hier von Anfang an für alle Koordinaten.
Für alle Koordinaten im Endeffekt wichtig ist vor allem hier dieser
Winkel x.
Also der Winkel, den der Punkt hat zur x-Achse.
Und dieser Graham-Scan, der geht folgendermaßen vor.
Der bestimmt sukzessive die Extrempunkte, indem er die Punkte
entsprechend ihrer radialen Sortierung abläuft.
Das Ganze läuft folgendermaßen ab.
Wir wählen irgendeinen sicheren Extrempunkt als Startpunkt, das ist
unser P. Ein sicherer Extrempunkt ist zum Beispiel der Punkt, der die
kleinste y-Koordinaten hat.
Das ist ja von vornherein klar, dass der Teil der komplexen Hülle sein
muss.
Und als nächstes nutzen wir da den Winkel zwischen drei jeweils
aufeinanderformenden Punkten, um zu entscheiden, welcher dieser Punkte
Teil der komplexen Hülle ist.
Und diese aufeinanderformenden Punkte, die sind durch die radiale
Sortierung gegeben.
Also durch die radiale Sortierung ist ja eindeutig bestimmt, welche
Punkte aufeinander folgen.
Wir betrachten jetzt exemplarisch.
Also es gibt drei Fälle, die auftreten können, wenn wir drei
aufeinanderfolgende Punkte betrachten.
Also wir haben P, dann als Nachfolger P1, P2, P3.
Was kann hier passieren, wenn wir den Winkel betrachten, der von
diesen drei aufeinanderfolgenden Punkten bestimmt wird?
Also diesen Winkel an sich, den müssen wir auch nicht direkt
berechnen, sondern wir nehmen auch hier wieder die Determinante.
Durch die können wir ja entscheiden, ob ein Punkt links oder rechts
von einer Gerade liegt, beziehungsweise auf einer Gerade.
Okay, also was passiert hier?
Wir haben ja die zwei Punkte P1, P2, P3.
Wir berechnen diese Determinante, die sagt uns, wenn die Größe gleich
0 ist, dass hier eine Linkstrehung stattfindet.
Das bedeutet ja im Endeffekt nichts anderes, dass der Punkt P1, dass
der links dieser Gerade P2, P3 liegt.
Das heißt, wenn hier eine Linkstrehung stattfindet, dann weiß ich,
dass dieser Innenwinkel hier, also dieser Winkel hier, dass der konvex
ist, also kleiner als 180 Grad.
Wenn das der Fall ist, weiß ich, dass P2, muss man auch mal unserem
momentanen Kenntnisstand, muss ein Extrempunkt sein.
Aber wenn ich ja hier P2 jetzt auslassen würde, nur P1, P3, dann wäre
das ja keine konvexe Hülle.
Denn P2 würde ja außerhalb dieses konvexen Polygons liegen.
Nachdem ich diese Berechnung durchgeführt habe, nehme ich P2 in die
konvexe Hülle auf und mache weiter mit P4.
Also führe diese Berechnungsvorschrift hier in Schritt 2 für den
nächsten Punkt durch.
Das Ganze nur sofern dieser dritte Punkt hier nicht dem Startpunkt
entspricht.
Denn diese Abbruchbedingung hier, das trifft genau dann auf, wenn ich
nach meinem Verfahren wieder ganz am Anfang gelandet bin.
Also wenn ich einmal diese konvexe Punktlänge vollständig abgelaufen
habe.
Der zweite Fall, der auftreten kann, ist, wenn alle drei Punkte auf
einer Linie liegen.
Das ist ja genau dann der Fall, wenn die Determinante, also von diesem
Punktedreieck, wenn die gleich Null ist.
Also das heißt, man nennt das auch, wenn die auf einer Linie liegen,
dass die kolinear sind.
Das heißt, wenn die kolinear sind, dann weiß ich ja, P2 kann kein
Extrempunkt sein.
Beziehungsweise ich brauche P2 nicht, denn alle Informationen, die ich
für die konvexe Hülle benötige, sind bereits in P1 und P3 enthalten.
Also P2 liegt zwar auf der konvexen Hülle, aber ich brauche P2 nicht,
um die konvexe Hülle eindeutig bestimmen zu können.
Das heißt, ich lösche P2, beziehungsweise ich gehe einfach weiter und
ich schreibe den nächsten Punkt P4.
Auch hier wieder unter der Bedingung natürlich, nur wenn P3 nicht
schon der Startpunkt war, weil ich dann bereits am Ende des Verlaufs
bin.
So, dann der letzte Fall.
Ist eigentlich auch der interessanteste.
Und zwar passiert, wenn hier eine Rechtsdrehung stattfindet.
Und zwar ist dann folgendermaßen, wenn der Punkt P3 rechts von dieser
geraden P1, P2 liegt.
Und es bedeutet ja letztendlich hier, also an der Zeichnung kann man
sehr schön sehen, dass P2 kein Teil der konvexen Hülle sein kann, weil
wenn ich hier einen Kantenzug ziehen würde, dann wäre das Polygon hier
nicht konvex.
Dann hätte ich hier so eine konkabe Hüllung.
Das heißt, wir haben ja keine Sorge gesehen, der Innenwinkel von
diesem Dreieck, der wäre ja über 180° groß.
Ja, das heißt, er ist konkab.
P2 kann nicht Teil der konvexen Hülle sein.
Falls P1 der Startpunkt war, also gegeben P1 war der Startpunkt, dann
mache ich weiter mit P1, P3, P4.
Also dann lösche ich P2 direkt und mache weiter mit P4.
Falls allerdings P1 nicht der Startpunkt ist, dann gehe ich einen
Schritt zurück.
Das ist eigentlich hier der entscheidende Punkt.
Und zwar dann mache ich weiter hier mit P3, P1 und P0.
Es könnte ja sein, dass ich im ersten Schritt, z.B.
in der Situation hätte ich jetzt irgendwie P2, also wenn ich jetzt
zuerst nur P0, P1 und P2 betrachtet hätte, hätte ich ja P2
hinzugefügt, weil der, sag ich mal, der Innenwinkel hier, weil der ja
konvex ist.
Allerdings habe ich im nächsten Schritt festgestellt, dass P2 gar
nicht zur konvexen Hülle gehört.
Da es nämlich einen anderen Punkt P3 gibt, der noch viel weiter rechts
liegt, der noch extremer ist als P2.
Das heißt, durch das Verfahren ist es auch möglich, dass Punkte, von
denen zunächst ausgegangen wurde, dass sie Teil der konvexen Hülle
sind, dass sie nachträglich eliminiert werden.
Bei einer Linksdrehung gehe ich einfach weiter in meiner Punktemenge,
so laufen die beide ab.
Bei einer Rechtsdrehung gehe ich gewissermaßen einen Schritt zurück
und schaue mir erst mal ab, okay, diese neue Information, die ich
jetzt hier gewonnen habe, dass ein Punkt doch nicht Teil der konvexen
Hülle ist, jetzt muss ich überprüfen, ob eventuell noch ein weiterer
Punkt, von dem ich bisher ausgegangen bin, dass er Teil der Hülle ist,
auch noch wegfällt.
Es könnte ja z.B.
auch sein, dass P1, wenn P1 noch weiter hier links liegen würde, dass
ich herausstelle, dass P1 auch nicht Teil der konvexen Hülle ist.
Bei der P3 einfach so viel extremer.
Die Laufzahl dieses Verfahrens ist insgesamt N log N, denn der größte
Aufwand, der auch hier wieder entsteht, ist durch die radiale
Sortierung.
Wenn ich Endpunkte sortiere, habe ich einen Aufwand von N log N.
Und der B-Teil, also das ist wieder hier der A-Teil, und der B-Teil,
hier steht es schon, also dieser Greyhound-Scan insgesamt benötigt
tatsächlich nur Endpunkte, da ich jeden Punkt einmal anschaue, bzw.
einmal hinzufüge.
Ich kann ihn zwar nachträglich entfernen, aber ich füge nur einmal
hinzu.
Der Platzaufwand ist auch hier wieder linear, denn im schlimmsten Fall
sind alle meine Punkte der Menge N, M sind die Teile der konvexen
Hülle.
Um das Ganze mal, das ist ein relativ abstrakter Algorithmus, um das
Ganze mal ein bisschen zu verdeutlichen, ich habe
hier noch ein kleines R-Blatt,
um es einfach
mal zu verdeutlichen, wie dieser Algorithmus praktisch abläuft.
Also im ersten Schritt wird hier diese radiale Sortierung
durchgeführt.
Das dauert ein bisschen lang, also hier werden alle Winkel berechnet.
Entsprechend sortiert, das wird hier farblich markiert durch diese
Kanten.
Und ein Extrempunkt wird auch noch bestimmt.
Also hier oben steht es nochmal genau, was passiert.
Also im ersten Schritt wird ein Extrempunkt bestimmt, der auf jeden
Fall Teil der konvexen Hülle ist, das ist zum Beispiel der oberste
Punkt.
Genau, hier steht es mit der größten Y-Koordinate.
Und im zweiten Schritt werden diese ganzen Punkte hier der Menge,
werden entsprechend ihrem Winkel zu Y sortiert.
Und im nächsten Schritt beginnt dann der Algorithmus, also gegen den
Uhrzeigersinn, die einzelnen Punkte abzulaufen und zu ermitteln,
welche Punkte denn Teil der konvexen Hülle sind.
Genau, also im ersten Schritt wurde festgestellt, okay,
diese Kante hier, die ist Teil der konvexen Hülle, die wird hier
zugefügt.
Und da bin ich auch schon ein bisschen schneller drüber.
Hier ist auch diese Kante, die wurde auch schon der zu konvexen Hülle
zugefügt.
So, als nächstes schaue ich mir an, sprechend der radialen Sortierung.
Das ist der Punkt hier.
Also man sieht ja ungefähr an dieser Sternformation, wenn man die von
links nach rechts durchgeht, sieht man hier diese radiale Sortierung.
Also das ist der nächste Punkt, der betrachtet wird.
Das ist dann der zweitnächste, der drittnächste, fittnächste und so
weiter.
Genau, da wurde jetzt eben entsprechend diese determinante berechnet.
Wurde festgestellt, okay, hier handelt es sich um eine Linksdrehung.
Diese drei Punkte, die sind Teil der konvexen Hülle.
Als nächstes schaue ich mir den Punkt an.
Stelle auch hier fest, das ist eine Linksdrehung.
Ich...
Dieser Punkt ist Teil der konvexen Hülle.
So, als nächstes in der radialen Sortierung ist dieser Punkt dran.
Da handelt es sich auch erstmal um eine Linksdrehung.
Als nächstes hier.
Und die Punkt wird auch erstmal davon ausgegangen, dass der Teil der
konvexen Hülle ist.
Jetzt wird es allerdings interessant, weil jetzt habe ich einen Punkt
hier unten gefunden, der extremer ist als die beiden.
Das heißt, ich berechne hier auch wieder dieses Dreieck.
Stelle fest, okay, hier ist keine...
Das ist eine Rechtsbindung, ja.
Also der in Winkel hier ist konkret.
Das heißt, ich muss den Punkt eliminieren.
Das mache ich auch im nächsten Schritt.
Also gehe ich wieder zurück.
Und will jetzt ein Dreieck mit dem Punkt, mit dem Punkt und mit dem
Punkt.
Berechne auch hier anstelle fest.
Okay, dieser Winkel ist konkav.
Also kann dieser Punkt hier auch nicht Teil der konvexen Hülle sein.
Okay, dann bin ich schließlich wieder...
Also ich bin nochmal einen Schritt zurückgegangen.
Berechne diesen in Winkel aus den drei Punkten.
Anstelle auch hier fest, ist der Punkt hier.
Hierdurch kommt auch ein konkaber Innenwinkel zustande.
Also kann dieser Punkt auch nicht Teil der konvexen Hülle
sein.
Allerdings habe ich...
Und dann betrachte ich die drei Punkte hier.
Und stelle fest, okay, hier handelt es sich wieder um einen konvexen
Innenwinkel.
Das heißt, die sind auf jeden Fall Teil der konvexen Hülle gegeben
unseres aktuellen Wissenstaates.
Gehe ich weiter mit dem Punkt hier oben.
Schaue mir den an.
Okay, hier handelt es sich wieder um eine Linkstrehung.
Schaue mir den Punkt als nächstes an.
Stelle fest.
Ja, okay.
Dieser Punkt ist doch nicht Teil der konvexen Hülle.
Weil hier im entsprechenden konkaber Innenwinkel ist.
Genau.
So kann man das Ganze hier durchmachen, sich durchklicken.
Sieht diese Punkte, die werden alle sukzessive abgearbeitet.
Entsprechend der radialen Sortierung.
Und am Ende, wenn man das Ganze beschleunigt, sieht man, dass hier
sukzessive die konvexe Hülle ausgebaut wird.
Und das ist dann unser Ergebnis.
Okay.
Das war dann der zweite Ansatz.
Dann machen wir weiter mit dem dritten Ansatz.
Und zwar, wir haben uns bisher immer darauf beschränkt, vor allem
zuerst mal die Extrempunkte zu bestimmen.
Und danach den Kantenzug.
Allerdings kann man auch andersherum vorgehen.
Das heißt, wir bestimmen direkt die Kanten Polygons und nicht nur die
Extrempunkte.
Das heißt, dadurch können wir uns z.B.
sparen, im Nachhinein die korrekte Reihenfolge der Extrempunkte durch
eine radiale Sortierung zu ermitteln.
Und zwar, wenn wir diesen dritten Ansatz wählen, also wenn wir direkt
nach den Kanten gehen, können wir folgende Eigenschaften ausnutzen.
Also gegeben, wir haben hier zwei Punkte P und Q.
Wenn die tatsächlich, diese Kante, Teil der konvexen Hülle ist, dann
ist es ja so, dass alle anderen Punkte aus M, dass sie nur auf einer
Seite von dieser Gerade liegen dürfen.
Also diese Gerade hier, die durch diese beiden Punkte bestimmt wird.
Das heißt, wenn man sich das mal aufmalt, wenn z.B.
hier, das kann man relativ schön sehen, das hier unser P ist z.B.
und das hier unser Q.
Wir haben noch viele andere Punkte hier in der Menge.
Dann sehen wir, dass alle Punkte der Menge M hier, das ist unser M,
dass die hier links von P kommen.
Und schon entsprechend lässt sich das auch für alle anderen Kanten der
konvexen Hülle, lässt sich das auch wie aufübertragen.
Das heißt, wie gehen wir hier vor?
Das heißt, wir wählen den, ja auch wieder einen sicheren Extrempunkt
als Startpunkt.
Da steht immer linksuntersten Punkt, man kann auch einfach den
untersten Punkt.
Und das heißt, wie gehe ich hier vor?
Ich suche, also wenn jetzt P z.B.
mein Startpunkt ist, suche ich aus dieser Menge Q, also einen Punkt Q
so heraus, dass der Winkel zwischen dieser gerade L hier,
dass dieser Winkel mit der x-Achse minimal ist.
Also hier ist der Winkel, der entspricht ja schon gerade der x-Achse.
Das ist ja im Endeffekt eine waagrechte Linie hier.
Und wenn wir jetzt weitergehen, wenn wir z.B.
hier irgendwie diesen Punkt R anschauen würden, also wenn das jetzt R
wäre, und wir wollen jetzt, wir sind bei Q angelangt und möchten für Q
den Punkt finden, sodass der Winkel zur x-Achse minimiert wird.
Schauen wir uns das an, ok, das ist hier der Winkel, das ist ein
Winkel, und der nächste Punkt hier in der Mitte, der wäre z.B., wäre
dann dieser, und der hat ja einen viel größeren Winkel.
D.h.
dadurch, dass ich ausnutzen kann, dass der Nachfolgepunkt der konvexen
Hülle, dass der den Winkel zur x-Achse minimiert mit dem Vorgänger,
kann ich so sukzessive durchgehen und schrittweise anhand der Kanten
die konvexe Hülle aufbauen.
Insgesamt führt ja dieses Verfahren dazu, dass ich mir lediglich die
Extrempunkte anschaue.
Also ich starte bei jedem Extrempunkt.
Bei diesem Extrempunkt muss ich allerdings insgesamt einen Vergleich
hier durchführen.
Also ich muss ja die Winkel von diesem Punkt P zu allen anderen
Winkeln der Menge M berechnen.
Und aus diesen Winkeln dann den Minimalen bestimmen, um den korrekten
Punkt Q herauszufinden.
D.h.
insgesamt führt mich das, wenn ich h Extrempunkte habe, führt mich das
zu einer Laufzeit von h mal n.
Also pro Extrempunkt habe ich n Vergleiche, da ich jeden Extrempunkt
mit jedem Punkt der Menge M vergleichen muss.
Und insgesamt, wenn ich h Punkte habe, komme ich dann auf eine
Laufzeit von h von M.
D.h.
je nachdem wie groß h ist, also wenn h sehr klein ist, dann komme ich
tatsächlich auf lineare Laufzeit.
Allerdings wenn z.B.
alle Punkte von M Teil der konvexen Hülle sind, dann habe ich
basalische Laufzeit.
Und auch hier gibt es ein kleines Applet, um das Ganze mal ein
bisschen praktischer zu verdeutlichen.
Also hier fangen wir an damit, einen sicheren Extrempunkt zu
bestimmen.
Das ist z.B.
hier der, der am weitesten rechts oben liegt.
Und jetzt gehe ich Schritt für Schritt durch.
Also ich berechne die...ah genau, der geht ja auch wieder entgegen den
Uhrzeigersinn.
D.h.
auch hier berechne ich jetzt...also das ist hier mein Startpunkt.
Jetzt berechne ich für diesen Startpunkt alle Winkel zu diesen Punkten
hier in der Menge.
Das wird sukzessive durchgeführt.
Und ich merke mir jeweils immer den Punkt, der den kleinsten Winkel
erzeugt hat.
Das ist nach derzeitigem Stand der Punkt hier oben.
Jetzt haben wir noch einen gefunden hier, der einen noch kleineren
Winkel erzeugt.
Gehen weiter durch, Schritt für Schritt alle Punkte.
Hier oben, wir haben nochmal einen neuen Punkt gefunden, der einen
kleineren Winkel erzeugt.
Bis wir ganz am Ende den Punkt hier gefunden haben, der den kleinsten
Winkel erzeugt.
Jetzt haben wir hier oben alle einzelnen Punkte gesehen, die
abgelaufen sind.
Und können uns dann den nächsten Punkt finden.
An der Stelle gehen wir auch wieder durch.
Alle einzelnen Punkte und speichern entsprechend denjenigen, der
momentan den kleinsten Winkel erzeugt.
Wenn ihr das immer laufen lässt, auch wenn das Ganze ein bisschen
schneller läuft, was da passiert.
Wir können schön sehen, dass hier Schritt für Schritt alle Punkte
angeschaut werden.
Wenn jeweils immer die Kante so bestimmt wird, dass der Winkel eben
minimiert wird.
Wir sehen ja auch hier, das ist sogar relativ schön, dass diese Winkel
hier alle relativ flach sind.
Also es sind relativ viele geringe Krümmungen zwischen den
nachfolgenden Punkten.
Okay, das bringt uns dann zum vierten Ansatz.
Und zwar einen Algorithmus, der das Divided-Conquer-Prinzip nutzt.
Also Divided-Conquer habt ihr ja schon kennengelernt.
Zuallererst bei Straßen, bei vielen anderen Algorithmen, bei
Sortierverfahren, die wir uns bereits angeschaut haben.
Und man kann eben Divided-Conquer auch nutzen, um eine konvexe Hülle
aus zwei existierenden konvexen Hüllen zu bestimmen.
Also wie gehen wir hier vor?
Falls unsere Punktemenge M sehr klein ist, also irgendwie weniger
Punkte hat als eine konstante K.
K ist jetzt in dem Fall relativ klein, aber wir halten mal offen, wie
klein eigentlich.
Dann konstruiere die konvexe Hülle durch irgendein beliebiges
effizientes Verfahren.
Ansonsten geben wir folgendermaßen vor.
Also hier, das sind alles unsere Punkte M, unsere Menge M.
Ich teile M, unsere ursprüngliche Punktmenge, in etwa zwei gleich
große Mengen, M1 und M2.
Für diese aufgeteilten Mengen bestimme ich rekursiv die konvexen
Hüllen.
Nachdem ich diese Hüllen rekursiv bestimmt habe, verschmelze ich die
miteinander.
Und jetzt ist natürlich die Frage, wie kann man denn solche konvexen
Hüllen miteinander verschmelzen.
Also die Rekursion ist ja klar, wenn ich das Verfahren rekursiv
durchführe, erhalte ich irgendwann die konvexen Hüllen dieser Menge M1
und M2.
Die Frage ist, wie kann ich die dann effizient miteinander
verschmelzen.
Das heißt, die konvexe Hülle von zwei konvexen Hüllen ist ja selbst
wieder eine konvexe Hülle.
Falls die Größe unserer Menge, wie wir anschauen, wenn die unterhalb
von diesem K ist, dann können wir irgendein effizientes Verfahren
verwenden, das einen konstanten Aufwand aufweist.
Das ist dann zum Beispiel der Fall, wenn wir uns auf der untersten
Rekursionsebene befinden, dann führen wir keine weitere Aufteilung
mehr durch, sondern bestimmen die konvexe Hülle direkt mit irgendeinem
effizienten Verfahren.
Das ist die Rekurrenzgleichung für das Verfahren.
Wir erzeugen ja in jedem Schritt zwei Teilprobleme.
Da M in etwa zwei gleichgroße Teilmengen geteilt wird, ist das
Verhältnis der Teilprobleme zum Ursprungsproblem ein Halb.
Entscheidend ist natürlich, wie wir diese Menge effizient aufteilen
können und wie wir sie auch wieder verschmelzen können, was ich ja
gerade schon angesprochen habe.
Und zwar dieses Teilen, da kann man relativ einfach vorgehen.
Man kann zum Beispiel die Punkte einfach entsprechend ihrer X
-Koordinaten aufteilen.
Also man fügt die irgendwie in einen binären Baum ein, einen
balancierten Suchbaum, und hat dadurch dann die Wurzel im Endeffekt,
die teilt dann den Baum in zwei gleichgroße Mengen auf.
Und das Verschmelzen kann man dann zum Beispiel über den Greyhound
-Scan machen.
Also was man hier im Endeffekt, wenn man die Mengen auf diese Art und
Weise aufteilt, muss man ja letztlich eigentlich nur diese obere Kante
hier und diese untere Kante hier bestimmen.
Die Frage ist ja, welche Punkte der beiden konvexen Hüllen brauche
ich, um die gesamte konvexe Hülle zu bilden.
Das heißt, die konvexe Hülle dieser beiden konvexen Hüllen, die wird
nicht mehr Punkte beinhalten, als die Summe der Punkte, die die
konvexe Hülle der jeweils der beiden Teilmengen formen.
Das heißt, ich kann aber diese zwei Hüllen einfach verschmelzen, indem
ich diese oberen Ränder bestimme.
Und diese oberen Ränder, die kann ich zum Beispiel eben über den
Greyhound -Scan bestimmen.
Das heißt, ich schaue mir einfach, ich führe einen Greyhound-Scan
durch mit den Punkten, die die konvexe Hülle von M1 und M2 bilden.
Das heißt, dieses Verfahren, wenn ich dann diese Rekursionsgleichung
auflöse, komme ich hier am Ende auf eine Laufzeit von N log N.
Das Ganze kann ich auch noch verbessern, wenn ich das Verfahren ein
bisschen effizienter mache, aber das schauen wir uns an der Stelle
nicht an.
Entscheidend ist auch, dass es ein sehr effizientes Verfahren ist.
Und hier steht es ja doch nochmal ausführlicher.
Dazu gibt es auch noch ein Applet, aber wir erklären nochmal ganz
kurz, wie diese Verschmelzungsoperation genau funktioniert.
Und zwar, also zuerst bestimme ich die oberen Ränder der konvexen
Hülle von M1.
Die konvexen Hüllen, die sind ja selbst schon als Polygon zugegeben.
Das heißt, ich kann diese oberen Ränder relativ leicht bestimmen in
linearer Zeit.
Weil dadurch, dass die bereits als Polygon zugegeben sind, müssen die
ja entsprechend sortiert sein.
Und dann ist hier, was ich eben gerade schon aufgeführt habe, dass man
eben den Greyhound-Scan verwenden kann, um diese Verschmelzung hier
oben durchzuführen.
Das heißt, ich habe auch hier für den Greyhound-Scan einen Aufwand von
linearer Zeit, weil die Sortierung kann ich mir sparen.
Punkte sind ja bereits vorsortiert, dadurch, dass die konvexen Hülle
gegeben ist.
Aber im schlimmsten Fall muss ich noch immer M-Punkte betrachten.
Da ist nämlich genau dann der Fall, wenn alle Punkte von M1 und M2 zu
konvexen Hüllen gehören.
Also für diesen oberen Rand, das Verfahren kann ich auch analog für
den unteren Rand durchführen.
Und entsprechend dadurch, dass ich mir die Sortierung sparen kann, ist
der Aufwand für diesen Teilschritt also ja offensichtlich weniger.
Dazu gibt es auch mal ein App-Blatt.
Der Slider, ja, hier kann man nicht die Geschwindigkeit steuern, also
die einzelnen Schritte durchgehen.
Hier ist ja dann der Algorithmus automatisch.
Bei dem Dividing-Conquer-Prinzip hier, der Algorithmus funktioniert
so, dass er angegeben ist, dass erst mal, also das Problem wird auf
die kleinste Ebene runtergebrochen.
Und dann wird angefangen, also sukzessive die Teilprobleme
abzuarbeiten.
Also hier sieht es so aus, dass zuerst quasi ein Rekursionsass
durchgegangen wird.
Das ist hier die größte Menge, M2.
Das heißt, dass zuerst ein Ast abgearbeitet wird und danach der
andere.
Das heißt, wie man es am Ende gesehen hat, also wenn hier unser M1
ist, also die Punkte hier in der Mitte teilen würden, dann, wenn hier
links unser M1 wäre und hier rechts unser M2, dann wird zuerst
rekursiv M2 bestimmt und danach wird rekursiv M1 bestimmt.
Das sieht man ja hier.
Also auf der untersten Ebene hier werden einfach zwei Geraden zusammen
verschmolzen zu einer konvexen Hülle.
Die wird hier sukzessive aufgebaut.
Hier sieht man genau der linke Ast.
Also hier wird im Endeffekt M1, die Konvexhülle von M1, rekursiv
bestimmt.
Und diese beiden konvexen Hüllen, die werden am Ende verschmolzen.
Dann gibt es auch noch ein fünftes Verfahren.
Und zwar, wir haben eingekündigt, dass es ja nur vier gibt, aber es
gibt auch noch ein fünftes.
Und zwar, das ist auch ein relativ interessanter Ansatz und hier
arbeitet man wieder mit den Extrempunkten.
Das heißt, wir bestimmen zunächst mal die Extrempunkte unserer Menge,
also die Punkte, die am weitesten nördlich-westlich sind.
Die Punkte, die nördlich-südlich und östlich liegen.
Und jeweils auch noch die Extrempunkte, die zum Beispiel hier nord
-östlich liegen und nord-westlich.
Sodass wir erstmal eine möglichst grobe Approximation dieser
Konvexhülle haben.
Im nächsten Schritt werden dann alle inneren Punkte dieses
Polygonenzugs eliminiert.
Also alle diese Punkte, die hier drin sind, die müssen wir nicht
weiter betrachten.
Von denen wissen wir ja bereits, dass die nicht Teil der Konvexhülle
seien.
Im nächsten Schritt kann es ja allerdings noch sein, dass sich, wie
hier, noch weitere Punkte, die jetzt nicht Teil dieser Extrempunkte
waren, dass sie sich noch außerhalb dieses Polygonenzugs befinden.
Das heißt, um dann tatsächlich zu ermitteln, welche Punkte denn von
diesen, die da draußen liegen, auch wirklich Teil der Konvexhülle
sind, kann man irgendein effizientes Verfahren verwenden, das in der
Laufzeit N log N Konvexhülle bestimmen kann.
Diese Extrempunkte kann man relativ einfach in linearer Laufzeit
bestimmen.
Man kann einfach nach den Koordinaten gehen, nach den größten und
kleinsten Koordinaten.
Da kann man einmal, wenn diese Menge M als Punktemenge gegeben ist,
kann man die einmal traversieren.
Die Punkte zu eliminieren, die alle innerhalb dieses konvexen Polygons
liegen, da kann man auch wieder mit dieser Determinante argumentieren.
Also man weiß, wenn diese Punkte einmal, wenn die zum Beispiel rechts
von dieser Kante liegen und links von dieser, dann müssen wir, dass
die innerhalb sein müssen.
Und entsprechend, wenn wir R restliche Punkte haben, dann können wir
eben entsprechend die resultierende konvexe Hülle in der Laufzeit R
log R bestimmen.
Also R sind die restlichen Punkte, die übrig bleiben hier, nachdem wir
die inneren Punkte entfernt haben.
Zu denen muss man natürlich noch hinzuaddieren unsere Extrempunkte
hier, die wir im ersten Schritt bestimmt haben.
Das könnte auch beispielsweise sein, zumindest bei diesem Punkt hier,
dass der doch nicht Teil der konvexen Hülle ist, und dass man den
entsprechend auch eliminieren muss.
Im schlechtesten Fall, wenn alle Punkte auf der konvexen Hülle liegen,
haben wir auch hier wieder, dass wir eine Laufzeit von N log N haben.
Aber falls die Punkte einigermaßen gleich verteilt sind, hier in der
Ebene, dann erhalten wir im Mittel eine lineare Laufzeit.
Interessant ist natürlich, indem wir uns so viele Algorithmen
angeschaut haben zur Bestimmung der konvexen Hülle, wie sieht es denn
eigentlich mit unseren Schranken aus?
Für Multiplikationsverfahren haben wir das ja auch schon angeschaut.
Wie gut kann eigentlich ein Algorithmus zur Bestimmung der konvexen
Hülle eigentlich sein?
Um hierzu zu zeigen, wie diese Schranke aussieht, wir folgen der Idee,
also wir konstruieren eine Menge M mit paarweise verschiedenen
Punkten, also mit N Punkten, x1 bis xn.
Und diese Punkte, die sind folgendermaßen gegeben, ja, also durch
diese Vorschrift.
Das sind im Endeffekt, also sagt diese Menge M, das ist nichts anderes
als aufeinanderfolgende Punkte einer Parabel.
Ja, also das ist quasi die x-Koordinate und das hier ist die y
-Koordinate.
Also ein Beispiel, wenn wir fünf Punkte haben, wäre zum Beispiel das
hier.
Das ist dann x1, x2, x3, x4, x5.
Das heißt, indem wir diese Punkte so konstruieren, die Koordinaten,
haben wir im Endeffekt einfach nur Punkte, die auf einer Parabel
liegen.
Das heißt, jedes Verfahren ist irgendwie die, genau, und das hier ist
auch die zugehörige konvexe Hülle.
Also die konvexe Hülle ist im Endeffekt nichts anderes als so eine
Diskretisierung der Parabel und am Ende wird eben zwischen dem Punkt,
der am weitesten rechts liegt und am weitesten links liegt, hier muss
auch noch eine Kante eingefügt werden, um den Polygonzug zu
vervollständigen.
Das heißt, was macht eigentlich ein Algorithmus, der die konvexe Hülle
bestimmt?
Das heißt, alle Punkte hier sind ja Teil der konvexen Hülle, weil die
eben entsprechend auf dieser Parabel liegen.
Das heißt, ein Algorithmus, der die konvexe Hülle bestimmt, der muss
ja eigentlich nur ermitteln, in welcher Reihenfolge diese Punkte
angeordnet werden müssen.
Das heißt, um diese Anordnung durchzuführen, ist ja nichts anderes als
ein einfacher Sortiervorgang.
Das heißt, die untere Schranke fürs Sortieren, also im schlechtesten
Fall worst case, und auch gleichzeitig die untere Schranke für die
Konstruktion der konvexen Hülle.
Das heißt, die untere Schranke für den worst case-Fall zur Bestimmung
der konvexen Hülle ist auch wieder ein Locker.
Allerdings, im Unterschied zum Sortierverfahren, ist es so, dass
lineare Aufwand eine scharfe untere Schranke für das mittlere
Verhalten ist.
Bei Sortierverfahren gesehen, dass im Mittel, also für die
effizientesten Verfahren, dass wir trotzdem einen Aufwand von NlogN
haben.
Wie wir allerdings durch die Algorithmen vorher gesehen haben, gibt es
tatsächlich einige Verfahren, die im Mittel allerdings lineare
Laufzeit erzielen.
Das beendet uns mit einem kleinen Ausflug in die algorithmische
Geometrie.
Wir haben hier nur einen sehr kleinen Ausschnitt der Verfahren
betrachtet, die in dem Gebiet so gängig sind.
Und es gibt auch eine Vielzahl interessanter Probleme, die sich
allerdings bereits mit den vorgestellten Methoden hier lösen lassen.
Allein für dieses Gebiet der algorithmischen Geometrie wurden auch zum
Beispiel neue Datenstrukturen entworfen.
Gerade diese balancierten Suchbäume sind unter anderem nötig, um
dieses Sweepline-Verfahren effizient implementieren zu können.
Okay,
ein paar Minuten haben wir noch.
Dann beginne ich jetzt mit dem achten und letzten Kapitel für die
Vorlesung.
Das war mit verteilten Algorithmen.
Im Speziellen werden wir uns bei verteilten Algorithmen sogenannte
Leader Election Probleme anschauen.
Was sind eigentlich verteilte Algorithmen?
Was betrachten wir eigentlich?
Wir haben eine Menge an sequentiellen Prozessen, die unabhängig
voneinander arbeiten und ihre Aktivitäten durch Kommunikation
koordinieren.
Also sequentielle Prozesse, das kann zum Beispiel ein Conquer-Gleich
sein, aber das sind also irgendwelche Aktivitäten, die unabhängig
voneinander ausgeführt werden können.
Zum Beispiel bei den Conquer-Verfahren.
Und diese Prozesse, die sind nicht nur unabhängig voneinander
bearbeitbar, sondern die werden auch auf einem verteilten System
bearbeitet.
Das heißt, es sind auch die einzelnen Akteure oder die einzelnen
Maschinen, die diese Prozesse bearbeiten, die sind auch räumlich
unabhängig voneinander.
Also das heißt zum Beispiel, wir haben hier Workstation-Netze oder PC
-Netze, also auch einzelne Maschinen, die physikalisch voneinander
getrennt sind.
Um ein paar konkrete Beispiele zu nennen, ist zum Beispiel hier der
Zip -Pool hier im Gebäude.
Die Rechner hier im Keller des Gebäudes, die funktionieren ja alle
unabhängig voneinander und die können auch dazu verwendet werden, um
Berechnungen, die an anderer Stelle getätigt werden, auszulagern.
Es gibt ja zum Beispiel das Joschka-System, das an unserem Lehrstuhl
entwickelt wurde, Job Schedule in Karlsruhe heißt es.
Das System kann genutzt werden, um Rechner im Rechenzentrum, die
gerade nicht benutzt werden, zu verwenden, um große rechenintensive
Probleme zu lösen.
Das hat zum Beispiel auch ein Kollege von mir im Tool entwickelt, mit
dem ein Multi-Agenten-System.
Man kann Code in dessen Framework schreiben und das entsprechend auf
Joschka deployen und ausführen lassen.
Das heißt, wenn der eigene Rechner zu schwach ist, um diese Simulation
durchzuführen, kann man die Berechnung einfach auslagern und bekommt
dann die Ergebnisse zurückgeliefert.
Solche verteilten Systeme, die werden zum Beispiel von Reisebüros,
Banken eingesetzt, IBM, SAP, die haben ja alle Systeme, die darauf
basieren, dass man verteilte Rechnerstrukturen nutzt, um besonders
aufwendige Aufgaben zu erledigen.
Also Rechner im Internet, beziehungsweise das Internet selbst, ist
auch ein klassisches Beispiel dafür.
Im Internet sind ja die Rechner physikalisch getrennt voneinander und
man kann diese Struktur entsprechend nutzen, um besonders
rechenintensive Anwendungen auszulagern.
Das Entscheidende bei verteilten Algorithmen, da ist eigentlich das
Nadelöhr bei der Berechnung.
Das ist nicht die Rechenleistung der einzelnen beteiligten Maschinen,
da kann ja einfach diese, theoretisch noch mehr Maschinen hinzunehmen
bei der Berechnung.
Entscheidend ist hier der Kommunikationsaufwand, den man betreiben
muss, um die Prozesse miteinander zu koordinieren.
Das heißt, wie verwendet man eigentlich verteilte Algorithmen?
Um ähnliche Probleme zu lösen, kann man verteilte Algorithmen genauso
verwenden wie sequenzielle oder parallele Algorithmen.
Also man kann den Berechnungsaufwand einfach aufteilen auf
verschiedene einzelne PCs.
Wir schauen uns allerdings, also wir sind jetzt nicht so sehr daran
interessiert, wie man diese Probleme, also die Problemlösung möglichst
effizient aufteilen kann in dem Kapitel.
Sondern wir schauen uns eigentlich an, welche Lösungen, welche
Probleme in solchen verteilten Systemen direkt auftreten.
Also Lösungen, die speziell bei verteilten Algorithmen auftreten, die
jetzt bei sequenziellen oder parallelen Verfahren hier auf einer
Maschine auftreten, nicht passieren.
Sind zum Beispiel, also hier sind ein paar Probleme genannt.
Entscheidend ist zum Beispiel die Gewährleistung zuverlässiger
Kommunikation und Kooperation.
Also es kann ja sein, dass einzelne Übertragungskanäle ausfallen.
Die Frage ist, wie kann man denn sicherstellen, dass die einzelnen
Prozesse dennoch ihre Arbeit ausführen können.
Stimmung der Netzgebologie ist auch entscheidend.
Also wenn ich ein Netzwerk habe, zum Beispiel im Internet, da kennt ja
ein Knoten, weiß ja nicht, wie der Rest des Netzwerks aussieht.
Also man braucht auch spezielle Verfahren oder effiziente Verfahren,
damit jeder einzelne Teilnehmer weiß, wie die Topologie aussieht.
Und entsprechend, je nachdem, wie die Topologie aussieht, auch
unterschiedliche Routingverfahren verwenden.
Also je nachdem, wie die Netzgebologie aussieht, macht es vielleicht
Sinn, Nachrichten über kürzere Wege zu schicken oder über längere.
Was auch ein interessanter Aspekt ist, und zwar die Ermittlung einer
globalen Zeit.
Also man muss sich das ja vorstellen, wenn man irgendwie zehn
verschiedene Rechner hat in einem System, die alle ihre eigene interne
Uhr haben.
Wie können denn diese Uhren miteinander synchronisiert werden?
Das ist ja auch ein nicht-triviales Problem, denn es kann ja zum
Beispiel sein, dass ein bestimmter Prozess genau zu einem bestimmten
Zeitpunkt gestartet werden soll.
Und das ist natürlich nur möglich, wenn alle Beteiligten, der Rechner,
wenn die alle über die gleiche Uhrzeit verfügen, dass die wissen, wann
sie starten müssen.
Datenverwaltung ist auch ein ganz entscheidender Punkt hier und einmal
die Zugriffe lesen und schreiben.
Also wie kann ich denn auf Daten zugreifen, die über ein System
verteilt sind?
Also welche Prozesse dürfen überhaupt lesen und schreiben?
Es kann ja sein, dass bestimmte Prozesse nur lesen auf Daten
zugreifen, sondern andere wiederum auch schreiben.
Kann ich hier bei der Replikation von Daten umgehen?
Das heißt, wenn ich jetzt meine Daten in irgendeinem Datenzentrum
gespeichert habe, wie kann ich diese Daten möglichst effizient
transportieren?
Also wenn natürlich alle Prozesse auf einmal auf dieses Datenzentrum
zugreifen, dann kann es natürlich sein, dass dieses Datenzentrum
abschmiert.
Dann muss man sich auch überlegen, verteilt man die Daten zum Beispiel
in so eine Baumstruktur?
Das nach und nach, also um den Kommunikationsaufwand möglichst
gleichmäßig zu verteilen.
Konsistenz ist natürlich auch ganz entscheidend.
Wenn viele verteilte Prozessoren auf den gleichen Daten arbeiten, wie
kann ich denn sicherstellen, dass die Daten konsistent gehalten
werden?
Gerade bei Datenbanken beispielsweise.
Dass alle Prozesse immer jeweils auf die korrekten aktuellen Daten
zugreifen.
Synchronisation von Startzeiten habe ich eben schon genannt.
Das spielt eben besonders bei der Ermittlung bei einer globalen Zeit
wie das eine Rolle.
Terminierungserkennung ist auch interessant.
Wenn ich beispielsweise ein Problem aufteile, also per Branch-and
-Bound -Verfahren, aufteile auf verschiedene Prozesse.
Und im Endeffekt bin ich nur daran interessiert, also wenn ein
einzelner Prozess eine Lösung findet, dann kann das Verfahren
terminieren.
Wie kann denn dieser Prozess, der terminiert hat, den anderen klar
machen, dass die nicht mehr weiterrechnen müssen?
Fehlerbehandlung ist natürlich ganz entscheidend.
Was passiert denn, wenn ein Prozess fehlerhafte Ergebnisse liefert
oder abstürzt?
Können andere Prozesse, die damit umgehen, die eventuell auf dessen
Ergebnisse angewiesen sind?
Und was wir uns anschauen werden, ist allerdings vor allem dieses
Leader -Election-Problem.
Und dieses Leader-Election-Problem gehört zu einer ganzen Klasse von
Abstimmungs - und Konsensverfahren.
Hier auch noch ein paar typische Beispiele für verteilte Algorithmen.
Wir haben einmal Suchmaschinen, beispielsweise Google.
Durchsucht ja das Internet mit seinen Bots stetig nach neuen Websites.
Dort werden diese Seiten, diese Bots, die agieren alle unabhängig
voneinander.
Also das sind verteilte Prozesse, die allerdings dann aber natürlich
wieder in die gleiche Datenbank geschrieben werden müssen.
Zum Beispiel die Anfragen, die werden auch von verschiedenen einzelnen
Prozessen bearbeitet.
Also zum Beispiel entsteht dann irgendwie ein Server, der die Anfragen
aus Europa bearbeitet.
Ein anderes Beispiel ist zum Beispiel die Verkehrssteuerung.
Also wenn zum Beispiel grüne Wellen zu erzeugen, um den Verkehr zu
regeln in der Rushhour, müssen dann ja lokale Entscheidungen getroffen
werden.
Also wenn man sieht, dass ein sehr hohes Verkehrsaufkommen ist und
dass es besser ist, wenn man dieses komplette Aufkommen erstmal
durchleitet, um die Gesamtbelastung des Verkehrs zu verringern, muss
ja jede lokale Ampel im Endeffekt wissen, wann schalte ich denn von
Rot auf Grün, um dann einen optimalen Verkehrsflug zu erzeugen.
Bei Energiesystemen im Demandside-Management kann man auch verteilte
Algorithmen verwenden.
Beispielsweise bei der Koordination von Angebotemaßnahmen.
Also wie zum Beispiel einzelne Konsumenten aggregieren und ein Prozess
zum Beispiel optimiert den Verbrauch für eine Gruppe von Konsumenten.
Die werden wiederum aggregiert von einem noch früher gelegerten
Prozess.
Und dann wiederum optimiert.
Data Mining ist auch ein klassisches Beispiel.
Also wenn ich in Extraktion auf von relevanten Informationen aus
relativ großen Datenmengen oder über viele Datenbanken hinweg, das
Ganze kann ich auch parallel organisieren von vielen unabhängigen
Prozessen.
Und bei diesen ganzen Beispielen, die hier genannt sind, ist es halt
so, dass es keine sinnvolle Alternative zur verteilten Bearbeitung
gibt.
Es ist nicht so, dass ich einfach eine riesige Maschine, einen
riesigen Superrechner hinstellen könnte, der das alles hier schnell
und effizient löst, sondern ich brauche hier verteilte Prozesse, die
diese Teilprobleme lösen.
Weil es einfach, selbst ein Superrechner kann nicht genügend
Bearbeitungskraft aufbringen, um diese Probleme effizient zu lösen.
Wenn wir uns verteilte Algorithmen anschauen, müssen wir uns natürlich
überlegen, was sind denn die Kosten bei verteilten Algorithmen?
Also in was messe ich eigentlich meinen Aufwand?
Wenn wir einmal die Rechenzeit der Prozessoren, also wenn ich die
einzelnen Prozesse habe, wie lange benötigen die, um ihre Aufgabe zu
lösen?
Allerdings ist es bei verteilten Algorithmen nicht ganz so
interessant, denn die Bearbeitung, die Abarbeitung von irgendwelchen
Befehlen, von irgendwelchen Anweisungen in einem Prozessor, das geht
immer noch sehr viel schneller als die Übertragung von Nachrichten
über ein Netzwerk.
Deshalb ist vor allem eigentlich hier der Kommunikationsaufwand das
entscheidende Maß bei verteilten Algorithmen.
Und Kommunikationsaufwand kann man ja auch in verschiedenen Maßen
messen.
Also wir können uns einmal anschauen, die Anzahl der Nachrichten, die
überhaupt erzeugt werden.
Denn es ist ja so, jede Nachricht hat eine bestimmte Dauer, bis sie
übertragen wird.
Je mehr Nachrichten ich versende, umso länger muss ich warten, bis
alle Nachrichten übertragen sind.
Aber auf der anderen Seite ist es natürlich auch so, dass die Länge so
einer Nachricht auch einen entscheidenden Einfluss hat.
Und zwar vielleicht ist es so, dass ich ganz viele kleine Nachrichten
verschicken kann, aber stattdessen könnte ich auch eine lange
Nachricht verschicken.
Und bei der Länge der Nachricht ist ja entscheidend, wie groß sie ist,
weil je größer die Nachricht ist, umso länger benötigt sie, um
übertragen zu werden.
Das ist natürlich ganz klar im Internet.
Wenn man eine Datei verschickt, die ein paar Megabyte groß ist, ist
das kein Problem.
Aber wenn eine Datei mehrere Gigabyte groß ist, ist das mit hohem
Aufwand verbunden.
Da kann es sein, dass ich nur eine Nachricht verschicke.
Aber wenn die ein Gigabyte groß ist, brauche ich natürlich wesentlich
länger, wie wenn ich diese Datei irgendwie vielleicht aufteile und
effizient über verschiedene einzelne Routingkanäle verschicken kann.
Das alles läuft auch ein bisschen darauf hinaus, dass ich hier vor
allem die Übertragungszeiten betrachte.
Denn entscheidend ist ja zum Beispiel, wenn Rechner räumlich sehr nahe
sind, sind die Übertragungszeiten unter Umständen sehr kurz.
Wenn die allerdings weit auseinander sind, sind die relativ groß.
Und für die Koordination einzelner Prozesse ist ja gerade
entscheidend, dass die sich effizient absprechen können.
Und wenn der Nachrichtenaustausch sehr lange dauert, dann dauert ja
unter Umständen die Bearbeitung des Problems länger als die
Übertragung der Ergebnisse.
Für unseren Fall nehmen wir an, dass die Rechenzeit gleich Null ist.
Wie gesagt, Rechenzeit ist nicht so interessant.
Das heißt, die wird hier in unserem Szenario vernachlässigt.
Stattdessen beschränken wir uns ausschließlich auf den
Kommunikationsaufwand.
Diese Vereinfachung ist natürlich nur sinnvoll, solange die
Kommunikation wesentlich aufwendiger ist als die Berechnung.
Wenn die Berechnung am Ende doch, also eines einzelnen Prozesses,
wesentlich länger dauert als die Kommunikation, dann ist natürlich die
Aufteilung der Rechenzeit wesentlich bedeutungsvoller.
Man kann auch die Kommunikation in der Berechnung verstecken.
Und zwar diese sogenannte Latency Hiding.
Das funktioniert einfach, indem man z.B.
Kommunikation künstlich verzögert, bis die Berechnung abgeschlossen
ist.
Das heißt, man sagt, die Kommunikation, der Aufwand vergrößert sich
dadurch, dass ich erst warten muss, bis die Berechnung abgeschlossen
ist.
Dann ist das heute die letzte Folie, die wir uns anschauen.
Zwar auch für den Rest des Kapitels betrachten wir das sogenannte
Leader Election Problem.
Das Leader Election Problem ist eine typische Problemstellung, also
ein typisches Beispiel für ein Konsensproblem bei verteilten
Prozessen.
Wir gehen davon aus, dass wir N vollständig Leitprozesse haben und
diese Prozesse benötigen einen Koordinator, einen Leiter, einen
Anführer.
Ein Grund könnte dafür sein, dass ein bisheriger Leiter ausgefallen
ist.
Es kann auch einfach sein, man möchte anfangen ein Problem zu
bearbeiten, aber man hat gleichberechtigte Prozesse.
Prozesse müssen sich untereinander abstimmen, um eben einen Anführer
zu suchen.
Wir haben auch bestimmte Anforderungen.
Der erste ist, selbst wenn diese Prozessoren eindeutige Identitäten
besitzen, anhand derer sie identifiziert werden können, darf zunächst
mal trotzdem niemand aufgrund seiner Identität ausgewählt werden.
Das heißt, wenn diese Prozessoren alle von 0 bis N-1 durchnummeriert
sind, dürfen wir nicht einfach den Anführer wählen, weil wir sagen,
wir nehmen zum Beispiel den mit der niedrigsten Identität oder den mit
der höchsten.
Sonst könnte man immer den Prozess mit der kleinsten Nummer auswählen
und dann wäre dieses Problem trivial.
Es ist auch so, dass alle Beteiligten so in gleicher Weise mitwirken.
Das heißt, jeder Prozess kann theoretisch Anführer werden.
Wäre das nicht der Fall, wären die nicht gleichberechtigt.
Aber wir haben explizit vorausgesetzt, dass die Prozesse
gleichberechtigt sein müssen.
Und am Ende, also nachdem der Algorithmus durchgelaufen ist, müssen
alle Beteiligten, also alle beteiligten Prozesse die gleiche
Information über die Identität des Leiters haben.
Das heißt, allen Prozessen muss bekannt sein, wer denn der Leiter
geworden ist.
Wenn sie nicht wissen, wer der Leiter ist, dann können sie sich ja
nicht untereinander koordinieren.
Und ganz entscheidend ist dieser Punkt hier.
Das heißt, auf Basis dieser Anforderungen muss der Algorithmus, den
wir verwenden, um dieses Leader Election Problem zu lösen, der muss
vollständig verteilt und symmetrisch sein.
Das heißt, dass alle Prozesse lokal mit dem gleichen Algorithmus
entscheiden.
Das heißt, wenn wir uns anschauen, welche Anweisungen von welchen
jedem Prozess durchgeführt werden, um dieses Problem zu lösen, ist es
so, dass lokal alle die gleiche Prozedur durchführen.
Dann sehe ich ja, sind wir heute vorbei, fertig.
Nächste Woche wird dann Prof. Schmeck wieder zurück sein und
entsprechend an der Stelle weitermachen und euch einige Verfahren
vorstellen, wie man dieses Leader Election Problem lösen kann.