Laufende Bachelorarbeiten

Abgeschlossene Bachelorarbeiten

Implementierung und Visualisierung eines Sweep-Line Verfahrens zur Berechnung des Voronoi-Diagramms von Punkten in der Ebene (Catarina Rupprecht, 2015)

In dieser Bachelorarbeit wird ein Sweep-Line Algorithmus zur Berechnung des Voronoi-Diagramms von Punkten in der Ebene vorgestellt. Es werden zunächst die theoretischen Grundlagen des Voronoi-Diagramms erläutert. Danach wird Fortunes Algorithmus zur Konstruktion mittels eines Sweep-Line Verfahrens vorgestellt, der das Voronoi-Diagramm von \(n\) Punkten in der optimalen Laufzeit \(O(n \log n)\) berechnet. Insbesondere wird dabei auf die benötigten Datenstrukturen eingegangen. Abschließend wird eine Implementierung beschrieben.

Non-Uniform Geometric Matchings under Translations for Square Grid Graphs (Sebastian Lützow, 2014)

Geometric matching problems are one of the central topics in the research field of Computational Geometry. In a recent line of research this concept has been generalized to so-called elastic shape matching problems. In this thesis, the task is to implement specific variants of this problem: elastic shape matching problems for planar point sets/sequences under translations.

Triangulation von Polygonen (Thomas Heinlein, 2014)

Die Bachelorarbeit befasst sich mit einer zentralen Problemstellung aus der Algorithmischen Geometrie. Thematisiert wird das Zerlegen eines einfachen Polygons mit \(n\) Ecken in Dreiecke. Die vorgestellten Verfahren wurden in einem bereitgestellten Framework implementiert. Durch die Arbeit werden die folgenden Themen abgedeckt: Es werden zwei Algorithmen zur Triangulierung von einfachen Polygonen vorgestellt. Der erste hat eine Laufzeit von \(O(n^2)\), während der andere Algorithmus aus zwei Schritten besteht: Zuerst wird das Polygon in monotone Polygone zerteilt, was \(O(n \log n)\) Zeit benötigt, anschließend werden diese durch einen Greedy-Algorithmus in linearer Zeit trianguliert. Ein anderer Aspekt der Arbeit ist die Realisierung der einer Datenstruktur zur Darstellung ebener Unterteilungen, der doppelt verkettete Kantenliste. Hierzu wird der Konstruktor und einige Hauptfunktionen, wie das Hinzufügen oder das Löschen von Kanten, vorgestellt.

Datenstrukturen für Prioritätswarteschlangen (Matthias Stachowski, 2012)

In dieser Bachelorarbeit werden verschieden Datenstrukturen zur für Prioritätswarteschlangen präsentiert und gegenübergestellt: Linksbäume, Binomial-Queues, Fibonacci-Heaps und Quake-Heaps. Mit Hilfe prototypischer Implementierungen werden die unterschiedlichen Datenstrukturen experimentell miteinander verglichen.

Kd-Tree and ICP Implementations Using Graphics Hardware (Maximilian Reischl, 2012)

Der ICP-Algorithmus (Iterative Closest Point) ermittelt eine Transformation zwischen zwei Punktemengen \(M\) (Modell) und \(D\) (Daten) im \(R^3\), mit der sich \(D\) möglichst gut auf \(M\) abbilden lässt. Diese Problemstellung tritt z.B. bei der Landschaftsvermessung, der Computertomographie und einer Vielzahl anderer Anwendungen auf. Diese Bachelorarbeit befasst sich mit der Implementierung des ICP-Algorithmus auf Grafikkarten und untersucht, inwieweit sich eine Beschleunigung des Verfahrens durch die Nutzung von GPUs erreichen lässt. Ein zentraler Aspekt ist dabei die Implementierung von Datenstrukturen zur Suche des nächsten Nachbarn auf der GPU (hier ibs. kd-Bäumen und Quadtrees).