Navigationssysteme und Verkehrsschätzungen spielen eine entschei- dende Rolle im täglichen Leben, indem sie die Reisezeit verkürzen, den Kraftstoffverbrauch minimieren und die Sicherheit durch die Bereitstel- lung von Echtzeit-Verkehrsinformationen und optimalen Routen erhöhen. Ein wesentlicher Bestandteil dieser Systeme ist das Map-Matching, das rohe GPS-Koordinaten mit den entsprechenden Straßen auf einer digitalen Karte abgleicht. Diese Arbeit untersucht drei Hauptklassen von Map- Matching-Algorithmen: geometrische, max-weight und hybride Ansätze. Die Arbeit untersucht drei unterschiedliche Ansätze: zwei Max-Weight- Methoden basierend auf Hidden Markov Modellen, von denen eine eine Geschwindigkeitssteigerung durch Routen-Vorberechnung einbezieht, und eine hybride Methode, die die vertex-monotone Fréchet-Distanz verwen- det. Die theoretischen Grundlagen und die Laufzeitanalyse des Algorith- mus zur vertex-monotonen Fréchet-Distanz werden detailliert diskutiert. Ein wesentlicher Beitrag dieser Arbeit ist die Implementierung des Al- gorithmus zur vertex-monotonen Fréchet-Distanz in Rust, begleitet von einem Visualisierungstool, das die Überprüfung sowohl der abgeglichenen als auch der ursprünglichen Trajektorien ermöglicht.

Darüber hinaus präsentiert die Arbeit eine empirische Bewertung dieser Ansätze, mit einem Fokus auf Laufzeiten, Matching-Anteile und Trajekto- rienformen. Die Analyse umfasst Visualisierungen und Diskussionen zu verschiedenen Algorithmusparametern, wie räumlichen Strukturen, Toler- anzdistanzen und Gewichtungsfaktoren. Die primären Vergleichsmetriken sind Laufzeiten und Matching-Anteile, ergänzt durch manuelle Überprü- fungen der Routenformen mithilfe des Visualisierungstools.

This thesis presents a comprehensive survey of methods for maintaining a dynamic Minimum Spanning Forest in planar graphs, with a focus on analyzing the approaches of Gabow and Stallmann, as well as the work of Eppstein et al. Gabow and Stallmann’s method provides optimal performance for edge weight modifications in fixed graph struc- tures, while Eppstein et al. extended this by introducing support for dynamic structural changes. Their approach is based on a dynamic tree data structure, which allows the algo- rithm to achieve logarithmic time complexity per operation and linear space complexity. Additionally, a discussion on the lower bounds of the algorithms’ time complexity confirms their optimality under certain computational models.

Unlike conventional matching algorithms based on the combinatorial approach, we present an algebraically randomized algorithm for finding maximum (perfect) matchings in planar graphs. Our algorithms are, in part, based on an O(n^ω) Gaussian elimination approach induced in [18], and furthermore, combined with the separator theorem of planar graphs and the nest dissection algorithm, where the framework of separator tree has been utilized.

The running time of this algorithm is only O(n^ω/2), where ! is the matrix multipli- cation constant. Since ! now is somewhere between 2 and 2.373, this algorithm not only provides the first result of this kind of general planar graph to break through the O(n^1.5) barrier for the matching problem, but also might lead to a new practical approach to solving the maximum matching problem in planar graphs.

The Erdős-Szekeres theorem, established in the 1930s, posits that for a sufficiently large set of points in the plane in general position, it is guaranteed to contain n points forming a convex polygon. In other words, there exists a quantity denoted as N(n) such that any set of N(n) points contains a convex n-gon. This problem is colloquially referred to as the "happy ending problem."

The exact value of N(n) remains elusive, motivating efforts to establish both lower and upper bounds as accurately as possible. Over the course of more than 90 years, extensive research has been dedicated to refining the bounds. For general n, Erdős and Szekeres demonstrated in 1935that N(n) = 2^n-1 + 1. Over the course of these 90 years, there have been eight improvements to the original upper bound, albeit the majority of these remain within the limit of 4^n-o(n). A noteworthy development occurred in 2016 when Andrew Suk improved the upper bound to 2^{n +o(n)}. The best upper bound till today is 2^{n +O(√n logn)}.

Recently, a pertinent question has arisen in an article by G.Damasdi et al. concerning the Erdős-Szekeres problem. The question is to determine the smallest value, denoted as S(n), for which a set of S(n) points in general position in the plane does not form a convex n-gon initially, but the addition of any arbitrary point results in the formation of a convex n-gon. This question is of recent origin, with an unestablished upper bound, and it remains unresolved, even in relatively simple cases.

This thesis will commence with an introduction to foundational concepts and provide a historical perspective on the problem's evolution. Subsequently, it will survey the existing upper and lower bounds from the literature concerning the core Erdős-Szekeres problem, along with simpler instances. Following this, the thesis will shift its focus to an investigation of the open question, offering explanations for simple cases and formulating a conjecture regarding its bounds. Finally, it will introduce two interactive tools, namely, the saturation game and the extremal game, both rooted in the Erdős-Szekeres theorem and the open question.

Analyzing a theoretical problem often involves a single structure with multiple arrangements, like a binary tree with a fixed number of nodes where the tree structure can be different or the permutations of a fixed number of playing cards. Sampling random elements from these arrangements can be complex, especially if that structure has an exponential number of elements. In contrast, a definition of a local operation switching randomly between the arrangements is relatively easy, like the rotation of a tree or a shuffle of the cards.

We can use that if we start at one specific configuration and perform the operation until we get a random arrangement. The mixing time is the expected number of local operations we must perform to get from the fixed element to a random one.

We go through the main theory for deriving this mixing time, by A. Sinclair. For Catalan structures, a family of structures growing by following a specific sequence, we illustrate several techniques to derive bounds for that mixing time. These are analyzed, and the results are compared. Also, we give an outlook for applications in other contexts.

Die vielschichtige Komplexität in der Entwicklung, Pflege und Konfiguration von Software verlangt eine kontinuierliche Prozessoptimierung zur Effizienzsteigerung und Fehlerminimierung. Aus diesem Grund wird innerhalb dieser Arbeit eine domänenspezifische Konfigurationssprache für die Bibliothekssoftware ProBase Store des Unternehmens Diebold Nixdorf entwickelt, um den aktuellen Konfigurationsprozess von Retail-Geräten zu optimieren.

Im theoretischen Teil dieser Arbeit wird ein fundiertes Verständnis für formale Sprachen, Grammatiken und Compilerbau geschaffen, welches als Basis für die Entwicklung einer domänenspezifischen Sprache dient. Anschließend werden domänenspezifische Sprachen (DSLs) als Schnittstellen zwischen Mensch und Maschine definiert, was eine Bewertung hinsichtlich Usability ermöglicht. Diese Definition dient der Entwicklung einer dem Entwicklungsprozess folgenden Nutzerstudie zur Evaluation der Konfigurations-DSL hinsichtlich Effektivität, Effizienz sowie Benutzerzufriedenheit.

Auf Basis der theoretischen Grundlagen wird eine DSL unter Verwendung des Xtext-Frameworks entwickelt. Die Entwicklung beruht auf einer umfassenden Analyse der Konfigurationsdomäne und der dem vorherigen Konfigurationsprozess zugrundeliegenden Sprache, welche es ermöglicht, eine die DSL beschreibende kontextfreie Grammatik zu definieren. Darauf aufbauend werden sämtliche Bestandteile der DSL, einschließlich Validierungs- und Scoping-Mechanismen sowie die Abbildung auf die ursprüngliche Sprache, implementiert und in einen für den Konfigurationsprozess optimierte Web-basierten Editor integriert.

In einer Nutzerstudie mit 12 Teilnehmer:innen wird die entwickelte domänenspezifische Sprache (DSL) mit dem bisherigen Prozess verglichen. Die Ergebnisse der Studie zeigen, dass Teilnehmer:innen im Vergleich zum alten Prozess bei der Bearbeitung von Testaufgaben durchschnittlich 46,88 % weniger Zeit benötigen sowie 16,66 % weniger Fehler mit der DSL-basierten Lösung machen. Dies sorgt für eine signifikante Verbesserung in Bezug auf Effektivität (von 80,13 % auf 96,79 %) und Effizienz (von 76,91 % auf 93,59 %). Hinsichtlich Usability wird mit Hilfe der System-Usability-Scale (SUS) für den DSL-basierten Prozess ein durchschnittlicher Score von 87,71 ermittelt, was eine deutliche Steigerung im Vergleich zum alten Prozess (SUS-Score: 30,21) darstellt. Im Allgemeinen gelten Systeme mit einem SUS-Score von über 68 als überdurchschnittlich gut. Die Ergebnisse verdeutlichen das Potenzial von DSLs, um Entwicklungs- und Konfigurationsprozesse in Softwareprojekten zu optimieren, insbesondere wenn diese mit Toolunterstützung für Nutzer:innen zur Verfügung stehen.

Die Berechnung von kürzesten Wegen ist ein fundamentales Problem in Graphen. Eine besonders interessante Klasse von Graphen ist dabei der Unit Disk Graph, dessen Eigenschaften gut genutzt werden können, um effiziente Algorithmen für verschiedene Probleme auf diesen zu finden. Diese Arbeit behandelt drei fortgeschrittene Algorithmen für das kürzeste Wege Problem auf ungewichteten Unit Disk Graphen, die auf diesen Graphen das SSSP Problem in O(n log n) Zeit und das APSP Problem sogar in leichter subquadratischer Zeit O(n² sqrt(log log n) / log n)) lösen können.

Diese wurden vorgestellt, erklärt, analysiert, im Rahmen der Arbeit implementiert und dann auf eine mögliche Anwendung evaluiert. Ein paar der Algorithmen haben sich dabei als gut implementierbar herausgestellt, deren Vorteile sich gegenüber den einfacheren Standardalgorithmen jedoch nur auf sehr großen Unit Disk Graphen zeigen werden.

In dieser Ausarbeitung werden verschiedene Clipping-Algorithmen für Dreiecke vorgestellt und in Bezug auf ihren Rechenaufwand miteinander verglichen. Einer von ihnen ist ein für diese Abschlussarbeit entwickelter Algorithmus, der auf Entscheidungsbäumen basiert. Es geht darum, seine Entwicklung vorzustellen und zu messen, ob sich dieser Ansatz im Vergleich zu herkömmlichen Clipping-Algorithmen als effizient erweist. Es soll hierbei ein möglichst genaues Ergebnis< durch Zählen der arithmetischen Punktoperationen erzielt werden: Benötigt der hier entwickelte Algorithmus die gleiche oder sogar eine geringere Anzahl arithmetischer Operationen, so ist die Effizienz und damit auch eine gleichwertige bzw. höhere Aufwandsgerechtigkeit erwiesen. Eine praktische Anwendung dieser Überlegungen für die beim Rendern von tessellierten 3D-Modellen verwendeten Dreiecke wäre vorstellbar.

The complexity class Unique End of Potential Line (UniqueEOPL) was introduced in 2018 by Fearnley et al. and captures total search problems that are promised to have a unique solution. Therefore, the original promise version of each problem is transformed to a total search version. UniqueEOPL contains some interesting problems like P-LCP, Cube-USO and Arrival. It is an especially interesting class because it has a  ”natural” complete problem: One Permutation Discrete Contraction (OPDC).

The goal of this work is to give a comprehensive introduction to the complexity theory of search problems with a focus on the class UniqueEOPL. A list of all currently known problems in UniqueEOPL is presented and for each problem, a definition and examples are given. Some selected reductions are shown in full detail and with corrections.

The main contribution is the new containment result of Grid-USO in UniqueEOPL, which is proven via a reduction from Grid-USO to Unique Forward EOPL. From that result it also follows that P-GLCP is contained in UniqueEOPL too.

The pairing heap is an efficient, easy-to-implement self-adjusting heap which is in widespread practical use. Multiple variants of this heap have been proposed in the original paper by Fredman, Sedgewick, Sleator and Tarjan, but these have proven difficult to analyse. Furthermore, a related heap – the smooth heap – has recently been proposed and partial theoretical analysis of this heap appears promising. Stable linking, which is a twist on the linking operation used by pairing heaps, is a characteristic operation of this heap. This operation can be retrofitted into the pairing heap, giving rise to further heap variants. We implement these variants and measure efficiency by counting the number of link operations and the number of comparisons performed overall in various experimental settings, viz. in sorting mode and when used as priority queues in Dijkstra’s algorithm forshortest paths.

The results suggest that the original variant of the pairing heap is generally superior to its other variants, and that the smooth heap may outperform the pairing heap and its variants in certain cases. The smooth heap performs particularly well in sorting mode – when sorting inputs which contain many sorted subsequences – and perhaps also in use cases where the number of decrease-key operations dominates the others. In these cases, smooth heaps perform fewer comparisons and fewer link operations than the pairing heap and its variants. Furthermore, in more general settings the smooth heap appears to perform fewer link operations than all pairing heap variants, at the cost of requiring slightly more comparisons. Depending on the relative cost of linking operations and comparisons this might mean that the smooth heap outperforms the pairing heap in practice even in general cases.

It is also shown that none of the heaps considered here are capable of sorting Jordan permutations, a special permutation class, in linear time.

Furthermore, two theoretical results for related heaps are shown: First, that the sort heap, proposed by Iacono and Özkan as an instance of their pure heap model which has amortised cost O(log log n) insert and decrease-key operations and O(log n log log n) amortised delete-min, does not in fact conform to those worst-case bounds, because the proof of this bound for decrease-key is flawed.

Finally, we show a property of instances of the stable heap model, to which the smooth heap conforms. We prove that the order in which stable-links are performed during consolidation of the forest into a single heap is not relevant for the outcome, because any resulting tree can also be constructed using a sequence of stable-links which requires only O(n) pointer moves.

Many algorithms to compute convex hulls or envelopes are static and cannot be extended to work dynamically, that is, to support changes like insertions or deletions in the data set. Overmars and van Leeuwen proposed a data structure that allows this for both convex hulls and envelopes. The data structure is a binary search tree where elements are stored in the leafs and the internal nodes are augmented with another data structure to store the convex hull or envelope. Recently a new algorithm was developed to maintain the lower envelope of pseudo-lines by Agarwal et al. which is based on the Overmars and van Leeuwen data structures.

While dynamic convex hulls have been studied extensively from a theoretical perspective, there is only very little experimental work. In this work we evaluate the practicability of the Overmars and van Leeuwen data structure and its extension by Agarwal et al.

We implemented and compared several versions of the data structure by Overmars and van Leeuwen and compared it to a simple approach based on maintaining the Delaunay triangulation. In our experiments, Delaunay triangulations outperformed the dedicated data structures except for very large sizes of convex hulls.

We also implemented the data structure for maintaining the lower envelope of pseudo-lines by Agarwal et al. The algorithm performs as expected, but our implementation suffers from robustness issues.

The Hitting Set Problem is a well-studied, NP-complete problem in combinatorial optimization. It can be formulated as follows: Given a finite ground set X and a collection R of its subsets, find a minimum-cardinality set H ⊆ X which intersects (hits) all sets in R. In this thesis we focus on special cases where X is a set of points in plane, and elements of R correspond to geometric objects. We describe different approximation techniques used for attacking these problems, namely LP-rounding, ε-nets, local search, as well as greedy algorithms.

In chapter 2, we describe three techniques for approximating the general hitting set problem: greedy, randomized rounding and ε-nets. In chapter 3, we describe several geometric instances of the problem. Section 3.1 describes the well-known interval hitting problem, that will be used in later sections for solving more difficult cases. Section 3.2 is about hitting sets of horizontal segments and vertical lines, where we give an approximation algorithm and a bound on the duality gap. The next two sections describe two useful approximation techniques, namely LP-rounding (section 3.3) and local search (section 3.4). Section 3.5 is about a special case of the art gallery problem, where guards have the so-called rook vision. The results in section 3.5 and the bounds on the duality gap in 3.2.2 are original.

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.

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

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.

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.

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

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.

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.

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.

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.

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 ∈ R² 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.

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.

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.

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.

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.

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.

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}).

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

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.

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.

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.

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.

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. 

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.

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.

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.

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.

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.