Das dynamische Konturpolygon
Diese Arbeit beschreibt das Dynamische Konturpolygon einer Menge von Punkten in der Ebene. Das Konturpolygon ist die
grafisch dargestellte Verbindung aller maximalen Punkte der Menge. Die maximalen Punkte werden beschrieben und definiert.
Für die dynamische Verwaltung der Punkte in der Ebene – insbesondere der maximalen Punkte – werden Algorithmen
angegeben. Das Gleiche gilt auch für die dynamische Verwaltung des Konturpolygons. Es wird gezeigt, dass das Einfügen und
das Löschen von Punkten mit dem Zeitaufwand O(n log n) möglich ist. Dabei bezeichnet n die
Anzahl der Punkte in der Menge.
In einem zweiten Teil der Arbeit werden die Punkte und das Konturpolygon datentechnisch realisiert. Dafür wird die
Programmiersprache Java verwendet. Besonderer Wert wird auf die Datenstruktur gelegt. Die Punkte werden in einem
ausgeglichenen binären Suchbaum (AVL-Baum) verwaltet. Damit wird die Zeitschranke O(n log n) eingehalten.
Die maximalen Punkte stehen an den inneren Knoten für die von diesem Teilbaum überdeckten Punkte zur Verfügung.
Damit auch für die Verwaltung der maximalen Punkte die geforderte Zeitschranke O(n log n) eingehalten wird,
werden die Punkte in einer speziellen “concatenable queue“ verwaltet, welche als 2-3-Baum dargestellt wird.
Für den Aufwand an Speicherplatz wird O(n) eingehalten. Bei der datentechnischen Realisierung werden die
Verwaltung der Punktemengen und die Darstellung strikt getrennt. So können die Verwaltung der Punkte in der Ebene und die
Berechnung des Konturpolygons unabhängig von der Darstellung auch in anderen Anwendungen verwendet werden.