Und jetzt kommen wir zum vierten Problem.
Konvexe Hüllen bestimmen.
Wir hatten ja gesehen, wir hatten einfache Polygone betrachtet.
Da konnten wir bestimmen, ob ein Punkt innen oder außen liegt.
Das war aber linearer Aufwand.
Wir hatten gesagt, wie kann man bestimmen, ob ein Polygon einfach ist.
Haben wir gerade eben gelöst.
Dann hatten wir das andere Problem gehabt, wenn wir ein konvexes
Polygon haben, konnten wir einige Aufgaben noch einfacher lösen.
So war die Frage, woher weiß ich denn, ob ein Polygon konvex ist.
Also wir haben hier irgendeinen Polygon, dass das hier konvex ist, das
merken Sie sofort, wenn Sie einmal rumlaufen, weil Sie hier jeweils
Rechtsdrehungen haben, wenn Sie hier rumlaufen.
Also wenn Sie durch das Polygon durchlaufen, das wäre also eine
einfache Überlegung, zu bestimmen, ob ein Polygon, wir haben ein
einfaches Polygon, Sie wollen wissen, ob das konvex ist, dann brauchen
Sie nur einmal durchzulaufen.
Jetzt gebe ich Ihnen ein beliebiges Polygon,
ich sage also nicht, dass es einfach ist, und Sie sollen überprüfen,
ob das konvex ist.
Wenn es konvex ist, ist es natürlich auch einfach, das ist ja klar.
Ja, das muss ja so sein.
Immer nur Rechtsdrehungen, das ist ja offensichtlich, dass das
funktioniert.
Dann male ich Ihnen ein kleines anderes Polygon daneben.
Wenn Sie da rumlaufen, haben Sie auch nur Rechtsdrehungen.
Das ist aber sicherlich nicht konvex, weil es nicht einfach ist.
Und es zeigt sich bei geometrischen Problemen, bei geometrischen
Objekten, dass man manchmal auf den Bauch fällt, weil man gewisse
Vorstellungen hat, was passieren kann, und gewisse entartete Objekte,
die entdeckt man gar nicht so ohne weiteres in seiner Vorstellung.
Das ist zunächst einleuchtend, also dieses Überprüfen, ob so ein
Polygon konvex ist, naja, über Rechtsdrehungen.
Aber da muss man zunächst mal überprüfen, ob es einfach ist.
Also, ein bisschen mehr Aufwand zu machen.
Das Problem, das ich ja angesprochen habe, war eigentlich ein ganz
anderes.
Nämlich, ich habe eine Menge von Punkten im E2, und ich will die
konvexe Hülle bestimmen.
Also, eigentlich habe ich hier irgendeine Menge von Punkten, und ich
will die konvexe Hülle bestimmen, also gerade die Extrempunkte
bestimmen, deren Verbindung gerade die konvexe Hülle angibt.
Also, ich möchte ein umschließendes Polygon ermitteln, das konvex ist.
Die kleinste konvexe Teilmenge im E2, die die Menge M enthält.
Ich könnte auch sagen, ich nehme alle konvexen Mengen her, die die
Menge M enthalten, und nehme deren Durchschnitt.
Mathematische Beschreibungen.
Oder, ich betrachte ein konvexes Polygon, das den Rand der konvexen
Hülle bildet.
Also, die konvexe Hülle ist ja die kleinste konvexe Teilmenge von E2,
das ist also der ganze Bereich hier.
Das konvexe Polygon ist nur der Rand dieser konvexen Hülle.
Meistens reicht es mir, diesen Rand zu bestimmen.
Dafür reicht es in der Regel, einfach die Folge der Extrempunkte zu
kennen.
Was sind die Punkte der konvexen Hülle, also dieses konvexen Polygons,
das den Rand der konvexen Hülle bildet.
Und das ist das Problem, das wir uns jetzt angucken.
Ich habe mir irgendeine Menge von Punkten gegeben, und ich muss
feststellen, wie ich diese Extrempunkte bestimmen kann.
Beliebige Punkte, wir sehen sofort, wo die Extrempunkte sind.
Also, man kann ja mal anfangen, man stellt fest, naja, das ist
sicherlich einer, da ist noch so einer.
Die haben wahrscheinlich fast den gleichen, fast gleiche Y-Koordinate.
Das ist sicherlich auch einer, das ist auch einer, das ist auch einer,
das ist auch einer.
Also die sieht man natürlich, das sind natürlich Extrempunkte.
Das sehen wir.
Aber wie stellt ihr das im Rechner fest?
Da ist jetzt irgendeine Menge von Punkten irgendwie gegeben als Liste,
und ich möchte wissen, welche sind die Extrempunkte.
Man könnte sagen, naja, schaut mir doch an, das mit dem Dominieren,
das war doch eine Möglichkeit.
Wenn ich weiß, also ein Punkt wird von keinem anderen dominiert, ist
es natürlich so, das kann ich einmal in der Richtung machen.
Ich muss aber, damit ich feststelle, dass das hier ein Extrempunkt
ist, muss ich das in der Richtung machen.
Damit ich feststelle, dass das hier ein Extrempunkt ist, muss ich das
in der Richtung machen.
Damit ich feststelle, dass das ein Extrempunkt ist, muss ich das in
der Richtung machen.
Im Prinzip müsste ich hier vierfach solche Dominanzprobleme lösen.
Kann man so machen.
So kann man feststellen, was die Extrempunkte sind.
Es geht aber auch anders.
Also die konvexe Hülle liegt halt hier außen drum, und es gibt eine
Vielfalt von Verfahren, um konvexe Hüllen zu bestimmen.
Und da nutzt man Eigenschaften konvexer Hüllen aus, und zwar jeweils
sehr unterschiedliche Eigenschaften.
Und ich werde Ihnen einfach ein paar dieser Verfahren jetzt
vorstellen, dann sehen Sie, was man da alles machen kann.
Also, der erste Ansatz.
Was steht hier?
Wenn ein Punkt X in einem Dreieck mit Eckpunkten P, Q, R aus M liegt.
Also wir nehmen an, dass P, Q, R und X alles Elemente der Menge sind.
Und das X ist also ungleich P, Q und R.
Dann ist X sicherlich kein Extrempunkt.
Ich denke, da stimmen Sie zu.
Weil es innerhalb so eines Dreiecks liegt, kann das X kein Extrempunkt
sein, P, Q und R könnten Extrempunkte sein.
Es sei denn, sie liegen selber wieder innerhalb eines Dreiecks.
Daraus ergibt sich sofort ein Verfahren, wie ich feststellen kann, was
ein Extrempunkt ist.
Ein Extrempunkt ist ein Extrempunkt, wenn er nicht im Inneren
irgendeines Dreiecks aus beliebigen Punkten der Menge M liegt.
Also muss ich beliebige Dreiecke aus jeweils drei Punkten meiner Menge
M betrachten.
Also, für jeden Punkt alle möglichen Dreiecke anschauen.
Aufwand N³.
Und dann muss ich die Extrempunkte noch entsprechend anordnen.
Ich muss also wissen, wie die angeordnet sind.
Ich habe die Punkte gefunden.
Ich weiß, die liegen am Rand eines konvexen Polygons.
Dann muss ich die nur zu einem Punkt im Inneren bestimmen und dann
kann ich sie radial anordnen.
Das ist also möglich.
Das kann ich mit Sortieren machen.
Dann habe ich hier insgesamt, hier ist es angegeben, so ordne ich die
jetzt der Reihe nach.
Ich bestimme jeweils den Winkel zu irgendeinem inneren Punkt und habe
damit den gesamten Aufwand von naja, N³ für den ersten Schritt.
Ich habe ja N³, warum N³?
N³ pro Punkt.
Das ist ein Aufwand von N³ insgesamt.
Und, also im schlechtesten Fall natürlich nur, wenn es schon für das
erste ist, sobald ich feststelle, dass ein Punkt innerhalb eines
Dreiecks liegt, ist es kein Extrempunkt, ich kann aufhören.
Und dann muss ich natürlich für die Menge der Extrempunkte noch diesen
Sortiervorgang machen, dass es dann, wenn ich h solche Extrempunkte
habe, ist das h log h nochmal als Aufwand.
Und der Platz ist natürlich O von N für meine Punkte.
Wenn Sie jetzt, wenn also Ihre Punktmenge wirklich sehr dicht
beieinander liegt, dann kann es eben sein, dass Sie hier irgendwelche
Punkte haben und Sie wollen, das sind beides Extrempunkte, sonst
müssen Sie feststellen, welcher Reihenfolge die liegen.
Ich verweise da immer wieder drauf, das Problem, wenn Sie hier ein
bisschen entartete Verhältnisse haben, die Punkte liegen sehr eng
zusammen, dann kann es sein, dass man sich vertut.
Dass man die falsche Reihenfolge wählt.
Und auf einmal haben Sie, wenn Sie es dann vergrößert anschauen, eine
Situation, dass Sie aus Versehen hier haben Sie einen Punkt, da haben
Sie einen Punkt, da haben Sie einen Punkt, Sie haben sich vertan mit
der Reihenfolge der Punkte und Sie verbinden jetzt erst die beiden,
dann den und dann den nächsten.
Sie hätten kein konvexes Polygon mehr.
Es kann nicht sein, dass das alles drei Extrempunkte sind, aber ich
hätte es jetzt ein bisschen anders malen müssen.
Auf jeden Fall ist es so, dass Sie, lassen Sie mich das richtig malen.
Was kann passieren?
Sie haben zwei Punkte, die sind sehr eng nebeneinander und Sie haben
hier noch irgendeinen weiteren Punkt.
Das sind alles drei Extrempunkte.
Jetzt vertun Sie sich durch die Ungenauigkeiten der Rechnungen bei
diesen beiden hier bezüglich Ihrer Lage.
Aufgrund von Rechenungenauigkeiten, was passieren kann, wenn Sie mit
reellen Zahlen rechnen.
Dann kann es eben passieren, wenn jetzt der nächste Punkt vielleicht
da liegt, dass Sie tatsächlich so etwas malen.
So und so.
Hätten Sie das auf einmal als konvexes Polygon bestimmt, es ist aber
keins.
Sie haben hier ein nicht einfaches Polygon konstruiert.
Das darf natürlich nicht passieren.
Das heißt, da muss man aufpassen.
Bei realen Problemen kann es aufpassen, da muss man auf solche
Situationen achten.
Wenn man davon ausgeht, dass solche Situationen nicht auftauchen, dass
die weit genug voneinander weg sind, kann man diese Entscheidungen
alle eindeutig treffen, welcher Punkt vor einem anderen kommt
bezüglich dieser Radialsortierung.
Und dann hat man also hiermit ein Verfahren, das aber natürlich von
Zeitaufwand her wahnsinnig schlecht ist.
Man könnte es sicherlich parallelisieren, auf einfache Art und Weise,
indem man alle diese Anfragen gleichzeitig macht.
Also für jeden Punkt und für jedes Rechteck kann ich ja alles parallel
überprüfen.
Ich kann für jeden Punkt und für jedes Rechteck diese Prüfung parallel
machen.
Und hätte dann bei einem genügend hohen Parallelitätsgrad, der
natürlich immens ist in dem Fall, hätte ich halt in konstanter Zeit
diese Anfrage gelöst und müsste dann nur noch den Aufwand für
Sortieren dazu machen.
Parallel sortieren, wissen wir, können wir einen Aufwand in Zeitlog N.
Also hätten wir dann insgesamt in Zeitlog N unser Problem gelöst, die
konvexe Hülle zu bestimmen und auch das konvexe Polygon zu bestimmen,
das diese Hülle tatsächlich dann umschließt.
Also man kann es auch parallelisieren, sehr naiv in dem Fall, mit sehr
hohem Parallelitätsgrad, aber ich würde die Zeit durchaus
runterkriegen.
Zweiter Algorithmus.
Das ist also ein Verfahren von Graham, 1972 entwickelt worden, geht
von folgendem aus.
Ich habe meine Punktmenge, irgendwelche Punkte, also diese Linien
sollen jeweils Punkte andeuten.
Jetzt nehme ich mir irgendeinen Punkt hier, zum Beispiel hier dieses
X, oder ich nenne es nicht X, sondern Z.
Dieser Punkt Z nehme ich mir irgendeinen her und berechne einfach
Polarkoordinaten.
Also berechne, ich habe hier irgendeinen Punkt genommen und berechne
einfach jetzt die Polarkoordinaten dieser Punkte.
Das heißt, ich hätte dann hier eine ganze Reihe von solchen
Polarkoordinaten zu berechnen.
Sie können sich vorstellen, hier habe ich natürlich wahnsinnig viele
dieser Punkte, die ganz eng beieinander liegen.
Das Problem, das ich gerade eben angedeutet hatte, tritt hier extrem
auf.
Und jetzt habe ich durch diese Bestimmung der Polarkoordinaten einfach
die Möglichkeit, die zu sortieren.
Und dann habe ich eine Reihenfolge für die Punkte festgelegt bezüglich
dieser Radialsortierung und kann jetzt systematisch die Punkte
abarbeiten.
Ich gehe einfach jetzt von links nach rechts, also nicht von links
nach rechts, sondern von unten anfangend sukzessive hier rum, um
diesen beliebig gewählten inneren Punkt, bezüglich dessen ich alle
Punkte radial sortiert habe, wähle also einen sicheren Extrempunkt P
als Startpunkt, da kann ich also den linkesten untersten zum Beispiel
wählen.
Ich nehme also irgendeinen Punkt her und dann gehe ich der Reihe nach
zu den weiteren Punkten.
Und da können folgende Situationen auftreten.
Ich habe also einen Punkt P1, bei dem ich jetzt gerade gelandet bin,
danach kommt ein weiterer Punkt, P2, und ich gucke mir noch den
nächsten Punkt an, P3.
Die nächsten zwei Punkte.
Und ich kann jetzt den Winkel bestimmen zwischen diesen drei Punkten.
Ist das eine Linksdrehung, P1, P2, P3, oder eine Rechtsdrehung?
Wie wir das bestimmen können, wissen wir.
Linksdrehung oder Rechtsdrehung ist eine einfache
Dreiecksflächenberechnung.
Dreiecksflächenberechnung geht über unsere Determinante.
Können wir einfach feststellen.
Also, wenn das eine Linksdrehung ist, ist das Ganze ein... wir hatten
ja einen untersten Punkt gewählt, ist also alles das, was hier auf
dieser Seite ist, ist im Inneren dieser konvexen Hülle.
Wenn das eine Linksdrehung ist, ist der Winkel also konvex.
Das heißt, wir können jetzt den nächsten Punkt dazunehmen.
Wir wissen jetzt, P1, P2, P3 könnten Extrempunkte sein.
Jetzt kann es sein, dass wir eine andere Situation haben.
P1, P2 und P3, wie das hier angegeben ist, liegen auf einer Geraden.
Wenn das der Fall ist, dann streiche ich P2 raus und mache mit P1 und
P3 weiter.
Also im oberen Fall mache ich mit P2 und P3 weiter und nehme den
nächsten Punkt dazu.
Dann kann es natürlich passieren, dass ich eine Situation habe, wie
hier unten angedeutet.
Ich hatte, also ich betrachte immer jetzt P1, P2, P3 als die
Situation, die gerade zu beurteilen ist.
Und nun könnte es natürlich sein, wie hier angedeutet, wir haben keine
Linksdrehung, sondern eine Rechtsdrehung.
Wenn es eine Rechtsdrehung ist, dann ist es bezüglich des inneren
Bereichs hier ein nicht-konkaber Bereich.
Das heißt, der Punkt P2 ist sicherlich kein Extrempunkt, weil ja
eigentlich diese beiden, P1 und P3, verbunden sein müssten.
Das heißt, ich vergesse den Punkt P2.
Dann habe ich einen neuen Punkt dazu genommen.
Jetzt muss ich gucken, je nachdem, wo dieser Punkt P3 liegt, kann es
sein, dass ich etwas anderes noch korrigieren muss.
Also hier muss ich nichts korrigieren und das kann ich überprüfen,
indem ich einfach den davor liegenden Punkt noch anschaue.
Der Punkt P0, der also noch davor lag, da muss ich mir jetzt mal
angucken, sind P0, P1, P3 eine Linksdrehung oder eine Rechtsdrehung?
Wenn das eine Rechtsdrehung ist, müsste ich auch P1 vergessen, also
ausstreichen und wieder den Punkt davor mir dazunehmen.
Das heißt, ich bewege mich also entweder nach oben, also in dieser
Richtung, wenn es eine Linksdrehung war.
Wenn ich eine Rechtsdrehung hatte, muss ich mich mal stückweise nach
hinten bewegen nochmal und eventuell etwas überprüfen, weil Punkte,
die ich bisher als einen möglichen Extrempunkt angesehen habe, durch
die neue Kante, die jetzt dazugekommen ist, eventuell zu einer
Rechtsdrehung kamen und dieser P1 auch wegfallen muss.
Ich muss aber sicherlich jeden Punkt maximal einmal aufnehmen und
maximal einmal rauswerfen.
Ich muss ihn eventuell mehrfach überprüfen, aber das mache ich immer
nur, wenn ich einen neuen Punkt reinnehme.
Also bei jedem Punkt kann ich die Entscheidung treffen und Punkte, die
ich vorher aufgenommen habe, werde ich eventuell nochmal rausnehmen
müssen.
Aber es ist kein sehr großer Aufwand.
Das heißt, ich muss hier einmal durchlaufen durch meine Folge der
Punkte.
Ich musste sie erstmal sortieren.
Das war der Aufwand nlog n für Sortieren.
Und für diese Entscheidungen habe ich jeweils lokal konstanten Aufwand
bzw.
für die n Punkte dann insgesamt linearen Aufwand.
Und damit bin ich also jetzt von einem Aufwand von n hoch 4 runter auf
Aufwand nlog n.
Also es geht deutlich besser, das war auch zu erwarten.
Das hier können Sie aber nicht mehr parallel so einfach machen.
Diese Entscheidung, ob ein Punkt Extrempunkt ist oder nicht, hängt in
diesem Fall ja davon ab, in welcher Reihenfolge Sie durchlaufen durch
die Punkte.
Weil Sie hier feststellen müssen, ob das hier jeweils eine
Rechtsdrehung war oder wie hier eine Linksdrehung.
Das sind die beiden Dinge, die ich unterscheiden muss.
Und das heißt, das hängt davon ab, in welcher Reihenfolge ich durch
die Punkte durchlaufe.
Da muss ich dann noch von vorne weiterlaufen oder nach hinten wieder
gehen.
Das heißt, diese Liste der potenziellen Extrempunkte wird dynamisch
verwaltet.
Das ist ein strikt sequenzieller Prozess.
Den kann ich nicht so einfach parallelisieren.
Man kann durchaus hier auch noch parallele Sachen machen, aber ein
bisschen anders.
Und das ist also jetzt das zweite Verfahren.
Ich werde Ihnen noch ein paar weitere vorstellen.
Auch hier gilt, dass, wie bei dem anderen Verfahren, hatte ich schon
gesagt, gerade wenn man hier viele Punkte hat, die hier oben
angedeutet, dann ist natürlich extrem wichtig, in welcher Reihenfolge
ich jeweils diese Punkte betrachte.
Und wenn ich da durch sehr eng nebeneinander liegende Punkte bezüglich
dieser Radialsortierung Probleme habe, komme ich auf ein ganz
schlechtes Verfahren, weil nämlich das Ergebnis falsch ist.
Und ich erwähne das einfach immer wieder, weil genau diese Probleme
auftauchen, wenn Sie konvexe Höhlenalgorithmen implementieren, werden
Sie bei praktischen Problemen feststellen, dass solche Schwierigkeiten
da sind.
Und da muss man dafür sorgen, dass man trotzdem noch effizient
arbeiten kann.
Also der Grahamscan ist 1972 entwickelt worden.
Jetzt gerade vor ein paar Wochen hat der Kurt Nehlhorn hier bei uns in
der Glockführungsreihe berichtet, dass er sich genau mit dem Problem
beschäftigt, wie man durch geeignete Modifikation der Problemstellung
solche Fehler durch Ungenauigkeiten bei Gleitpunktberechnungen
ausmerzen kann.
Sehr interessantes Problem.
Wie gesagt, nächstes Mal machen wir dann noch ein paar andere
Verfahren, um konvexe Höhlen zu bestimmen.
Man sieht daran eben auch so ein paar prinzipielle Vorgehensweisen.
Ich werde Ihnen dann auch noch eine untere Schranke für konvexe Höhlen
vorstellen und dann sind wir auch schon am Ende angekommen.
Ich habe einiges dazu bereits erzählt.
Wir hatten diese verschiedenen geometrischen Objekte ja zunächst
betrachtet.
Mit Punkten haben wir uns beschäftigt, mit Linien, Schnittproblemen
und haben also Polygone betrachtet.
Gehen wir nochmal kurz da durch.
Das war das Problem, festzustellen, wie viele Punkte innerhalb eines
beliebigen Rechtecks liegen.
Innerhalb so einer Ebene, in der Punkte irgendwie verstreut sind.
Ein Problem, wo man sich leicht die praktische Anwendung vorstellen
kann.
Dass man halt irgendein Fenster auf einem Bereich hat und man muss
sehen, welche Objekte liegen eigentlich in diesem Fenster, das die
Sichtbarkeit gerade charakterisiert.
Und wir hatten dann gesehen, wie man das durch gewissen
Vorbereitungsaufwand deutlich beschleunigen kann, beziehungsweise wie
man die einzelnen Anfragen, wie viele Punkte jetzt in so einem
Rechteck liegen, deutlich beschleunigen kann.
Das kostet allerdings erhebliche Vorbereitungszeit, nur wenn man viele
solche Punktanfragen hat, ist das durchaus vorteilhaft.
Das zweite war dann die Frage, also bezogen auf Polygone, und zwar
einfache Polygone, ob ein Punkt innerhalb oder außerhalb so eines
Polygons liegt, was nicht immer so einfach ist, selbst wenn das
Polygon einfach ist, aber ein einfaches Polygon muss ja keineswegs so
einfache geometrische Form haben, wie das hier ja auch gut zu sehen
ist.
Wir hatten gesehen, dass man mit der Strahlmethode hier das
entscheiden kann, allerdings muss man halt feststellen, mit welchen
Kanten sich ein solcher Strahl schneidet, und das kostet halt linearen
Aufwand in der Anzahl der Kanten.
Für konvexe Polygone war das dann einfacher, da konnten wir Sektoren
bestimmen, in denen wir nur entscheiden müssen, ob der Punkt innerhalb
oder außerhalb so eines Vektors liegt, und das war dann wieder mit Log
N Aufwand zu machen, also diese einzelne Anfrage, auch das
Feststellen, in welchem Sektor dieser Punkt liegt, das ist mit Log N
Aufwand zu machen, und die Entscheidung, ob links oder rechts von der
Kante, ist halt mit konstantem Aufwand zu machen.
Dieses Überprüfen, ob ein Punkt links oder rechts von einer Kante
liegt, ging halt mit der Determinanten von den drei beteiligten
Punkten, aufgefüllt mit einer Eins-Spalte, und damit hatten wir
entweder positives oder negatives Vorzeichen, also der Wert ist
eigentlich gar nicht so wichtig, wesentlich kommt es darauf an, ob wir
einen positiven oder negativen Wert haben.
Sobald man das festgestellt hat, ist man eigentlich fertig.
Und deswegen ist das eine sehr effiziente Art, diese Bestimmung zu
machen, insbesondere ohne jeden Rückgriff auf trigonometrische
Funktionen, was man zunächst, wenn man an Geometrie denkt, eigentlich
immer vermutet, dass man die brauchen würde.
Wir hatten dann uns überlegt, wie kann ich feststellen, ob ein Polygon
einfach ist?
Dazu muss ich halt wissen, ob sich Kanten überschneiden.
Das hatten wir mit dem Plane Sweep gemacht, das war eine weitere
Methode.
Entschuldigung, da ist ein anderes Programm dazwischen geraten.
Wir hatten festgestellt... was ist denn jetzt passiert hier?
Auf irgendeinem Grund hat er sich... so, jetzt geht's weiter.
Also das war das Polygon, wir hatten hier den... ich war ja noch gar
nicht im Präsentationsmodus, richtig.
Also, machen wir hier weiter.
Der Plane Sweep, eine weitere Methode, algorithmische Methode, um ein
Problem, das hier ein zweidimensionales Problem ist, zu reduzieren auf
ein eindimensionales Problem.
Diese Methode kann man genauso anwenden, um ein d-dimensionales
Problem auf ein d-1-dimensionales Problem zu reduzieren, was durchaus
zu effizienteren Verfahren führen kann.
Und ich hatte das halt hier kurz erläutert, wobei ich auf die genaue
Ausführung, die einzelnen Operationen in den Haltepunkten, gar nicht
so explizit eingegangen war.
Das Wesentliche ist, dass man das Überschneidungsproblem von Geraden
oder von Liniensegmenten hier überträgt in ein
Intervallschneideproblem.
Und das ist halt ein Intervallschneideproblem auf einer Geraden, was
deutlich einfacher zu lösen ist, insbesondere wenn man eine geeignete
Datenstruktur hat, als das Problem festzustellen, welche Kanten sich
überschneiden.
Und der Aufwand war dann halt, hier nochmal aufwandfrei reduziert
worden, dann auf nlogn, im Wesentlichen der Aufwand, um die
Haltepunkte in sortierte Reihenfolge zu bringen.
Schließlich haben wir dann uns begonnen damit zu beschäftigen, wie man
eine konvexe Hülle einer Punktmenge bestimmt, ein Problem, das häufig
auftritt.
Dass man die umhüllende Linie einer Punktmenge braucht.
Und diese konvexe Hülle konnte man halt in verschiedener Art erstmal
definieren, als konvexe Teilmenge, als kleinste konvexe Teilmenge, die
die Punkte alle enthält.
Oder über das Polygon, das außenrum läuft und halt konvex ist.
Also dafür braucht man dann halt die Menge der Extrempunkte, die halt
gerade die Eckpunkte des Polygons bilden.
Und ich hatte Ihnen hier einen Ansatz kurz vorgestellt, der sich sehr
leicht parallelisieren ließ, allerdings sehr viel Rechenoperation
braucht, weil wir nämlich hier überprüfen für jeden Punkt, ob er
innerhalb eines Dreiecks aus beliebigen drei anderen Punkten liegt.
Und die Punkte, die halt in keinem Dreieck liegen, sind genau die
Extrempunkte.
Und dass das hier parallel sehr effizient zu machen ist, also parallel
in kurzer Zeit, aber mit sehr viel Aufwand.
Effizienz ist relativ niedrig, weil ich das vergleichen muss mit den
besten optimalen Verfahren, und da werden wir sehen, es geht durchaus
noch besser.
Und es ist auf jeden Fall ein Ansatz, den man verwenden kann.
Und es ist einfach interessant zu sehen, was gibt es für geometrische
Eigenschaften, die man ausnutzen kann, um so ein Problem zu lösen.
Das nächste Verfahren war das von Graham, der Graham-Scan, der uns ein
bisschen erinnert an diese Strahlmethode, um festzustellen, ob ein
Punkt innerhalb oder außerhalb eines konvexen Polygons liegt.
Hier werden zunächst einmal alle Punkte radial sortiert um einen
beliebigen Punkt, der irgendwo eigentlich liegt.
Es ist völlig egal, wo der liegt.
Man nimmt normalerweise irgendeinen Punkt aus der Menge und sortiert
alle anderen Punkte der Menge radial.
Das Problem dabei ist allerdings, darauf hatte ich hingewiesen, wenn
solche Punkte sehr nah zusammenliegen, was natürlich in diesem Fall,
der hier oben angedeutet ist, natürlich dann immer auftreten kann,
dann mag es aufgrund von Rechenungenauigkeiten schwierig sein,
tatsächlich die radiale Sortierung durchzuführen.
Es mag schwierig sein, exakt zu entscheiden, ob zwei Punkte links oder
rechts voneinander liegen, weil einfach die Rechenungenauigkeit da zu
falschen Ergebnissen führen kann.
Also das ist ein Problem bei diesem Gram-Scan.
Wenn wir annehmen, dass diese Probleme nicht auftreten, dann können
wir so vorgehen, wie es hier steht.
Man geht einfach kreisförmig, wie es hier angedeutet war, durch alle
diese Punkte hindurch und hat dann diese drei Situationen zu
unterscheiden.
Die erste Situation war so, dass man einen Konvexenwinkel im Prinzip
gegangen ist, der darauf hindeutet, dass der Punkt P2 ein Extrempunkt
ist.
Man nimmt an, P1 ist auch ein Extrempunkt.
Und dann macht man halt entsprechend anschließend weiter.
Wenn man eine andere Situation hat, dass die drei auf einer Linie
liegen, vergisst man den mittleren, also streicht den raus, das ist
kein Extrempunkt.
Und wenn man die Situation hat, wie sie hier unten angedeutet ist,
dass wir einen konkarven Winkel haben, dann ist der Punkt P2
garantiert kein Extrempunkt und wird rausgestrichen.
Und dann geht man halt zurück, betrachtet den Winkel P0, P1, P3 und
hat dabei, wenn man Pech hat, wieder einen konkarven Winkel, sodass
dieses Rausstreichen eventuell sich fortsetzen kann.
Aber es ist klar, dass jeder Punkt nur einmal aufgenommen werden kann
als potenzieller Extrempunkt und eventuell später einmal wieder
gelöscht werden kann.
Danach muss man ihn nie wieder besuchen.
Die wesentliche Überlegung ist also, ob ich bei diesem Graham-Scan um
diese Punkte außen herum einen konkarven oder konvexen Winkel finde.
Oder ich kann auch sagen, ob ich eine Linksdrehung oder eine
Rechtsdrehung mache, wenn ich diese Punkte P1, P2, P3 betrachte, wobei
das jeweils die aktuellen Punkte sind, die ich gerade anschauen muss.
Der Aufwand ist halt NlogN, um die radiale Sortierung zu machen.
Haben Sie da noch eine Frage zu gehabt?
Ich muss ja die radiale Sortierung erst einmal machen, das bringt das
NlogN, der Rest ist dann mit linearem Aufwand zu machen.
Das war die letzte Folie vom vorigen Mal und jetzt machen wir mit
dieser Folie weiter.
Die Eigenschaft, die wir hier genutzt haben, ist die Eigenschaft, die
hier oben noch einmal angedeutet ist, alle inneren Winkel zwischen
aufeinanderfolgenden Kanten eines konvexen Polygons sind konvex.
Also kleiner als 180 Grad.
Das ist halt gerade alles solche Winkel, wenn das hier das innere ist
und das hier das äußere.
Und auf diese Art und Weise kann man halt gerade die Extrempunkte
finden.
Ein anderer Ansatz ist, dass man nicht nach Extrempunkten sucht,
sondern nach Kanten.
Also jetzt haben wir versucht, sukzessive herauszufinden, welche der
Punkte sind Extrempunkte.
Dadurch, dass wir die Winkel betrachtet haben, gesehen haben, ob eine
Linksdrehung oder eine Rechtsdrehung, konnten wir feststellen, ob ein
Punkt, der gerade Kandidat ist, Extrempunkt zu sein, tatsächlich einer
ist oder nicht.
Was man natürlich auch machen kann, ist, man sucht von vornherein die
Kanten, die garantiert in diesem umschließenden Polygon drin sind.
Natürlich findet man implizit auch bei der anderen Methode die Kanten,
aber man macht es hier schon anders.
Also, die Eigenschaft, die wir jetzt ausnutzen, ist hier angedeutet.
Und die sagt jetzt folgendes aus.
Wenn wir eine Kante haben, unserer konvexen Hülle, also hier ist
irgendeine Kante und hier irgendeine Kante.
Was passiert dann?
Dann liegen alle Punkte von M auf der gleichen Seite der Geraden durch
P und Q oder auf PQ.
Die beiden Punkte P und Q hier, da und da.
Und wenn wir hier die Gerade betrachten, dann liegen alle Punkte also
entweder auf der gleichen Seite der Geraden, nämlich alle in diesem
Fall in diesem Bereich, oder halt auf der Geraden.
Das waren genau die Punkte, die wir in der Überlegung, die wir vorher
auch hatten.
Wenn Punkte auf der Geraden liegen, dann wurden sie halt
rausgestrichen.
So.
Das nutzen wir einfach aus.
Wie kann ich denn so eine Kante finden?
Ich nähe mich einfach, ich gehe von einem Punkt aus, lege da
irgendeine Gerade rein und bewege diese Gerade nach links.
Ich vergrößere praktisch diesen Winkel mit der X-Achse immer mehr, bis
ich einen Punkt finde, Punkt Q, der auch in der Menge liegt.
Sobald ich zwei Punkte habe, fange ich also mit dem Punkt Q an und
schiebe einfach so eine Gerade darum.
Im Prinzip ist das, was man mit einem Lineal machen würde.
Und das ist etwas, was sich jetzt nicht Gram-Scan nennt.
Gram-Scan hatte die Punkte ja radial sortiert.
Das ist jetzt der Jarvis-Marge.
Also einer Jarvis hat das herausgefunden oder hat sich diesen
Algorithmus überlegt.
Und das heißt, wir gehen jetzt so vor, dass wir einen Punkt wählen,
zum Beispiel diesen Punkt hier unten.
Und dann sucht man einen Punkt Q dazu, sodass der Winkel dieser Linie
oder der Geraden, die zwischen P und Q geht, mit der X-Achse minimal
ist.
Also hier ist es andersherum formuliert.
Hier geht man durch alle Punkte durch und sucht sich denjenigen,
der...
Also ich habe hier alle möglichen Punkte drin und ich gehe praktisch
immer weiter rüber, bis ich den Punkt habe, bei dem der Winkel zur X
-Achse minimal ist.
So.
Und wenn das der Fall ist, dann habe ich ja gerade diese Gerade
gefunden, dann liegen alle anderen Punkte auf der linken Seite dieser
Gerade.
Und das ist im ersten Fall halt hier die horizontale, das wäre dann
diese Gerade, das sollte eine Gerade sein.
Und wenn ich halt diesen Punkt gefunden habe, mache ich das wieder so,
dann werde ich irgendwann diesen Punkt finden und komme zu dieser
Kante.
Anschließend finde ich diese Kante, dann finde ich die Kante, ich
finde die Kante, die Kante und die Kante und bin fertig.
Und das Interessante ist, dass ich pro Extrempunkt nur diese
Vergleiche machen muss.
Vorher habe ich bei dem Grahamscan, muss ich durch alle Punkte
durchgehen und jeweils gucken, ob ich eine Linkdrehung oder
Rechtsdrehung habe.
Hier fange ich bei einem sicheren Extrempunkt an, das ist der
linkeste, unterste Punkt, und suche von dem aus den nächsten
Extrempunkt.
Der Aufwand pro Extrempunkt ist linear,
und das heißt, wie ist der Gesamtaufwand?
Ich muss für jeden Extrempunkt, wenn wir annehmen, wir haben h
Extrempunkte, muss ich linearen Aufwand betreiben.
Je nachdem, wie viele Extrempunkte vorkommen, habe ich also einen
Aufwand, der im besten Fall linear sein kann, im schlechtesten Fall
ist er quadratisch.
Wenn ich in Größenordnung n Extrempunkte habe.
Aber wenn ich Glück habe, ist die Anzahl der Extrempunkte relativ
niedrig.
Und dann geht das Verfahren recht schnell.
Also das ist ein interessantes Verfahren, wobei wir hier das Problem,
das wir vorher beschrieben haben, mit diesen Ungenauigkeiten, das
tritt hier nicht ganz so stark auf.
Wir müssen hier nur das Minimum bestimmen.
Kann natürlich da auch passieren.
Wenn wir hier jetzt Punkte haben, die sehr nah beieinander liegen,
also ob ich hier jetzt irgendwelche kleinen Punkte habe, das kann sich
auch noch verändern.
Also insofern können die Probleme auch hier auftreten.
Aber ich betrachte ja nur die Extrempunkte.
Von denen aus gehe ich an die anderen ran.
Ich habe das nicht untersucht, aber es wäre interessant, das
algorithmisch zu untersuchen, wie anfällig die verschiedenen Verfahren
zum Rechnen der konvexen Hülle sind, bezüglich der Ungenauigkeiten bei
den Gleitpunktberechnungen.
Also das ist ein Problem, das ist so noch nicht untersucht worden,
kann man sich mal angucken, wäre ein Thema für eine mögliche
Diplomarbeit.
Kann man sich durchaus mal angucken, ist zur Zeit ein Thema, das
durchaus angeguckt wird.
Also diese Problematik mit den Ungenauigkeiten, die durch
Gleitpunktoperationen auftreten, das wird zur Zeit angeguckt und ist
aber hier in Bezug auf diese Fragestellung so noch nicht betrachtet
worden.
So, jetzt kommt, ich glaube das Verfahren ist klar gewesen, wie man
das macht, da brauche ich nicht weiter darauf einzugehen.
Jetzt kommt das nächste Prinzip, die beiden Konker, das haben wir uns
immer angeguckt.
Wie kann man mit Problemen umgehen?
Wir sind gerade eben eigentlich mehr so iterativ da durchgelaufen,
haben uns sukzessive die einzelnen Punkte angeschaut.
Jetzt machen wir das anders, so wie der Informatiker gerne vorgeht.
Er hat ein großes Problem und sagt, das ist mir viel zu schwer.
Ich teile es auf, mache erst mal, mache daraus zwei oder mehr kleinere
Probleme, die ich auch lösen kann.
Und wenn sie mir immer noch zu schwer sind, teile ich es halt weiter
auf.
Also das ist die beiden Konker-Prinzip.
Und jetzt ist einfach wie üblich die Idee, wenn ich ein genügend
leichtes Problem habe, also die Menge, die Anzahl der Punkte ist
kleiner gleich K, dann nehme ich irgendein Verfahren, um die komplexe
Hülle zu konstruieren.
Aber wenn es zu groß wird, dann mache ich daraus zwei Hälften und baue
daraus, also in irgendeiner Weise, teile ich die Menge auf, wir sehen
das hier angedeutet, wird also in etwa aufgeteilt, wir sehen, dass es
hier nicht genau gleichmäßig sein muss, aber so in etwa mittig wird
das aufgeteilt.
M1 und M2.
Hätten wir also hier die Menge M1, da hätten wir die Menge M2.
Und das Problem ist, also mach es rekursiv weiter, da kann ich
natürlich jetzt rekursiv die konvexen Hüllen bestimmen, dann habe ich
die konvexen Hüllen von M1 und von M2 und die Frage ist, wie baue ich
denn daraus jetzt die gesamte konvexe Hülle.
Also das Aufteilen ist einfach, das ist sicherlich mit linearem
Aufwand zu machen.
Ich muss ja nur festlegen für jeden Punkt, ob er in der Menge M1 oder
M2 liegt.
Und dann muss ich halt rekursiv weiterarbeiten und muss anschließend
die beiden konvexen Hüllen verschmelzen.
Im Prinzip ist das nicht Merge Sort, sondern ein Verschmelzen von
konvexen Hüllen.
Und muss man sich angucken, wie groß der Aufwand ist dafür.
Also, wenn der Schritt für das Verschmelzen linear ist, was hier
angenommen ist, also O von N, und wir müssen zweimal Aufwand für halbe
Größe machen, kommen wir mit N log N hin.
Das wäre natürlich ein gutes Ergebnis.
N log N für die konvexe Hülle.
Hier steht sogar, man kann das verbessern auf N log H, also nur die
Anzahl der logarithmisch, also N mal Logarithmusanzahl der
Extrempunkte.
Aber selbst N log N ist schon nicht schlecht.
Wir hatten ja vorher Verfahren gehabt, das war der N hoch 4.
Jarvis-March hatte bis N².
Und auch der Gram-Scan lag bei N log N.
Insofern, hier hätten wir auch wieder N log N, aber halt ein völlig
anderer Ansatz.
Und auch hier könnte man sich überlegen, welche Rolle spielen hier
wieder diese Ungenauigkeiten.
So, wie macht man das?
Wie konstruiert man eine konvexe oder wie verschmilzt man zwei konvexe
Hüllen?
Muss man sich mal überlegen.
Wir haben zwei konvexe Hüllen.
Hier sieht es so einfach aus.
Ich brauche ja nur hier oben diese eine Linie zu malen und hier unten
eine Kante rein zu zeichnen und ich bin fertig.
Das kann natürlich auch ganz anders aussehen.
Also ich werde immer irgendeine neue Kante da reinziehen müssen.
Aber es ist halt immer die Frage, wie viele Kanten der konvexen Hüllen
gehen dann verloren, was sind eigentlich die neuen Extrempunkte?
Und ja, wie macht man das?
Wir haben die beiden konvexen Hüllen gegeben.
Das heißt, wir wissen, fängt meinetwegen hier irgendwie an, P1, P2,
P3, P4 und so weiter und hier hätten wir meinetwegen Q1, na, hier
unten wäre Q1, Q2, Q3, Q4 und so weiter.
Das heißt, wir haben schon mal zwei reine Folgen gegeben.
Das heißt, wir hätten also zwei konvexe Hüllen.
Da können wir erst mal Folgendes machen.
Wir können die einfach voneinander trennen, die obere und die untere
Hälfte.
Und betrachten einfach erst mal nur den oberen Rand.
Ich weiß ja, was ist der obere Rand der konvexen Hülle von M1, was ist
der obere Rand der konvexen Hülle von M2.
Das kann man leicht feststellen beim Durchlaufen, welche Punkte zum
oberen Rand gehören.
Wenn ich da durchlaufe, wie lange werden die x-Werte größer.
Sobald sie kleiner werden, bin ich im unteren Rand angekommen.
Das ist also einfach.
Das ist kein Sortieraufwand, die sind bereits in dieser Reihenfolge
gegeben.
Ich muss nur einmal durchlaufen und habe festgestellt, wie die
Reihenfolge ist.
Dann habe ich also diese Punkte alle so angeordnet.
Im Prinzip habe ich so eine Folge von x-Koordinaten.
Und da liegen jetzt meine Punkte drauf.
Das sind meinetwegen die y-Koordinaten zu diesen x-Koordinaten, die
wir hier gerade festgestellt haben, der beiden konvexen Hüllen, die
jetzt verschmolzen werden sollen.
Und was mache ich dann?
Ich gehe einfach jetzt von links nach rechts in einer Reihenfolge
dadurch und stelle fest, habe ich hier jeweils die richtigen Winkel.
Ich mache im Prinzip einen Gram-Scan auf diesen beiden oberen Teilen
der konvexen Hülle.
Und sobald ich einen konkaven Winkel habe, kann ich den sofort
streichen.
Dann hätte ich wieder einen konkaven Winkel.
Ich würde auch die Linie rausstreichen.
Ich würde hier hingehen, hätte wieder einen konkaven Winkel.
Ich würde hier hingehen, hätte wieder einen konkaven Winkel und würde
dann hier die letzte Kante dazu nehmen.
Man hätte damit mit dem Gram-Scan im Prinzip, angewandt auf diese
oberen beiden konvexen Hüllen-Teile, die gemeinsame konvexe Hülle
gefunden.
Für den oberen Teil.
Und für den unteren Teil macht man es dann entsprechend genauso.
Und der Aufwand, den wir gerade eben zu machen hatten, war linear.
Wir müssen nur von links nach rechts durch die Punkte durchgehen.
Wir können jeweils feststellen, ob es eine Links- oder Rechtsdrehung
ist, also konkaver oder konvexer Winkel.
Und bei den konkaven Winkeln müssen wir halt entsprechend Punkte
vergessen.
Bei konvexen Winkeln können wir weitermachen.
Und damit ist der Aufwand linear.
So wie das hier auch steht, ist auch der Aufwand für das Verschmelzen
in linearer Zeit zu machen.
Und damit haben wir insgesamt Aufwand in Locking.
Auch hier könnte man gucken, inwieweit dieses Verfahren numerisch sich
stabiler verhält als irgendeins der anderen.
Gut.
Ich denke, das ist ein sehr naheliegendes Verfahren.
Brauche ich nicht weiter darauf einzugehen.
Hier steht das Verfahren nochmal beschrieben.
Das ist also genau das, was ich gerade eben erläutert habe.
Dass man die beiden Ränder bestimmt, die oberen Ränder, und dann der
Reihe nach einfach da durchläuft.
Jetzt haben wir noch ein Verfahren.
Ein Verfahren, das ist das Verfahren, das nach dem Wegwerfprinzip
arbeitet.
Das Prinzip habe ich Ihnen bisher noch verschwiegen.
Wegwerfprinzip.
Ist aber auch ganz interessant.
Und man könnte sagen, das ist so ein bisschen ähnlich wie Branch and
Bound.
Es ist einfach die übliche Idee, ich möchte mein Problem möglichst
stark reduzieren, indem ich irgendeine Operation darauf ausführe, die
mir Informationen liefert, sodass ich einen großen Teil der Punkte
wegwerfen kann.
Also gar nicht mehr berücksichtigen muss.
Ich will das Problem durch ein paar Operationen möglichst drastisch
reduzieren.
Und das macht man in diesem Fall so, dass wir uns anschauen, die Menge
der Punkte.
Ich habe hier einfach mal so ein Rechteck da drum gemalt.
Und wir suchen ja die konvexe Hülle dieser Punkte.
Jetzt machen wir einfach eine Approximation.
Wir suchen einfach Extrempunkte, die relativ einfach zu bestimmen
sind, nämlich mit jeweils linearem Aufwand.
Wir suchen acht Extrempunkte im Norden, Nordosten, Osten, Südosten,
Südwesten, Westen, Nordwesten.
Dann haben wir diese Punkte hier E1, E2, E3 bis E8.
So, jetzt haben wir also acht Punkte.
Und der Aufwand, um diese Punkte zu finden, ist jeweils linear.
Weil wir feststellen müssen, was ist also der Punkt in der
entsprechenden Richtung, also jeweils der Extrempunkt.
Das kann man mit linearem Aufwand feststellen.
Ich muss nur in der entsprechenden Richtung die Distanz vom Zentrum
feststellen.
Ich muss also einen mittleren Punkt irgendwie wählen, dann kann ich
von dem aus die Sektoren mir angucken und kann die Punkte berechnen.
Und dann habe ich so eine approximierte konvexe Hülle.
Die gestrichelten Linien hier, das können bereits die Linien sein, die
nachher auch meine Kanten der konvexen Hülle sind.
Ich weiß auf jeden Fall, die Extrempunkte E1 bis E8 sind sicherlich
tatsächlich Extrempunkte.
Es kann sogar sein, dass welche von denen zusammenfallen.
Wenn das also eine sehr einfache Figur ist, dann würden die
zusammenfallen.
Also das Rechteck außen drum, was ich da gezeichnet habe, da hätten
wir nur vier solcher Extrempunkte.
Also da würden einige dieser Punkte zusammenfallen.
Aber hier haben wir jetzt also einen Fall angenommen, da haben wir
jetzt diese acht Punkte.
Und dann kann es natürlich sein, dass es noch weitere Punkte gibt, die
sind hier in dem Bereich dort zu sehen.
Ein paar Punkte, die fallen nicht unter diese acht Extrempunkte,
liegen aber außerhalb unseres Polygons, das wir jetzt eingezeichnet
haben, aus diesen acht sicheren Extrempunkten.
Aber die ganzen Punkte, die hier drin liegen, die hier im Inneren
liegen, dieses approximierten konvexen Polygons, die kann ich alles
vergessen.
Die kann ich wegwerfen.
Und die Erwartung ist halt, dass die meisten Punkte innen liegen
werden und nur wenige Punkte irgendwo mal draußen liegen.
Da haben wir noch einen, da haben wir noch einen, die hier angedeutet
sind, das sind sie dann auch.
Das heißt, ich werfe alle Punkte weg, die im Inneren dieses
gestrichelt angedeuteten Polygons liegen.
Das ist mit linearem Aufwand machbar, weil ich ja nur acht solche
Kanten, die ich betrachten muss, oder nur sieben solche Kanten, acht
Punkte durch sieben Kanten verbunden.
Und das heißt, ich muss nur feststellen, welche Punkte liegen halt im
Inneren dieses Polygons.
Das ist also relativ einfach zu machen, auf jeden Fall mit linearem
Aufwand.
Ich habe acht Punkte... Entschuldigung, ja, beim Kreis habe ich acht
Kanten, ja.
Da habe ich mich gerade... Manchmal hat man solche... Danke, ja.
Also es sind selbstverständlich acht Kanten, weil ich ja E1 und E8
nicht identifiziert habe.
Dann wären es sieben Kanten.
Selbstverständlich sind es acht Kanten.
Also auf jeden Fall habe ich acht Mal diesen Aufwand zu machen,
festzustellen, ob die Punkte links oder rechts liegen.
Und diejenigen, die im Inneren dieses ganzen Polygons liegen, bei
denen weiß ich dann, die kann ich wegwerfen.
Und die, die draußen liegen, die muss ich halt noch weiter
berücksichtigen.
Das heißt, dann habe ich eine Restmenge und dann nehme ich irgendein
Verfahren, dessen Aufwand NlogN hat.
Oder NlogH, wie wir gerade gesehen haben, das Verfahren davor.
Und wenn wir jetzt annehmen, dass das wenig oder wenn das wenig sind,
wenn wir irgendwie schließen können, dass es relativ wenig Punkte
sind, die draußen liegen, dann hätten wir also hiermit zwar NlogN,
aber bezogen auf die Anzahl der Punkte in der Restmenge.
Und das heißt, wenn R die Anzahl der Punkte in der Restmenge ist, dann
wäre das ein Aufwand RlogR.
Und wenn wir jetzt noch annehmen, dass die Punkte im Wesentlichen
gleich verteilt sind in unserer Ebene, dann ist der Erwartungswert für
den Aufwand linear.
Weil wir dann nämlich davon ausgehen können, dass nur ein sehr, sehr
kleiner Anteil außen liegt.
Und wenn das R liegt in klein o von N, dann habe ich kein Problem mit
dem Aufwand.
Und davon kann ich ausgehen, wenn ich Gleichverteilung habe der
Punkte, dann liegen nur sehr wenige außerhalb.
Im schlechtesten Fall natürlich NlogN, aber ich denke, das ist ein
ganz interessantes Verfahren, weil man hier eben einfach so eine grobe
Abschätzung macht, wie könnte in etwa so über den Daumen erstmal die
konvexe Hülle aussehen.
Und das, was man dann noch an Ungenauigkeiten drin hat, muss man halt
korrigieren.
Das ist halt Teil C, und dann ist man damit fertig.
Und das Interessante ist eben, dass man sieht, man kann diese Stimmung
der konvexen Hülle wirklich mit sehr viel verschiedenen Verfahren
machen.
Man nutzt unterschiedliche Eigenschaften dieser konvexen Hülle aus,
oder dieser Punktmenge aus, und kann dadurch dieses Problem lösen.
Auch dieses Problem hier ist relativ gut parallel zu machen.
Also diese Entscheidung, die acht Extrempunkte zu bestimmen, das kann
ich unabhängig voneinander machen.
Auch festzustellen, welche Punkte im Inneren liegen, das kann ich gut
parallelisieren, auch mit einem geringen Parallelitätsgrad.
Und bringt mir also durchaus einige Vorteile.
Gut, damit haben wir uns eigentlich jetzt alle Verfahren angeschaut,
die ich Ihnen vorstellen wollte.
Ein Problem ist noch die untere Schranke.
Hatten wir uns auch ein paar Mal angeschaut, wie ist der minimale
Aufwand, was kann ich darüber aussagen.
Und hier steht es schon, ich habe diese Folie nicht animiert, deswegen
ist gleich alles zu sehen.
Ich möchte also bestimmen, eine untere Schranke für den schlechtesten
Fall.
Und da nehme ich einfach eine Menge von Punkten her, irgendeine Menge
von Punkten, x1 bis xn, das seien einfach irgendwelche ganzen Zahlen.
Oder sogar natürliche Zahlen, also nicht negative.
Und ich definiere einfach Punkte auf einer Parabel.
Wenn ich Punkte auf einer Parabel betrachte, dann weiß ich, die liegen
in etwa so, wie das hier angedeutet ist.
Wenn ich die konvexe Hülle bestimmen möchte, von dieser Punktmenge,
dann weiß ich, jeder Punkt in dieser Menge ist ein Extrempunkt.
Die konvexe Hülle hat keinen Punkt im Inneren, die liegen alle auf dem
Rand.
Und dadurch wird das Problem, die konvexe Hülle zu bestimmen,
eigentlich festgelegt durch das Problem, die Punkte zu sortieren.
Also die x-Koordinaten zu sortieren.
Wenn ich die in dieser Reihenfolge anordnen kann, habe ich die konvexe
Hülle bereits gefunden.
Und das heißt, egal welches Verfahren ich betrachte, ich muss in der
Lage sein, auch für dieses Polygon oder für diese Punktmenge die
konvexe Hülle zu bestimmen.
Und die Bestimmung der konvexen Hülle hier ist mindestens so schwer
wie das Problem, die Endpunkte dieser Menge zu sortieren.
Und wir wissen, wenn wir keine anderen Informationen haben als eben
den Vergleich der Werte dieser Punkte, wir können nicht davon
ausgehen, dass wir hier mehr ausnutzen können, dann haben wir also
untere Schranke NlogN für den schlechtesten Fall zur Bestimmung der
konvexen Hülle.
Also das ist klar, dass wir damit die untere Schranke haben, Omega von
NlogN.
Im Mittel ist es aber so, dass wir durchaus Omega von N haben.
Wir hatten ja gerade eben gesehen, es gibt Verfahren, bei denen wir
unter gewissen Annahmen eine lineare Laufzeit garantieren können.
Das Werkseilsprinzip war so ein Verfahren.
Das heißt, hier haben wir im Mittel lineare Laufzeit, anders als beim
Sortieren.
Das ist also schon etwas anders als das Sortierproblem, aber im
schlechtesten Fall untere Schranke NlogN.
Und damit bin ich schon am Ende angekommen von diesem ganzen Kapitel
über algorithmische Geometrie.
Ich hätte durchaus noch mehr Sachen machen können.
Ich hätte dieses Problem mit den Versuchen, auch bei entarteten oder
ungünstigen Problemstellungen exakte Ergebnisse zu kriegen, noch ein
bisschen genauer machen können.
Ich will das aber angesichts der Temperaturen zur Zeit und anderer
Gründe diesmal lassen.
Ich hoffe, dass Sie gesehen haben, dass algorithmische Geometrie auch
ein interessantes Gebiet ist, dass man dort interessante Probleme
angucken kann.
Für jemanden, der an Geometrie Interesse hat und an Informatik, ist
das ein ideales Betätigungsfeld.
Es gibt viele interessante Probleme zu bearbeiten.
Man hat für dieses Gebiet einige interessante neue Lösungstechniken
für Probleme entwickelt.
Also dieses Planesweep-Verfahren, das hat natürlich noch nur Sinn bei
solchen geometrischen Problemen.
Reduktion eines Problems auf ein Problem niedrigerer Dimensionen und
systematische Lösung des Problems durch eine Folge von Problemhalt
niedrigerer Dimensionen.
Und das führt also zu durchaus besseren Verfahren und zu guten
Laufzeiten.
Planesweep ist ein interessanter Ansatz, den man auch in anderen
Bereichen einsetzen kann.
Ich habe Ihnen das Wechselprinzip nochmal vorgestellt.
Was ich nicht vorgestellt habe, sind die neuen Datenstrukturen, die
für den Bereich algorithmischer Geometrie entwickelt wurden.
Segmentbäume und Intervallbäume sind entwickelt worden.
Ich denke aber, das reichte als Einblick in die Problemstellungen, die
hier von Interesse sind.
Und damit bin ich am Ende dieses Kapitels und kann jetzt eigentlich
nur noch...
es sei denn, Sie haben noch Fragen zu dem Bereich algorithmische
Geometrie.
Jetzt komme ich nur noch schnell zu einem abschließenden Kapitel.
Das müsste ich ja eigentlich auch noch in meinem...
Na, wo habe ich es?
Einmal sortieren...
Genau.
Das ist...
Gehe ich mal lieber auf die andere Datei.
Auf diese hier.
Abschließende Bemerkung, ganz kurz.
Das Algorithmik ein zentrales Gebiet der Informatik ist, ich denke,
das ist durchaus jedem klar.
Informatik lebt davon, dass wir effizient mit den Ressourcen umgehen
können.
Wenn wir Mathematik und Informatik vergleichen, dann geht es in der
Informatik halt darum, dass man Ressourcen effizient verwendet.
Mathematiker interessieren sich dafür, ob ein Problem prinzipiell
lösbar ist.
Aber da geht es weniger darum, die Kosten abzuschätzen.
Und wir wissen, dass die Rechner nie schnell genug sind.
Also es gibt durchaus schon mal Menschen, die durchaus ernsthaft
Wissenschaft machen, sagen hören, naja, um Effizienz brauchen wir uns
nicht zu kümmern, die Rechner werden doch immer schneller und damit
ist das erledigt.
Wir wissen aber durchaus, dass eine Wachstumskurve, die so läuft,
durchaus Nachteile hat gegenüber einer, die so läuft.
Logarithmisch oder etwas, was deutlich stärker wächst als linear.
Das sind schon für große Probleme Unterschiede, die sehr sehr wichtig
sind.
Und wir hatten durchaus Beispiele gesehen, wo man sehr große
Unterschiede hat zwischen dem Aufwand für naive Algorithmen und für
etwas intelligentere Algorithmen.
Also es lohnt sich immer, nach effizienten Lösungen zu suchen.
Man muss aber natürlich immer aufpassen, wenn wir solche Kurven haben,
da kann es halt sein, dass man sich genau anschauen muss, in welchem
Bereich betrachte ich denn eigentlich meine Probleme?
Wo sind die Problemgrößen, für die ich mich interessieren muss?
Und da muss ich sehen, wie sehen dort die Kosten aus?
Also Kostenanalyse darf nicht nur asymptotisch sein, sondern muss auch
die Kosten in dem Bereich betrachten, in dem ich meine Anwendungen
habe.
Und es ist klar, dass Entwurf und Aufwand gucken müssen, was ist das
Berechnungsmodell?
Da hatten wir ja RAM angeguckt, als elementares Berechnungsmodell,
aber eben auch die ganzen parallelen Berechnungsmodelle.
Und wenn ich halt Parallelrechner zur Verfügung habe, muss ich sehen,
in welcher Form kann ich dort Kosten reduzieren?
Und was muss ich dafür an anderer Stelle bezahlen?
Und dann haben wir halt das Problem, dass wir unterschiedliche
Datenstrukturen verwenden können.
Und natürlich, also Rechnerstrukturen ist im Berechnungsmodell
eigentlich auch schon mit abgegolten.
Also wir müssen sehen, was sind die Strukturen, die uns erlauben, die
Probleme darzustellen, damit umzugehen?
Welche Operationen habe ich auf diesen Strukturen auszuführen?
Und wie kann ich das so machen, dass insgesamt der Aufwand für die
Lösung eines Problems dann klein bleibt?
Die Probleme, die wir betrachtet haben, sind hier nochmal aufgelistet.
Algebraische Probleme, Graphprobleme recht kurz, Such- und
Sortierverfahren und die algorithmische Geometrie.
Und was wir gemacht haben, ist hier nochmal die Prinzipien, die ich
Ihnen vorgestellt habe, algorithmische Entwurfsprinzipien.
Ich habe Ihnen systematische Verfahren für den Entwurf von parallelen
Algorithmen vorgestellt.
Das enthält den Mapping-Ansatz, bei dem wir gesehen haben, wie man
einfach durch affine Transformationen von Problemstellungen, also von
Abhängigkeitsstrukturen, tatsächlich Algorithmen entwerfen kann,
sodass man eine ganze Vielfalt von verschiedenen parallelen
Realisierungen, meinetwegen der Matrixmultiplikation, einfach durch
solche unterschiedlichen affinen Transformationen erzeugen konnte.
Was ein ganz wichtiger Punkt ist, dadurch ist man in der Lage,
systematisch, ingenieurmäßig, tatsächlich Algorithmen zu entwerfen.
Ja, das waren so die verschiedenen Themen, die verschiedenen
Prinzipien.
Und was kann man bei uns noch alles machen?
Das sind so die verschiedenen Bereiche, die bei uns am Institut
vorhanden sind.
Mein Bereich ist halt effiziente Algorithmen, wobei das Thema
effiziente Algorithmen in unterschiedlichster Form bei uns behandelt
wird.
Ich glaube, das wissen Sie auch, dass wir sehr viel, ich weiß gar
nicht, was ich jetzt noch an weiteren Folien habe.
Da gehe ich nur mal kurz drauf ein.
Ich komme gleich noch auf die verschiedenen Themen der Forschung, die
wir machen.
Also unsere Vorlesungsthemen kennen Sie, glaube ich, auch.
Welche Vorlesung haben Sie gemacht?
Bisher nur diese.
Aha, dann kann ich Ihnen also die Vorlesung natürlich auch empfehlen.
Angewandte Informatik 2, Informatikwerkzeuge für den elektronischen
Handel oder Algorithms for Internet Applications auf Englisch.
Da geht es halt um Algorithmen speziell in verteilten Systemen, sehr
speziell in verteilten Systemen, speziell also im Internet.
Und dann gibt es noch eine Vorlesung verteilter Algorithmen, der man
speziell Probleme in verteilten Systemen anschaut.
Die biete ich aber sehr, sehr unregelmäßig an, weil ich einfach nicht
die Lehrkapazität habe, um alle diese Vorlesungen anzubieten.
Naturanaloge Verteilte Optimierungsverfahren läuft immer parallel zu
dieser hier.
Da geht es halt um Meteoristiken, um schwierige Probleme zu lösen.
Und das, was wir eben sehr stark machen, sind die genetischen oder
evolutionären Algorithmen und Ameisenalgorithmen.
Oder auch Kombinationen von diesen Dingern.
Und eine Vorlesung, die Herr Branke, mein Assistent, gemeinsam mit
einem Assistenten aus der Informationswirtschaft macht.
Economics, agentenbasierte Simulation von wirtschaftlichen Problemen.
Sehr interessante Verfahren, die dort eingesetzt werden.
Das ist unser Lehrprogramm zur Zeit.
Natürlich auch Seminare, wobei, Sie sehen, ich habe das nicht
aktualisiert.
Das stimmt jetzt natürlich nicht ganz.
Was machen wir im Seminar zur Zeit?
Also, wenn ich hier ein Oberthema hinschreiben soll, dann sind die
Themen, die wir zur Zeit betrachten, haben alle zu tun mit Organic
Computing.
Ich weiß nicht, ob ich Ihnen schon mal von Organic Computing erzählt
habe.
Habe ich schon, insofern wissen Sie etwas darüber.
Also lebensehnliche Systeme, die sich anpassen können.
Und das spielen die Themen, die hier stehen, eine Rolle.
Was wir jetzt im kommenden Wintersemester machen, ist das Thema
gesteuerte Selbstorganisation oder Controlled Self-Organization.
Klingt wie ein Widerspruch, ist aber genau das, was wir im Organic
Computing behandeln müssen.
Wie kann ich Systeme, die selbstorganisierend arbeiten, einfach weil
sie nicht zentral gesteuert werden können, wie kann ich die trotzdem
noch beherrschbar halten, wie kann ich sie beeinflussen, sodass sie
immer das tun, was ich will, und nicht auf einmal in
Verhaltensbereiche abdriften, die eigentlich nicht gewünscht sind.
Ein Thema, das in der Literatur immer wieder behandelt wird, die außer
Kontrolle geratenen technischen Systeme.
Wenn Sie das Buch Beute oder Prey kennen, dann wissen Sie, wovon die
Rede ist.
Und man muss halt sehen, dass man Mechanismen entwirft, sodass so
etwas wie in Prey nicht vorkommen kann.
Deswegen die gesteuerte Selbstorganisation.
Und damit beschäftigen wir uns im Wintersemester, also Wintersemester
2006 -07.
Und Seminar Praktika hatten wir im letzten Wintersemester Service
-orientierte Architekturen.
Das bezog sich auf unser Projekt KIM, diese Karlsruhe-integrierte
Informationsmanagement -Systeme.
Und in diesem Wintersemester machen wir ein Seminar über Spamfilter.
Spamfilter für E-Mail.
Was ist daran interessant, das sind Lernverfahren, die man dabei
einsetzt, unterschiedlichste Lernverfahren.
Und da sollen einfach mal ein paar solches Filter gebaut werden, im
Prinzip sollen also Lernverfahren implementiert werden.
Das ist also jetzt in diesem Wintersemester.
Das sind die beiden Seminar, also Seminar und Seminarpraktikum.
Und Themen zum Oberthema Organic Computing oder Service-orientierte
Architekturen oder Autonomic Computing, das sind so die Themen, die
uns zur Zeit beschäftigen.
Und dann gibt es natürlich auch noch Diplomarbeiten, die Sie
irgendwann mal machen können, da dürfen Sie gerne zu uns kommen.
Auch die haben sehr viel zu tun mit unserem wesentlichen
Forschungsgebiet und das ist halt zur Zeit Organic Computing.
Und da spielen aber viele verschiedene Themen rein.
Ich hatte gesagt, ein Thema, das auch interessant sein könnte, wäre
diese Untersuchung der Robustheit oder Stabilität von Verfahren in der
algorithmischen Geometrie.
Also speziell, wie wirken sich verschiedene Verfahren der konvexen
Höhlenbestimmung aus auf die numerische Stabilität.
Kann man sich ein bisschen angucken.
Die anderen Themen hier, Grid Computing, da bauen wir einen
Jobscheduler, der in einer intelligenten Art und Weise Jobs verteilt
im Netz.
Oder bei Informationsdienstleistung, IT-Controlling, arbeiten wir in
Kooperation mit einem lokalen Dienstleister im Bankbereich.
Und dort werden halt Verfahren zur effizienten Nutzung der
Rechenressourcen in so einem großen Informationsdienstleistungszentrum
entwickelt.
E -Learning ist ein bisschen mehr an den Rand gegangen, auch da gibt
es aber Arbeiten.
Das sogenannte Activity Tree, Harvesting, wird dort gemacht.
Mobile Anwendungen haben wir im Augenblick etwas in den Hintergrund
gerückt, aber hat ein bisschen auch mit Organic Computing zu tun.
Das Projekt Notebook University ist ja nicht mehr so akut.
Allerdings haben wir im Bereich KIM durchaus Themen, die man da auch
betrachten kann.
Und dann ist es so, dass wir eine ganze Reihe unserer Themen in
Kooperation mit der Industrie machen.
Wer also vielleicht über Praktikum oder ähnliches schon Kontakte mit
der Industrie hat, kann gerne zu uns kommen, sofern das Thema zu den
Themen meiner Gruppe passt.
Und die Thematik hier oben, Informationsdienstleistung, IT
-Controlling, das sind alles Themen in Kooperation mit der Industrie.
Ja, das also zu der Gruppe soweit.