Abgeschlossene Master- und Diplomarbeiten

50Abschlussarbeit(en)

Georges, Robert: Online-Erkundung von Polygonen

Betreuer: Frank Hoffmann
Abschluss: Diplom
Abgabedatum: 25.01.2012

Gruben, Gerrit: The Kinetic Framework of Computational Geometry and its Applications

Betreuer: Prof. Dr. Günter Rote
Abschluss: Diplom
Abgabedatum: 25.03.2014

In 1983 Leo Guibas, Lyle Ramshaw, and Jorge Stolfi published "The Kinetic Framework for Computational Geometry" ([GRS83]). In this framework oriented polygonal outlines, the polygonal tracings, are defined.

Polygonal tracings generalise polygons in a way that enables the definition of topological quantities, such as the winding number, the degree, and a new quantity: the sweep number. A calculus of tracings is introduced, involving the convolution and product - a generalisation of intersection - of tracings. Interesting theorems relating these quantities and operations are discovered.

Applications of this theory include the computation of Minkowski sums of polygons with the convolution method. This method beats decomposition methods in terms of run-time efficiency by a factor of two to five ([Wei06]).

Convexity is described in a novel way by convex tracings. Convex tracings and their generalisation, the monostrofic tracings, are used to solve classical problems involving convex polygons. This encompasses, but is not limited to, finding common tangents and solving the containment problem for three polygons. A notion of duality is introduced by an oriented variant of projective geometry.

This thesis fills the nowadays still existing gap of proofs left by [GRS83].

References:

[GRS83] L. Guibas, L. Ramshaw, and J. Stolfi, “A kinetic framework for computational geometry,” Foundations of Computer Science, IEEE Annual Symposium on, vol. 0, pp. 100–111, 1983.

[Wei06] R. Wein, “Exact and efficient construction of planar minkowski sums using the convolution method,” in ESA, 2006, pp. 829–840.

Smilevets, Anton: Optimale Stadt mit Lücken

Betreuer: Prof. Dr. Günter Rote
Abschluss: Master of Science (M.Sc.)
Abgabedatum: 13.03.2012

In dem Vortrag wird das Problem "Optimale Stadt mit Lücken" vorgestellt und der Algorithmus zur dessen Lösung erklärt.Es gehört zu den grundlegenden Problemen - eine optimale Menge von Standorten auszuwählen.

Die Aufgabe dabei ist es, bei n gegebenen Standorten eine Menge zu bilden, dessen Kostenfunktion am geringsten ist.

Krause, Rasmus: 2,5-dimensionale Mechanismen

Betreuer: Christian Knauer
Abschluss: Diplom
Abgabedatum: 01.01.2008

Neumann, Max: Objekterkennung in Seitensichtsonar-Bilddaten

Betreuer: Christian Knauer
Abschluss: Diplom
Abgabedatum: 01.01.2008

Skyarenko, Georgy: Optimale Manhattan-Netzwerke

Betreuer: Frank Hoffmann
Abschluss: Diplom
Abgabedatum: 01.01.2008

Schlipf, Lena: Kontrollpfadanfragen in einfachen Polygonen

Betreuer: Christian Knauer
Abschluss: Diplom
Abgabedatum: 01.01.2008
Homepage des Autors:

Lenz, Tobias: Efficient Construction of Contour Trees Using Monotonic Paths

Betreuer: Prof. Dr. Günter Rote
Abschluss: Diplom
Abgabedatum: 01.01.2002
Homepage des Autors:

Willert, Max: Routing Schemes for Disk Graphs and Polygons

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Master of Education (M.Ed.)
Abgabedatum: 09.08.2016

Ehrhardt, Marcel: An In-Depth Analysis of Data Structures Derived from van-Emde-Boas-Trees

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Master of Science (M.Sc.)
Abgabedatum: 22.10.2015

IP-packet routing is one of the most practical solved problems in computer science with millions of routed packets per second. The algorithmic problem behind it is the so-called predecessor problem. Assuming a universe U, in this problem one can query a set S ⊆ U for the *predecessor* of an element q within the set S, i.e. max{x ∈ S | x < q}. If the set S can be manipulated, the problem is called the *dynamic* predecessor problem, otherwise it is called the *static* predecessor problem.

I give an overview of several different data structures for the w-bit word RAM on *bounded integer universes*, i.e. U = {0, ..., 2^w − 1}. Those data structures are based on the van-Emde-Boas-Tree [BKZ76]. For each data structure I work out the details of the algorithms by giving pseudo-code and for some of them I present new techniques, which give an easier and clearer presentation of the data structure and the algorithms. Last but not least, I answer an open problem concerning the space usage stated by Bose et al [Bos+13].

Mulzer, Wolfgang: Minimum Dilation Triangulations of the Regular n-Gon

Betreuer: Christian Knauer
Abschluss: Diplom
Abgabedatum: 21.10.2004
Homepage des Autors:

Stein, Yannik: Tolerated Tverberg Partitions: An Algorithmic Approach

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Master of Science (M.Sc.)
Abgabedatum: 28.03.2013
Homepage des Autors:

Let $P$ be some point set in $R^d$. A t-tolerated Tverberg partition of $P$ is a partition into disjoint subsets $P_1,P_2,...,P_m$ whose convex hulls have a nonempty intersection even if up to $t$ points from $P$ are removed. Soberon and Strausz proved the existence of a t-tolerated Tverberg partition of size $m$ for each point set of size at least $(t+1)(m-1)(d+1)+1$. It is conjectured that this bound is tight.

As tolerated Tverberg partitions have not been studied in the context of algorithmics so far, this thesis focuses on the development of algorithms that compute such partitions. We present an algorithm that improved the bound by Soberon and Strausz in one dimension and for many cases in two dimensions. Two deterministic approximation algorithms exist for the special case of untolerated Tverberg partitions (i.e., $t=0$). In order to adapt these algorithms, we developed several approximation preserving reductions to the untolerated Tverberg problem. While the complexity of actually computing a t-tolerated Tverberg partition is still unknown, we could prove the coNP-completeness of a related decision problem.

Bortfeld, Benjamin: Experimenteller Vergleich verschiedener binärer Suchbäume unter verschiedenen Abfragesequenzen

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Diplom
Abgabedatum: 19.07.2012

Binäre Suchbäume sind eine der wichtigsten Datenstrukturen der Informatik. Jeder Informatiker kennt die balancierten Varianten, wie den AVL-Baum oder den Rot-Schwarz-Baum, von denen die ältesten bereits in den 1960er Jahren entwickelt wurden. Doch auch in neuerer Zeit beschäftigt sich die Forschung mit binären Suchbäumen, um das Verwalten großer Datenmengen effizienter zu gestalten. Ein Forschungzweig beschäftigt sich dabei mit den dynamischen binären Suchbäumen. Das sind Bäume, die ihre Struktur auch bei Suchen ändern können. Zwei interessante dynamische Bäume wurden erst 2007 und 2010 vorgestellt: der Tango- und der Zipper-Baum. Sie versprechen in der Theorie eine gute Performance, aber praktische Untersuchungen zu ihnen gibt es nocht nicht. Aus diesem Grund wollen wir in dieser Arbeit Tango- und Zipper-Bäume experimentell untersuchen und mit anderen Bäumen vergleichen. Damit erhoffen wir uns, diese Bäume in Hinsicht auf ihre Laufzeit für ihren Einsatz unter realen Bedingungen besser einschätzen zu können. Da Tango- und Zipper-Bäume keine Möglichkeit bieten, Elemente einzufügen nachdem sie einmal aufgebaut wurden, beschäftigen wir uns nur damit zu untersuchen, wie effizient die Bäume für verschiedene Abfragesequenzen sind.

Werner, Daniel: On the Parameterized Complexity of Geometric Stabbing Problems

Betreuer: Christian Knauer
Abschluss: Diplom
Abgabedatum: 01.01.2009
Homepage des Autors:

Driemel, Anne: Matching Polygonal Curves through Curvature

Betreuer: Prof. Dr. Helmut Alt
Abschluss: Diplom
Abgabedatum: 01.01.2009

Naively, the matching of two polygonal curves requires the computation of an optimal similarity transformation that maps one curve onto the other. Curvature, as defined for continuous curves, is invariant under rigid motions and to a certain extend also under affine transformations. To circumvent the computations involved in searching the transformation space, the curvature functions will be matched directly. Different ways of defining the curvature for polygonal curves will be surveyed as well as the possibility of admitting different parametrizations and whether the curvature alone suffices for a good similarity measure.

All implementations will be in Java.

The thesis is partly supervised by Jean Gallier, University of Pennsylvania.

Scharf, Ludmila: Computing the Hausdorff distance between sets of curves

Betreuer: Prof. Dr. Helmut Alt
Abschluss: Diplom
Abgabedatum: 01.01.2004
Homepage des Autors:

Abstract: This paper describes an algorithm for computation of the Hausdorff distance between sets of plane algebraic rational parametric curves. The Hausdorff distance is one of the frequently used similarity measures in geometric pattern matching algorithms. It is defined for arbitrary non-empty bounded and closed sets A and B. Hausdorff distance assigns to each point of one set the distance to its closest point on the other and takes the maximum over all these values. We work with Euclidean distance as point to point distance measure.

The algorithm presented here is restricted to the curves with rational parameterization and no poles on the defining interval. We also describe a polygon line approximation algorithm, based on Douglas-Peucker polygon line simplification algorithm.

Jain, Manuel: "Unions of Onions: Preprocessing Imprecise Points for Fast Onion Decomposition" - Die Implementierung und Visualisierung

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Diplom
Abgabedatum: 27.08.2015

Die Onion Decomposition, eine natürliche Erweiterung der konvexen Hülle einer Punktmenge finden viele praktische Anwendungen in der Informatik. In meiner Arbeit präsentiere ich eine Implementierung der von Dr. Mulzer und Dr. Löffler verfassten Arbeit "Unions of Onions: Preprocessing Imprecise Points for Fast Onion Decomposition". Es wird eine unpräzise Eingabe als Basis genommen und derart vorverarbeitet, dass die Berechnung der Onion Decomposition sehr effizient möglich ist, sobald die präzise Eingabe vorliegt. Um diesen und auch andere geometrische Algorithmen einfach implementieren zu können und schnell Fehler zu identifizieren, wird ebenfalls eine graphische Benutzeroberfläche vorgestellt, die einzelne Schritte eines Algorithmus in Echtzeit darstellt. Mit Hilfe dieser Oberfläche ist es möglich schnell einen Algorithmus zu implementieren, sowie eigene geometrische Objekte darstellbar zu machen.

Spexard, Jaqueline: Visualisierung von endlichen Symmetriegruppen in zwei und drei Dimensionen

Betreuer: Prof. Dr. Helmut Alt , Claudia Dieckmann
Abschluss: Diplom
Abgabedatum: 12.04.2012

Symmetrie findet sich in allen Bereichen des Lebens. Sie ist dessen ständiger Begleiter. Nicht nur die Natur gehorcht den Gesetzen der Symmetrie, auch die Menschen lassen sich bei ihren Kreationen, zum Beispiel in Architektur, Musik und Kunst von ihr in- spirieren. Meist ist dies ein unbewusster Prozess, mit welchem Schönheit und Ästhetik assoziiert wird. Auch die verschiedenen wissenschaftlichen Disziplinen beschäftigen sich eingehend mit der Symmetrie und bieten beispielsweise Visualisierungstools an, um Sym- metriegruppen zu veranschaulichen. Allerdings beschränken sich diese Anwendungen auf den jeweiligen wissenschaftlichen Kontext und sind für andere Personenkreise nicht ver- ständlich. Eine Anwendung, welche die endlichen Symmetriegruppen anschaulich erklärt, kreatives Gestalten erlaubt und eine intuitive Nutzung zulässt, gibt es, bis zum gegen- wärtigen Zeitpunkt, nicht.

Im Rahmen dieser Arbeit wird ein zweiteiliges Programm entwickelt, welches für den Wis- senschaftler, Normalanwender, Künstler und Designer gleichermaßen interessant ist. Der Schwerpunkt der Anwendung liegt zum einen darin, endliche Symmetriegruppen mit Hilfe visueller Mittel mathematisch zu erklären, zum anderen soll das Programm durch seine einfache und intuitive Handhabung eine kreative Erstellung endlicher Symmetrie- gruppenobjekte ermöglichen.

Eingeleitet wird die Arbeit mit einer anschaulichen mathematischen Erklärung der endli- chen Symmetriegruppen im Zweidimensionalen. Darauf basierend werden die dreidimen- sionalen Gruppen erklärt und zu den jeweiligen Dimensionen jeweils ein Programm und dessen Implementierung vorgestellt.

Als Schlussfolgerung lässt sich sagen, dass dieses Programm ein grundlegendes Verständ- nis der Theorie der endlichen Symmetriegruppen schafft und eine kreative Anwendung ermöglicht. Sie bietet außerdem eine Grundlage für weitere Möglichkeiten der Implemen- tierung anderer Symmetriegruppen, welche auch für andere Nutzergruppen interessant sein könnten.

Weise, Andreas: Computation of the Fréchet-Distance on GPU

Betreuer: Prof. Dr. Helmut Alt , Ludmila Scharf
Abschluss: Master of Science (M.Sc.)
Abgabedatum: 01.01.2012

Jeschke, Sophie: Planare Graphen kleiner Dilatation

Betreuer: Christian Knauer
Abschluss: Diplom
Abgabedatum: 01.01.2006

Holweger, Kathrin: Kontrollpolygone als geometrische Filter

Betreuer: Christian Knauer
Abschluss: Diplom
Abgabedatum: 01.01.2006

Schindler, Yvonne: EMD (Earth Mover's Distance)

Betreuer: Christian Knauer
Abschluss: Diplom
Abgabedatum: 01.01.2006

Scharf, Nadja: Approximating smallest containers for packing three-dimensional convex objects

Betreuer: Prof. Dr. Helmut Alt
Abschluss: Master of Science (M.Sc.)
Abgabedatum: 28.08.2016
Homepage des Autors:

Die Arbeit befasst sich mit dem nichtüberlappenden Packen dreidimensionaler konvexer Objekte in einen achsenparallelen Container, wobei das Volumen des Container minimiert werden soll. Es werden Approximationsalgorithmen für das Packen von Quadern unter Translation und unter starren Bewegungen und für das Packen von konvexen Polyedern unter starren Bewegungen entwickelt. Nach bestem Wissen sind dies die ersten Approximationsalgorithmen für das gegebene Problem.

Kania, Oliver: Musteranpassung bei geometrischen Graphen

Betreuer: Prof. Dr. Helmut Alt
Abschluss: Diplom
Abgabedatum: 01.01.2005

Seiferth, Paul: Computational Aspects of Triangulations with Constant Dilation

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Master of Science (M.Sc.)
Abgabedatum: 26.11.2012
Homepage des Autors:

Let $G$ be a plane geometric graph. For two distinct vertices $u,v$ of $G$ we can consider the ratio between the length $d_G(u,v)$ of the shortest path and the Euclidean distance $|u,v|$ between $u$ and $v$. The dilation of $G$ is the maximum over all these ratios, i.e. $\max_{u,v\in V(G)}\frac{d_G(u,v)}{|u,v|}$.

The aim of this Master Thesis is to examine the geometric properties of triangulations that have bounded dilation and to utilize them in an algorithmic way. Krznaric and Levcopoulos showed that given the Delaunay triangulation for a planar point set $S$ we can compute a hierarchical clustering for $S$ in linear time. We present a similar algorithm that does not insist on the Delaunay triangulation but uses triangulations that have constant dilation. Unfortunately, when analyzing the running time it turned out that the running time of the algorithm is not linear. We identified two properties that are necessary to achieve linear running time. It is left as an open question what kind of triangulations, except for the Delaunay triangulation, fulfill these properties. Furthermore, we state additional properties of triangulations with constant dilation that were encountered during the analysis of the algorithm. 

Kübart, Thore: Berechnung akkumulierter Fréchet-Abstände

Betreuer: Prof. Dr. Helmut Alt
Abschluss: Diplom
Abgabedatum: 02.07.2012

Echterhoff, Jonas: Suchstrukturen für Formen

Betreuer: Prof. Dr. Helmut Alt
Abschluss: Diplom
Abgabedatum: 01.01.2007

Eversmann, Dustin: Interferenzminimierung in eindimensionalen Sensornetzen

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Diplom
Abgabedatum: 05.04.2013

Das Ziel dieser Arbeit war die Entwicklung eines Polynomialzeitalgorithmus zur Interferenzminimierung in eindimensionalen Sensornetzen. Diese Minimierung soll die Anzahl erneuter Übertragungen und somit den Energieverbrauch reduzieren.

Es wird die bereits gezeigte obere Schranke der optimalen Interferenz von 2logn auf logn + 1 und somit annähernd auf das Optimum gesenkt. Ausgehend von dem bereits gezeigten Zusammenhang zwischen optimalen Lösungen und binären Suchbäumen werden neue Erkenntnisse über die Struktur optimaler Lösungen gewonnen sowie Zusammenhänge aufgezeigt und damit eine Vermutung widerlegt.

Darauf aufbauend werden Algorithmen vorgestellt, die sich unterschiedlicher Methoden bedienen und unter denen sich ein Verfahren mit quasi-polynomieller Laufzeit befindet. Da kein Polynomialzeitalgorithmus gefunden wurde, werden darüber hinaus diverse Heuristiken vorgestellt und die Bearbeitung einer weiterführenden Fragestellung nahegelegt.