So, ich begrüße Sie zur Fortsetzung der Vorlesung Effiziente
Algorithmen.
Ich gucke gerade, ist das von der Qualität her, von der Helligkeit
ausreichend, oder müssen wir ein bisschen dunkel machen?
Ich glaube, wir müssen etwas dunkel machen.
So, jetzt dürfte es in Ordnung sein.
Also nochmal letzte Vorlesung Effiziente Algorithmen.
Ich freue mich, dass Sie heute so zahlreich da sind.
Letztes Mal hat Herr Schukla mich vertreten, weil ich eine andere
wichtige Sitzung hatte.
Und er hat etwas erzählt über die Graph-Algorithmen, hat dort einiges
Ihnen berichtet.
Da hatte ich ja schon angefangen gehabt.
Er hat dann etwas erzählt über die so typischen Graph-Probleme,
Warshals -Algorithmus, den Sie kennen aus OR.
Im Wesentlichen dann diese parallele Variante, bei der man halt sieht,
wie kann man diese andere Struktur dieser drei Schleifen hier aus dem
Warshals -Algorithmus, wie kann man die sinnvoll auf so ein
zweidimensionales Feld bringen.
Und das Problem ist dort ja, dass die Datenbeziehungen, die
Datenabhängigkeiten nicht so sind, dass das den nächsten
Nachbarschaften auf dem Feld entspricht.
Deswegen musste man irgendwie einen Trick finden, wie man die Daten
zusammenbringen kann, sodass man doch mit lokalen Operationen
auskommt.
Und die wesentliche Idee dabei ist halt dieser im Prinzip Broadcast
der jeweils Karten, Zeile und Spalte über das ganze Feld.
Und einen Broadcast über das ganze Feld kann man eben auch sequenziell
machen, im Pipelining-Verfahren.
Und das war dann halt so, dass man dann auf dieses Bild kam, wo man im
Pipelining -Verfahren die jeweils Karte-Zeile für K gleich 1 bis N so
durch das Feld, also hier jeweils die Zeilen, die man dann im Prinzip
mit einem zyklischen Schiff durch das ganze Feld hindurchschiebt und
dadurch dann dafür sorgt, dass man mit lokalen Operationen halt einen
hohen Zeitgewinn erzielen kann, mit N²-Prozessoren tatsächlich in
linearer Zeit den Warshall-Algorithmus ausführen kann, sodass man
einen optimalen Zeitgewinn hat gegenüber der sequenziellen Variante
des Warshall-Algorithmus.
Dann stand hier noch Wavefront Arrays.
Ich weiß nicht, ob ich Ihnen darüber viel erzählt habe.
Das ist halt eine klassische Variante der Mesh-Connected Arrays mit
einem sehr einfachen Prinzip der Programmierung über solche
wellenförmigen Programme.
Und die Instructional Systolic Arrays sind ein Konzept, mit dem man
Parallelrechner programmieren kann in einer Art, die Ideen des
systemischen Algorithmen, die ich Ihnen bei Matrixmultiplikation und
auch bei Sortierverfahren vorgestellt habe, wobei man die sinnvoll
überträgt auf die Programmierung von zweidimensionalen Feldern,
Konzept, das ist in meiner Gruppe vor einigen Jahren mal entstanden.
Es gab auch mal eine Einsteckkarte für einen PC mit 1000 Prozoren, die
von meinen ehemaligen Mitarbeitern über eine Firma produziert wurde.
Ist dann aber, wie so viele Parallelrechner, leider nicht zum
wirtschaftlichen Erfolg geworden, weil die Prozessorentwicklung damals
so war, dass die Einzelprozessoren eigentlich die Leistungsfähigkeit
so stark steigern konnten innerhalb kurzer Zeit, dass die
Parallelrechner -Entwicklungen, die dann doch sehr spezielle
Programmiermodelle brauchen, dass die damit nicht mitkommen konnten.
Inzwischen sieht das alles wieder anders aus und diese Konzepte werden
also bei den Multicore und Minicore-Architekturen neue Relevanz
bekommen.
Dann hat er Ihnen den Dijkstra-Algorithmus mal vorgestellt, den kennen
Sie auch aus Erreichungs-Research, hier vielleicht ein bisschen anders
präsentiert, als Sie das dort kannten.
Dann kam noch der Floyd-Algorithmus dazu, wo man wieder sieht, dass es
im Prinzip nur eine andere Variante des Warshall-Algorithmus, bei der
sich hier die innere Zeile etwas anders darstellt, aber ansonsten ist
das das Schema Warshall-Algorithmus.
Das heißt, ich habe hier drei ineinander geschachtelte Schleifen, bei
der, anders als bei der Matrix-Multiplikation, das K außen ist und
dann I und J innen drin laufen.
Und diese andere Struktur beutete sich auf dem zweidimensionalen Feld
durch diese andere Struktur mit dem wellenförmigen Durchreichen der
Zeilen und Spalten.
Das kann man hier ganz genauso machen.
Es gibt eine ganze Reihe anderer Probleme, die man auch auf diese
beiden Strukturen, entweder Struktur-Matrix-Multiplikation oder
Struktur -Warshall-Algorithmus überführen kann, sodass man sofort
parallele Varianten hat, die alle nach dem gleichen Muster ablaufen,
mit denen man dann Graph-Probleme sehr effizient auf zweidimensionalen
Feldern lösen kann.
Das sind also nur diese beiden Beispiele.
Warshall-Algorithmus und Floyds-Algorithmus in der gleichen Struktur.
Das heißt, wenn man einmal diese Struktur implementiert hat, braucht
man nur im Prinzip die lokale Operation auf den Prozessoren zu ändern.
Hier ist es halt bei dem Floyds-Algorithmus eine Minimums-Operation
zwischen zwei Werten, also hier das Dij, also zwei Distanzen, Dij und
Dik plus Dikj.
Beim anderen war das logische Operation, das ist aber eigentlich nur
die Operation in den kleinen Knoten.
Und der ganze Rest, die algorithmische Struktur, bleibt gleich.
Und deswegen war es wichtig, das zu präsentieren, dass man sieht, hier
ist ein systematischer Ansatz, um eine ganze Klasse von Problemen
sinnvoll zu lösen.
Das war dann hier nochmal eine Reihe anderer Probleme kurz aufgeführt.
Und das war dann der Abschluss schon von dem Kapitel.
Und es kam dann das nächste Kapitel, nämlich die algorithmische
Geometrie, wo Herr Schukler Ihnen ganz kurz die Einführung gegeben
hat, worum es eigentlich geht, also um verschiedene geometrische
Probleme.
Geometrische Probleme treten heutzutage an vielen Stellen auf, wenn
Sie irgendetwas visualisieren wollen mit grafischen Strukturen.
Da haben Sie eine ganze Reihe von Problemen zu lösen, wenn Sie einen
Bereich auf dem Bildschirm darstellen wollen.
Es ist immer die Frage, was ist eigentlich sichtbar, was ist nicht
sichtbar, das muss man effizient bestimmen können.
Und dafür brauche ich solche Algorithmen, die hier bearbeitet werden.
Und ein Problem, das er Ihnen dargestellt hat, war dieses Problem, wie
viele Punkte liegen eigentlich innerhalb so eines Rechtecks, das hier
gestrichelt ist oder schraffiert ist, und das in einer optimalen Art
und Weise.
Und man hatte gesehen, wenn man das mit einem naiven Ansatz macht,
kommt man hier mit linearer Zeit hin, was gar nicht schlecht ist, aber
mit einer gewissen Vorbereitung hat man dann gesehen, mit Vorbereitung
n² kommt man am Ende mit einer Zeit pro Suchanfrage von log n hin, was
natürlich eine deutliche Beschleunigung ist gegenüber dem linearen
Aufwand für den naiven Ansatz.
Das heißt, für großes n, wenn man viele Punkte hat, ist das ein
wichtiger Ansatz, eine wichtige Sache, die man hier erkennt.
Durch eine gewisse Vorbereitung kann ich dafür sorgen, dass ich
Datenstrukturen aufgebaut habe, mit denen ich sehr effizient Probleme
lösen kann in dem Bereich.
Und dann kommt das nächste Problem, AG2 genannt.
Ich habe hier das durchnummeriert, die verschiedenen Probleme der
algorithmischen Geometrie, die ich Ihnen hier kurz präsentieren
möchte.
Und da gehen wir jetzt nochmal in die Präsentation rein.
Und Sie haben eine Frage.
Es wäre nett, wenn Sie das Fenster entweder richtig aufmachen würden
oder zumachen, damit das uns hier nicht stört.
Sie haben eine Frage.
Ja, gerne.
Ist völlig egal.
Das ist völlig egal.
Das kommt aufs Gleiche raus.
Weil der Median von vier Elementen ist das zweitgrößte Element.
Der Median von drei Elementen ist auch das zweitgrößte Element.
Das heißt, Sie haben das gleiche Element.
Das Einzige ist, wenn Sie den dort reinnehmen, kann es natürlich sein,
dass der neue Knoten das zweitgrößte Element ist, den Sie dort
reinnehmen.
Das könnte höchstens sein.
Das verändert dann die Struktur etwas.
Aber wenn Sie den dann einfügen, dann kommt...
Dann, was passiert denn dann?
Passiert eigentlich ein Schlimmes.
Das ändert sich dann je nachdem, ob der kommt entweder oben rein oder
unten rein.
Das ist halt der Unterschied, in welche Ebene er reinkommt.
Aber das ist für die...
Nehmen wir mal an, Sie hätten eine Aufgabe zu zwei, drei, vier Bäumen,
wo Sie das ausführen müssen.
Wenn dann der Knoten auf einer anderen Ebene ist, und das hängt davon
ab, ob Sie jetzt erst den Median genommen haben oder anschließend den
Median genommen haben, das ist nicht relevant für die Beurteilung, ob
das richtig ist oder nicht.
Beides sind berechtigte Verfahren.
Es verändert die Struktur nicht wirklich.
Die Struktur bleibt ja gleich.
Es ändert sich nicht wirklich.
Die Anzahl der Ebenen bleibt gleich.
Die Struktur bleibt nicht ganz gleich.
Das stimmt nicht, weil der Knoten ja eventuell oben hinkommt und nicht
unten.
Dadurch verändert sich die Struktur leicht.
Ich habe dann oben einen dickeren Knoten und nicht unten einen
dickeren Knoten.
Das kann sich verändern.
Aber wenn klar ist, wie Sie es gemacht haben, ist das völlig in
Ordnung.
Zu all diesen Verfahren gibt es zig verschiedene Varianten.
Ich sollte natürlich in der Vorlesung eine einheitliche Variante Ihnen
präsentieren.
Ich habe bisher immer so gemacht, dass ich ein paar Beispiele
erläutert habe.
Ich werde das zukünftig genauer mit den Verfahren machen, sodass man
ganz klar sieht, das ist eine Variante, die ich jetzt hier vorschlage.
Und die ist durchaus konsistent im Prinzip mit anderen, aber auch wenn
Sie sich die Applets angucken, die im Web existieren, die haben auch
immer leicht unterschiedliche Arten, mit diesen Rot-Schwarz-Bäumen
oder 2-3-4-Bäumen umzugehen.
Aber das Prinzip ist eigentlich gleich.
Und das sind so marginale Varianten, ob Sie jetzt erst aufteilen oder
später aufteilen.
Okay.
Also ich habe gesehen, das Forum zur Vorlesung ist relativ gut
besucht.
Und zwar liegt das anscheinend daran, dass wir in den Aufgaben zu der
Vorlesung eigentlich davon ausgegangen sind, ich komme etwas schneller
ran mit dem Stoff.
Und deswegen waren ein paar mal Aufgaben dabei, die sich schon auf
Dinge bezogen, die in der Vorlesung noch gar nicht dran waren, was
eigentlich ärgerlich ist.
Das ist so ein bisschen Spalt.
Ich habe hier in der Vorlesung versucht, häufig auf Fragen einzugehen.
Da ergaben sich hier viele interessante Zwiegespräche, was dazu führt,
wie auch jetzt, dass ich mit dem Stoff nicht so vorankomme.
Mir liegt aber daran, dass Sie wirklich Dinge verstehen.
Und da kommt es auf ein paar Einzelheiten, die ich Ihnen eigentlich
präsentieren möchte, gar nicht so sehr an.
Mir sind einige wichtige Prinzipien einfach viel wichtiger, die zu
vermitteln und dass Sie die verstehen, als dass ich jetzt den siebten
oder achten Algorithmus noch dargestellt habe.
Und es ist ja auch so, wenn im Forum viel gefragt wird und geantwortet
wird, ist es ja auch gut.
Dann bekommen Sie ja über das Forum die Antworten.
Ich hoffe, dass Sie mit den Übungen zurechtgekommen sind,
einigermaßen.
Ich habe gesehen, in der Bewertung war es halt so, dass die Aufgaben
von Ihnen als schwer angesehen wurden.
Ich weiß nicht, wie in anderen Vorlesungen, die jetzt zum Beispiel im
OR oder in anderen Bereichen Aufgaben gemacht werden, aber ich finde,
die Aufgaben waren nicht so wahnsinnig schwer.
Etwas, was ich immer gerne drin habe in Übungen, sind Aufgaben, bei
denen Sie nachdenken müssen.
Bei denen Sie nicht nur einfach ein Verfahren nochmal ausführen, da
lernen Sie nichts dabei.
Aber wenn Sie merken, wie man ein Problem löst, unter Nutzung der
Ideen, die ich Ihnen vorhin präsentiert habe, dann haben Sie eine
Fähigkeit gelernt.
Dann haben Sie nicht nur das Verfahren gelernt, das Sie wiedergeben
können, sondern haben Sie eine Fähigkeit gelernt und darin müssen Sie
sich üben, wie man mit etwas anderen Problemstellungen zurechtkommen
kann, wenn man Prinzipien, die man an einigen Beispielen hier gelernt
hat, sinnvoll überträgt.
Und dieser Übertragungsvorgang von einigen Vorgehensweisen auf andere
Problemstellungen, das ist das, was Sie lernen müssen und was Sie
später brauchen.
Sie werden später normalerweise nicht genau die Problemstellungen
haben, die wir Ihnen hier in den Vorlesungen erzählen, aber Sie
brauchen Vorgehensweisen, Sie müssen wissen, wie Sie an bestimmte
Probleme herangehen, Sie brauchen Problemlösungsstrategien.
Und darauf kommt es mir vor allen Dingen an.
Deswegen sind die Aufgaben auch so, dass Sie eigentlich immer so ein
bisschen andere Varianten in den Aufgaben kriegen, damit Sie diesen
Transfer hinkriegen müssen oder damit Sie sich daran üben, einfach
neue Problemstellungen unter Nutzung der Prinzipien, die wir Ihnen
vorgestellt haben, sinnvoll zu bearbeiten.
Das ist eigentlich mein Ziel bei den Übungen.
Das ist dann manchmal ein bisschen schwer, weil es nicht einfach ist,
nur wiederholen von Dingen ist, die Sie hier in der Vorlesung gemacht
haben.
Okay, ich muss weitermachen, können wir gerne an anderer Stelle
nochmal weiter diskutieren.
Was ist das Problem, das ich jetzt hier Ihnen darstellen möchte bei
dem zweiten Problem der algorithmischen Geometrie?
Wir haben ein einfaches Polygon.
Was ist ein einfaches Polygon?
Das ist eins, bei dem die Ebene in genau zwei disjunkte Regionen
eingeteilt ist.
Also dieses Polygon hier, das ist nicht einfach, weil wir dort so eine
komische Schleife drin haben.
Da ist die Ebene nicht in genau zwei disjunkte Regionen eingeteilt,
sondern da haben wir irgendwie drei verschiedene Regionen.
Da haben wir nämlich noch hier in der Mitte diesen Bereich.
Ist der nun außen oder ist der innen?
Eigentlich ist der außerhalb, aber der liegt irgendwie mitten im
Inneren.
Ganz seltsam.
Also solche Überkreuzungen, die machen es manchmal etwas schwieriger,
mit solchen Polygonen umzugehen.
Einfache Polygone sind zum Beispiel solche wie diese hier.
Das sind ganz einfache.
Sieht schwieriger aus als das andere.
Aber es ist einfach, weil es die Ebene genau in zwei Bereiche teilt,
nämlich das Innere und das Äußere.
Das ist bei dem oberen kleinen Beispiel nicht der Fall.
So, dieses ist ziemlich verwinkelt.
Und jetzt hat man folgendes Problem.
Ich habe hier irgendein Kreuz, dieses X, und ich möchte wissen, liegt
dieser Punkt...
eigentlich hätte ich ihn Q nennen müssen hier, also das ist der Punkt
Q.
Liegt dieser Punkt innerhalb oder außerhalb unseres Polygons?
Und hier sieht man natürlich sofort, er liegt innen.
Das ist aber nicht immer so einfach.
Also wenn der hier liegen würde, sieht man auch, der ist wohl
tatsächlich innen.
Aber wenn Sie sich sowas vorstellen, das ist gar nicht so einfach.
Oder stellen Sie sich jetzt ein ganz anderes Beispiel vor.
Sie machen Urlaub in Australien.
Und in Australien gibt es, das ist mein Standardbeispiel, weil ich das
selbst erlebt habe, Sie fahren durch Australien und da finden Sie ganz
viele Felder auf den Rinderweiden.
Und jetzt suchen Sie sich eine Stelle, wo Sie Ihr Zelt aufschlagen.
Sie wollen aber nicht auf einer Weide Ihr Zelt aufstellen, sondern Sie
wollen das außerhalb der Weide aufstellen.
Sie wollen nicht innerhalb eines Feldes sein.
Und Sie fahren also los, Sie fahren von außerhalb des Feldes los und
Sie fahren durch die Landschaft.
Und jetzt wollen Sie wissen, bin ich jetzt eigentlich in einem Feld
oder bin ich außerhalb eines Feldes.
Die Grenze zwischen den Feldern, die sind auf diesen Straßen ganz
einfach.
Das sind hier so kleine, das sind also so irgendwelche Eisengitter,
damit die Rinder da nicht rüberlaufen können.
Das heißt, Sie merken das beim rüberfahren, dass Sie hier über eine
Grenze eines Feldes rübergefahren sind.
Die Rinder können da nicht rüber.
Und die Frage ist, wenn Sie also jetzt hier irgendeine Strecke
gefahren sind bis dahin, sind Sie jetzt, wenn Sie hier gelandet sind,
sind Sie da im Feld oder sind Sie außerhalb des Feldes?
Und die einfache Idee ist, das ist ja ganz einfach.
Wenn ich außerhalb anfange, dann komme ich mit dem ersten Zaun rein,
mit dem nächsten wieder raus.
Dann brauche ich nur die Anzahl der Zäune zu zählen, über die ich
gefahren bin.
Und wenn ich eine gerade Zahl von Zäunen überfahren habe, dann bin ich
draußen.
Wenn ich eine ungerade Zahl habe, bin ich drin.
Und das heißt, das einfache Verfahren, diese sogenannte Strahlmethode,
ist also so, dass ich einfach eine Gerade betrachte durch dieses
Polygon hindurch und ich bestimme die Anzahl der Schnittpunkte.
Diese Geraden, die fängt ja außerhalb an, hier in dem Bereich
irgendwo.
Und dann brauche ich nur bis zu dem Punkt rüber zu gehen.
Wenn die Anzahl der Schnittpunkte gerade ist, ist der Punkt draußen.
Wenn die ungerade ist, ist der Punkt drinnen.
Das heißt, ich muss dann natürlich diese ganzen Schnittpunkte hier
feststellen.
Die muss ich alle ermitteln.
Ich muss also feststellen, wie viele dieser Kanten schneide ich, wenn
ich hier zu dem Punkt rübergehe.
Und da muss man natürlich einfach gucken.
Einfacher Ansatz, ich nehme hier alle Kanten her und überprüfe, ob
diese Kanten sich mit dieser Geraden schneiden.
Und wenn das eine gerade Zahl von Kanten ist, bis zu diesem Punkt hin,
also alle Kanten, die jetzt hier rechts davon liegen in dem Fall, wenn
das eine gerade Zahl ist, ist der Punkt außerhalb.
Wenn das eine ungerade ist, ist er innerhalb.
Also das ist ein einfacher Ansatz.
Und genauso kann also der Bauer, wenn er nach seinen Kühen guckt und
sieht, ist mein Rind da irgendwo auf der Weide, ist das innerhalb oder
außerhalb, guckt dann mit dem Fernglas rüber und zählt einfach die
Anzahl der Zäune auf dem Weg dahin, die er sehen kann.
Man geht davon aus, man kann alle sehen.
Und dann zählt er einfach nur und dann sieht er, ist das Rind drin
oder draußen.
Also ganz praktische Probleme, die man dann lösen kann, die man in der
Landwirtschaft an der Endung finden könnte.
Nur so, dass Sie sehen, das ist ein typisches Problem in
algorithmischer Geometrie.
Ohne Vorbereitung wollen wir auch gar nicht weiter uns mit
beschäftigen, kann man auch die Vorbereitung nicht wirklich
verbessern, weil die Information, die ich habe, einfach, das Polygon
ist einfach, mehr weiß ich aber nicht.
Die Struktur des Polygons kann ziemlich kompliziert sein, da kann ich
durch Vorbereitung nicht wirklich viel machen.
Also das sind so verschiedene horizontale Geraden, die da einfach mal
reingemalt sind und dann kann ich also feststellen, liegt der Punkt
drinnen oder draußen.
Jetzt nehme ich mir noch weitere Eigenschaften her und dann wird es
interessanter.
Ich nehme mir jetzt die Eigenschaft dazu, nicht nur einfach, sondern
auch noch konvex.
Wann ist ein Polygon konvex?
Das ist ein einfaches Polygon, bei dem ich hier irgendwo in einem
Punkt anfange und dann meinetwegen in dieser Richtung hier durchlaufe.
Wenn das Polygon einfach ist, dann mache ich nur Rechtsdrehungen.
Das heißt, wann immer ich hier rumlaufe, habe ich hier Rechtsdrehungen
zu machen.
Wenn ich in dieser Richtung da durchlaufe.
Bei diesem hier, das ist nicht konvex, dann mache ich hier zwar eine
Rechtsdrehung, aber da muss ich eine Linksdrehung machen.
Und das heißt, das ist nicht konvex.
Und was hilft uns die Konvexität?
Konvexität hat eine schöne Eigenschaft, das wissen Sie auch.
Eine andere Definition von Konvexität ist, wenn ich irgendeinen Punkt
im Inneren habe, oder ich kann auch sagen, wenn ich zwei Punkte im
Inneren habe, die Verbindungslinie zwischen zwei Punkten im Inneren
liegt immer vollständig in dem Polygon drin.
Das heißt aber auch, dass was hier steht, wenn ich irgendeinen Punkt
im Inneren habe, diesen Punkt R, und ich nehme irgendeinen Strahl von
diesem Punkt aus nach außen, hier sind so ein paar angedeutet, dann
schneidet dieser Strahl das Polygon an nur einem Punkt.
Das ist also bei diesem hier nicht der Fall, wenn ich von dem hier
nach außen gehe, in die Richtung, sehen Sie, da habe ich mehrere
Schnittpunkte mit Kanten des Polygons.
Und das heißt, bei Konvexen habe ich eine interessante Eigenschaft,
jeder Strahl nach außen schneidet das Polygon nur einmal.
Wir hatten bei dem anderen Beispiel mit diesen Rindern gerade eben das
Problem gesehen, da habe ich also eine ganze Reihe von Schnittpunkten,
hier habe ich tatsächlich nur einen Schnittpunkt.
Und das nutzt man jetzt aus, um eine geeignete Vorbereitung zu machen,
wenn man diese Frage beantworten will, liegt ein Punkt innerhalb oder
außerhalb so eines einfachen konvexen Polygons.
Man geht dabei jetzt folgendermaßen vor, man bestimmt einfach
irgendeinen Punkt, nimmt sich irgendeinen Punkt R her, im Inneren von
P, und teilt jetzt das Polygon durch Strahlen auf in Sektoren, in N
-Sektoren, dadurch, dass ich einfach diesen Punkt R verbinde mit allen
Eckpunkten meines Polygons.
Dann habe ich also hier diese Strahlen, die ausgehen von dem Punkt R,
verbunden mit den jeweiligen Polygonpunkten.
Dadurch habe ich jetzt eine ganze Reihe von Sektoren.
So, was hilft mir das?
Ich kann jetzt das Verfahren folgendermaßen machen, ich möchte also
gerne die Lage des Punktes Q, der hier angegeben ist, möchte ich
bestimmen, liegt er innen oder außen.
Wir sehen natürlich sofort, dass er außen liegt.
Aber wie kann ich das algorithmisch machen?
Also, ich suche erstmal den Sektor, in dem dieser Knoten liegt.
Wie kann ich den Sektor suchen?
Ich habe ja bei einem Polygon eine Reihenfolge der Knoten.
Die Reihenfolge des Polygons ist gegeben durch die Polygonpunkte P1,
P2 usw.
bis Pn meinetwegen.
Das sind meine N-Polygonpunkte.
Fängt meinetwegen hier irgendwie an, P1, P2 usw.
So, jetzt sind also meine Polygonpunkte nun mal so angeordnet.
Da kann ich natürlich genauso gut sagen, meine N-Sektoren sind einfach
so radial angeordnet.
Ich kann ja im Prinzip hier der Reihe nach so rumlaufen.
Das ist eine sortierte Reihenfolge.
Ich könnte das jetzt so rum machen, ich könnte es auch andersrum
machen.
Auf jeden Fall kann ich hier in einer Reihenfolge durchlaufen.
Und ich kann auf der Folge dieser Sektoren eine binäre Suche machen.
Was für eine binäre Suche?
Ich stelle einfach fest, liegt dieser Punkt Q rechts oder links von
einem gewissen Element in der Folge.
Was sind die Elemente dieser Folge?
Zum Beispiel gucke ich, liegt der Punkt Q meinetwegen links von dem
Punkt P2.
Da liegt in dem Fall rechts davon.
Also da liegt der Punkt Q.
Und dadurch kann ich also binäre Suche machen.
Ich gehe in die Mitte der Folge usw.
Ich stelle fest, liegt er links oder rechts.
Und dann gehe ich immer weiter, bis ich genau zwei Elemente gefunden
habe, zwischen denen der Punkt liegt.
Wie hier zwischen PI und zwischen PI plus 1.
Er liegt rechts von PI und links von PI plus 1.
Und damit habe ich einen Sektor identifiziert.
Binäre Suche braucht log N Schritte, also kein Problem.
Oder es geht sehr schnell.
Dann muss ich nur noch feststellen, ob Q in diesem Sektor innerhalb
oder außerhalb von P liegt.
D.h.
liegt dieser Punkt Q links oder rechts von dieser Verbindungslinie
zwischen PI und PI plus 1, also zwischen dieser Kante des Polygons.
Auch dies ist wieder ein Problem.
Liegt der Punkt links oder rechts von einer Geraden oder von einem
Liniensegment.
D.h.
ich muss diese Aufgabe mehrfach lösen.
Das muss ich bei der binären Suche machen.
Wenn ich feststellen will, in welchem Sektor bin ich, muss ich
feststellen, liegt der Punkt links oder rechts von irgendeiner
Geraden.
Und hier innerhalb des Sektors genauso.
D.h.
das, was ich als Operation brauche, ist, wie kann ich feststellen, ob
ein Punkt links oder rechts von einer Geraden liegt.
Sie kennen das aus der Geometrie, da kann man irgendwelche Winkel
bestimmen oder ähnliche Dinge.
Da muss man sich überlegen, wie kann man das jetzt hier in einer
geschickten Art und Weise machen.
Diese Lagebestimmung für einen Punkt.
Schauen wir uns das ein bisschen genauer an.
Wenn wir den Punkt Q haben und wir haben hier R und Pi.
Was wir betrachten ist im Prinzip dieser Winkel.
Wenn der Winkel, also wenn Q links von R, Pi liegt, R, Pi, also dieses
Stück hier.
Wenn der links davon liegt, dann ist dieser Winkel Q, R, Pi eine
Linksdrehung.
Wenn Sie von Q nach R nach Pi gehen, machen Sie eine Linksdrehung.
Wenn der rechts davon liegt, dann ist Q, R, Pi eine Rechtsdrehung.
Das heißt, Sie gucken jetzt, ist das eine Linksdrehung oder eine
Rechtsdrehung.
Wie kann ich das dann schon wieder feststellen?
Ob das eine Linksdrehung oder eine Rechtsdrehung ist, das hat was mit
Winkeln zu tun.
Bei Winkeln denkt man auf trigonometrische Funktionen.
Das macht alles relativ kompliziert.
Wenn ich trigonometrische Funktionen berechnen möchte, muss ich mit
reellen Zahlen arbeiten.
Das kann ziemlichen Aufwand verursachen und das ist also etwas
schwierig.
Schauen wir uns das nochmal genauer an.
Hier betrachten wir jetzt auf einmal eine Anzahl von geometrischen
Flächen.
Und zwar betrachten wir, was wir rauskriegen wollen, ist die Fläche
dieses Dreiecks von Q, R und Pi.
Das heißt, da hätten wir so ein Dreieck, da haben wir auch so ein
Dreieck.
Und Sie sehen, wenn das hier die Fläche ist, einmal liegt sie oberhalb
der geraden Pi, einmal unterhalb dieses Segments Pi.
Und wenn ich die Fläche berechnen will, kann ich das machen mit
folgender Formel, die wie folgt entsteht.
Ich betrachte erstmal hier, was steht da denn?
Y plus YI halber.
Also Y ist dieses Stück.
YI ist das Stück.
Und XI minus X ist genau dieses Stück.
Das ist also mein XI minus X.
Jetzt habe ich durch diese Elemente ein Trapez aufgespannt.
Fläche des Trapezes ist genau das, was hier steht.
Das ist also die Fläche des Trapezes, das von Q und Pi im Prinzip mit
der X-Achse aufgespannt wird.
Die nächsten beiden sind ebenfalls Flächen von Trapezen.
Und zwar ist das nächste Y plus T halber, also Y und T.
Das ist also dieses Trapez hier.
Dann habe ich hier noch ein Trapez, YI plus T und so weiter.
Das ist dieses hier.
Und das muss ich abziehen von der Summe der beiden anderen Trapeze.
Dann habe ich genau das, was hier übrig bleibt.
Das ist genau die Fläche dieses Dreiecks.
Wenn allerdings dieser Punkt, wenn wir einen Q-Strich hätten, der hier
liegt, dann würde ich bei der Berechnung eines hier bekommen, der
negativ ist.
Weil ich bei der gleichen Vorgehensweise zunächst mal das Trapez
berechnen würde, dann das Trapez hier, das Trapez und ich würde das
Trapez, das große, abziehen und dann hätte ich einen negativen Wert
herausgerechnet.
Und das, was ich im Prinzip berechne, was hier in dieser Formel steht,
das ist sehr ähnlich wie die Berechnung einer Determinanten.
Und zwar ist die Fläche, die da oben berechnet steht, ist genau der
halbe Wert der Determinante aus diesen drei Punkten QR und PI.
QR und PI stehen hier.
Ich berechne die Determinante, schreibe hier hinten noch die Einsen
daneben, dann habe ich genau die Formel, die da oben drüber steht.
Also im Prinzip muss ich nur die Formel da oben drüber einmal
implementieren, dann habe ich das.
Nur, dass Sie sehen, was wird hier eigentlich berechnet.
Das ist die Determinante.
Und das, was ich brauche, ist eigentlich nur, ich muss wissen, ist der
Wert der Determinanten größer 0 oder kleiner 0.
Ich will ja nicht wissen, wie weit ist der weg, wie groß ist der
Inhalt dieser Fläche.
Ich möchte nur wissen, ist der Wert positiv oder negativ.
Wenn er positiv ist, liegt der Punkt links von der Geraden, wenn er
negativ ist, liegt er rechts von der Geraden.
Und das heißt, ich brauche eigentlich nur hier diese beiden, also nur
diese Entscheidung zu treffen, ist der Wert dieser Determinanten
positiv oder negativ.
Wenn er positiv ist, liegt der Punkt Q links von der Geraden, wie das
hier dargestellt ist.
Ansonsten wäre das ein Punkt Q' der irgendwo, also wenn das ein Punkt
Q' ist, dann würde der Wert kleiner 0 sein, dann liegt er rechts
davon.
Also insofern haben wir hier diese Möglichkeit, wie man das
entscheiden kann, durch ganz einfache Berechnungen.
Wir brauchen keine trigonometrischen Funktionen, müssen nur diese
einfache Formel auswerten.
Und das Vorzeichen bestimmen, das Wert, das dabei herauskommt.
Wobei ich eines sagen muss, wenn Sie sich jetzt eine Situation
vorstellen, Sie haben hier unseren Punkt, meinetwegen R, da haben wir
den Punkt PI, nein, ja, gerade den Punkt PI, jetzt haben wir hier
einen Punkt Q.
Das ist jetzt mein Punkt Q.
Liegt der Punkt links oder rechts?
Ja?
So, nun sieht das ein bisschen nicht aus wie eine Gerade.
Also es kann sein, dass der Punkt ganz nah dran liegt an dieser
Gerade.
Stellen Sie sich vor, das sind irgendwelche reellwertigen Koordinaten.
Sie haben Punkte, die liegen irgendwo hier ganz nah an dieser Gerade
dran.
Dann kann diese Entscheidung, ob dieser Wert, der herauskommt, positiv
oder negativ ist, davon abhängen, mit welcher Genauigkeit Sie die
reellen Koordinaten bestimmen.
Und wir gehen mal davon aus, dass diese Probleme im Augenblick nicht
existieren, dass wir eine ganz klare Entscheidung haben, dass wir
eindeutig entscheiden können, fehlerfrei, liegt der Punkt rechts oder
links daneben, ist der Wert positiv oder negativ.
In der Praxis, darauf weise ich gleich hin, in der Praxis, da kann es
also durchaus auftreten, dass Sie sowas haben, dass Sie solche
Situationen haben, dass Punkte sehr nah aneinander liegen und
Algorithmen, die auf diese Art und Weise das bestimmen, können auf
einmal in Probleme geraten.
Wir werden nachher noch Beispiele sehen, wo das auftreten kann.
Da muss man wieder andere Verfahren einsetzen.
Also kann ich auch an dieser Stelle gleich darauf eingehen.
Wenn Sie nur feststellen wollen, Sie haben hier eine Menge von Punkten
und wollen feststellen, wie viele liegen links oder rechts von dieser
geraden RPI.
Wenn die so ganz eng da dran liegen, ist das schwierig zu bestimmen.
Was man dann macht, ist einfach eine zufällige Veränderung, sage ich
mal einfach.
Zufällige Veränderungen dieser geraden RPI, leicht verschieben und
dann können Sie feststellen, wie sich das Ganze verändert.
Da können Sie Veränderungen feststellen an diesen Entscheidungen,
welcher Punkt links oder rechts liegt.
Und über mehrere solche Veränderungen kriegen Sie dann im Prinzip
raus, was eine bessere Abschätzung ist für die Anzahl der Punkte, die
links oder rechts liegen.
Nur als kurze Randbemerkung, dass man hier in der Praxis aufpassen
muss, wie das mit reellwertigen Zahlen aussieht.
Bei den Algorithmen der algorithmischen Geometrie sind häufig eine
ganze Reihe Annahmen gemacht, dass so etwas, wie ich hier angedeutet
habe, gar nicht auftritt.
Es wird also angenommen, es gibt eigentlich nie den Fall, dass Sie
drei Punkte haben, die in einer Linie liegen.
Dann streiche ich den mittleren immer raus, weil ich ja sage, den
brauche ich nicht.
Da kann ich genauso gut sagen, wenn ich aus meinen Wegen zwei Punkte
verbinde, da wird nie irgendeiner genau dazwischen liegen.
Und den brauche ich nicht, den streiche ich raus.
In der Praxis kommt das nicht vor.
Nehme ich an.
Tatsächlich kann das in der Praxis auftauchen und dann muss ich mit
diesem Problem arbeiten.
Dann muss ich dazu etwas tun.
Dazu gibt es eine ganze Reihe Arbeiten, die am MPI in Saarbrücken
gemacht wurden.
Max-Planck-Institut für Informatik in der Gruppe von Herrn Mehlhorn,
der hat dazu eine ganze Reihe von Algorithmen entworfen, mit denen man
an diese tatsächlichen Probleme in der Praxis, so eigentlich
Randfälle, Extremfälle, die einen manchmal stören, wie man damit
trotzdem noch umgehen kann.
Ganz interessante Prinzipien, die er da einsetzt.
Das ignorieren wir jetzt erstmal alles und sagen, wir gehen davon aus,
diese Entscheidungen sind problemlos zu treffen.
Wir wissen jetzt, wie wir feststellen können, ob ein Punkt links oder
rechts liegt.
Das heißt, wir bestimmen nur diese Determinante und haben dann diese
Entscheidung getroffen und können davon ausgehen, dass das also
einfach machbar ist.
Insbesondere ist es eben in konstanter Zeit machbar.
Ich muss halt diese kleine Formel auswerten, dann habe ich diese
Entscheidung getroffen.
Und das heißt, dieser Algorithmus, um festzustellen, wo liegt dieser
Punkt Q, liegt der außen oder innen, ist in logarithmischer Zeit in N
zu lösen, weil ich einmal mit binärer Suche den Sektor bestimme und
dann nur feststellen muss, liegt der links oder rechts von der Polygon
-Linie.
Und was ich hier noch brauche an Platz, ist natürlich der
Speicheraufwand für meine Polygon-Punkte und die Vorbereitung, Aufwand
O von N.
Ich musste ja einmal diese Aufteilung in die Sektoren tatsächlich
vornehmen.
Wenn ich die noch sortieren müsste, meine Punkte, wenn die nicht in
der sortierten Reihenfolge vorliegen würden, müsste ich die Punkte
noch sortieren, hätte ich einen Aufwand von N log N.
Beim einfachen Polygon gehe ich davon aus, ich habe die in einer
Reihenfolge gegeben, es ist ein Rundlauf durch mein Polygon und dann
habe ich die sortierte Reihenfolge bereits in Bezug auf die radiale
Anordnung meiner Punkte.
Das heißt, ich brauche keine Sortierung zu machen.
Und deswegen, weil diese radiale Sortierung bereits in der
Problemstellung gegeben ist, habe ich also insgesamt für Vorbereitung
nur Aufwand O von N und für die einzelne Beantwortung der
Punktanfragen O von log N.
Das heißt, die Konvexität meines Polygons bringt mir hier einen Gewinn
oder Verbesserung von linearer Zeit auf logarithmische Zeit.
Jetzt nur noch die Frage, woher weiß ich, ob ein Polygon einfach ist.
Das muss ich ja feststellen, damit ich diese Verfahren einsetzen kann.
Das heißt, ich muss feststellen, wo liegen eigentlich die
Schnittpunkte zwischen oder welche Kanten schneiden sich eventuell.
Ich habe also mein Polygon gegeben.
Es ist die Frage, welche dieser Polygonlinien schneiden sich.
Gibt es solche Schnittpunkte?
Wenn sie hier irgendwelche Punkte schneiden oder welche Kanten
schneiden, dann habe ich ein nicht einfaches Polygon.
Die Frage ist, wie kann ich das überprüfen?
Ich könnte auch sagen, ganz allgemein, ich betrachte eine Reihe von
irgendwelchen Kanten und frage mich, wie viele Schnittpunkte gibt es
zwischen diesen Geraden oder Liniesegmenten.
Etwas verallgemeinerte Problemstellung.
Hier ist das Problem einfach, ich will feststellen, ist das Polygon
einfach oder nicht.
Dann reicht es festzustellen, gibt es einen Schnittpunkt.
Sobald ich diesen Schnittpunkt gefunden hätte, wäre ich fertig.
Wenn ich alle Schnittpunkte zwischen Geradensegmenten haben möchte,
müsste ich ein bisschen mehr machen.
Naiv würde ich wieder so vorgehen, dass ich einfach sage, okay, was
ist die Problemstellung?
Ich habe mein Polygon gegeben mit N Kanten.
Ich will feststellen, welche dieser Kanten schneiden sich.
Da gucke ich einfach für jede Kante, ob sie sich mit irgendeiner der
anderen schneiden.
Das ist ein typisches Problem, jeder mit jedem zu überprüfen.
Quadratische Zeit, also quadratischer Aufwand dafür, der Platz für die
N Kanten ist natürlich nur linear.
Vorbereitung ist hier null.
Und jetzt ist die Frage, wie kann ich hier besser vorgehen?
Kann ich das Verfahren verbessern?
Und ich zeige Ihnen jetzt die Verbesserung, weil ich Ihnen ein
weiteres Prinzip präsentieren möchte, das in Zusammenhang mit dem
Problem der algorithmischen Geometrie entwickelt worden ist.
Eine Vorgehensweise, wie man solch ein Problem lösen kann.
Und das ist der Ansatz, der hier als klug dasteht.
Das ist der Plane Sweep.
Was macht der Plane Sweep?
Der Plane Sweep sagt, ich nehme hier ein Besen her und fege mit diesem
Besen einmal über meine Ebene rüber.
Diese Linie hat eine Reihe von Punkten, wo etwas Interessantes
passiert.
An dieser Stelle, wenn diese Linie hier angekommen ist, ist es
interessant, weil hier zwei Linien beginnen.
Die ersten beiden Kanten meines Polygons beginnen.
Wenn ich hier bin, ist wieder ein interessanter Punkt.
Dazwischen tut sich nichts Interessantes.
Überall habe ich nur zwei Linien-Segmente meines Polygons.
Da brauche ich nichts weiter zu tun.
An dieser Stelle, wenn ich dort bin, beginnt eine neue Polygonlinie.
Und jetzt könnte ja passieren, dass hier eine Polygonlinie beginnt,
die sich mit der anderen hier schneidet.
Mit der da unten drunter.
Könnte man überprüfen.
Gibt es da eine Überschneidung?
Gibt es in dem Fall nicht.
Dann kommt hier der nächste Punkt.
Hier oben endete eine Polygonlinie, eine andere beginnt.
Hier endet auch eine Polygonlinie, eine andere beginnt.
Auch da kann man wieder feststellen, gibt es dadurch irgendwelche
neuen Überschneidungen.
Dann gibt es, also dass hier hinten eine Überschneidung vorkommt, sehe
ich jetzt noch nicht, wenn ich an diesem Punkt hier vorne bin.
Hier also an diesem Punkt.
Dann komme ich zu dem Punkt.
Jetzt gehe ich mal davon aus, dass der eindeutig links neben dem
liegt, da unten.
Und dann habe ich wieder etwas zu tun.
Dann kommt dieser Punkt hier.
Und da beginnen jetzt zwei Kanten.
Diese beiden.
Und Sie sehen, hier ist eine, die unten drunter, also die hier auf der
Linie im Prinzip unten drunter abgespeichert wurde.
Wenn ich davon ausgehe, ich speichere auf dieser Linie im Prinzip ab,
wo jeweils meine Kanten liegen.
Und in dem Augenblick, wo ich Informationen über diese Kante habe und
über diese Kante, kann ich feststellen, die beiden überschneiden sich.
Das kann ich lokal feststellen, indem ich nur gucke auf meiner Linie,
was ist die Nachbarschaft dieses Punktes.
Hier beginnen zwei Kanten.
Welche Kante liegt direkt daneben?
Überschneiden die sich eventuell?
Ich kenne ja die Richtungen dieser Liniesegmente.
Und dann würde ich hier feststellen, da überschneiden sich die beiden
Kanten.
Und ich wäre fertig.
Wenn wir alle Schnittpunkte feststellen wollen, müssten wir
weiterlaufen.
Dann wäre das der nächste interessante Punkt, das der nächste Punkt,
das, das und das hier auch noch einer.
Ja, also ich habe eine Reihe von Punkten, die ich mir angucken muss.
An denen etwas interessantes passiert.
Und es ist die Frage, wie kann ich diese interessanten Ereignisse
sinnvoll bearbeiten.
Offensichtlich ist hier schon folgendes.
Ich habe ein Polygon mit N Kanten und N Punkten.
Wie viele Haltepunkte habe ich?
Natürlich N in dem Fall.
Woher weiß ich, wie ich die von links nach rechts durchlaufen muss?
Dazu muss ich sie bezüglich ihrer X-Koordinaten sortieren.
Ja, also ich muss wissen, was sind die X-Koordinaten meiner Punkte.
Ich muss ja, das ist der erste, der zweite, der dritte, der vierte,
der fünfte und so weiter.
Diese Reihenfolge muss ich einmal mitteln.
Das ist ein Sortieren meiner Polygonpunkte bezüglich der X
-Koordinaten.
Damit habe ich die Folge der Punkte, auf denen ich links laufen muss.
Und dann muss ich mir überlegen, wenn ich an so einer Position hier
bin, meinetwegen hier an dieser Stelle, da habe ich einige
Informationen auf dem Weg dahin bereits angeguckt.
Das, was links davon liegt, hier in diesem Bereich, das kann ich alles
herausstreichen, kann ich vergessen.
Was ich wissen muss ist nur, welche Information ist gerade aktuell,
dass die Informationen über die Kante, über die Kante, die Kante, die
neu dazukommen und die Kante, die unten drunter lag.
Also das ist der aktuelle Ausschnitt meines Problems, das ich mir
angucken muss.
Ich kann sagen, mein Aufmerksamkeitsfenster oder so ähnlich.
Oder das ist eben das, was auf diesem Besen gerade an Informationen
gespeichert ist über die aktuelle Situation.
Jetzt muss ich sehen, wie kriege ich dieses Ereignis, es kommt ein
neuer Punkt dazu.
Das heißt, eventuell enden ein paar Kanten, die kann ich
herausstreichen, neue kommen dazu.
Wie kann ich dann meine Frage sinnvoll beantworten, schneidet sich
eine dieser neuen Kanten mit einer Kante, die bereits drin ist.
Und welchen Aufwand macht das?
Und natürlich ist die Idee, dass das einen konstanten Aufwand nur
macht, das muss ich nur mit meinen nächsten Nachbarn überprüfen.
Aber die Frage ist, wie finde ich eigentlich den richtigen Punkt auf
meiner Geraden.
Auf der Geraden sind eine ganze Reihe von Informationen abgespeichert.
Ich suche also den aktuellen Punkt, das ist im Prinzip die Y
-Koordinate dieses Punktes, damit ich da hinkomme.
Ein Suchen eines Punktes in einer Menge von Informationen, die bereits
abgespeichert sind, das ist ein einfaches Suchproblem.
Ich brauche also eine Suchstruktur.
Und Suchstrukturen wissen wir, können wir so aufbauen, dass wir
logarithmische Zeit brauchen für das Finden der einzelnen
Informationen darauf.
Das heißt, dieser Aufwand, um festzustellen, an welcher Stelle sind
wir jetzt gerade in unserer Suchstruktur, und wie sieht die lokale
Nachbarschaft aus, das kann ich mit einer geeigneten Datenstruktur
aufbauen, die logarithmische Zeit braucht für Suche, Einfügen und so
weiter.
Da haben wir uns mit Suchstrukturen beschäftigt.
Und dann mache ich die einzelne Operation hier darauf in konstanter
Zeit.
Das heißt, ich habe jetzt N Haltepunkte.
An jedem Haltepunkt habe ich einen Aufwand, der etwa logarithmische
Zeit braucht.
Wenn wir Pech haben, wenn wir Glück haben, sogar wesentlich schneller,
aber maximal logarithmische Zeit.
Das heißt, wir haben N mal Log N, um hier einmal ganz durchzulaufen,
bis wir die Entscheidung haben, wenn also keine Schnittpunkte da sind,
das Polygon ist einfach, oder falls wir vorher einen Schnittpunkt
haben, wissen wir vorher, das Polygon ist nicht einfach.
Der Aufwand zur Vorbereitung in dem Fall wäre aber, wir müssen erstmal
unsere Punkte lokal, also unsere Haltepunkte, das ist also nicht
Vorbereitung, sondern Teil des Verfahrens.
Wir müssen die X-Koordinaten sortieren.
Aufwand N Log N und nach Hilfe des Durchlaufen dieser Geraden darüber
ist das nochmal ein Aufwand von N Log N.
Also insgesamt N Log N sind Verbesserungen von O von N².
Was steckt eigentlich dahinter, wenn ich sage, wir fahren mit einem
Besen über diese Gerade drüber und stellen fest, welche Informationen
habe ich lokal auf diesem Besen, die relevant ist.
Das Wesentliche ist, dass ich das zweidimensionale Problem reduziere
auf ein eindimensionales.
Und dann mein Originalproblem löse durch eine Folge von Problemen auf
einer Geraden.
Das ist ein Intervallüberschneidungsproblem auf einer Geraden, weil
ich das nur noch untersuchen muss.
Das heißt, ich transformiere mein Originalproblem in N-Dimensionen
oder K-Dimensionen auf ein Problem mit K-1-Dimensionen.
Das sieht ein bisschen anders aus und muss dann eine Folge von solchen
Problemen in K-1-Dimensionen lösen.
In diesem Fall eine Folge von eindimensionalen Problemen auf dieser
Geraden.
Und diese jeweils eindimensionalen Probleme sind
Intervallüberschneidungsprobleme, die ich jeweils mit logarithmischem
Aufwand lösen kann.
Das war das ganze Verfahren, das auf den folgenden Folien jetzt
genauer beschrieben wird.
Also, das ist unsere Idee.
Wir haben hier das gleiche Bild hier unten nochmal mit dieser Anzahl
von Haltepunkten.
Und das, was wir eigentlich machen, wir gucken ein
Intervallüberschneidungsproblem an.
Was ist ein Intervallüberschneidungsproblem?
Ich betrachte in der Reihe von Intervallen, zum Beispiel das Intervall
I1, X1, Y1.
Ich habe also eine X-Achse gegeben und betrachte darauf Intervalle.
Das nächste Intervall, X2, Y2, läuft von da nach da.
Das nächste Intervall, X3, läuft von dort nach dort.
X4 läuft von dort nach dort.
Und Sie sehen, hier haben wir einige Überschneidungen von Intervallen.
Die Frage ist also, wie kann ich solch ein
Intervallüberschneidungsproblem sinnvoll lösen.
Ich möchte also alle Intervalle feststellen, die sich jeweils
schneiden.
Hier kann man es so machen, dass man die Endpunkte sortiert.
Die sind hier also einfach so sortierter Reihenfolge angegeben.
Zunächst sind die Intervalle mir gegeben als eine Folge von N
Intervallen.
Dann muss ich alle Koordinaten sortieren.
Dann muss ich nur feststellen, ob irgendein XI vor einem Yj auftritt
mit j kleiner i.
Das ist hier der Fall.
Hier tritt also ein X3 auf vor ein Y2.
Da X3 vor Y2 auftritt, ist klar, da habe ich eine Überschneidung.
Der Aufwand dafür ist n log n, nämlich für das Sortieren.
Dieses festzustellen, kommt dort ein XI vor einem Yj mit j kleiner i
vor.
Das ist dann ein linearer Aufwand, einmal durchlaufen durch die Linie.
Also das Intervallüberschneidungsproblem ganz allgemein in der einen
Dimension des Aufwandes n log n.
Das wäre aber dumm, wenn ich das jedes Mal für meine...
wenn ich also sage, ich habe hier eine Folge von n
Intervallüberschneidungsproblemen.
Das wäre sehr dumm, wenn ich für jedes Intervallüberschneidungsproblem
hier einen Aufwand von n log n hätte.
Bei diesem Planesweep-Verfahren.
Ich habe aber nicht jedes Mal ein neues
Intervallüberschneidungsproblem zu lösen, sondern ich habe ja immer
nur eine sehr lokale Änderung in meinen Intervallen, die ich auf
diesen Geraden hier aufmalen muss.
Nämlich nur die Informationen über die Intervalle, die gerade
interessant sind.
Und es kommt immer nur an einer Stelle ein neues Intervall hinzu.
Und in der lokalen Umgebung kann ich feststellen, ob es
Überschneidungen gibt oder nicht.
Also das ist nochmal der Planesweep.
Ich bewege also diese Gerade über mein Polygon hinweg.
Und die Haltepunkte sind gerade die Anfangs- und Endpunkte der Kanten
des Polygons.
Das heißt, ich brauche die nur nach ihren X-Koordinaten zu sortieren.
Und bin dann also sofort fertig.
Wenn hier steht lexikografisch, heißt das nur, ich habe hier zwei
Komponenten drin.
XI und YI.
Und ich sortiere nur nach XI.
So.
Und was muss ich am Haltepunkt machen?
Das ist hier genau dargestellt.
Ich habe es Ihnen im Prinzip gerade eben vorher erklärt.
Aber nicht genau.
Hier stehen die Details drin.
Und das sind also die einzelnen Operationen, die ich machen muss.
Lösche alle Kanteninformationen von Sweepline L.
Also L ist meine Sweepline, dieser Besen.
Die zu Kanten gehören, die in PH.
PH ist der Haltepunkt.
Hier, an dem ich gerade bin.
Meinetwegen dieser Punkt oder auch dieser da unten.
Die in PH enden und links von L liegen.
Also, wenn ich hier so eine Situation habe, dass ich in einem Punkt
bin.
Und da enden, entweder enden dort zwei.
Die Situation kann eintreten, dass zwei enden, dann werden die beiden
rausgestrichen.
Wenn dort nur eine Kante endet, eine neue anfängt, dann muss ich also
erstmal die eine enden, die in PH endet, links von L liegt.
Also, das ist diese Kante, die würde rausgestrichen werden.
So, jetzt kann es sein, dass ich hier drüber und da drunter
Informationen habe, über Kanten, die vorher nicht benachbart waren,
direkt.
Hier lag diese Kante dazwischen.
Wird also diese Kante K hier gelöscht, dann überprüfe, ob die Kanten,
die direkt da drüber oder da drunter liegen, das sind also jetzt K o,
heißt also K oberhalb und K u für K unterhalb, ob diese Kanten sich
schneiden.
Das brauchte ich vorher nicht zu überprüfen, weil da noch eine Kante
dazwischen war, die Kante K war dazwischen.
Da habe ich vorher überprüft, ob sich K und K o überschneiden.
Offensichtlich nicht.
Oder K u und K.
Jetzt nehme ich nämlich die Kante K heraus und dann sind diese beiden
oberhalb und unterhalb von K auf einmal direkt benachbart und die
könnten sich schneiden eventuell.
Das muss ich jetzt überprüfen, ob die beiden sich überschneiden.
Wenn nicht, mache ich weiter und trage jetzt für jede Kante, die von
PH nach rechts führt, also es kann nur eine sein in dem Fall, in
diesem Fall, wenn eine von links kam, wenn ich aber eine Situation
hätte, wie meinetwegen hier, dass ich an so einem Punkt bin und da
gehen jetzt zwei Kanten raus.
Das ist die Situation, die wir dort haben, an dieser Stelle.
Da würden zwei Kanten nach rechts rausgehen.
Dann müsste ich für diese Kanten den Endpunkt PJ eintragen.
Also jeweils die Endpunkte dieser beiden Kanten oder der einen Kante.
Ich muss die neue Kante eintragen und dann muss ich feststellen, ich
habe jetzt hier eine neue Kante, überschneidet sich die so
eingetragene Kante mit ihrem direkten Nachbarn K u oder mit dem
anderen direkten Nachbarn K u.
Das waren die beiden Nachbarn, die wir gerade eben hier festgestellt
hatten, die also meinetwegen da und da liegen oder hier dieses K u und
da das K u.
Ich habe eine neue Kante eingefügt, muss feststellen, überschneidet
sie sich mit ihrem direkten Nachbarn.
Wenn ich zwei eingefügt habe, muss ich natürlich nur die beiden
überprüfen oder die beiden.
Die beiden, die ich neu eingefügt habe, können sich ja nicht
schneiden.
Also ich muss sehen, was sind neue Nachbarschaften zwischen Kanten.
Da muss ich überprüfen, gibt es Überschneidungen.
Wenn nicht, mache ich weiter.
Wenn also hier eine Kantenüberschneidung festgestellt wird, bin ich
fertig.
Andernfalls mache ich weiter, gehe zum nächsten Haltepunkt, muss
wieder Kanten rausflöschen, andere einfügen, neue Nachbarschaften
überprüfen und muss also immer sehen, wo liegt dieser neue Punkt, auf
wo bin ich in meiner Datenstruktur.
Und dieses Fragen, wo bin ich in der Datenstruktur, braucht eventuell
logarithmischen Aufwand.
Logarithmisch in der Anzahl der Informationen, die auf diesem Besen
gerade liegen.
Und es kann natürlich sein, dass sehr viele Graden auf diesem Besen
liegen.
Stellen Sie sich vor, Sie haben hier ein Polygon, das meinetwegen so
aussieht.
Dann hätten Sie eventuell sehr viele Kanten, die gleichzeitig auf
dieser Graden liegen.
Sie hätten sehr wenige Haltepunkte, aber viele Informationen auf
diesem Besen.
Das heißt, Sie können dort in Größenordnung N Kanten drauf haben.
Und deswegen ist der Aufwand Log N, im schlechtesten Fall.
Wenn Sie eine andere Situation haben, die hier angedeutet ist, da
hätten Sie nur sehr wenige Kanten auf diesem Besen drauf.
Da wäre der Aufwand natürlich entsprechend geringer.
Aber das sind halt unterschiedliche Situationen, die man hier im
schlechtesten Fall mit berücksichtigen muss.
Wenn das der letzte Haltepunkt war, den man betrachtet hat, und man
hat keinen Schnittpunkt gefunden, dann ist man an der Stelle fertig
und weiß, das Polygon ist einfach.
Und hier steht es nochmal, wenn ich die Datenstruktur auf meinem Besen
geschickt wähle, als balancierten Suchbaum, Sie wissen, wie man das
macht, dann benötigt jede Einfüge-Lösch-Operation jeweils Zeit O von
Log N.
Wobei man hier noch eine gewisse Randbedingung hat.
Ich möchte natürlich auch die Nachbarschaften, Informationen über die
direkt benachbarten Kanten, sehr effizient herausfinden können.
Dafür kann man auch noch gewisse besondere Datenstrukturen sich
überlegen, auf die ich hier aber nicht eingehe.
Ich wollte hier vor allen Dingen vermitteln, diese Idee, ich löse ein
gewisses Problem dadurch, dass ich es in der Dimensionalität
verringere, auf ein anderes Problem abbilde und dann eine Folge von
Instanzen dieses kleineren Problems bearbeiten muss, dass natürlich
ein kleinerer Aufwand gelöst werden kann.
Und diese Anzahl der Lösungen des kleineren Problems insgesamt kann
eben besser sein, schneller sein, geringeren Aufwand verursachen, als
die Lösung des größeren Problems mit einem anderen Ansatz, wie wir das
vorher gesehen haben.
Da war der Aufwand N² und hier mit dieser Reduktion auf diesem Besen
habe ich halt Aufwand von NlogN.
Also ein weiteres Prinzip, das ich Ihnen an der Stelle darstellen
wollte.
Jetzt kommen wir schon zu dem nächsten Problem, nämlich eine konvexe
Hülle zu bestimmen.
Klassisches Problem in algorithmischen Geometrie.
Und hier kann ich Ihnen in der restlichen Zeit noch ein paar Verfahren
oder Ansätze vorstellen.
Es gibt hier viele Verfahren, um eine konvexe Hülle zu bestimmen.
Was ist eine konvexe Hülle?
Ich habe eine Punktmenge.
Hier, das ist meine Punktmenge.
Und jetzt möchte ich die konvexe Hülle bestimmen.
Konvexe Hülle ist die kleinste konvexe Teilmenge von E², die M
enthält.
Also, ich muss im Prinzip hier das Polygon so außen drum malen.
Ich gucke mir sogenannte Extrempunkte an, die ganz außen liegen.
Das hier wäre die kleinste konvexe Teilmenge von E², die die Menge M
gerade enthält.
Also, das ist der Schnitt aller Teilmengen von S, sodass M enthalten
ist und S ist eine konvexe Menge.
Ich kann auch sagen, ich möchte bestimmen, dass das, was ich hier
gerade eben angemalt habe, das konvexe Polygon P gleich CH, konvex
Hall von M, also konvexe Hülle von M, das den Rand dieser konvexen
Menge hier gerade bildet.
Also, woran ich interessiert bin, ist dieses konvexe Polygon.
Das möchte ich gerne bestimmen.
Ich muss also folgendes machen.
Ich muss die Menge der Extrempunkte feststellen.
Sie haben solche Probleme in anderem Zusammenhang mal kennengelernt,
wenn Sie zum Beispiel Simplex-Verfahren oder sowas angucken.
Da wollen Sie auch Extrempunkte bestimmen.
Das sind gerade die besten Lösungen oder die effizientesten Lösungen
für gewisse Probleme.
Wenn Sie Pareto-optimale Punkte haben wollen in einer Menge von
Punkten bezüglich gewisser Kriterien, wollen Sie genau solche Punkte
finden, solche Extrempunkte, und wollen also gerade solche konvexen
Hüllen oder Teile von konvexen Hüllen bestimmen.
Also ein Problem, das man sich auch in einer ganzen Reihe
unterschiedlichster Fragestellungen anguckt.
Und nun ist die Frage, wie macht man das?
Ich muss also diese Extrempunkte bestimmen.
Wenn ich die Extrempunkte habe, habe ich im Prinzip die Menge der
Punkte, die das konvexe Polygon bilden, also die konvexe Hülle bilden.
Um das konvexe Polygon tatsächlich angeben zu können, reicht es nicht
nur die Menge der Extrempunkte zu haben, ich muss auch die Reihenfolge
der Punkte haben, um eben auch wirklich wissen zu können, was sind
hier die jeweils benachbarten Punkte meines Polygons.
Ja, das heißt, ich brauche diese sortierte Reihenfolge meiner Punkte,
aber sortiert nicht in Bezug auf die x-Koordinaten, sortiert in Bezug
auf das Rundlaufen rund um diese Menge.
Das heißt, es ist eine radiale Sortierung in Bezug auf irgendeinen
Punkt hier.
Im Prinzip muss ich diese Sortierung so der Reihe nach hier machen.
Welchen Schnitt?
Hier?
Das ist der Durchschnitt aller Mengen S, aller Teilmengen meines
solidischen Raumes, die die Menge m enthalten und konvex sind.
Es kann irgendwelche Mengen geben, es kann eine Riesenmenge haben, die
ist auch konvex.
Das ist die kleinste.
Der Durchschnitt aller Mengen, die die Menge m enthalten und konvex
sind.
Das ist genau diese Menge.
Die anderen liegen außen.
Das ist also die mathematische Definition, die es aber nichts bringt.
Algorithmisch bringt sie gar nichts.
Das ist aber die mathematische Definition.
Der Mathematiker ist zufrieden, das ist die konvexe Hülle.
Der Informatiker sagt, was habe ich davon?
Ich muss wissen, wie kann ich das algorithmisch, das Problem dann
angehen.
Und diese Tatsache, dass das der Durchschnitt aller größeren Mengen
ist, die m enthalten, hilft mir nicht viel.
Zumindest in diesem Augenblick sage ich, das hilft mir nichts.
Vielleicht gibt es andere Fragestellungen, wo uns das was hilft.
So, und hier ist dann doch animiert, dass das Polygon tatsächlich zu
sehen ist.
Also wenn ich das hier alles raus streiche, sehen Sie, jetzt habe ich
hier, ohne diesen vielen Annotationen, das konvexe Polygon nochmal
schön eingezeichnet.
So, und jetzt werde ich Ihnen ein paar Verfahren vorstellen, wie man
diese Menge der Extrempunkte bzw.
das konvexe Polygon außenrum bestimmen kann.
Da werden einfach unterschiedliche Ideen verwendet.
Ich versuche wieder Ihnen zu zeigen, wie kann man so ein Problem
lösen.
Da gibt es eine ganze Reihe unterschiedlicher Ansätze, die jeweils
natürlich unterschiedliche Eigenschaften haben.
Die erste Eigenschaft ist folgendes.
Wenn ich einen Punkt X habe, in einem Dreieck mit Eckpunkten P, Q und
R.
Also hier habe ich P, Q und R.
So, das ist unsere Menge.
P, Q, R und dieses X hier in der Mitte.
Wenn das X in so einem Dreieck drin liegt, von drei anderen Punkten,
ist es garantiert kein Extrempunkt.
Es kann natürlich sein, dass hier noch weitere Punkte außenrum liegen,
aber das X ist garantiert kein Extrempunkt.
P, Q, R vielleicht auch nicht, aber X ist garantiert kein Extrempunkt.
Das kann ich ausnutzen.
Ich stelle einfach fest, liegt ein Punkt im Inneren eines Dreiecks aus
drei anderen Punkten.
Und wenn ich einen Punkt habe, der in keinem Dreieck aus drei anderen
Punkten liegt, dann muss das ein Extrempunkt sein.
Also, ganz einfacher Ansatz.
Sie sehen, ich hatte das hier tatsächlich vorbereitet an der Stelle,
war mir gar nicht mehr bewusst.
Da ist also dieses schöne Bild, wo das nochmal zu sehen ist.
P, Q und R sind dort angegeben.
Das X liegt dort drin.
Und der Algorithmus ist also ganz einfach, der nur diese eine
Eigenschaft ausnutzt.
Ich habe eine ganz tolle Idee.
Oh, das sagt mir, welcher Punkt kein Extrempunkt ist.
Das kann ich ja feststellen.
Prüfe für jeden Punkt, ob er in einem Dreieck liegt.
Wenn ich die Eigenschaft habe, bin ich fertig.
Die Punkte, die nicht in einem Dreieck liegen, sind die Extrempunkte.
Die Frage ist nur, welchen Aufwand macht das?
Wie kann ich feststellen, ob ein Punkt in irgendeinem Dreieck liegt?
Dazu muss ich alle möglichen Dreiecke aus Punkten von M erstmal
bestimmen.
Und wenn ich das naiv mache, habe ich N hoch 3 Dreiecke zu betrachten.
Wenn ich also alle möglichen Teilmengen von drei Punkten aus meiner
Menge M betrachte, habe ich O von N hoch 3 solche Dreiecke zu
betrachten.
Die Entscheidung, ob der Punkt dann im Inneren oder im Äußeren seines
Dreiecks liegt, ist ja ganz einfach.
Das ist konstanter Aufwand.
Das wissen wir, wie man das macht.
Wir wissen, wie ich feststellen kann, liegt der Punkt im Inneren oder
im Äußeren eines Dreiecks.
Wir wissen, wann er im Inneren eines konvexen, einfachen Polygons
liegt oder nicht.
Das ist eine einfache Geschichte.
Hier muss ich nur überprüfen, mit konstantem Aufwand hier sogar, weil
ich ja nur drei Kanten habe, ob er drinnen liegt oder draußen liegt.
Also der Aufwand pro Punkt oder pro Dreieck ist konstant, aber ich
habe N hoch 3 Aufwand.
Und daraus bekomme ich dann meine Extrempunkte.
Dann muss ich die Kanten der konvexen Hülle von M einfach nur durch
die geeignete Anordnung meiner Extrempunkte finden.
Wenn ich also hier irgendwelche Extrempunkte habe, dann muss ich nur
noch irgendeinen Punkt im Inneren von M nehmen, also einen der Punkte,
der als innerer Punkt gekennzeichnet war, und muss dann einfach nur
hier diese radiale Sortierung meiner Punkte machen.
Diese radiale Sortierung der Punkte, dieser Linien, ich male einfach
die Verbindung.
Ich habe hier irgendeinen Punkt R im Inneren von M als Ursprung,
irgendeinen Punkt, der nicht Extrempunkt ist, und ich sortiere einfach
die Extrempunkte bezüglich ihres Winkels mit der x-Achse.
Das kann ich also so machen, dass ich sage, das ist hier ein Winkel,
das ist einer, das und so weiter.
Dann habe ich irgendeine radiale Sortierung meiner Punkte.
Der Aufwand ist natürlich nochmal Anzahl Extrempunkte mal Logarithmus
Anzahl Extrempunkte.
Dann bin ich das, also hier genau das Bild, das da steht.
Und dann ist der Aufwand O von N hoch 4, da oben war doch O von N hoch
3 pro Punkt.
Ich habe aber N Punkte, also mit dieser naiven Abschätzung Aufwand N
hoch 4 plus Aufwand H log H für H Anzahl der Extrempunkte macht
insgesamt Aufwand N hoch 4.
Sehr, sehr großer Aufwand.
Stellen Sie sich vor, Sie können das Ganze parallel machen.
Dann hätten Sie einen Schritt, um alle diese Überprüfungen zu machen
für jeden Punkt und für jedes Dreieck.
Sie brauchen halt viele, viele Prozessoren.
Wenn das möglich wäre, könnten Sie alle diese Entscheidungen,
abgesehen davon, dass ich auf gleiche Daten zugreifen müsste, dass ich
also Datenkonflikte haben könnte, aber wenn ich gleichzeitig lesen
kann, ist kein Problem.
Könnte ich hier mit N hoch 4 Prozessoren, könnte ich genau diesen
Aufwand, oder diesen Schritt A in einem Schritt machen und hätte dann
nur noch anschließend die radiale Sortierung zu machen.
Sortieren geht im Prinzip, wissen wir, in logarithmischer Zeit
parallel.
Dann hätte ich also beim parallelen Verfahren, hätte ich hier einen
Gesamtaufwand von Log N.
Oder logarithmisch in der Anzahl der Haltepunkte.
Das heißt, für einen parallelen Ansatz wäre das ideal, weil ich viele
unabhängige Operationen habe, aber die Effizienz wäre nicht sehr groß.
Wobei wir noch nicht wissen, wie die Effizienz tatsächlich zu
bestimmen ist, weil wir nicht wissen, wie ist das optimale
sequenzielle Verfahren im Augenblick.
Okay, das ist ein Ansatz.
Schauen wir uns das anders an, der sogenannte Graham-Scan.
Graham hat das im Jahr 72, also vor, mein Gott, fast 40 Jahren hat er
das gemacht.
Und der hat sich gesagt, ich mache das Ganze anders.
Ich sortiere meine Punkte nach ihren Polarkoordinaten.
Also, ich habe hier meine beliebig vielen Punkte.
Ich nehme mir irgendeinen Punkt hierher, im Inneren, und sortiere die
nach ihren Polarkoordinaten.
Sie können sich vorstellen, wenn Sie jetzt so eine Punktwolke haben
mit ganz vielen Punkten, dann tritt die Situation, die ich vorhin
sagte, die etwas Schwierigkeiten macht, wenn Punkte nah beieinander
liegen, festzustellen, welcher Punkt liegt jetzt eigentlich, liegen
jetzt hier zwei Punkte links oder rechts voneinander?
Welche Reihenfolge liegen die?
Das kann bei so einer Situation, wenn ich eine dichte Punktwolke habe,
und da diese ganzen Radialkoordinaten bestimmen möchte, äh, Quatsch,
die Polarkoordinaten, bezüglich irgendeines Punktes im Inneren, dann
kann ich hier Situationen haben, dass hier irgendwelche
Polarkoordinaten sehr eng beieinander liegen, und dann gibt es
Schwierigkeiten festzustellen, welcher Reihenfolge liegen die
eigentlich?
Kommt da eine vorher oder nachher?
Komme ich also damit wieder zurück auf das Problem von zu Anfang,
diese Annahme, die sind immer schön genügend weit voneinander
entfernt, dass es keine Schwierigkeiten gibt, diese Annahme machen wir
normalerweise, und dann funktioniert der Graham-Scan auch.
Wenn wir eine dichte Punktwolke haben, gibt es beim Graham-Scan
praktische Probleme, weil sich da eventuell in der Reihenfolge der
Punkte ändern.
Das sehen wir gleich, wo das Problem liegen könnte.
Ich mache also erstmal diese Sortierung, dann habe ich eine Sortierung
meiner Punkte in der Punktmenge.
Und dann führe ich diesen Graham-Scan aus.
Ich wähle einen sicheren Extrempunkt als Startpunkt.
Ein sicherer Extrempunkt ist einfach zu bestimmen.
Ich nehme zum Beispiel den untersten, linkesten Punkt.
In dem Fall habe ich nur einen untersten.
Wenn ich mehrere unterste hätte, die die gleiche y-Koordinate haben,
dann müsste ich da den linkesten davon nehmen.
Dann beginne ich bei dem Punkt, bzw.
später bin ich irgendwo am Punkt P, und bestimme den Winkel zwischen
drei aufeinander folgenden Punkten.
Was ist dieser Winkel?
Ich habe hier verschiedene Situationen.
P1, P2, P3.
Hier habe ich P1, P2, P3 in dieser Richtung, und hier habe ich P1, P2,
P3.
Das sind die verschiedenen Situationen.
Wenn ich eine Linksdrehung habe, ich gehe jetzt nicht im
Uhrzeigersinn, sondern gegen den Uhrzeigersinn, das heißt bei einem,
ich möchte eine konvexe Hülle haben, muss ich also, damit es konvex
bleibt, immer Linksdrehungen haben.
Wenn ich im Uhrzeigersinn laufe, hatte ich Ihnen vorhin erzählt, beim
konvexen, beim einfachen Polygon, das konvex sein soll, habe ich immer
Rechtsdrehungen.
Gegen den Uhrzeigersinn habe ich Linksdrehungen.
Also wenn es eine Linksdrehung ist, weiß ich, dieser Winkel ist
kleiner als 180 Grad.
Der innere Winkel hier, das heißt, das ist ein konvexer Winkel.
Ich kann weitermachen mit P2, P3 und irgendeinem P4 zum Beispiel.
Das heißt, ich mache hier weiter mit den nächsten drei Punkten.
Ich gehe davon aus, P1 und P2 sind Extrempunkte.
Weil ich einen konvexen Winkel festgestellt habe, im Augenblick sind
das Extrempunkte.
Davon kann ich ausgehen.
Also P1, P2, P3 nehme ich an.
P3 ist auch ein Extrempunkt.
Und dann kommt der nächste Punkt, P4, dazu.
Bei dem wird die gleiche Entscheidung nochmal gemacht.
Die andere Situation könnte sein, das sind kollineare Punkte.
Dann streiche ich P2 raus, den mittleren Punkt.
Den benenne ich nicht als Extrempunkt.
Sondern ich mache mit P1, P3, P4 weiter.
Also hier irgendein weiterer Punkt liegt.
Oder da meinetwegen, nehmen wir mal den Punkt an.
Das wäre der nächste Punkt.
Dann würde ich also anschließend mit der Situation weitermachen.
Also könnte sein, dass die genau in einer Linie liegen.
Dritte Situation wäre, ich habe keine Linksdrehung, das ist nicht
kollinear.
Sondern ich habe eine Rechtsdrehung.
Rechtsdrehung heißt bei gegen den Uhrzeigersinn durchlaufen.
Ich habe einen Konkarvenwinkel, der ist größer als 180°.
Und das heißt, der Punkt P2 kann kein Extrempunkt sein.
Weil nämlich die konvexe Verbindung zwischen P1 und P3 liegen würde.
So, dann vergesse ich also P2 und mache weiter mit P1, P3 und P4.
P1, P3 und irgendeinem P4.
Nächster Punkt.
Vielleicht ist es ja der da.
Falls das P1 gleich P ist, falls ich also gerade angefangen hatte.
Wenn ich aber nicht angefangen hatte, bei diesem Punkt.
Wenn ich also mittendrin war, also nehmen wir mal an, ich habe hier
diese andere Situation.
Ich habe jetzt hier festgestellt, ich muss P2 rausstreichen.
Jetzt könnte es ja sein, dass der Punkt P3 nicht dort liegt, sondern
der liegt irgendwo dort.
Wenn der hier liegen würde, dann hätte ich vorher P0, P1, P2
betrachtet.
Das war eine Linksdrehung.
Das heißt, ich nehme an, P0, P1 und P2 gehören zur konvexen Hülle.
Dann habe ich P1, P2, P3 betrachtet, festgestellt, P2 ist kein
Extrempunkt.
Beziehungsweise P0, P1, P3 sind in dem Fall dorthin.
Wenn ich jetzt weitermachen würde mit P1, P3 und dem nächsten Punkt,
dann würde ich denken, dieses P1 hier ist ein Extrempunkt.
Wenn ich mir das aber anschaue, dann stelle ich fest, P0, P1 sind die
Punkte auf der konvexen Hülle.
P1 ist kein Extrempunkt.
Das konnte ich aber vorher nicht feststellen, weil ich den Punkt noch
gar nicht gesehen hatte.
Das heißt, ich muss nochmal zurückgucken, ist dieser Winkel P0, P1,
P3, wenn das hier jetzt P3 ist, ist das eventuell ein konkaver Winkel?
Dann muss ich nämlich P1 streichen.
Und wenn das so ist, dann müsste ich wieder zurücklaufen und sehen,
was ist dann mit dem Winkel davor und so weiter.
Das heißt, hier hätte ich eventuell das nochmal zu überprüfen.
Das heißt, was ich im Prinzip mache, ist, ich gucke mir diese
Situation an, ich habe mir P1 und P2 bereits betrachtet, gehe jetzt zu
P3 und habe dann entweder eine Linksdrehung oder überhaupt keine
Drehung oder ich habe eine Rechtsdrehung.
Und das kann es sein, dass ich einen Punkt, den ich vorher aufgenommen
habe, als Kandidaten ein Extrempunkt zu sein, dass ich ihn wieder
streichen muss aus der Liste.
So, wie ist der Aufwand für dieses Verfahren?
Ich muss jeden Punkt, ich habe also für jeden Winkel diese
Entscheidung zu treffen, für jeden Punkt stelle ich fest, gehört der
dazu, zu der Menge der potenziellen Extrempunkte oder nicht.
Zunächst mal nehme ich ihn auf, wenn ich also einen Konvexenwinkel
gefunden habe.
Eventuell muss ich das später revidieren, wenn ich feststelle, da war
ein Konkaverwinkel auf einmal entstanden für einen Folgepunkt.
Und dann muss ich den eventuell nochmal rausnehmen.
Dann habe ich aber alle Punkte, die ich danach eingetragen habe, auch
schon rausgenommen.
Und ich mache dann von dem Punkt, bei dem ich jetzt gelandet war,
mache ich weiter.
Das heißt, ich habe also für jeden dieser Punkte einen konstanten
Aufwand.
Einmal eintragen, einmal eventuell wieder rausnehmen.
Und was ich machen musste war, ich musste erstmal die radiale
Sortierung machen.
Die radiale Sortierung ist Aufwand nlog n.
Der Aufwand für diese Überprüfung, für den Gram-Scan in der Folge der
sortierten Punkte, der ist linear, weil ich pro Punkt nur einen
konstanten Aufwand habe.
Und jetzt verlässt mich hier mein Stift.
Ich will aber jetzt das nicht mehr...
Ich male also jetzt nicht mehr weiter.
Das ist jetzt sehr unangenehm.
Jetzt muss ich das anders machen.
Ich will jetzt den Rechner nicht nochmal runterfahren und wieder
hochfahren.
Dann nehmen wir jetzt den Pfeil.
Ich habe also einen linearen Aufwand für den Punkt B.
Und der Platz insgesamt ist natürlich nur linear, weil ich nur diese
Punkte für meine Punktmenge abspeichern muss.
Damit habe ich also diesen anderen Ansatz.
Insgesamt Aufwand nlog n.
Vorher hatten wir einen Aufwand von n hoch 4.
Das ist schon eine schöne Verbesserung.
Aber hier habe ich ein streng sequenzielles Verfahren.
Das kann ich auch durch Parallelisierung nicht wirklich verbessern.
Ich muss sequenziell durch meine ganzen Winkel durchlaufen.
Das heißt, da habe ich ein inherent sequenzielles Verfahren.
Auch parallel bleibt das hier bei Aufwand n.
Das heißt, wenn ich zumindest genau diesen Gram-Scan nehme, der ist
inherent sequenziell.
Was ich parallelisieren könnte, wäre das Sortieren der Punkte.
Aber den linearen Anteil, den kann ich hier nicht reduzieren durch
Parallelverarbeitung.
Das, was ich hier halt mache, ist...
Das war die Eigenschaft, die wir ausgenutzt haben.
Ich kann nicht mehr malen, das ist dumm.
Oder ich könnte es vielleicht noch mit dieser...
Genau, dann könnte ich das noch machen.
Aber dann sehe ich nicht mehr, wo ich gerade bin.
Genau, ich bin jetzt da oben.
Also, das ist die Eigenschaft 2.
Ich lasse es mit dem Malen, das bringt jetzt nichts.
Ich gehe hier nur mit dem Pfeil über die Sachen rüber.
Also, alle inneren Winkel zwischen aufeinanderfolgenden Kanten eines
konvexen Polygons sind natürlich konvex.
Also kleiner als 180 Grad, das ist klar.
Das haben wir ausgenutzt.
Und damit haben wir diesen Gram-Scan gemacht.
Aufwand n log n für das Verfahren.
Das nächste ist, ich suche nicht nach Extrempunkten.
Sondern ich suche nach den Kanten der konvexen Hülle.
Wieder ein anderer Ansatz.
Ich zeige Ihnen diese verschiedenen Sachen einfach umzustellen.
Es gibt halt unterschiedliche Ideen, wie man sowas machen kann.
Das ist das Verfahren von Jarvis, genannt Jarvis-March.
Also der Marsch von Jarvis um diese Menge von Punkten herum.
Und der geht folgendermaßen vor.
Der wählt wieder so einen untersten linkesten Punkt.
Nehmen wir mal an, dass der, oder wir können auch gleich zu dem hier
gehen.
Oder zumindest, wenn das dieser hier wäre, da unten links.
Dann wäre der erste klar.
Was mache ich?
Ich suche den nächsten Punkt, zu dem aktuellen Punkt.
Den Punkt Q aus M.
Sodass der Winkel mit der X-Achse minimal ist.
Naja, das wäre sofort dieser Punkt dort.
Das wäre der nächste.
Der wäre nämlich 0, der Winkel mit der X-Achse.
Dann wäre ich bei dem Punkt gelandet.
Dann würde ich jetzt von dem Punkt aus in meiner Punktwolke alle
Punkte durchgucken.
Und den Punkt suchen, der am weitesten rechts liegt.
Der hat nämlich den kleinsten Winkel mit der X-Achse.
Dann gehe ich zum nächsten, zu dem Punkt, den ich gefunden habe.
Mache das gleiche wieder.
Suche alle Punkte durch.
Suche den, der am weitesten rechts liegt.
Der, der am weitesten rechts liegt.
Naja, das ist immer nur eine Maximumsbestimmung.
Geht jeweils mit linearem Aufwand.
Und so weiter.
Dann gehe ich also diese Punkte hier durch.
Und ich habe pro Extrempunkt O von N vergleiche.
Ich muss ja immer den mit der maximalen X-Koordinate raussuchen.
Und so habe ich also die Folge der Extrempunkte.
Ich habe also für jeden Extrempunkt, nur die muss ich betrachten,
jeweils einen Aufwand von N.
Wenn ich nur konstant viele Extrempunkte habe, habe ich insgesamt
linearen Aufwand.
Ja, es könnte ja sein, dass ich eine ganz einfache Punktmenge habe.
Mit einer konstanten Anzahl von Extrempunkten.
Dann hätte ich hier eine konstante Anzahl von Extrempunkten.
Pro Extrempunkt linearen Aufwand.
Also ganz einfach zu bestimmen.
Ich hätte einen Aufwand, der zwischen linear und im schlechtesten Fall
natürlich N² liegt.
Wenn also alle Extrempunkte sind, dann hätte ich hier einen Aufwand
von N².
Das ist Charles March.
Also nicht immer den gleichen Aufwand wie beim Gram-Scan, sondern
variabel zwischen linear und quadratisch.
Nächstes Verfahren.
Die beiden Conker.
Auch ein klassischer Ansatz.
Vielleicht nur ganz kurz.
Ich teile hier meine Menge auf in zwei Teilmengen, bestimme für die
beiden Teilmengen die konvexen Höhlen und muss dann die konvexen
Höhlen zusammenbauen.
Und das Zusammenbauen muss einen Aufwand produzieren, der linear ist.
Wenn ich auf die Uhr gucke, gehe ich darüber jetzt etwas schneller
rüber.
Hier ist aufgeschrieben, wie man das macht, wie man die beiden
konvexen Höhlen einfach kombiniert mit linearem Aufwand.
Und das, was ich Ihnen nämlich noch zeigen wollte, ist ein ganz
anderes Prinzip.
Das sogenannte Wegwerfsprinzip kennen Sie auch noch nicht.
Das ist das letzte Prinzip, das ich Ihnen präsentieren wollte.
Sie gehen ganz anders vor, heuristisch, und sagen, meine Punktmenge
ist hier irgend so eine Menge.
Und jetzt bestimme ich einige Extrempunkte.
Einige Extrempunkte bestimmen zum Beispiel, ich könnte nur die vier im
Norden, Osten, Süden, Westen bestimmen.
Ich nehme jetzt auch noch jeweils die Zwischenpunkte hinzu, Nordosten,
Südosten, Südwesten und Nordwesten.
Dann habe ich acht Extrempunkte.
Die kann ich jeweils mit linearem Aufwand bestimmen.
Extrempunkte bestimmen ist keine Schwierigkeit, das geht mit einfach
Maximumsbestimmung in den jeweiligen Richtungen.
Das ist also lineare Aufwand, das steht hier.
Und dann mache ich Punkt B, und das ist jetzt das Wegwerfen.
Ich nehme einfach das Polygon aus diesen acht Punkten mir her und
werfe alle Punkte im Inneren dieses Polygons weg.
Ich weiß ja, das sind garantiert keine Extrempunkte.
Extrempunkte können nur irgendwo noch außen liegen, zwischen diesen
Punkten, die ich jetzt herausgefunden habe.
Und wenn ich mal davon ausgehe, dass die Punkte so einigermaßen
gleichmäßig verteilt sind im Raum, dann sind ja nur ganz wenige
irgendwo hier noch außerhalb liegen, die jetzt gerade nicht einer
dieser acht Extrempunkte waren.
Und jetzt bestimme ich einfach die konvexe Hülle der Restmenge mit
einem Standardverfahren, zum Beispiel mit dem Gram-Scan.
Ja, das sind nur ganz wenige Punkte, die übrig bleiben, da kann ich
die konvexe Hülle bestimmen.
Und da das nur r restliche Punkte sind, sehr wenige, ist das ein
Aufwand von r log r in der Anzahl der restlichen Punkte.
Im schlechtesten Fall ist das natürlich ein Aufwand von n log n.
Wenn n Punkte in der Restmenge sind.
Wenn ich Glück habe, sind es nur konstant viele, dann habe ich hier
mit jenem Aufwand meine konvexe Hülle bestimmt und ich bin fertig.
Das heißt, das ist ein Prinzip, da treffe ich einfach erstmal so eine
über den Daumen abschätzende Entscheidung.
Ich lege da so ein ganz grobes Ding rüber, eine Abschätzung für die
konvexe Hülle, kann, wenn ich Glück habe, ganz viel wegwerfen und
mache mit dem Rest weiter.
Eigentlich kennen Sie so etwas.
Das war die Idee bei QuickSort, QuickSelect.
Da macht man auch eine Abschätzung bei QuickSelect.
Ich wähle irgendeinen Punkt und hoffe, dass dann nicht so viele übrig
bleiben, wo ich noch weitersuchen muss.
Hier wählen wir auch so eine Art Partitionierung, also eigentlich der
ganz ähnliche Ansatz wie QuickSelect oder QuickSort.
Ich wähle eine Partitionierung meiner Menge in die, die ich garantiert
wegwerfen kann und die, wo ich weitermachen muss.
Und ich hoffe, dass die, wo ich weitermachen muss, klein ist.
Und jetzt kommt noch ganz kurz eine untere Schranke.
Wenn Sie Pech, wenn Sie also sagen, was muss ich mindestens an Aufwand
reinstecken, um im schlechtesten Fall die konvexe Hülle zu
konstruieren, also schlechtesten Fall für die konvexe Hülle.
Wenn ich Pech habe, sieht meine Menge so aus, wie das hier angegeben
ist.
Wenn ich hier die konvexe Hülle bestimmen möchte und die Menge ist mir
irgendwie gegeben, was ich hier bestimmen muss, ist eigentlich nur die
sortierte Reihenfolge der Punkte bezüglich ihrer x-Koordinaten.
Das heißt, wenn ich also irgendeine Punktmenge habe und diese
Punktmenge sieht so aus, naja, ich kann auch einfach eine Folge von x
-Koordinaten haben, möchte die sortieren, dann mache ich daraus
einfach eine solche Punktmenge, bilde die konvexe Hülle und ich habe
sortiert, weil ich dann das konvexe Polygon habe.
Und das heißt, der Aufwand, um die konvexe Hülle zu bestimmen, ist im
schlechtesten Fall leider nicht kleiner als der Aufwand, um zu
sortieren.
Und da brauchen wir im schlechtesten Fall ein Log N, deswegen brauchen
wir das hier auch.
Und damit sind wir also damit durch mit algorithmischer Geometrie.
Ich bin mit dem Kapitel durch und hätte jetzt nur noch, wenn Sie den
kleinen Augenblick noch mir geben, abschließende Bemerkungen zu dieser
Vorlesung.
Was habe ich Ihnen präsentiert in dieser Vorlesung?
Eine ganze Reihe von Prinzipien, wie man Algorithmen systematisch
entwirft.
Und es ist klar, dass wir Algorithmen überall brauchen.
Wir müssen sehen, dass wir einigermaßen effizient mit unseren
Rechenressourcen umgehen.
Effizient unter verschiedenen Gesichtspunkten, Rechenzeit, Platz oder
auch Energie.
Auf Energieeffizienz sind wir gar nicht darauf eingegangen.
Das kann man auch noch mit berücksichtigen.
Es lohnt sich auf jeden Fall, nach effizienten Lösungen zu suchen.
Und das, was ich Ihnen eigentlich präsentieren wollte, war, dass Sie
festmerken, man muss dabei einerseits das richtige Berechnungsmodell
suchen, sequentiell, parallel oder Hardware oder was immer.
Ich brauche geeignete Datenstrukturen, ich brauche natürlich geeignete
Rechnerstrukturen.
Also das bedingt sich alles und es kann sein, dass eine algorithmische
Idee, die ich für einen sequentiellen Rechner gemacht habe, die dort
vielleicht gar nicht so gut war, auf einmal im parallelen Rechner sich
was ganz Tolles erweist.
Das habe ich in mehreren Beispielen gezeigt.
Und ich kann manchmal eben auch Dinge sehr, sehr systematisch
entwickeln.
Dieser Mappingansatz zum Beispiel, da haben wir im Prinzip ein
mathematisches Verfahren genommen und daraus Algorithmen produziert.
Also das waren unsere verschiedenen Themen, die wir behandelt haben.
Die werden im Prinzip alle jetzt natürlich Kandidaten sein, um auch in
einer Klausur abgefragt zu werden.
Aber ist klar, das was ich Ihnen heute präsentiert habe, ist natürlich
in Einzelheiten nicht mehr Klausurrelevant.
Normalerweise kommen die Sachen, die ich in der letzten
Vorlesungsstunde mache, nicht mehr in der Klausur dran.
Ich kann also jedenfalls nicht erwarten, dass Sie dort sehr viele
Einzelheiten dieser Verfahren dann schon alle sich erarbeitet haben.
Sie haben auch keine Gelegenheit gehabt, das in Übungen nochmal zu
vertiefen.
Was ich Ihnen präsentieren wollte, waren natürlich die Probleme, aber
vor allen Dingen die Prinzipien.
Da habe ich Ihnen eine ganze Reihe genannt.
Und wenn wir uns jetzt angucken, was kann man bei mir ansonsten noch
machen.
Es gibt andere Vorlesungen, die Sie sich angucken können, wenn Sie
Interesse haben.
Organic Computing lief parallel zu dieser Vorlesung, also im gleichen
Semester.
Die AIA-Vorlesung waren vielleicht einige von Ihnen schon.
Naturspirit-Optimierungsverfahren, noch eine weitere Veranstaltung von
meiner Gruppe, von Frau Mostagim und Herrn Schukler.
Computational Economics war im letzten Winter eine Vorlesung nur im
Bereich BWL.
War ursprünglich mal eine Vorlesung, die in Kombination von
Lehrstühlen Weinhardt und meinem Lehrstuhl gemacht wurde, von Herrn
Branke und Herrn Veith ursprünglich.
Jetzt im Wintersemester wird die gemeinsam von Herrn Schukler und
einem Mitarbeiter von Herrn Weinhardt gemacht.
Also wieder sowohl anrechenbar für Informatik als auch für BWL.
Und das ist insofern ein Sonderfall, den wir sonst nie haben.
Also eine Reihe von Vorlesungen und Seminare, Seminar-Praktika.
Schauen Sie sich an, was zurzeit angeboten wird bei uns.
Systemsimulation ist das Thema im Wintersemester bei mir im Seminar.
Und bei Praktika haben wir etwas zu Service-orientierten Architekturen
bzw.
zu Services für Studierende.
Und zu Swarm Robotics, das sind die beiden Praktika, die wir anbieten.
Und was noch, Diplomarbeiten sind in vielen Bereichen möglich bei uns.
Natürlich nicht nur Diplomarbeiten, Bachelor, für Sie sind nur noch
Bachelorarbeiten interessant, nicht mehr Diplomarbeiten.
Abschlussarbeiten zu einer Reihe von Themen oder auch Masterarbeiten.
Und schauen Sie sich an auf unseren Seiten, was da alles gerade
aktuell ist.
Kommen Sie zu meinen Mitarbeitern oder zu mir und dann betreuen wir
Sie gerne bei Ihren Abschlussarbeiten.
Und das ist der Abschluss der Vorlesung.
Ich hoffe, dass es Ihnen Spaß gemacht hat und hoffe, Sie auch mal
wieder irgendwo zu sehen.
Und wünsche Ihnen viel Erfolg für die Klausur jetzt in Effiziente
Algorithmen und natürlich auch sonst.
Also vielen Dank und das war's.