So, ich begrüße Sie zur Fortsetzung der Vorlesung effizienter
Algorithmen.
Nur kurz zu Beginn der Bemerkung nochmal zu den Prüfungen.
Ich habe bisher einen Wunsch für eine Prüfung im September.
Ansonsten habe ich keine explizite Wünsche für den 3.8.
Da habe ich, glaube ich, jetzt die Termine festgelegt.
Und wenn also jemand eine Prüfung im September haben möchte, muss er
das mitteilen.
Ich werde auf jeden Fall die Einladung jetzt so machen, dass ich alle
bis auf den einen für den 3.8.
zur Prüfung einlade.
Und wer dann an dem Termin nicht kann, muss das halt rechtzeitig
mitteilen, damit wir das noch verlegen können.
Gut, zur Vorlesung.
Es ging letztes Mal los mit algorithmischer Geometrie.
Ein Thema, das durchaus interessant ist.
Es geht um die Lösung geometrischer Probleme.
In vielen Anwendungen hat man damit zu tun.
Erstaunlich viele Anwendungen sind es.
Letztes Mal hatte ich hier diese Objekte aufgezeichnet und dabei ein
paar Probleme, die aufgelistet sind, einfach kurz illustriert,
visualisiert.
Überwachung von Galerien oder Geschäften.
Oder die Überschneidungsprobleme bei geometrischen Figuren, die man
für Layout oder für Darstellungen auf jeden Fall im Griff haben muss.
Zum Beispiel ein Anwendungsbereich, den ich letztes Mal gar nicht
erwähnt habe, ist der des Entwurfs von Leiterbahnen oder des Entwurfs
von Schaltkreisen.
Wenn Sie Leiterbahnen zeichnen im Full-Custom-Entwurf, dann zeichnen
Sie geometrische Objekte, im Prinzip Rechtecke.
Und da gibt es genaue Vorschriften, welche Überschneidungen dort
vorkommen müssen, genaue Regeln, wie weit sie sich überlappen müssen,
einzelne Rechtecke, die Leiterbahnenabschnitte charakterisieren.
Und da braucht man also auch effiziente geometrische Algorithmen.
So, was für Objekte, um welche Objekte geht es?
Lassen Sie mich das kurz auf Präsentationsmodus umschalten.
Es geht um verschiedenste Objekte, die dabei auftauchen können, in
unterschiedlichen Dimensionen.
Es geht los mit Punkten, die müssen irgendwo auf dem Bildschirm
dargestellt werden.
Punkte, ja, was für Punkte?
Das können Punkte auf einer Linie geraden sein, das können
unterschiedlich dimensionale Räume sein, in denen wir Punkte
betrachten, allgemein halt irgendein euklidischer Raum.
Und warum müssen wir hier sagen euklidischer Raum?
Es geht halt darum, dass wir eine bestimmte Metrik haben, um die
Abstände zwischen Punkten zu berechnen.
Wir haben halt hier den Rd angenommen mit euklidischer Metrik, wobei
das hier durchaus ein Problem sein kann.
Reelle Zahlen als Koordinaten für Punkte zuzulassen, hat gewisse
Probleme, weil nämlich reelle Zahlen relativ klein sein können, oder
relativ nah oder sehr dicht nebeneinander liegen.
Wir wissen, dass wir im Rechner nur eine gewisse Genauigkeit haben,
aber auch unsere Berechnungen haben nur gewisse Genauigkeiten.
Und wenn Sie also hier so eine Reihe Punkte haben, und ich male hier
so ein paar Punkte mal auf, im Prinzip liegen die ja, die liegen hier
eigentlich auf einer Linie.
Liegen die wirklich auf einer Linie, oder liegt einer rechts oder
links davon?
Es ist keineswegs klar, ob man das mit der nötigen Genauigkeit
feststellen kann.
Ich gehe darauf später nochmal ein.
Wir machen normalerweise Annahmen, dass so etwas nicht auftaucht.
Dass die Punkte gutartig sind, dass sie weit genug auseinander liegen,
sodass man eindeutig etwas darüber sagen kann, z.B.
dass dieser Punkt hier, wenn wir da eine Gerade durch die anderen
beiden legen, dass der rechts von dieser Geraden liegt.
Oder wenn wir so eine Gerade durchziehen, ist es halt klar, dass der
dritte Punkt links davon liegt.
Solche Aussagen muss man manchmal machen.
Und dafür ist es natürlich wichtig, dass man solche Aussagen auch
eindeutig, auch korrekt macht.
Die Grundannahmen werden sein, dass die Punkte so geartet sind, dass
keine großen Probleme auftauchen.
Man muss sich aber auch um die anderen Probleme kümmern, und darauf
gehe ich auch noch etwas ein.
Nächstes Objekt, das man sich anschaut, sind Geraden.
Ich hätte gerade hier Geraden reingezeichnet.
Eine Gerade ist allgemein eine eindimensionale Teilmenge des
eukalyptischen Raumes, gegeben durch einen Punkt und eine Richtung.
Das reicht, ein Punkt und eine Richtung.
Oder ich brauche zwei Punkte, dadurch habe ich auch eine Gerade
gegeben.
Dadurch kann ich eine Geradengleichung aufstellen.
Das wissen wir alle aus der Schulmathematik oder auch aus sonstigen
mathematischen Veranstaltungen.
Dann gibt es Linien oder Streckenkanten, irgendwelche Abschnitte auf
einer Geraden.
Da habe ich auf jeden Fall zwei Punkte, nämlich einen Anfangspunkt und
einen Endpunkt.
Da kann ich über die Länge seiner Strecke reden und kann auch darüber
reden, da kann ich mich dafür interessieren, wenn ich jetzt zwei
Strecken habe, die würden sich nicht überschneiden, die würden sich
überschneiden.
Solche Punkte kann man anschauen.
Also da reicht es nicht, wenn ich zwei Geraden betrachte, und da habe
ich Punkt und Richtung, da kann ich immer irgendeinen Schnittpunkt
feststellen, es sei denn, sie sind parallel.
Bei Linien muss ich, um zu entscheiden, ob sie einen Schnittpunkt
haben, halt auch die genauen Abschnitte mir angucken, auf denen
tatsächlich die Punkte liegen, damit in so einer Situation dieses
hier, dieses Linienstück hier, wenn wir die Gerade betrachten, die
dadurch definiert ist, würde es natürlich einen Schnittpunkt geben zu
der Linie oder zu der anderen Linie, aber so natürlich nicht.
Dafür braucht man Dinge wie, dass zum Beispiel dieser Punkt rechts von
der anderen Linie liegt.
Also hier, ein Beendpunkt.
So, Hyper-Ebenen, das ist eigentlich das Gegenteil.
Keine eindimensionale Teilmenge, sondern eine d-1-dimensionale
Teilmenge eines d-dimensionalen onklidischen Raumes.
Im dreidimensionalen wäre das halt eine ganz normale Ebene, im
zweidimensionalen ist eine hyper-ebenene Gerade.
Und, ganz wichtig, Polygone, Streckenzüge, also geschlossene
Kantenzüge im E2.
Normalerweise betrachten wir nur den E2.
Wir haben also eine Folge von Eckpunkten und verbinden diese Punkte
durch Liniensegmente.
Und das sind dann im E2, nennt man sie auch Polyeder oder Polytopen,
oder man kann natürlich anders.
Man kann natürlich, wenn man nicht den E2 betrachtet, im E2 sind das
Polygone.
Wenn man höhere Dimensionen betrachtet, dann haben wir Polyeder oder
Polytope.
Auch dort kann man eine ganze Reihe, eine Vielfalt von geometrischen
Problemen untersuchen.
Das machen wir aber nicht.
Wir beschränken uns hier auf den zweidimensionalen Fall, der ist schon
schwierig genug.
Und man sieht, dass es durchaus sehr unterschiedliche Arten von
Polygonen geben kann.
Wenn Sie sich dieses Polygone hier anschauen, ein Quadrat, oder dieses
hier oben, die unterscheiden sich dadurch, dass das eine konvex ist,
das andere konkav.
Bei dem oberen sehen wir halt, dass wir Punkte haben, die wir
miteinander verbinden, die die Verbindungslinie nicht vollständig im
Inneren.
Und dann gibt es auch so etwas wie hier unten, das ist noch anders, da
kann ich nicht so ohne weiteres sagen, was ist eigentlich das Innere
des Polygons, was ist das Äußere.
Bei den anderen drei Beispielen habe ich eindeutig einen inneren
Bereich und einen äußeren Bereich.
Bei dem verdrehten Viereck, dort rechts unten, kann ich nicht sagen,
was ist jetzt Innen und was ist Außen.
Also solche Fragen sind aber häufig wichtig, dass ich weiß, ob ein
Punkt innerhalb eines Bereiches liegt oder außerhalb eines Bereiches.
Und da müsste ich im Prinzip einen künstlichen weiteren Punkt hier
dazunehmen.
Und dann hätte ich natürlich zwei innere Bereiche und einen äußeren
Bereich.
Aber das wäre dann ein anderes Polygon.
Und Sie sehen, ansonsten haben wir beim Polygon immer nur eine Kante,
die reinläuft, eine, die rausläuft.
Was ich gerade reingemalt habe, diesen roten Punkt, das wäre ein
Punkt, bei dem zwei Kanten reinlaufen, also vier Kanten im Prinzip mit
dem verbunden sind.
Und das ist etwas, was wir normalerweise in Polygonen gar nicht
betrachten.
So etwas würden wir eigentlich als zwei getrennte Polygone auffassen.
So, wenn wir jetzt solche Objekte haben, wie modellieren wir die?
Zunächst schaut man sich an, was sind eigentlich hier die
Problemgrößen.
Das ist relativ eindeutig.
Wenn wir Mengen von Punkten haben, die Anzahl der Punkte.
Bei Geraden haben wir die Anzahl der Geraden zu betrachten, bei
Polygonen die Anzahl der Eckpunkte.
Das ist eigentlich offensichtlich, dass das die Problemgröße ist.
Datenstrukturen, auch relativ einfach, obwohl so einfach ist es gar
nicht.
Es hängt davon ab, was für Fragen man beantworten will.
Dafür muss man entsprechende Datenstrukturen machen.
Also, man macht häufig Suchanfragen, dafür brauchen wir Suchbäume.
Wir wissen, wie wir Suchbäume aufbauen.
Für einige Dinge ist es sinnvoll, ein Array zu verwenden.
Wenn ich also eine feste Menge von Punkten habe und keine Dynamik in
der Probleminstanz, dann kann ich auch eine andere Struktur nehmen.
Sobald ich Dynamik habe mit Einfügen und Löschen, sind immer Suchbäume
wichtig, wie wir festgestellt haben.
Ich kann Folgen von Punkten betrachten.
Bei den Polygonen muss ich ja Folgen betrachten.
Das heißt, da werde ich entweder ein Array verwenden oder eine lineare
Liste oder ein Vektor oder irgendetwas.
Dann gibt es einige Probleme, bei denen man Prioritätswarteschlangen
braucht.
Dann wird man so etwas wie ein Heap verwenden.
Also unterschiedliche Strukturen sind hier sinnvoll.
Bei den Suchbäumen gibt es übrigens bei geometrischen Problemen
einige, die man speziell für geometrische Probleme entworfen hat, die
noch besondere Eigenschaften haben.
Aufwand ist das Übliche.
Wir schauen uns an den Zeitaufwand, arithmetisch-logische Operationen.
Hier kommen auch Vergleiche vor.
Auch die logischen Operationen sind ja drin.
Wir können uns also nicht auf die arithmetischen Operationen
beschränken oder auf Vergleiche.
Wie bei den algebraischen Problemen hatten wir nur die arithmetischen
Operationen.
Bei den Sortieren-Suchverfahren hatten wir die Vergleichsoperationen
genommen.
Hier müssen wir beides berücksichtigen.
Platzaufwand ist auch klar, dass das eine Rolle spielt.
Was ich jetzt nicht betrachte, sind parallele Varianten von solchen
Verfahren.
Kann man aber alles auch parallelisieren, parallel betrachten.
Werde ich aber in diesem Abschnitt nicht weiter vertiefen.
Sondern hier geht es mir eigentlich mehr um so ein paar Prinzipien des
Algorithmenentwurfs, die wir jetzt noch... oder algorithmische
Werkzeuge, die hierfür entwickelt wurden, ganz interessant sind.
Wenn ich den Aufwand abschätze... also normalerweise haben wir immer
den Aufwand abgeschätzt, um ein Problem zu bearbeiten.
Bei der Auswertung eines Polynoms oder Matrixmultiplikationen oder
ähnliches.
Bei den Polynomenmultiplikationen oder Polynomen... nicht
Multiplikationen, sondern Polynomenauswertung hatten wir uns auch
einmal überlegt, dass man, sofern man mehrfach ein Polynom auswerten
muss, auch einen gewissen Aufwand reinstecken kann in die
Vorbereitung.
Und das ist das, was man hier auch macht.
Das werden wir gleich sehen.
Dass es manchmal sehr sinnvoll ist, wenn ich weiß, ich werde bezüglich
einer gewissen geometrischen Problemstellung viele gleichartige
Anfragen haben, dann macht es Sinn, sich entsprechende Datenstrukturen
zu konstruieren, durch die dann diese vielfachen Anfragen sehr
effizient ausführbar sind.
Der Zeitaufwand für die Vorbereitung kann dann vernachlässigt werden.
Und jetzt zeige ich also einfach ein paar typische Probleme, die man
in der algorithmischen Geometrie betrachtet.
Und das erste Problem, das ich hier anspreche, ist, ich habe eine
Menge von Punkten gegeben.
Und jetzt irgendwelche Punkte, was immer das ist, ist völlig egal.
Und ein achsenparalleles Rechteck, das irgendwie dort rüber geschoben
wird.
Sie gehen praktisch mit einem Fenster über Ihren Bildschirm.
Jetzt wollen Sie wissen, wie viele Punkte der Menge innerhalb des
Rechtecks liegt.
Also, Sie wollen wissen, wie viele Punkte der gegebenen Menge habe ich
mit meinem...
oder auch welche Punkte, das sind zwei unterschiedliche Dinge, welche
Punkte oder nur wie viele, liegen innerhalb des Rechtecks.
Das kann man natürlich ganz einfach feststellen.
Ein bisschen Überlegung, geometrische Überlegung, man muss ja nur
feststellen, ob er im Rechteck liegt oder nicht.
Das ist ganz einfach zu machen.
Also, für jeden Punkt stelle ich fest, wenn ich also hier den Punkt
betrachte, wie sind dessen Koordinaten.
Ich kann über den Vergleich der Koordinaten mit den Viereckpunkten,
mit den Koordinaten, ob der da drin liegt.
Punkte hier liegen offensichtlich eben drin, weil die Koordinaten
größer sind als die Koordinaten von den beiden unteren Punkten.
Und kleiner als die x-Koordinate von den rechten Punkten hier und
größer bei den x-Koordinaten als die beiden linken Punkte.
Also x-Koordinaten zwischen den beiden Werten x und x'.
y-Koordinaten zwischen y und y'.
Wenn das der Fall ist, liegt der Punkt drin.
Wenn er draußen ist, liegt er halt... oder wenn die Koordinaten
außerhalb sind, liegt er halt draußen.
Und damit kann man das einfach überprüfen.
Für n Punkte muss man das halt überprüfen.
Also muss man für jeden Punkt das überprüfen, ob er drin liegt oder
nicht.
Da habe ich offensichtlich eine Zeit von o von n.
Also ich weiß ja, ich muss also für ein beliebiges Rechteck, will ich
also wissen, wie viele Punkte sind dort drin.
Und der Aufwand dafür ist offensichtlich linear in der Anzahl der
Punkte.
Wie will man das auch kürzer machen?
Es könnte sein, dass alle Punkte drin sind.
Wenn ich also wissen will, wie viele das sind, muss ich ja alle mal
durchgehen.
Und also dieser Zeitaufwand hier, Platzaufwand ist offensichtlich, wir
haben nichts in die Vorbereitung gesteckt.
Und jetzt ist die Überlegung, kann ich sinnvoll eine Vorbereitung
machen, wenn ich weiß, ich habe eine bestimmte Punktmenge gegeben und
die Problemstellung, die jetzt kommt, ist, dass ich ein beliebiges
Rechteck da reinlege und ich will das für viele solcher Rechtecke
überprüfen können, wie viele Punkte da drin liegen.
Und diese Überlegung oder die Idee, wie man das machen kann, geht über
folgenden Ansatz.
Wenn ich wissen will, wie viele Punkte in dem Rechteck liegen, dann
schaue ich mir im Prinzip die vier Eckpunkte an.
Und ich kann im Prinzip die Frage, wie viele Punkte liegen im
Rechteck, transformieren in eine Frage, wie viele Punkte zum Beispiel
sind kleiner gleich x'y'.
Ich gucke mir diesen Punkt hier an und schaue mir an, wie viele Punkte
kleiner gleich x'y' sind.
Wieso ist das?
Also das ist sicherlich eine Anzahl von Punkten, die größer sein wird
als die Anzahl der Punkte, die im Rechteck sind.
Da habe ich sicherlich zu viele gezählt.
Jetzt schaue ich mir an, alle Punkte, die kleiner gleich sind, x'y'.
Das heißt, ich schaue mir jetzt an diese hier.
Die habe ich ja zu viel da drin.
Die muss ich abziehen.
Also ziehe ich diese Anzahl von Punkten ab.
Dann schaue ich mir an, alle, wobei ich sage ja einfach Punkt kleiner
gleich, wann ist x'y kleiner gleich x'y', genau dann, wenn x kleiner
gleich x' und y kleiner gleich y'.
Ja, das ist klar.
So, dann muss ich die abziehen, die kleiner gleich x' und y' sind.
Alle in diesem Bereich hier.
Jetzt habe ich aber den einen Punkt dort zweimal abgezogen.
Da habe ich ein zu viel abgezogen.
Ich muss also alle die nochmal dazunehmen, die kleiner sind als xy,
weil ich die zweimal abgezogen hatte.
Das muss ich noch einmal dazu.
Das muss ich aber explizit nochmal feststellen.
Wie kommt man auf die Idee, so etwas zu machen, wenn man doch nur
wissen will, welche Punkte oben in diesem Rechteck drin liegen.
Das, was wir gerade eben gemacht haben, sind vier Fragestellungen, bei
denen ich jeweils feststellen muss, wie viele Punkte kleiner gleich
als ein bestimmter Punkt sind.
Das ist doch viel schwieriger, viel mehr Aufwand.
Aber auf jeden Fall stellt man hier fest, ich kann das Problem
festzustellen, wie viele Punkte in einem Rechteck liegen, durch vier
Punktanfragen lösen bezüglich der Eckpunkte des Rechtecks.
Und jetzt überlegt man sich, gibt es eine Möglichkeit, wie ich solche
Punktanfragen lösen kann, für einen beliebigen Punkt in diesem
zweidimensionalen Bereich.
Kann ich das einfach mir vorher schon überlegen?
Das ist ja nur, ich kann ja einfach alle möglichen Punkte, die infrage
kommen, einfach mal durchgehen.
Und damit dann das vielleicht schneller machen.
Und es ist tatsächlich so, werden wir sehen, dass man mit ein bisschen
Vorbereitung in der Lage ist, diese Punktanfragen jeweils mit
konstantem Aufwand zu beantworten.
Nach entsprechender Vorbereitung.
Und wenn man das kann, dann wird...
Stimmt nicht, konstanter Aufwand nicht.
Ich brauche logarithmischen Aufwand, weil ich noch eine gewisse Suche
machen muss.
Also logarithmischer Aufwand für logarithmischen N, Anzahl der Punkte,
habe ich, um jeweils die Punktanfragen zu beantworten.
Und dann komme ich auf insgesamt, also von linearem Aufwand auf
logarithmischen Aufwand runter, für die Beantwortung der Frage, wie
viele Punkte liegen im Rechteck.
So.
Und jetzt geht es darum, wie kann man das Ganze jetzt vorbereiten?
Dazu mache ich Folgendes.
Ich habe meine Punktmenge, und das lege ich einfach durch jeden Punkt
zwei Geraden.
Eine vertikale, eine horizontale.
Dadurch unterteile ich meine Ebene in eine Reihe von Rechtecken.
Entsprechend diesen Koordinatenlinien.
Und ich habe auch noch Randflächen.
Also hier sehen wir, da sind solche Randflächen.
Einmal rum habe ich diese vier N-Randflächen.
Und außerdem habe ich eben eine ganze Reihe von Rechtecken.
Ich muss mir also im Prinzip jetzt alle diese Rechtecke merken.
Ich bestimme jetzt im Prinzip für jedes Rechteck so einen rechten
oberen Punkt.
Damit charakterisiere ich im Prinzip hier meine ganzen...
Also eigentlich brauche ich natürlich zwei Punkte jeweils.
Und damit kann ich jetzt so viele Rechtecke verwalten.
Das mache ich jetzt noch schwieriger.
Jetzt habe ich N² Objekte, die ich verwalten muss.
Jetzt mache ich Folgendes.
Ich berechne für jedes Rechteck.
Schauen wir uns also irgendein Rechteck an.
Für jedes Rechteck berechne ich die Anzahl der dominierten Punkte.
Also, das heißt, ich schaue mir irgendeinen Punkt an in solch einem
Rechteck.
Wenn ich also für dieses Rechteck hier rechts mache.
Irgendeinen Punkt in einem Rechteck.
Und schaue mir an, wie viele Punkte der Menge werden dadurch
dominiert.
Ich habe meine N-Punkte in der Menge.
Also, werden dominiert heißt, wie viele Punkte sind kleiner oder
gleich diesem X.
Und in dem Fall wäre das klar.
Da habe ich hier alles, was in dem Bereich liegt.
Das sind die Punkte, die kleiner gleich sind.
Und es ist klar, diese N-Punkte sind ja gerade rechte obere Ecken von
solchen Rechtecken.
Damit ist es klar, wenn ich irgendeinen Punkt in einem solchen
Rechteck nehme, wie dieses X hier.
Ich brauche das nur im Prinzip für einen Eckpunkt zu berechnen, welche
anderen Punkte kleiner sind.
Ich brauche nicht hier für jeden Punkt im Rechteck das genau zu
machen.
Weil ja in dem Rechteck selbst kein Punkt der Menge liegt.
So, jetzt überlegt man sich, wie man das hinkriegen kann.
Es ist klar, dass die Aussage für das Rechteck, in dem dieses X hier
liegt, natürlich bestimmt wird durch die Aussagen von den anderen
Punkten.
Man kann das mit dem Aufwand insgesamt N² hinbekommen.
Das würde bedeuten, konstanter Aufwand pro Rechteck.
Das macht man durch ein einigermaßen systematisches Verfahren.
Das will ich nicht im Einzelnen machen.
Ja, man macht das für die einzelnen Punkte, kann man feststellen.
Für die Rechtecke, bei denen jetzt die einzelnen Punkte rechts oben
sind, da kann man das sehr einfach feststellen, wie viele dominiert
werden.
Da brauche ich nur punktweise Vergleiche zu machen und ich kriege das
raus.
Wenn ich das für alle Rechtecke machen würde, hätte ich einen Aufwand
von N⁴.
N²-Punkte mit N²-Punkten vergleichen.
Oder nein, N² mit N-Punkten vergleichen, nicht mit N².
Einen Aufwand von N³ hätte ich.
Das wäre natürlich zu viel.
Das geht mit O².
Das will ich hier nicht im Einzelnen ausführen.
Kann man aber machen, weil die Eigenschaften so eines Rechtecks,
die Eigenschaften dieses Rechtecks sind bestimmt durch die
Eigenschaften der begrenzenden Linien und für die kann man das im
Prinzip festlegen.
Man macht das im Prinzip über diese 2N-Linien, über die kann man das
hinbekommen.
So, wenn ich das habe, für jedes Rechteck weiß ich, wie viele Punkte
dominiert sind.
Für jedes dieser festen Rechtecke.
Dann mache ich folgendes, ich sortiere die x-Koordinaten der Punkte.
Wir sehen das hier sortiert, aber im Rechner habe ich bisher nur eine
Menge von Punkten.
Die ist nicht notwendigerweise sortiert.
Ich habe hier diese Linien gemalt, die sind auch nicht
notwendigerweise sortiert.
Also muss ich einmal diesen Sortieraufwand reinstecken.
Dann habe ich also einmal den Aufwand NlogN für das Sortieren der
Koordinatenlinien.
Wozu brauche ich das?
Weil ich anschließend die Punktfragen beantworten muss.
Ich nehme ja irgendeinen Punkt hier, irgendeinen Punkt XY und zum
Beispiel diesen Punkt hier oben, der hat die Koordinaten XY.
Dann muss ich wissen,
welches Rechteck ist damit gemeint.
Ich muss ja in der Datenstruktur das auffinden können.
Ich bestimme also einfach durch binäre Suche auf den X- und Y
-Koordinatenlinien das Rechteck, in dem das XY liegt.
Ich habe das ja verwaltet irgendwo, kann ich darauf zugreifen.
Ich muss also den, ich habe ja, die sind ja irgendwie von X1 bis XN
und Y1 bis YN durchnummeriert.
Und da muss ich halt das richtige Koordinatenpaar finden, zwischen dem
jetzt das X bzw.
das Y liegt.
Und damit habe ich das Rechteck identifiziert.
Und für jedes Rechteck habe ich abgespeichert, wie viele Punkte
kleinergleich irgendeinem beliebigen Punkt in dem Rechteck sind.
Und damit habe ich die Anfrage beantwortet.
Die binäre Suche macht Aufwand Log N.
Und damit habe ich das Zeit für eine Punktanfrage Aufwand Log N.
Für vier Punktanfragen, wenn ich also das bestimmen will bezüglich
eines Rechtecks, muss ich halt dann den entsprechenden vierfachen
Aufwand berücksichtigen, aber das immer noch Log N.
Gut, ich habe jetzt das Verfahren hier oben nicht genauer erläutert,
aber ich denke, das Wesentliche hier ist jetzt zu sehen, dass ich
aufgrund einer gewissen Vorbereitung in der Lage bin, die einzelnen
Anfragen dann tatsächlich effizient zu bearbeiten.
Sehen Sie das hier einfach als ein Orakel an, das Ihnen diese Punkte
gibt oder diese Antworten gibt.
Solche Punktanfragen kann man in unterschiedlichster Art und Weise
machen.
Gerade eben hatten wir Rechtecke betrachtet.
Ein Rechteck ist ein relativ einfaches Gebilde.
Jetzt betrachte ich ein einfaches Polygon.
Also das, was hier unten ist, ist das typische Beispiel eines nicht
einfachen Polygons.
Da überschneiden sich zwei Kanten.
Ich hatte auf einer der ersten Folien auch schon ein nicht einfaches
Polygon angegeben.
Also ein Polygon ist einfach, wenn die Ebene durch das Polygon in
genau zwei Bereiche aufgeteilt wird.
Einen inneren Bereich und einen äußeren Bereich.
Und das ist bei dem Beispiel dort nicht der Fall.
Und jetzt ist die Frage, ich habe irgendeinen Punkt in einem einfachen
Polygon.
Die sieht gar nicht so einfach aus, aber sie ist einfach.
In dem Sinne, wie ich es gerade definiert habe.
Das ist ein einfaches Polygon, weil der Bereich in einen inneren und
äußeren eingeteilt wird.
Und die Frage ist, wenn ich irgendeinen Punkt habe, also das hier ist
jetzt mein Punkt Q.
Liegt der innerhalb oder außerhalb?
Wenn Sie da so rauf gucken, das sehen Sie nicht sofort.
Stellen Sie sich das als praktisches Problem vor.
Sie haben hier einen Landwirt mit seinem Haus.
Und dahinten steht nicht der Buchstabe Q, sondern eine Kuh.
Und der Landwirt steht hier und möchte gerne wissen, diese Kuh
dahinten, ist die eigentlich noch auf der Weide oder ist die
ausgebrochen?
Und er schaut einfach auf diese komplizierte Weide rauf, mit seinem
Fernblas.
Und die Frage ist, wie kann er feststellen, wenn er darüber guckt, ob
die Kuh in der Weide ist oder außerhalb von der Weide?
Und das ist ganz einfach.
Er steht ja außerhalb, in diesem Fall.
Das weiß er, wo er steht.
Wenn er außerhalb ist, dann zählt er einfach die Anzahl der Zäune, die
zwischen ihm und der Kuh liegen.
Und wenn diese Anzahl der Zäune gerade ist, dann heißt das, er ist
einmal rein und wieder raus.
Rein und wieder raus und wieder rein.
Und bei einer geraden Fall wäre er wieder raus.
Dann würde er immer rein-raus gehen.
Wenn er aber ungerade ist, dann weiß er, die Kuh ist drin.
Also muss man nur zählen die Anzahl der Linien des Polygons, die durch
die Verbindungslinie zwischen dem äußeren Beobachter und diesem Punkt
geschnitten werden.
Wenn es gerade ist, ist der Punkt draußen.
Wenn es ungerade ist, ist der Punkt drinnen.
Sehr praktisches Problem.
Können Sie sich auch so überlegen, wenn Sie durch Australien fahren
und Sie wissen, Sie starten mit Ihrem Fahrzeug irgendwo außerhalb
einer Weide.
Jetzt fahren Sie durch die Landschaft und ab und zu mal sind dort
diese Gitter oder die Zäune über die Straße rüber, die dort einfach
als Metallgitter vorkommen.
Sie wollen abends ihr Zelt aufschlagen, wollen aber nicht gerne
innerhalb der Weide übernachten, sondern wollen außerhalb der Weide
übernachten.
Sie müssen nur zählen, ob Sie eine gerade oder ungerade Anzahl von
Zäunen überfahren haben.
Sie wissen, ob Sie in der Weide sind oder außerhalb der Weide sind.
Ganz einfach festzustellen.
Also, das nennt man formal die Strahlmethode.
Wir betrachten eine beliebige Gerade durch diesen Punkt Q.
Hier nochmal gestrichelt angedeutet.
Und jetzt bestimmt man einfach die Anzahl der Schnittpunkte der
geraden Mitkanten des Polygons auf dem Weg von Q nach draußen.
Genau das haben wir gerade eben gemacht.
Und damit haben wir also dieses Problem gelöst.
Aufwand ist natürlich linear, weil Sie überprüfen müssen für jede
Kante des Polygons, ob sie geschnitten wird durch diesen Strahl oder
nicht.
Also, hier haben wir keine Vorbereitung.
Es ist die Frage, geht das besser.
Also nach dem ersten Problem wird man vorsichtig mit der Frage, kann
man das eventuell schneller hinkriegen oder nicht.
In diesem Fall kann man für beliebige Polygone das nicht verbessern.
Weil das ist zu unstrukturiert.
Das andere war ein strukturiertes Problem.
Dieses hier wird durch die beliebige Lage der Polygonkanten
unstrukturiert.
Aber jetzt schauen wir uns als nächstes ein etwas anderes Polygon an.
Immer noch einfach, aber sogar sehr einfach, weil es auch noch konvex
ist.
Also hier haben wir ein typisches konvexes Polygon.
Das daneben ist nicht konvex.
Und die schöne Eigenschaft ist, wenn Sie einen beliebigen Punkt nehmen
innerhalb dieses konvexen Polygons, dann wird jeder Strahl nach
draußen nur eine einzige Kante schneiden.
Wenn Sie ein nicht konvexes Polygon haben, dann gibt es Strahlen von
dem Punkt aus nach draußen, die mehrere Kanten schneiden.
Beim konvexen Polygon nur eine Kante.
Und das kann man ausnutzen.
Wenn ich weiß, ich habe irgendeinen Punkt R hier oder irgendeinen
Punkt im Inneren eines konvexen Polygons, dann schneidet also jeder
von R ausgehende Strahl das Polygon genau einmal.
Ich kann sogar Folgendes machen.
Das kommt jetzt gleich.
Ich nutze das aus, um systematisch festzustellen, ob der Punkt innen
oder außen ist.
Und zwar, das kommt jetzt auf...
Ich nehme die nächste Folie, da steht es drauf.
Hier ist die Idee.
Ich habe diesen Punkt R.
Und jetzt teile ich mein Polygon auf in Sektoren.
Ich habe also hier meinen Punkt R.
Dieser Punkt R, beliebiger Punkt im Inneren des Polygons, teilt mein
Polygon auf in Sektoren.
Also, das ist zum Beispiel ein Sektor.
Ich habe einen beliebigen Punkt Q.
Und für diesen Punkt Q möchte ich feststellen, liegt er im Inneren
oder im Äußeren.
Dazu kann ich jetzt einfach sagen, ich muss zunächst mal wissen, in
welchem Sektor liegt dieser Punkt Q bezogen auf den Punkt R im Inneren
des Polygons.
Diesen Sektor kann ich suchen durch binäre Suche.
Für binäre Suche brauche ich eine lineare Anordnung.
Die lineare Anordnung bekomme ich, indem ich einfach einmal hier
radial rumlaufe.
Das heißt, ich betrachte von dem R aus eine Folge der Polygonpunkte
und laufe dann einfach einmal hier rum.
Ich kann ja Polarkoordinaten zu den einzelnen Polygonpunkten
bestimmen.
Und kann feststellen, in welchem Sektor liegt jetzt dieser Punkt Q.
Dessen Radialkoeffizienten kann ich auch bestimmen.
Und damit weiß ich, in welchem Sektor dieser Punkt Q liegt.
Wenn ich jetzt feststellen will, ob er innen oder außen liegt, muss
ich nur feststellen, ob er in diesem Sektor innen oder außen liegt.
Das heißt, ich muss das nur vergleichen mit dieser Kante.
Verbindungslinie zwischen PI und PI plus 1.
Und da muss ich also nur feststellen, liegt der Punkt rechts oder
links von der Kante.
Wenn er rechts liegt, ist er draußen, wenn er links liegt, ist er
drinnen.
Und diese Aufgabe ist also jetzt eine Aufgabe, die man lösen muss.
Man sieht, auch hier haben wir das Problem reduziert auf ein
Teilproblem.
Wir müssen feststellen, ob ein Punkt links oder rechts von einer
Geraden liegt.
Und das ist ja einfach zu lösen.
Wie macht man das denn?
Fällt man da irgendwie das Lot da drauf, oder wie macht man das?
Die Idee ist auch hier relativ einfach, ein bisschen Geometrie.
Es gibt zunächst mal diese beiden Möglichkeiten.
Wir haben hier eine beliebige Anordnung, drei Punkte.
Und wir haben einen Winkel QRPI.
Wenn wir so durchlaufen, habe ich mich von QR nach PI einmal links
herum gedreht.
Das war eine Linksdrehung.
QRPI in diesem Fall ist eine Rechtsdrehung.
Also geht es jetzt darum, habe ich wieder ein anderes Problem.
Nicht, liegt ein Punkt links oder rechts von einer Geraden, sondern
ist ein Winkel eine Rechtsdrehung oder eine Linksdrehung?
Und das ist durchaus wichtig.
Interessante andere Fragestellung.
Und das gucken wir uns jetzt nochmal ein bisschen anders an.
Das linke Bild, hier einfach etwas anders dargestellt.
Wir gucken uns bestimmte Flächen an.
Und das, was wir bestimmen wollen, ist also der Inhalt des Dreiecks,
das von QR und PI aufgespannt wird.
Und wie kann man dieses Dreieck bestimmen?
Ich habe hier einige Flächen unterschiedlich schraffiert.
Die Fläche dieses Dreiecks, also ich möchte dieses Dreieck hier genau
bestimmen, ist durch diese Formel gegeben.
Wie kommt diese Formel zustande?
Ist ganz einfach.
YI plus Y halbe mal XI minus X.
XI ist dieser Punkt hier.
X ist der Punkt.
Und YI ist also diese Distanz, dieser Teil.
Und Y ist der Teil.
Ich schaue mir einfach die Fläche des Trapezes an, das hier
aufgespannt wird.
Diese Trapez.
Die Fläche dieses Trapezes ist offensichtlich YI plus Y halbe mal XI
minus X.
Das ist die Fläche dieses Trapezes.
Und jetzt nimmt man das Gleiche im Vergleich zwischen den Punkten Q
und R.
Dann hat man dieses Trapez hier betrachtet, die Fläche.
Addiert man dazu.
Wenn ich die beiden addiert habe, habe ich aber genau diesen Bereich
hier zu viel da drin.
Ich will ja nur die Fläche des Dreiecks haben.
Also ziehe ich das wieder ab.
Und das Trapez hat gerade die Fläche, die hier abgezogen wird.
Das heißt, ich habe hier ganz einfache Berechnungen.
Ich muss nur so ein paar Additionen, Subtraktionen machen und ein paar
Modifikationen.
Und dann natürlich auch noch hier durch zwei dividieren.
Aber das ist ja auch eine einfache Operation.
Durch zwei dividieren ist einmal shiften.
Also das sind sehr einfache Operationen.
Ich brauche keine komplizierten Winkelberechnungen zu machen.
Also wenn Sie fest sind, Sie würden normalerweise denken, das mache
ich irgendwie mit Sinus und Kosinus und irgendwelchen Dingen.
Braucht man hier nicht.
Keine trigonometrischen Funktionen.
Ich berechne einfach die Fläche dieses Dreiecks.
Wieso berechne ich die Fläche des Dreiecks?
Was hilft mir das?
Stellen Sie sich vor, wir hätten diese Situation.
Dann würde ja das so aussehen, dass wir hier den Punkt haben.
Jetzt hätten wir einmal dieses Trapez berechnet, dann dieses Trapez
und ziehen davon ab die Fläche dieses Trapezes.
Und wenn wir das abziehen, dann wird daraus ein negativer Wert.
Das heißt, das was uns interessiert, ist eigentlich nur, ob der Wert,
der hier berechnet wird, positiv oder negativ ist.
Ist der größer 0, weiß ich, dass der Punkt links liegt von meiner
Geraden.
Dann ist das diese Situation.
Ist der Wert negativ, dann habe ich diese Situation.
Und das was hier oben steht als Formel, die ich berechnen muss, kann
ich ein bisschen allgemeiner aufschreiben als gerade diese
Determinante.
Da werden genau diese Operationen gemacht, ich muss den Wert nur noch
durch zwei teilen.
Also ein halbmal der Wert dieser Determinante, in dem die drei Punkte
genau in der Art vorkommen, also q, r, p, i in der Reihenfolge,
Koordinaten so aufgeschrieben.
Davon die Determinante berechnet und dann muss noch der Einzelrechts
daneben berücksichtigt werden, damit das richtig hinkommt.
Das ist genau der Wert, den ich berechnen muss.
Keinerlei trigonometrischen Funktionen berechnet, sondern ich brauche
hier nur ganz einfache Multiplikationen, Additionen zu machen.
Eine Division durch zwei.
Das Problem ist nur, was mache ich?
Das hatte ich vorhin schon angesprochen.
Ich weiß, das sind alles Reelle Werte der einzelnen Koordinaten.
Und wenn dieser Punkt q sehr nah an der Verbindungslinie liegt, also
wenn ich hier so eine Gerade habe und der Punkt liegt irgendwo da ganz
nah dran, dann kann das zu Problemen führen.
Aber wir gehen in der Regel davon aus, dass wir die sauber voneinander
trennen können.
Wenn man das nicht kann, muss man durchaus einige andere Überlegungen
noch machen.
Aber man könnte einfach sagen, man lässt nur Punkte zu, die einen
gewissen Mindestabstand voneinander haben.
Das wäre einmal eine Vorbereitung und dann kann man das Verfahren so
laufen lassen.
Also, Interpretation ist jetzt klar.
Wenn der Wert größer 0 ist, das ist der Fall, der hier oben angedeutet
ist, dann ist der Wert, der den Flächeninhalt positiv berechnet.
Das heißt, q liegt auf der linken Seite.
Und wenn es kleiner ist, dann habe ich eine Rechtsdrehung, dann ist
der Punkt rechts davon.
Und damit habe ich also genau die Antwort, die ich brauchte.
Und der Aufwand insgesamt für den Algorithmus besteht also jetzt
darum, dass ich einmal, also zur Vorbereitung, erstmal den Sektor
bestimmen muss.
Den Sektor zu bestimmen ist, naja, ich sage hier in linearer Zeit
möglich, also ich kann das in linearer Zeit vorbereiten.
Das geht nur, wenn ich das beim konvexen Polygon, die Punkte bereits
radial sortiert vorliegen habe.
Das muss schon der Fall sein.
Wenn das nicht der Fall ist, dann müsste ich die erst noch radial
sortieren, das wäre dann Aufwand nlog n.
Wenn die schon radial sortiert sind, und wir nehmen in der Regel an,
dass die, so wie es hier steht, der Reihe nach nummeriert sind, geht
irgendwo mit dem untersten Punkt los, P1, P2, P3 usw.
Dann weiß ich genau, wie die Punkte verbunden sind und genau in der
Reihenfolge.
Und dann brauche ich die nicht nochmal zu sortieren, um diese Sektoren
dann bestimmen zu können mit dieser Punktanfrage.
Und der Aufwand danach ist ja konstant, um festzustellen, rechts oder
links, haben wir gerade eben gesehen, wie das geht.
Also ist dann der Aufwand für die einzelne Anfrage logarithmisch, im
Wesentlichen der Aufwand, um den richtigen Sektor zu bestimmen.
Und jetzt haben wir das Ganze gerade eben vereinfacht betrachten
können, weil das Polygon konvex war, natürlich auch einfach.
Und die Frage ist, was sind das eigentlich für Eigenschaften?
Wie kann man die eigentlich bestimmen?
Also, woher weiß ich, ob ein Polygon einfach ist oder nicht?
Wir haben gesagt, einfach ist es dann, wenn das Polygon die Ebene in
genau zwei unterschiedliche Bereiche teilt.
Hier habe ich ein Beispiel, wo die Ebene in drei verschiedene Bereiche
geteilt wird.
Nicht einfach, zwei Kanten überschneiden sich.
Und das heißt, was man machen kann, ist, ich kann einfach je zwei
Kantenpaare mir hernehmen und überprüfen, ob die sich überschneiden.
Das wäre aber ein Aufwand von n².
Ich habe n solche Liniensegmente.
Wenn ich das überprüfen will, der jeweilige Überprüfungsaufwand ist
konstanter Zeit machbar.
Das heißt, ich habe hier für einen naiven Ansatz Zeit n².
Und der kluge Ansatz würde halt versuchen, das zu reduzieren.
Und jetzt kommt eine weitere Technik.
Ich nehme ein Planesweep-Verfahren, also ein Ebenenfegen-Verfahren auf
Deutsch.
Planesweep.
Ich fege die Ebene einmal ab.
Und die Idee ist ganz einfach.
Ich nehme eine Linie und bewege diese Linie durch meinen Bereich, der
die interessanten Punkte enthält und die interessanten Objekte
enthält, einfach durch.
Ich komme irgendwann auf der rechten Seite wieder raus.
Und irgendwann erreiche ich irgendeinen Punkt da drin, den ersten
Punkt.
Den zweiten Punkt, den dritten Punkt, den vierten Punkt, den fünften
Punkt.
Ich werde also... auch das ist eine Annahme.
Ich habe das jetzt schnell so... bin ein bisschen ausgewichen.
Man nimmt immer an, dass nie zwei Punkte die gleichen x-Koordinaten
haben.
Noch so eine Annahme.
Wenn das der Fall ist, muss man Sondermaßnahmen ergreifen.
Aber um die Algorithmen vorzustellen, kann man diese Anfangsannahmen
machen.
Wenn man so ein Ding tatsächlich implementiert, muss man Sonderfälle
betrachten.
So.
Was passiert an diesen Punkten?
Wenn ich ganz rechts angelangt bin, an dieser Stelle hier, dann heißt
das, ich habe einen Punkt, von dem gehen zwei Kanten aus.
Und ich kann sofort feststellen, ob... gut, diese zwei Kanten
schneiden sich natürlich in diesem Punkt, weil die beiden davon
ausgehen.
Die können sich nicht nochmal schneiden.
Ich kann also weitergehen nach rechts.
Ich komme zum nächsten Punkt.
Von dem geht natürlich auch eine Kante aus.
Diese Kante hier.
Ich weiß aber, das habe ich mir hier drauf gemerkt, hier war eine
Kante...
oder hier hatte eine Kante begonnen, mit Koordinaten.
Bestimmten Koordinaten von Anfangs- und Endpunkt.
Und ich füge jetzt eine neue Kante ein, in meine Datenstruktur, die im
Prinzip sich bezieht auf das, was ich an Ereignissen auf dieser Linie
habe.
Auf der vertikalen Linie.
Und ich weiß, da gibt es bereits eine Kante.
Und es kommt eine neue Kante dazu.
Und ich kann feststellen, überschneiden sich die beiden Kanten.
Machen sie nicht.
Kein besonderes Ereignis.
Ich merke mir aber, dass ich jetzt zu der Kante gekommen bin.
Ich gehe weiter, komme zu diesem Punkt.
Da hört die eine Kante auf.
Ich kann also den Eintrag von meiner Linienstruktur löschen.
Ich muss eine neue Kante hinzufügen.
Ich muss jetzt diese Kante, den Eintrag über diese Kante, vergleichen
mit dem Eintrag über die Kante, die ich hier oben gespeichert hatte.
Ich stelle fest, die beiden überschneiden sich nicht, weil sie nicht
weit genug laufen.
Wenn sie länger laufen würden, würden sie sich überschneiden.
Dann gehe ich wieder weiter, komme zu dem Punkt hier oben.
Auch von dem geht eine Kante nach rechts raus.
Ich stelle fest, keine Überschneidung.
Ich gehe weiter, komme zu diesem Punkt.
Hier laufen zwei Kanten los.
Und jetzt werden hier Kanten eingetragen, diese Kante und die Kante.
Und da kann ich jetzt eine Überschneidung feststellen.
Also ich kann...
Ich habe hier nebeneinander liegende Ereignisse.
Das Ereignis ist hier gespeichert, das ist gespeichert, die beiden
liegen übereinander.
Und ich kann feststellen, die beiden Kanten, die schneiden sich
tatsächlich.
Man sieht, dass man auf dieser Linie im Prinzip stets nur
Eigenschaften abspeichert, die sich auf die gerade aktiven Kanten
beziehen, die gerade durch diese Vertikale betroffen sind.
Und wenn sich zwei Kanten schneiden, dann nur dadurch, dass ich
übereinander liegende Ereignisse im Prinzip habe.
Diese hier liegen genau nebeneinander.
Nur die Kanten, die von den Punkten ausgehen, können sich überhaupt
schneiden.
Mit anderen kann es keine Schnittpunkte geben.
Und insofern habe ich hier immer nur ganz lokal Entscheidungen zu
treffen.
Und ich muss also nur über diese Haltepunkte hinweg meine Kante oder
meine Linie, die vertikale Linie über diese Ebene hinweg bewegen.
Ich habe eine Reihe Ereignisse, die dabei auf dieser Ebene oder auf
dieser Linie auftauchen oder auf dieser Geraden.
Die Ereignisse verwalte ich in einer effizienten Art und Weise in
einer gewissen Baumstruktur.
Und damit kann ich an jedem Haltepunkt diese Frage über Schneiden sich
zwei Kanten mit konstantem Aufwand lösen.
Beziehungsweise es ist kein konstanter Aufwand, ich habe eventuell
hier logarithmischen Aufwand, um den richtigen Punkt zu finden, an dem
ich das einsortieren muss in diese Suchstruktur.
Also habe ich an Endpunkten logarithmischen Aufwand.
Dieser logarithmische Aufwand kommt immer dadurch, dass ich in einer
Suchstruktur einen neuen Punkt einfügen muss.
Und ich muss den richtigen Ort für das Einfügen finden.
Das ist immer ein Aufwand Log N.
Und damit habe ich insgesamt einen Aufwand von N Log N.
Und das ist die Idee von dem Plane Sweep.
Und das, was man hier macht, ist das, was hier steht.
Ich reduziere das Problem, das ich habe, durch Plane Sweep, auf eine
Folge von Problemen in einem d-1 dimensionalen Raum.
Wenn ich einen d-dimensionalen Raum habe, schaue ich mir das an auf
einem eindimensionalen Objekt, nämlich auf dieser Linie.
Eine Folge von Ereignissen auf einem eindimensionalen Objekt.
Und das ist die interessante algorithmische Technik, die man hier
einsetzt.
Durch diese Reduktion des Problems auf etwas anderes, auf dieser
eindimensionalen Geraden, kann ich das Problem insgesamt effizienter
lösen.
Plane Sweep.
Ein ganz wichtiges Prinzip.
Damit kann man eine ganze Reihe von Problemen in der algorithmischen
Geometrie auf effiziente Art und Weise lösen.
Und das, was man hier, hier ist es nochmal angedeutet, wie man das
macht, im Prinzip löst man hier so eine Art
Intervallüberschneidungsproblem.
Denn die Projektion dieser Linien auf die Geraden, das sind im Prinzip
Intervalle.
Wenn ich mir irgendeine Kante anschaue, auf meiner Linie, diese Kante
hier, ist ja hier drin ein Intervall auf der Linie.
Wenn ich hier rüber laufe, habe ich also eine Reihe von Intervallen.
Und solange sich die Intervalle nicht überschneiden, habe ich auch
keinen Schnittpunkt der Linien.
Nur wenn sich Intervalle überschneiden, habe ich Schnittpunkte.
Insofern reduziere ich das Problem der Überschneidung von Linien auf
ein Problem Überschneidung von Intervallen.
Und ich habe immer Operationen, irgendwo lokal auf meiner Linie.
Und wenn also hier Punkte eingefügt werden, dann kann ich feststellen,
ob sich auf der Linie jetzt hier irgendwelche Überschneidungen
ergeben.
Und man sieht in dem Fall ergeben sich Überschneidungen der
Intervalle, die gerade aktiv sind.
Also das ist in dem Fall das Linienüberschneidungs- oder
Schnittproblem auf ein Intervallüberschneidungsproblem reduziert.
Und ich brauche also nur diese Linie über diese Haltepunkte hinweg zu
bewegen.
Und die Haltepunkte sind die Anfangs- und Endpunkte der Kanten des
Polygons.
Also diese Punkte, die gerade die Linien definieren.
Und diese Intervallüberschneidungsprobleme kann ich eben jeweils
schnell lösen.
Ich muss nur wissen, an welcher Stelle bei der auf der Linie
gespeicherten Intervalle bin ich gerade.
Das geht in logarithmischer Zeit.
Und ob sich jetzt benachbarte Intervalle bzw.
durch den Eintrag eines neuen Intervalls oder die Veränderung eines
dort bisher abgespeicherten Intervalls eine Überschneidung ergibt, das
kann ich dann in konstanter Zeit feststellen.
Hier sind die Operationen an den Haltepunkten nochmal genau angegeben.
Ich glaube, ich kann darauf verzichten, das alles nochmal hier
aufzuführen, wie das exakt abläuft.
Ich habe das gerade eben aufgeführt oder versucht anzudeuten, wie man
das macht.
Und hier sind die Operationen nochmal explizit angegeben.
Schauen Sie sich das an.
Ich erwarte nicht, dass Sie in der Prüfung wissen, wie genau die
einzelnen Operationen an den Haltepunkten hier laufen.
Also Sie müssen mir nicht diese drei Punkte hier alle vorbeten können.
Aber was ich von Ihnen wissen will, ist, ob Sie eben die Idee dieses
Planesweep verstanden haben, was man dort eigentlich macht.
Und wie man eben dann auf den logarithmischen Zeitaufwand kommt.
Und es ist eben so, dass man jede Kante genau einmal einfügt und
wieder löscht.
Da haben wir also insgesamt an diesen Haltepunkten N-mal
logarithmischen Aufwand, den richtigen Ort zu finden.
Der Platz, den man braucht auf dieser vertikalen Linie, ist linear.
Wenn ich Pech habe, könnte es sein, dass alle Kanten gleichzeitig
abgespeichert sind.
Das ist ein sehr extremer Fall, taucht normalerweise gar nicht auf.
Größenordnung N als Platz muss natürlich irgendwo das ganze Problem
abspeichern.
Weniger habe ich hier, also geht hier auf keinen Fall.
Und das ist schon das Problem gewesen.
War das ausreichend jetzt zunächst mal?
Ja?
Gut.
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 das ist für ein Polygon, 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.
Und 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.
Und das ist zunächst einleuchtend, dass 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 hier 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.
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,
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 eine 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?
Ist das irgendeine Menge von Punkten, irgendwie gegeben als Liste?
Und ich möchte wissen, welche sind die Extrempunkte?
Man könnte sagen, naja, schau ich mir doch an, das mit dem Dominieren.
Das war doch eine Möglichkeit, wenn ich weiß, also ein Punkt wird von
keinem anderen dominiert.
Das ist 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 rum.
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 PQR aus M liegt.
Also wir nehmen an, dass PQR und X alles Elemente der Menge sind.
Und das X ist also ungleich PQ 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.
PQ 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 Punkt 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 sie angeordnet sind.
Ich habe die Punkte gefunden.
Ich weiß, sie liegen am Rand eines konvexen Polygons.
Dann muss ich nur einen 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 N³ für den ersten Schritt.
Ich habe ja N³ pro Punkt.
Das ist ein Aufwand von N³ insgesamt.
Also im schlechtesten Fall natürlich nur.
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.
Wenn ich H-sortierte Extrempunkte habe, ist das H log H nochmal als
Aufwand.
Und der Platz ist natürlich O von N für meine N Punkte.
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.
Jetzt müssen Sie feststellen, in welcher Reihenfolge sie liegen.
Ich verweise immer wieder darauf, 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 das so wie 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.
Und 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 den 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 her, 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 hergenommen 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.
Und 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 das eine Rechtsdrehung ist, dann ist das bezüglich des inneren
Bereichs hier ein nichtkonkaber Bereich.
Das heißt, der Punkt P2 ist sicherlich kein Extrempunkt.
Weil ja eigentlich diese beiden durch P1 und P3 verbunden sein
müssten.
Das heißt, ich vergesse den Punkt P2, dann habe ich einen neuen Punkt
dazugenommen.
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
diesen neuen Punkt, der jetzt dazu gekommen ist, eventuell zu einer
Rechtsdrehung kam 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, wie 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.
Der Gram-Scan ist 1972 entwickelt worden.
Jetzt gerade vor ein paar Wochen hat der Kurt Mehlhorn 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 ein paar andere Verfahren
noch, um konvexe Höhlen zu bestimmen.
Man sieht daran eben auch 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.