23 Geometrie I - Konvexe Hülle

• 23 Geometrie I - Konvexe Hülle
  • Einführung
  • Konvexe Hülle
    • Nagel und Schnur
    • Alle Kandidaten prüfen
    • Jarvis' March
    • Graham's Scan
    • Linear Scan
    • Konvexe Hülle testen
  • Schnitt von orthogonalen Liniensegmenten
    • Gibt es einen Schnitt?
    • Schnitte aufzählen
    • Schnitte zählen

$$

Disclaimer: Diese Mitschrift ist als Ergänzung zur Vorlesung gedacht. Wir erheben keinen Anspruch auf Vollständigkeit und Korrektheit. Wir sind jederzeit froh um Hinweise zu Fehlern oder Unklarheiten an [e-mail].

Wenn Sie an dieser Mitschrift mitarbeiten möchten, melden Sie sich hier.

Einführung

Heute wird's ganz leicht: Wir verlassen die Graphentheorie und beschäftigen uns mit der algorithmischen Seite der Geometrie.

Warum ist Geometrie überhaupt was algorithmisch Interessantes? Beim Sortieren, den Wörterbüchern, dem Hashing und allem was wir bis jetzt angeschaut haben handelte es sich immer um Mengen von Zahlen, also eindimensionalen Objekten. Nun betrachten

Wir stellen uns folgendes. In der 2 Dimensionalen Ebene, habe wir Punkten, die irgiendwie verteilt sind. Die Frage, die wir jetzt Stellen ist, dass wie koennen wir die konvexe Huelle erstellen. Die konvexe Huelle ist natuerlich die kleinste konvexe Huelle, die alle Punkte enthaelt.

Konvexe Hülle

Für eine Punktmenge in der Ebenen ist die konvexe Hülle, die kleinste konvexe Teilmenge der Ebene, welche alle Punkte erhält. Wir erinnern uns: Eine Menge ist konvex, wenn alle gewichteten Mittel von Punkten aus der Menge auch in der Menge liegen.

TODO Skizze

Wir beobachten, dass die konvexe Hülle immer durch ein Polygon bestehend aus einiger der Punkte beschrieben wird.

Wie koennen wir eine Algorithmus herausfinden, die diese keilste konvexe Polygon beschreibt?

Nagel und Schnur

Wie würden wir das physisch machen? Wir nehmen ein Brett ein, dass unsere euklidsche Ebene darstellt und schlagen einen Nagel für jeden Punkt ein. Nun nehmen wir eine Schnur und legen sie um alle Nägel herum und ziehen sie straff.
Ein solches Nagel & Schnur Verfahren kostet nur \O(n)$ Zeit. Aber wir haben im Rechner keine Nagel & Schnur Operation. 😢

Alle Kandidaten prüfen

Was können wir algorithmisch tun? Wir ueberlegen uns eine einfache Algorithmus

Pruefe jede Verbindung ob es auf der Huelle liegt. (Wie kann man das ueberpruefen ? Think about it!).

Wir verbinden zwei Pukten mir einer Gerade und schauen on alle uebrig gebliebene Punkten auf den gleichen Seiete der Gerade liegen.

Diese Gerade zu konsturieren kostet

$\mathcal{O}(1)$ und solche ahnliche Geraden soll man fuer alle andere Punkten konsturieren(

$\mathcal{O}(n)$). Weiters alle Punkten zu ueberprufen, ob die auf den gleichen Seite der Gerade liegt kostet

$\mathcal{O}(n)$???. Weiters sollen wir diese Operation fuer alle Punkten durchfuehren, deshalb bekommen wir als eine Gesamtlaufzeit von

$\mathcal{O}(n^3)$.

Jarvis' March

Versuchen wir den Schnur-Algorithmus zu simulieren. Starten wir am Punkt ganz links und lassen die Schnur gedanklich dort herunterhängen. Nun ziehen wir die Schnur nach rechts und möchten wissen an welchem Punkt die Schnur zuerst aneckt. Dazu bilden wir vom Startpunkt aus die Gerade zu jedem anderen Punkt und suchen diejenige mit der kleinsten Steigung (als dem steilsten Abfall). Anschliessend haben einen zweiten Punkt auf der Hülle gefunden und können das Herumziehen der Schnur von dort aus weitersimulieren.

Dieses Verfahren heisst Jarvis March, weil wir so um die Hülle herummarschieren.

starte mit einem Punkt auf der Hülle
wiederhole bis einmal rundherum
	ermittle den nächsten Hüllenpunkt 
	durch Inspektion aller Winkel

Jeder Schleifendurchlauf kostet

$\mathcal{O}(n)$ und wir wiederholen so oft, wie es Punkte auf der konvexen Hülle hat. Also:

$\mathcal{O}(n\cdot h)\subseteq \mathcal{O}(n^2)$. Das ist also schon viel besser als der naive Ansatz, insbesondere dann, wenn nur wenige Punkte auf der konvexen Hülle liegen.

Graham's Scan

Versuchen wir es wieder mal mit unserem Lieblingsalgorithmenentwurfsprinzip: Induktion!

Wir wählen einen extremalen Startpunkt

$s$ (zum Beispiel den ganz links unten)^[1] und sortieren die anderen Punkte zyklisch gemäss ihrem Winkel zu

$s$ im Gegenuhrzeigersinn^[2]. Nun machen wir Induktion über diese Punktereihenfolge und berechnen jeweils die konvexe Hülle der ersten

$i$ Punkte und speichern sie auf einem Stack.

TODO Skizze

Für einen neuen Punkt, wissen wir dass er auf der konvexen Hülle liegt. Wir fügen ihn auf den Stack und überprüfen ob die letzten drei Punkte immer noch eine Rechtsdrehung darstellen. Falls nicht, so können wir den zweitletzten Punkt der Hülle entfernen und wiederholen diesen Prüfschritt, bis wir wieder nur noch Rechtsdrehungen auf der Hülle haben.

Da jeder Punkt höchstens einmal auf die Hülle eingefügt und entfernt wird und wir nur so viele Drehungen testen, wie wir die Hülle verändern, kostet dieser Scan nach Winkel nur lineare Zeit. Das Teuereste ist also das initiale Sortiern.

Gesamtlaufzeit von diesem Graham's Scan ist somit

$\mathcal{O}(n\cdot \log (n))$

Linear Scan

Statt nach Winkel zu sortieren und dann radial durchzugehen, können wir auch lexikographisch, also von links nach rechts, sortieren und

	sortiere Punkte von links nach rechts
	spaziere lienar durch 
		falls zweimal gebogen, geh zurueck
		schau auf die Punkte, falls auf der Huelle ligt nimm
		sonst schau andere Punkte

Die Gesamtlaufzeit dieser Algorithmus ist

$\mathcal{O}(n\cdot \log (n))$.

Konvexe Hülle testen

Wie überprüfen wir, ob ein gegebenes Polygon wirklich konvex ist?
Wenn wir nur testen, ob wir nur Rechtsdrehungen haben, kann das schief gehen:

Wir müssen also aufpassen, dass sich das Polygon nicht selbst schneidet. Wie prüfen wir ob sich zwei Segmente schneiden?^[1]

Schnitt von orthogonalen Liniensegmenten

Gegeben eine Menge von waagrechten und senkrechten Liniensegmenten. Kreuzen sich zwei der Segmente?

Ein Anwendung für dieses Problem ist das Chipdesign. Wir haben Milliarden von Leiterbahnen und wollen rasch überprüfen, dass sich die Leiterbahnen nicht kreuzen.

Wie überprüfen wir überhaupt, ob sich zwei Liniensegmente kreuzen?^[1] Für je ein horizontales und vertikales Segment, beschrieben durch

$(x_l,x_r,y)$ und

$(x,y_u,y_o)$ müssen wir lediglich überprüfen, ob

$x_l\le x\le x_r$ und

$y_u\le y\le y_o$ gilt. Wir können also in konstanter Zeit zwei Segmente überprüfen.

Wie können wir nun für alle

$(\genfrac{}{}{0ex}{}{n}{2})$ Segmentpaare überprüfen ob sich zwei schneiden, ohne alle zu betrachten?

Gibt es einen Schnitt?

So wie vorher führen wir Induktion von links nach rechts durch. Wir stellen uns eine Linie vor, welche von links nach rechts geht. (genannt Scanline oder Sweepline)

Ereignisse entlang dieser Linie sind die sogenannten Haltepunkte. Also in unserem Problem zwei Punkte für die die horizontalen Segmente und einen Haltepunkt für senkrechte Segmente.

Für die horizontalen Segmente sagen wir, dass es schlafend ist, falls es noch komplett rechts der Scanline ist. Ein horizontales Segment ist tot, falls die Scanline schon komplett darüber hinweg ist. Falls die Scanline noch im Bereicht des Segments liegt, nennen wir das Segment aktiv.

Kommt nun ein vertikales Segment

$(x,y_u,y_o)$, so möchten wir wissen, ob es ein aktives Segment im Bereich

$[y_u,y_o]$ gibt. Wir müssen uns also die aktiven, horizontalen Segmente so vorrätig halten, dass wir sie nach der

$y$-Koordinate durchsuchen können.

Wir haben also drei Operationen:

• Beginn eines waagrechten Segmentes
  $(x_l,x_r,y)$: füge
  $y$ in die Datenstruktur ein.
• Ende eines waagrechten Segmentes
  $(x_l,x_r,y)$: entferne
  $y$ aus der Datenstruktur.
• senkrechtes Segment
  $(x,y_u,y_r)$: Suche nach Einträgen im Bereich
  $[y_u,y_r]$ in der Datenstruktur.

Die effizienteste Datenstrucktur für diese Operationen ist ein balancierter Suchbaum. Wir wählen deshalb einen AVL-Baum. Wir speichern die aktiven, horizontalen Segmente in den Blättern des AVL-Baums und ordnen nach

$y$-Koordinate. In einem solchen Blattsuchbaum benutzen wir die inneren Knoten nur als "Wegweiser", der zum Beispiel den grössten

$y$-Wert im linken Teilbaum speichert. Zusätzlich verknüpfen wir die Blätter in einer doppelt verketteten Liste damit wir die Elemente rasch in der

$y$-Ordnung rauf und runter gehen können. Diese verkettete Liste können wir leicht (d.h. ohne asymptotischen Mehraufwand) aufrecht erhalten, auch bei Rotationen des AVL-Baums etc.

Bei einem vertikalen Segment

$(x,y_u,y_o)$ suchen wir nun einfach nach

$y_u$ im Baum und finden den nächstgrösseren Schlüssel, also das nächsthöhere, aktive, horizontale Segment. Ist dessen

$y$-Koordinate kleiner als

$y_o$, so haben wir einen Schnitt gefunden! Andernfalls liegen alle aktiven horizontalen Segmente ausserhalb des Bereiches

$[y_u,y_o]$.

TODO Skizze

Mit dieser Datenstrucktur erreichen wir eine Gesamtlaufzeit von

$\mathcal{O}(n\log (n))$. Jede der

$\le 2n$ Operationen kostet

$\mathcal{O}(\log n)$ und das initiale Generieren und Sortieren der Haltepunkte kostet ebenfalls

$\mathcal{O}(n\log n)$.

Für einen Chipdesigener ist es aber nicht sonderlich praktisch zu hören: "Dein Design ist kaputt!" Oder: "Hier ist ein beliebiger Fehler!" Wir möchten lieber gleich alle Schnitte kennen.

Schnitte aufzählen

Um Schnitte Aufzaehlen zu koennen , berichten wir laut doppelt verketteter Blattliste, welche uns die Losung in

$\mathcal{O}(n\cdot \log (n)+k)$.

Schnitte zählen

Wenn wir einfach

$k$ wissen wollen machen wir uns folgende Ueberlegung. Wir schreiben in den Teilbaumen Anzahl der Blatter. Das machen wir fuer alle Teilbaume. Nach Bottom-Up Verfahren koennen wir mir einem einzigen Addition Anzahl der Baltter rechnen, aber die Frage jetzt waere, wie wir einen Update machen? Bereits beim Suchen, in anderen Worten unten gehen koennen wir diesen Update auf die Anzahl den Blaettern von Teilbaumen durchfuehren. Das nennt man Aggregat-Wert updaten. Wir beobachten, dass diesen Aggregat-Wert beim Einfuegen, Entfernen und beim Rotationen adjustierbar ist. Aber wie hilft diesen Aggregat-Wert uns? Wenn wir alle diesen Aggregat-Werte wissen, dann koennenn wir Anzahl der Knoten bzw. Blatter zwischen diesen beiden y-Punkte berechnen in dem wir die Teilbaume zwischen diesen y-Punkte betrachten. Das Resultat weaere einfach Summe alle Aggregat-Werte von den Teilbaumen, die sich zwischen diesen y-Punkte finden.(Die Gruppe diesen Teilbaumen nnnen einige als einen Schirm).

Die Anzahl diesen Teibaumen sund hoechstens logarithmisch viele also

$\mathcal{O}(\log (n))$.

TODO Skizze Kanonische Überdeckung des Intervalls

Damit können wir nun eine Anfrage nach den Anzahl Elementen in einem Interval rasch beantworten, egal wie gross die Antwort ist. Wir zählen also für jedes vertikale Segment die Anzahl Schnitte und addieren einfach auf. Damit ist auch die Gesamtlaufzeit

$\mathcal{O}(n\log n)$, egal wie gross die Antwort ist, also auch bei

$k\in \mathrm{\Omega }(n^2)$.