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
- Einleitung
- Grundlagen
- Theoretische Grenzen der Laufzeit
- Online und Offline Algorithmen
- Ein herkömmlicher Algorithmus
- Repräsentation der Konvexen Hülle durch Datenstrukturen
- Definition: Die Lc- und Rc-Hülle
- Feststellung der Lage in der Lc- und Rc-Hülle in O(log n)
- Verschmelzen von zwei Hüllen in O(log n)
- Binäre suche auf den beiden Hüllen: Die Fälle
- Die verschiedenen Lagen
- Implementierung der Entscheidungsregeln
Zielsetzung und Themenschwerpunkte
Der Text befasst sich mit der dynamischen Verwaltung von Konfigurationen von Punkten in der Ebene, insbesondere der konvexen Hülle. Dabei liegt der Fokus auf der effizienten Anpassung der konvexen Hülle bei Hinzufügen oder Entfernen von Punkten.
- Theoretische Grenzen der Laufzeit für die Konstruktion der konvexen Hülle
- Vergleich von Offline- und Online-Algorithmen für die Verwaltung von Konfigurationen
- Repräsentation der konvexen Hülle durch Datenstrukturen wie Lc- und Rc-Hülle
- Effiziente Algorithmen für die Feststellung der Lage eines Punktes innerhalb der konvexen Hülle
- Verschmelzen von zwei konvexen Hüllen in O(log n) Zeit
Zusammenfassung der Kapitel
Die Einleitung stellt das Problem der dynamischen Verwaltung von Konfigurationen in der Ebene dar, wobei die konvexe Hülle als zentrales Element behandelt wird. Kapitel 2 beleuchtet die theoretischen Grenzen der Laufzeit für die Konstruktion der konvexen Hülle und führt den Unterschied zwischen Offline- und Online-Algorithmen ein. Außerdem wird ein herkömmlicher Algorithmus zur Konstruktion der konvexen Hülle vorgestellt. Kapitel 3 beschäftigt sich mit der Repräsentation der konvexen Hülle durch Datenstrukturen, insbesondere der Lc- und Rc-Hülle. Es werden Algorithmen zur Feststellung der Lage eines Punktes innerhalb der konvexen Hülle und zum Verschmelzen von zwei Hüllen vorgestellt. Schließlich werden verschiedene Fälle für die binäre Suche bei der Verschmelzung von Hüllen erläutert.
Schlüsselwörter
Dynamische Verwaltung, konvexe Hülle, Algorithmen, Datenstrukturen, Lc-Hülle, Rc-Hülle, binäre Suche, Verschmelzen, Entscheidungsregeln, Online-Algorithmen, Offline-Algorithmen.
- 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
