Abgeschlossene Master- und Diplomarbeiten

Uzun, Murat: Konzeption und Entwicklung eines Smart-Home Add-Ons auf Basis einer Webanwendung zur Informationsausgabe des Wohngebietes

Abschluss
Master of Science (M.Sc.)
Abgabedatum
09.10.2019

Die Verwendung von Smart-Home Geräten in privaten Wohnungen und Häusern nimmt immer mehr zu. Smart-Home Geräte erlauben es Nutzern, Informationen über Wetter, Licht, Heizungszustand u. a. in der Wohnung schnell und verständlich bereitzustellen. Daher gibt es keinerlei Informationen über die Zustände außerhalb der Wohnung. Die Arbeit befasst sich mit der Implementierung und Entwicklung eines Smart-Home-Services auf Basis einer Webanwendung, die dazu dienen soll, bestimmte Informationen aus festgelegten Themenbereichen, wie z. B. Veranstaltungen oder Dreharbeiten, auch am Smart-Home Hauptgerät einzusehen.

Obenaus, Johannes: Spanning Trees with Low (Shallow) Stabbing Number

Abschluss
Master of Science (joint with ETH Zürich)
Abgabedatum
01.10.2019

Berendsohn, Benjamin Aram: Complexity of Permutation Pattern Matching

Abschluss
Master of Science (M.Sc.)
Abgabedatum
05.09.2019

Permutation pattern matching (PPM) is the problem of determining whether a permutation π is contained in another permutation τ, i.e. τ has a subsequence that is order-isomorphic to π. We study the complexity of PPM. In particular, we consider the variants of PPM where π itself does not contain a fixed permutation σ. We first investigate the incidence graphs avoiding a fixed permutation σ, and show that the treewidth of these graphs can be almost linear for almost all σ. This indicates that the restricted variants may be as hard as unrestricted PPM. For the counting variant #PPM, we show that, indeed, almost all restricted variants require exponential time, unless the exponential time hypothesis fails. Finally, we consider two on-line versions of PPM where π is fixed, and give upper and lower bounds on their space requirements depending on π.

Jentsch, Daniel: Explicit-State-Model-Checker für drei angewandte eingebettete domänenspezifische Sprachen zur Modellierung von Nebenläufigkeit in Scala

Abschluss
Master of Science (M.Sc.)
Abgabedatum
07.06.2019

In Scala werden eingebettete domänenspezifische Sprache häufig für die Beschreibung von Nebenläufigkeitsproblemen verwendet. Bestehende Byte-Code-basierte Model-Checkern überprüfen auch das Laufzeitsystem einer solchen Sprache, was diesen Prozess komplexer macht als in der Praxis notwendig.

In dieser Arbeit wurden drei unterschiedliche explicit state Model-Checker entwickelt und deren Eigenschaften untersucht. Diese Model-Checker beschreiben ausschließlich nur das Verhalten der jeweiligen Sprache.

Laßan, Christian: Automatisierte Verifikation von Systemarchitekturen und -spezifikationen unter Verwendung von semi-formalen Templatesprachen und SysML

Abschluss
Master of Science (M.Sc.)
Abgabedatum
22.03.2019

Heutige Hardware- und Softwaresysteme werden zunehmend komplexer und umfangreicher. Zusätzliche sicherheitskritische Anforderungen, die mitunter auch Menschenleben schützen sollen, sind nicht selten. Um Fehler bei der Fertigung dieser Systeme schon möglichst in einem frühen Stadium der Entwicklung zu vermeiden, sind Verifikationsmethoden während der Modellierungs- und Spezifikationsphase wünschenswert. Da Anforderungen aber derzeit überwiegend natürlichsprachlich vorliegen, sind Verifikationen oft mühsam und zeitaufwendig. Dennoch gibt es Möglichkeiten, den informellen Schein der natürlichen Sprache beizubehalten und Verifikationen sogar automatisiert durchlaufen zu lassen. Das Ziel dieser Masterarbeit ist die Fertigstellung eines Prozesses, der es erlaubt, Systeme visuell zu modellieren, geeignet informell zu spezifizieren und anschließend automatisiert zu verifizieren. Die Grundlagen bieten auf der einen Seite die Systembeschreibungssprache SysML und eine für die vertragsbasierte Spezifikation geeignete semiformale Templatesprache. Auf der anderen Seite können formal definierte Systeme mit dem Befehlszeilenwerkzeug OCRA bereits auf Korrektheit geprüft werden. Um diese Lücke zu schließen werden Regeln definiert, welche die semiformale Templatesprache schrittweise in eine lineare temporale Logik für hybride Systeme übersetzt. Diese Übersetzungen werden in einen vorhandenen Prototypen integriert, der die zuvor modellierten und informell spezifizierten Systeme automatisert in die OCRA verständliche Sprache überführt. Mit Hilfe eines zusätzlich entwickelten Plugins werden die Ergebnisse der Korrektheitsprüfung anschaulich visualisiert. Abschließend wird der vollständige Prozess anhand zweier Fallbeispiele validiert.

Shenkman, Natalia: A comparative study of some proofs of Chernoff ’s bound with regard to their applicability for deriving concentration inequalities

Abschluss
Master of Education (M.Ed.)
Abgabedatum
10.01.2019

Concentration inequalities provide bounds on the tail of the distribution of random variables. This thesis focuses on four different techniques used in the literature to derive the most basic tail bound for sums of independent {0, 1}-valued random variables, commonly referred to as the Chernoff bound. We study their suitability for deriving tail inequalities when the independence assumption as well as the restriction on the values of the random variables are relaxed. As a by-product, we improve the bound in Theorem 3.3 in Impagliazzo and Kabanets (2010).

Knorr, Kristin: Dynamic Connectivity for Intersection Graphs of Unit Squares

Abschluss
Master of Science (M.Sc.)
Abgabedatum
13.12.2018
Homepage des Autors

Maintaining the connectivity of a dynamic graph is a basic problem in data structure design. A dynamic graph is continuously subjected to changes such as single insertions or deletions of edges and vertices. As a connectivity data structure has to answer the question if two vertices in a graph are connected, it is sufficient to know the connected components. These can dramatically change with the deletion of one point which is incident to many (otherwise) disjoint subgraphs. Thus, the efficient handling of the connected components is crucial.

The problem becomes more challenging when the dynamic graph, whose connectivity should be maintained, is an intersection graph. In intersection graphs, the vertices represent point sets and there is an edge if and only if two sets intersect. Hence, a dynamic connectivity data structure for intersection graphs also has to determine which edges are affected by the insertion or deletion of one vertex.

The dynamic data structure for unit disk graphs by Kaplan et al. was used as a basis for this thesis. An unit disk graph is defined by a set of unit disks represented by their centers. Their data structure achieves an amortized update time of O(log n log log n) and a worst-case query time of O(log n) for connectivity queries.

In this thesis the data structure was adapted for unit squares. This means, that the point sets for the intersection graph are unit squares, represented by their centers. The developed data structure is able to maintain connectivity for axis-aligned unit squares and unit squares rotated by 45°. For this purpose, an adaptation of AVL trees is devised which supports a faster detection of edges. Hence, the connectivity data structure achieves an amortized update time of O(log n) and a worst-case query time of O(log n) for connectivity queries.

Sungaila, David: C delta: Design and Implementation of a Transcompiler for Language Integrated Finite-State Machines in C sharp

Abschluss
Master of Science (M.Sc.)
Abgabedatum
30.08.2018

C♯ is a programming language developed by Microsoft that supports multiple programming paradigms. Two of these paradigms are object-oriented programming and event-driven programming which allow developers to implement finite-state machines in their applications.

However, these implementations are not supported by a built-in programming paradigm, syntactic sugar, or the included base class libraries. This forces developers to either create their own robust general purpose finite-state machines or include a third-party class library.

This master’s thesis discuses automata-based programming as a programming paradigm and how C𝛿, a language designed and implemented in this thesis, will extend C♯ with this paradigm. Furthermore, other programming languages and code generators are compared to C𝛿 in their implementations of finite-state machines. Special attention is given to the programming language P♯, as its specification and goals are similar to C𝛿.

To show the practicability of the C𝛿 language, its compiler is rewritten into C𝛿 itself. This recursive bootstrapping is used to discuss the advantages and experiences of having language integrated finite-state machines, compared to other solutions.

Hartmann, Florian: Federated Learning

Abschluss
Master of Science (M.Sc.)
Abgabedatum
23.08.2018

Over the past few years, machine learning has revolutionized fields such as computer vision, natural language processing, and speech recognition. Much of this success is based on collecting vast amounts of data, often in privacy-invasive ways. Federated Learning is a new subfield of machine learning that allows training models without collecting the data itself. Instead of sharing data, users collaboratively train a model by only sending weight updates to a server. While this better respects privacy and is more flexible in some situations, it does come at a cost. Naively implementing the concept scales poorly when applied to models with millions of parameters. To make Federated Learning feasible, this thesis proposes changes to the optimization process and explains how dedicated compression methods can be employed. With the use of Differential Privacy techniques, it can be ensured that sending weight updates does not leak significant information about individuals. Furthermore, strategies for additionally personalizing models locally are proposed. To empirically evaluate Federated Learning, a large-scale system was implemented for Mozilla Firefox. 360,000 users helped to train and evaluate a model that aims to improve search results in the Firefox URL bar.

Putzke, Simon: Modellierung von Scheduling Regeln in business-optimiertem Timetabling

Abschluss
Master of Science (M.Sc.)
Abgabedatum
28.06.2018

Bei der automatischen Patiententerminvergabe müssen eine Vielzahl an Scheduling Regeln geprüft und eingehalten werden. Das zu Grunde liegende Problem ist ein Online Timetabling-Problem. Timetabling-Probleme sind NP-vollständig. Es bedarf einem Verfahren, wie dieses Problem dahingehend bearbeitet wird, dass die Eingabe möglichst gering ist, so dass eine schnelle Lösung des Problems erzielt werden kann. Diese Arbeit beschäftigt sich mit der Prüfung der Scheduling Regeln, die eingehalten werden müssen. Hierzu wird ein Modell entworfen, wie diese Regeln erzeugt und in boolesche Formeln umgewandelt werden können. Diese Formeln wiederum werden als Binärbäume dargestellt. Es wurden Methoden entwickelt, wie die Traversierung dieser Bäume, und damit die Prüfung der Regeln, minimiert werden kann. Darüber hinaus wurde ein Modell entworfen, wie die Regeln einheitlich strukturiert erfasst und in das Modell eingepflegt werden können. Der Einfluss der NP-Vollständigkeit auf das Problem wurde durch Vorberechnungen verringert, so dass diese Berechnungen nicht während der Patiententerminvergabe durchgeführt werden müssen.

Kauer, Alexander: Rotation Systems in Three Dimensions

Abschluss
Master of Science (M.Sc.)
Abgabedatum
29.09.2017
Homepage des Autors

Zur Lösung vieler geometrischer Probleme bezüglich Mengen an Punkten ist das Wissen um die Orientierung der Punkte untereinander ausreichend. Der Chirotop von einer benannten Punktmenge P ∈ R2 gibt an, ob ein gegebenes Tripel an Punkten im oder gegen den Uhrzeigersinn in der Ebene liegt. Viele grundlegende geometrische Eigenschaften von P, wie beispielsweise die konvexe Hülle, lassen sich bereits aus dem Chirotop ablesen.

Das Radialsystem von P gibt für jeden Punkt p ∈ P die Reihenfolge an, in der die anderen Punkte P \ {p} von einem Strahl getroffen werden, der im Uhrzeigersinn um p rotiert. Ein Chirotop bestimmt eindeutig das Radialsystem der dazugehörigen Punktmenge. Umgekehrt kann aus einem Radialsystem der Chirotop eindeutig gefolgert werden, sofern die ursprüngliche Punktmenge eine konvexe Hülle mit mindestens vier Elementen besitzt. Radialsysteme finden Anwendung unter anderem bei Routing- als auch Sichtbarkeitsproblematiken.

Radialsysteme können aufgrund ihres Prinzips der Rotation eines Strahls nicht direkt für höhere Dimensionen verallgemeinert werden. In dieser Arbeit werden daher mehrere zu Radialsystemen äquivalente Strukturen beschrieben, die aufgrund eines jeweils anderen Fokusses besser auf höhere Dimensionen erweiterbar sind. Diese Strukturen werden anschließend genutzt um Radialsysteme auf verschiedene Weisen auf drei Dimensionen zu erweitern. Die sich ergebenen Strukturen werden untersucht, insbesondere inwiefern sich daraus die Orientierung von Punkten untereinander rekonstruieren lässt.

Cleve, Jonas: Combinatorics of Beacon-based Routing and Guarding in Three Dimensions

Abschluss
Master of Science (M.Sc.)
Abgabedatum
30.03.2017
Homepage des Autors

A beacon is a point-like object which can be enabled to exert a magnetic pull on other point-like objects in space. Those objects then move towards the beacon in a greedy fashion until they are either stuck at an obstacle or reach the beacon's location. Beacons placed inside three-dimensional polytopes can be used to route point-like objects from one location to another. A second use case is to cover a polytope such that every point-like object at an arbitrary location in the polytope can reach at least one of the beacons once the latter is activated.

The topic of beacon-based routing and guarding was introduced by Biro et al. [2] in 2011 and covered in detail by Biro in his PhD thesis [1]. Therein various aspects of beacons in the polygonal domain of two dimensions were studied.

In this thesis we provide the first results for beacon-based routing and guarding for three dimensions. We first define the setting for three dimensions and look at two-dimensional beacon-based routing which lays the groundwork for our three-dimensional approach. We then have a look at the complexity of certain three-dimensional routing and guarding problems for which a smallest set of beacons should be obtained. We show that some of the problems are at least as hard as their two-dimensional counterpart which makes them NP-hard and APX-hard.

For the problem of finding a smallest set of beacons to be able to route between any pair of points in a polytope we show that it is always sufficient and sometimes necessary to place floor((m+1)/3) beacons, where m is the number of tetrahedra in a tetrahedral decomposition of the polytope.

Finally, we show that there exists a polytope which cannot be covered by placing a beacon at each vertex of the polytope.

[1] Michael Biro. “Beacon-Based Routing and Guarding”. PhD thesis. State University of New York at Stony Brook, 2013.

[2] Michael Biro, Jie Gao, Justin Iwerks, Irina Kostitsyna, and Joseph S. B. Mitchell. “Beacon-Based Routing and Coverage”. In: 21st Fall Workshop on Computational Geometry (FWCG 2011). 2011.

Klost, Katharina: Complexity of recognizing generalized transmission graphs

Abschluss
Master of Science (M.Sc.)
Abgabedatum
16.03.2017
Homepage des Autors

Der allgemeine Transmissionsgraph einer Menge von geometrischen Objekten, mit einem ausgezeichneten  Punkt für jedes Element der Menge, hat einen Knoten pro Element und eine gerichtete Kante (u,v) genau dann wenn der Punkt von v in u liegt. Diese Graphen sind ein mögliches Modell für Erreichbarkeit von Antennen.

Die Komplexitätsklasse ETR enthält alle Sprachen, die in Polynomialzeit auf einen Satz der Form ∃x_1,.,x_n:ϕ(x_1,..., x_n) reduziert werden können. Hierbei stammen x_1,..., x_n aus den reelen Zahlen. Es ist
bekannt, dass ETR zwischen NP und PSPACE liegt.

Für viele geometrische Entscheidungsprobleme, wie zum Beispiel das Erkennen von Kreisgraphen und  Schnittgraphen von Strecken ist bekannt, dass diese ETR-vollständig sind.

In dieser Arbeit werden allgemeine Transmissionsgraphen formal definiert und es wird gezeigt, dass das Erkennen von allgemeinen Transmissionsgraphen von k-Kugeln, regelmäßigen Polygonen, Strecken und Kreissektoren ETR-vollständig ist.

Mendoza, Daniel: Praktische Anwendungen des Fréchet-Abstands

Abschluss
Diplom
Abgabedatum
02.12.2016

Diese Diplomarbeit untersucht verschiedene Methoden, die die Fréchet-Metrik einsetzen. Beim Einsatz von GIS-Anwendungen für moderne Mobilgeräte sowie in der Entwicklung von Algorithmen Design hat die Fréchet-Metrik eine Schlüsselrolle. Vor allem die neuen Map-Matching-Algorithmen tragen bei Routing-Anwendungen zu effizienten Diensten und eröffnen zugleich immense Möglichkeiten für neue Anwendungsgebiete. Auch in der Bioinformatik bietet die Fréchet-Metrik zahlreiche Chancen. Im Gebiet der Nukleinsäuren- bzw. Proteinstrukturen existieren komplexe Strukturen, die sich durch Simulationen und Visualisierung durch die Fréchet-Metrik optimal vergleichen und vereinfachen lassen. Des Weiteren werden Anwendungen, die auf dem Dynamic Time Warping basieren, untersucht. Die diskrete Fréchet-Metrik ist eng mit der Dynamic-Time-Warping-Distanz verwandt, welche aus dem Kontext der Sprachsignalverarbeitung und Handschriftenerkennung sowie Schriftverifikation her bekannt ist. All diese Anwendungen werden nur theoretischer Natur untersucht und deren Ergebnisse vorgestellt.

Tippenhauer, Simon: On Planar 3-SAT and its Variants

Abschluss
Master of Science (M.Sc.)
Abgabedatum
15.11.2016

The aim of this study is to present a wide range of variants of Planar 3–SAT, to show their various use in many fields of computer science, and to identify their characteristics.

In 1977, David Lichtenstein introduced in his master thesis the concept of planar Boolean formulas. The motivation was to have an easier way to prove NP–completeness of properties for general graphs on their planar derivatives. Previously, the common approach was to first prove the NP–completeness for general graphs and then adjust the proof for planar graphs. This mainly involves the construction of complicated crossover boxes where two edges intersect. With Lichtenstein’s definition of Planar 3–SAT and its proof of NP–completeness he accomplished a new and often easier way to show NP-completeness for properties of planar graphs. It also opens the way for many variants of Planar 3–SAT and their usefulness for the study of computational complexity.

The idea of Planar 3–SAT is to restrict 3–SAT to Boolean formulas with some property that can be easily mapped to planar graphs. For that each Boolean formula φ in 3–CNF is associated with a graph. This graph consists of vertices for each variable and for each clause in φ. An edge is put between a variable-vertex and a clause-vertex if the clause contains a literal of the variable. Additionally the variable-vertices are connected with edges in a circular order.

The thesis concludes with some open problems and a categorization of the presented variants.

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

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.

Willert, Max: Routing Schemes for Disk Graphs and Polygons

Abschluss
Master of Education (M.Ed.)
Abgabedatum
09.08.2016
Homepage des Autors

Routing in networks is a fundamental problem that occurred in the 1980's and was well studied since then. However, there are still open problems, which have not been solved until now.

In this thesis I propose routing schemes for special graph classes. Let G=(V,E) be a weighted network or graph. For any two nodes  p, q in V, I would like to be able to route a data package from p to q. A routing scheme R assigns to each node p in V a label  l(p) from {0,1}* and a routing table rho(p) from {0,1}*. The label identifies the node in the network and the routing table is its own local read-only memory. Now the scheme works in the following way: the scheme starts with a current node p, the label of a target node and some additional information in the data package, called header. As a next step, the scheme computes a new node in the network, where the data package is forwarded to. It can use the information in the header and the local memory. The resulting sequence of nodes is the routing path. The stretch of R is the maximum ratio of the Euclidean length of the routing path and the shortest path.

Travelling in polygons is a well-known problem. The visibility graph VG(P) of a polygon P with n vertices and h holes is a graph in which two vertices in P are connected, iff they can see each other, meaning that the line segment between the two vertices is contained in P. I present the first routing scheme for polygons with holes. For any epsilon>0 the routing scheme provides the stretch 1+epsilon and uses no additional information in the header of a data package. The labels have O(log n) bits and the corresponding routing tables are of size O(epsilon^{-1} h log n). The preprocessing time is O(n^3+nh epsilon^{-1}) and can be improved for simple polygons to O(n^2+n epsilon^{-1}).

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

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].

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

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.

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

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.

Eversmann, Dustin: Interferenzminimierung in eindimensionalen Sensornetzen

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.

Stein, Yannik: Tolerated Tverberg Partitions: An Algorithmic Approach

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.

Seiferth, Paul: Computational Aspects of Triangulations with Constant Dilation

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. 

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

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.

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

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.

Smilevets, Anton: Optimale Stadt mit Lücken

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.

Georges, Robert: Online-Erkundung von Polygonen

Abschluss
Diplom
Abgabedatum
25.01.2012

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

Abschluss
Master of Science (M.Sc.)
Abgabedatum
01.01.2012

Driemel, Anne: Matching Polygonal Curves through Curvature

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.

Krause, Rasmus: 2,5-dimensionale Mechanismen

Abschluss
Diplom
Abgabedatum
01.01.2008

Schlipf, Lena: Kontrollpfadanfragen in einfachen Polygonen

Abschluss
Diplom
Abgabedatum
01.01.2008
Homepage des Autors

Skyarenko, Georgy: Optimale Manhattan-Netzwerke

Abschluss
Diplom
Abgabedatum
01.01.2008

Echterhoff, Jonas: Suchstrukturen für Formen

Abschluss
Diplom
Abgabedatum
01.01.2007

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

Abschluss
Diplom
Abgabedatum
01.01.2006

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

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.