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.
Inhaltsverzeichnis
1 Einleitung
2 Grundlagen
2.1 Theoretische Grenzen der Laufzeit
2.2 Online und Offline Algorithmen
2.3 Ein herkömmlicher Algorithmus
3 Repräsentation der Konvexen Hülle durch Datenstrukturen
3.1 Definition: Die Lc- und Rc-Hülle
3.2 Feststellung der Lage in der Lc- und Rc-Hülle in O(log n)
3.3 Verschmelzen von zwei Hüllen in O(log n)
3.4 Binäre suche auf den beiden Hüllen: Die Fälle
3.4.1 Die verschiedenen Lagen
3.4.2 Implementierung der Entscheidungsregeln
3.5 Konvexe Hülle nach Vorsortierung in O(n)
4 Structure und Algorithmus
4.1 Aufbau der Datenstruktur zur Speicherung der konvexen Hülle
4.2 Notationen
4.3 Prozedur "Down"
4.4 Prozedur "UP"
4.5 Lemmas und Beweise
4.6 Verwalten der konvexen Hülle
Zielsetzung und thematische Schwerpunkte
Ziel dieser Arbeit ist die Untersuchung und effiziente algorithmische Realisierung der dynamischen Verwaltung konvexer Hüllen in der Ebene, wobei insbesondere das Hinzufügen und Entfernen von Punkten bei optimaler Laufzeit betrachtet wird.
- Grundlagen der algorithmischen Geometrie und konvexer Hüllen.
- Vergleich von Online- und Offline-Algorithmen.
- Entwicklung effizienter Datenstrukturen zur Repräsentation konvexer Hüllen.
- Mathematische Herleitung von Laufzeitkomplexitäten für dynamische Operationen.
- Implementierung von Such- und Verschmelzungsalgorithmen zur Wartung der Hülle.
Auszug aus dem Buch
3.3 Verschmelzen von zwei Hüllen in O(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 eine Schlange räumlich komplett unter der anderen Schlange liegt (bezüglich y-Koordinate).
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 werden jeweils an den Endpunkten der Brücke aufgetrennt und das Resultat wieder verkettet. Die Operationen an den Schlangen dauern höchstens O(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 keine anderen Möglichkeiten für die Lagen der Endpunkte der Verbindungslinie gibt.
Zusammenfassung der Kapitel
1 Einleitung: Einführung in die Bedeutung konvexer Hüllen in der algorithmischen Geometrie und die Notwendigkeit ihrer dynamischen Verwaltung.
2 Grundlagen: Diskussion der theoretischen Laufzeitgrenzen und Abgrenzung zwischen statischen, Online- und Offline-Algorithmen.
3 Repräsentation der Konvexen Hülle durch Datenstrukturen: Vorstellung von Lc- und Rc-Hüllen sowie Verfahren zur effizienten Lagebestimmung und Verschmelzung innerhalb logarithmischer Zeit.
4 Structure und Algorithmus: Detaillierte Beschreibung der Datenstruktur, der Prozeduren "Down" und "UP" sowie mathematische Beweise zur Laufzeitkomplexität.
Schlüsselwörter
Algorithmen, Konvexe Hülle, Dynamische Geometrie, Datenstruktur, Laufzeitkomplexität, Binäre Suche, Verschmelzung, Offline-Algorithmen, Online-Algorithmen, Tangentiale Brücke, Geometrische Optimierung, Punktmenge, Y-Koordinate, Balancierter Baum.
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit befasst sich mit der effizienten, dynamischen Verwaltung konvexer Hüllen für Punktmengen in der zweidimensionalen Ebene.
Welche sind die zentralen Themenfelder?
Die zentralen Themen umfassen die geometrische Datenverarbeitung, die Optimierung von Laufzeit-Algorithmen für Punktmengen und die Nutzung spezifischer Datenstrukturen wie binärer Suchbäume.
Was ist das primäre Ziel der Untersuchung?
Ziel ist es, Algorithmen zu entwickeln, die das Hinzufügen und Entfernen von Punkten in einer konvexen Hülle ermöglichen, ohne die gesamte Hülle bei jeder Änderung neu berechnen zu müssen.
Welche wissenschaftliche Methode wird verwendet?
Es wird eine algorithmische und mathematische Analyse durchgeführt, ergänzt durch die Definition von Datenstrukturen und die Beweisführung der Laufzeitkomplexität mittels Lemmata.
Was wird im Hauptteil der Arbeit behandelt?
Der Hauptteil behandelt die theoretische Repräsentation durch Lc- und Rc-Hüllen, die Prozeduren für die dynamische Anpassung ("Down" und "UP") sowie die binäre Suche auf Hüllenstrukturen.
Welche Schlüsselwörter charakterisieren die Arbeit?
Die Arbeit lässt sich am besten mit Begriffen wie Konvexe Hülle, Algorithmische Geometrie, Laufzeitkomplexität und Dynamische Datenstrukturen beschreiben.
Was unterscheidet die Lc- von der Rc-Hülle?
Die Lc-Hülle (left-convex) und die Rc-Hülle (right-convex) repräsentieren unterschiedliche Teile der konvexen Hülle, die jeweils die linke bzw. rechte Seite der Punktmenge bezüglich ihrer y-Koordinaten beschreiben.
Welche Rolle spielt die "tangentiale Brücke" beim Verschmelzen?
Die tangentiale Brücke ist entscheidend, um zwei separate konvexe Hüllen zu einer einzigen zusammenzufügen, indem die Verbindungslinie bestimmt wird, welche beide Hüllen ohne Schnittmengen tangiert.
- Arbeit zitieren
- Thomas Plehn (Autor:in), Robert Einig (Autor:in), 2015, Die dynamische konvexe Hülle. Ein Verfahren zur Online-Lösung, München, GRIN Verlag, https://www.grin.com/document/369662
