In der algorithmischen Geometrie ist es oftmals von Bedeutung, Konfigurationen von Punkten zu beurteilen, die sich in einer Ebene befinden. Wichtig ist hier in vielen Fällen die konvexe Hülle, welche die Punkte bilden. Die konvexe Hülle ist das kleinste Polygon in der Ebene, welches alle Punkte umschließt. Dieses Polygon soll ermittelt werden. Da es aus praktischen Erwägungen immer wieder vorkommt, dass Punkte zwischenzeitlich entfernt und wieder hinzugefügt werden, wäre es wünschenswert, wenn solche Anpassungen algorithmisch nicht so teuer wären, wie eine Neuberechnung. Genau dies meint der Begriff dynamische Verwaltung.
1 Einleitung
In der algorithmischen Geometrie ist es oftmals von Bedeutung, Konfigurationen von Punkten zu beurteilen, die sich in einer Ebene befinden. Wichtig ist hier in vielen Fällen die konvexe Hülle, welche die Punkte bilden. Die konvexe Hülle ist das kleinste Polygon in der Ebene, welches alle Punkte umschließt. Dieses Polygon soll ermittelt werden.
Da es aus praktischen Erwägungen immer wieder vorkommt, dass Punkte zwischenzeitlich entfernt und wieder hinzugefügt werden, wäre es wünschenswert, wenn solche Anpassungen algorithmisch nicht so teuer wären, wie eine Neuberechnung. Genau dies meint der Begriff dynamische Verwaltung.
2 Grundlagen
2.1 Theoretische Grenzen der Laufzeit
Die minimale Grenze der Laufzeit von 0(n log n) für die Konstruktion der konvexen Hülle einer allgemeinen, nicht weiter eingeschränkten Punktwolke kann gezeigt werden. Natürlich könnten spezialisierte Algorithmen unter bestimmten Nebenbedingungen schneller sein.
2.2 Online und Offline Algorithmen
Offline Algorithmen arbeiten mit dem gesamten Satz an Punkten als Eingabe. Basierend auf dieser Eingabe wird das Ergebnis produziert, welches exakt zu dieser Eingabe passt. Online-Algorithmen können von einem früheren Ergebnis ausgehen, einen Punkt hinzufügen oder entfernen und davon ausgehend ein neues Ergebnis berechnen. Erstens ermöglicht dies ein inkrementelles Vorgehen, zweitens sind Anpassungen erheblich billiger, als jedes Mal alles neu zu berechnen. Es gibt außerdem praktische Fälle in denen sich die konvexe Hülle dynamisch ändert.
2.3 Ein herkömmlicher Algorithmus
Abbildung in dieser Leseprobe nicht enthalten
Ein früher Algorithmus von Graham et al. sortiert die Punkte zunächst nach dem polaren Winkel um den Mittelpunkt der Punktwolke. Angenommen, eine solche konvexe Hülle ist gegeben, als Folge von sortierten Punkten. Eine solche Hülle kann schnell gezeichnet werden. Möchte man nun einen weiteren Punkt hinzufügen, bestimmt man zunächst den Sektor, in dem sich der neue Punkt befindet. Liegt der neue Punkt unter der bestehenden Kontur, ist gar nichts zu tun.
Befindet er sich oberhalb, wird nach rechts und links nach Tangenten gesucht und die konvexe Hülle vervollständigt. Suchen des Sektors in der sortierten Folge dauert 0(log n), suchen der Tangenten, falls erforderlich, dauert mit binärer Suche auch 0(log n). Damit also 0(log n) per Einfügung.
Fast man zusammen ergibt das bei n Einfügungen exakt die theoretische Grenze von 0(n log n). Allerdings hat der Algorithmus einen wesentlichen Nachteil, denn er kann nur Einfügungen verarbeiten. Wir wollen hier einen Algorithmus vorstellen, der sowohl Einfügungen, als auch Entfernungen zulässt.
Abbildung in dieser Leseprobe nicht enthalten
3 Repräsentation der Konvexen Hülle durch Datenstrukturen
3.1 Definition: Die Lc- und Rc-Hülle
Abbildung in dieser Leseprobe nicht enthalten
Wenn man sich die Aufgabe stellt, die konvexe Hülle dynamisch zu verwalten, stellt sich die Frage nach ihrer tatsächlichen Repräsentation. Die Repräsentation als geordnete Punkte um das Zentrum S ist nicht mehr anwendbar, da sich insbesondere S so verschieben kann, dass es außerhalb der Menge liegt.
Daher wollen wir nun versuchen, die konvexe Hülle als ihre rechte Seite, und ihre linke Seite darzustellen.
Definition:
Aus algorithmischen Erwägungen wird die Rc und Lc-Hülle sortiert nach der y-Koordinate gespeichert.
3.2 Feststellung der Lage in der Lc- und Rc-Hülle in 0(iog n)
Gegeben seien die Koordinaten der Linienzüge, welche die Rc- und Lc-Hüllen bilden. Die Punktkoordinaten bilden eine Folge, welche nach der y-Koordinate der Punkte sortiert ist. Binäre Suche nach der y-Koordinate in der Lc-Hülle, bzw. Rc-Hülle dauert 0(log n). Dann können entweder zwei Punkte p_i, p_i+l gefunden werden, so dass die gesuchte y-Koordinate von p dazwischen liegt, oder p liegt sowieso außerhalb der konvexen Hülle. Anhand der Verbindungsgerade dieser zwei Punkte kann klassifiziert werden, ob p links oder rechts der Verbindungsgerade liegt. Daraus folgt nun die Zugehörigkeit zur Lc- bzw. Rc-Hülle. Liegt p sowohl in Rc als auch in Lc, liegt p auch in der gesamten konvexen Hülle.
3.3 Verschmelzen von zwei Hüllen in 0(log n)
Angenommen die konvexen Hüllen sind gegeben als zwei Folgen von Punkten, gespeichert als Schlangen, jeweils sortiert nach der y-Koordinate. Und zwar in der Weise, dass die eine Schlange räumlich komplett unter der anderen Schlange liegt (bezüglich y-Koordinate).
Abbildung in dieser Leseprobe nicht enthalten
Eine Verschmelzung sieht nun so aus, dass eine Verbindungslinie zwischen den beiden Hüllen bestimmt wird, die beide Hüllen tangential berührt. Die Verbindungslinie verläuft zwischen zwei Punkten der beiden konvexen Hüllen. Die so gefundene Verbindungslinie bildet die gesuchte
Brücke. Die Schlangen werdenjeweils an den Endpunkten der Brücke aufgetrennt und das Resultat wieder neu verkettet. Die Operationen an den Schlangen dauern höchstens 0(log n). Für die Bestimmung der tangentialen Brücke kann eine binäre Suche auf beiden Hüllen eingesetzt werden. Dabei kommen Unterscheidungsregeln in 3.4 zum Einsatz, welche es ermöglichen, die Anzahl der möglichen Lagen des einen oder anderen Endpunktes der Verbindungslinie weiter einzuschränken. Dieser Prozess wird iteriert und die Brücke am Schluss gefunden, wenn es keine anderen Möglichkeiten für die Lagen der Endpunkte der Verbindungslinie gibt.
Bei jeder Iteration werden entweder die möglichen Lagen des oberen Endpunktes der Verbindungslinie, oder die möglichen Lagen des unteren Endpunktes der Verbindungslinie halbiert. Möglicherweise werden auch beide Punktmengen (gespeichert als Schlangen) von ihrer Mächtigkeit halbiert. Das bedeutet also, dass es am Anfang n mögliche Lagen für den oberen Punkt und m mögliche Lagen für den unteren Punkt gibt. Die obere Hülle bezeichnen wir mit A, die untere mit C. Insgesamt ist also der Aufwand log2(n)+log2(m), 0.B.DAn> m, < 2*log(n) = 0(log(n)).
Da die beiden Hüllenpunkte, p und q, die die Endpunkte derjeweils neuen Verbindungslinie bilden, geschickt gewählt werden, also auf der Mitte der verbleibenden Schlangen, werden die Lagen tatsächlich durch die Unterscheidungsregeln in 3.4, halbiert, zumindest auf einer der beiden Hüllen injeder Iteration.
3.4 Binäre suche auf den beiden Hüllen: Die Fälle
Die Fälle(Cases) werden als Entscheidungsregeln bei der Binären Suche zur Suche der Brücke eingesetzt und zwar um die beiden Brückenpunkte zu finden. In Fall a ist die Brücke gefunden. In den anderen Fällen kann die Menge Punkte bei der Suche entfernt werden die in den Abbildungen als gestrichelte Linien gezeichnet sind. Dadurch können immer mehr Punkte der konvexen Hülle ausgeschlossen werden und man nähert sich so den eindeutigen Brückenpunkten, die zum Schluss in Fall a gefunden sind.
Die für das Ausschlussverfahren wichtigen Fälle werden hier gegeben:
3.4.1 Die verschiedenen Lagen
Die Darstellung erfolgt nach Jose Alberto Cisneros: Maintenance of the convex hull of a dynamic set [2]:
Abbildung in dieser Leseprobe nicht enthalten
3.4.2 Implementierung der Entscheidungsregeln
Overmas & van Leuwen leiten aus diesen oben genannten Fällen einfache Entscheidungsregeln ab, die sich einfacher implementieren lassen. Außerdem sind sie für eine Maschine schnell entscheidbar:
- p+ ist der kleinste Punkt, dessen y-Koordinate größer als die von p ist.
- p- ist der größte Punkt, dessen y-Koordinate kleiner als die von p ist.
- q+/q- sind analog definiert.
Basierend auf der Klassifizierung, ob nun p+/p-/q+/q-jeweils rechts oder links der Gerade, definiert durch p und q, liegen, wird eine Entscheidung für einen der Fälle getroffen.
Unten abgebildete Tabelle 1 zeigt die Fälle in der Übersicht; vergleiche [2]
Abbildung in dieser Leseprobe nicht enthalten
[...]
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen.