Theses

Simon Bülhoff, BSc

Mohammed-Khir Hatem, BSc

Joshua Kirchberg, BSc

Diese Arbeit beschäftigt sich mit einem neuen Ansatz zur Lösungsfindung von Signed und Unsigned Edge Matching Puzzles. Dazu wird ein SAT Modell gebildet, welches zunächst eindimensionale Puzzles beschreiben und lösen soll. Dieses Modell wird dann in Verfahren eingebettet, welche die Lösung eines zweidimensionalen Puzzles zum Ziel haben. Insgesamt werden zwei solcher Verfahren - ein Iterator und ein Backtrackingverfahren - vorgestellt. Ein Vergleich der beiden Verfahren stellt zunächst die Schwächen heraus, die ein iterativer Ansatz gegen¨uber der Tiefensuche mit Backtracking hat, während der Vergleich mit ähnlichen Lösungsverfahren zeigt, dass sich das eindimensionale SAT Verfahren der vorliegenden Arbeit unter bestimmen Bedingungen als kompetitiv erweist. Diese Erkenntnisse werden schließlich in einem Fazit zusammengefasst.

Lisa Salewsky, MSc

The ability to create customizable roundtrips is crucial for many people who enjoy outdoor activities. In this work, the Touring Problem is used to nd good routes that adhere to user-preferences. Finding and creating good and customizable routes for various outdoor sports that are presented in a user-friendly application which works in real time is the key problem this thesis addresses.
Much research has been done for shortest path problems and nding the quickest or fastest route, however, previous work lacked to address roundtrip paths. For these problems, a shortest or quickest route is not enough. Instead, a multitude of constraints has to be considered while trying to nd a relatively good solution.
In order to generate a user-friendly app that can compute roundtrips in real time for outdoor activities, an interface has been created. The web interface was structured to be easy to understand and use while simultaneously oering a good overview of all parameters for customization as well as all calculated tours. Additionally, dierent metaheuristics, i.e. Ant Colony and Simulated Annealing, have been implemented to solve the Touring Problem.
The resulting application is easy to use and oers a selection of algorithms to calculate the desired tours. Several tests were conducted, which demonstrated that the metaheuristics return results that match the user's preferences. All algorithms can be congured to run in real time, yet an option to allow for longer run times exists. Thus, the app is user friendly and generates solution tours for the Touring Problem in real time.

Jan Erik Swiadek, MSc

Joel Haubold, MSc

Alexander Korn, MSc

Datasets containing human or animal movement are often very sparse due to poor GPSreception during recording or considerations concerning the battery life of GPS trackers. Still, it may be desirable to estimate which path the observed subject could have taken. A practical solution to this problem is to interpolate between measurements using random walks. We extend a previous approach for generating random walks efficiently using dynamic programming by utilizing probabilities instead of absolute values during the computation. Besides being faster and more memory-efficient, this extension allows generating different kinds of random walks by incorporating probability kernels. Furthermore, a framework written in Rust is introduced that allows efficiently generating random walks and working with large datasets to generate random walks on specific data. Additionally, Python bindings are implemented, allowing users from other research fields to easily use the the framework. Finally, experiments using the framework are conducted, demonstrating the framework’s functionality, and comparing the results to other approaches.

Nicolas Wünderich, BSc

David Feininger, MSc

This master's thesis explores the use of map matching algorithms to automatically generate routes for GPS-Art. In GPS-Art, an artist attempts to create images, patterns, or text by walking or driving along a planned route. The goal of this work is to read in a given image and find a suitable route nearby that follows the road network and matches the image as closely as possible. Map matching algorithms are used to map temporally ordered GPS points on the road network. The work investigates two map matching methods: One follows a Greedy approach and the other is based on Fréchet distance. The Greedy algorithm uses a similarity measure to locally select the best edge, incrementally generating the path for GPS drawing. The Fréchet algorithm uses binary search to find an optimal upper bound for the Fréchet distance. In addition, Fréchet distance and Dynamic Time Warping are investigated as qua- lity measures to evaluate the automatically generated paths. Through numerous experiments, it is shown in this paper that both quality measures are not suitable for evaluation. Furthermore, the experiments reveal that both algorithms can achieve good results, but further research is needed to improve accuracy and speed.

Zafer Özsoy, BSc

Jona Scholz, BSc

We study the Minimum Cover by Convex Polygons problem, the problem of decomposing a polygon into a union of convex parts. Three algorithms that use another cover as input and try to reduce the size of that cover are presented.
The first algorithm, ConnectPolygons, greedily combines neighbouring polygons with convex unions. ConnectSetCover, an improvement of ConnectPolygons, also combines neighbouring polygons, but it finds all possible convex unions and uses the greedy approximation of the SetCover algorithm to remove unnecessary polygons. The third algorithm, Growing, adds new vertices to cover polygons at the vertices of the input polygon. We analyse the performance of the algorithms on the polygons from the 2023 CG:Shop challenge. The starting cover we used for the challenge are triangulations. On average, the output from ConnectPolygons was about a third of the size of the triangulation. ConnectSetCover performs better than ConnectPolygons, but has an increased runtime. Out of all three algorithms, Growing performed the worst while having the highest runtime.

Kateryna Brekhunenko, BSc

We focus on the following question: What is the amount of simple and Hamiltonian cycles a planar graph with n vertices can contain? We present three different approaches to represent simple and Hamiltonian cycles to compute the respective lower bounds on this amount. We have experimented with string, integer, and 2-Motzkin path representations, with the last proven most efficient. We computed new improved lower bounds for simple (Ω(2.4312ⁿ)) and Hamiltonian (Ω(2.0886ⁿ)) cycles using the transfer matrix technique on a twisted cylinder.

Lars Nitzschke, BSc

The Travelling Salesperson Problem (TSP) is one of the most important combinatorial optimization problems. As the TSP is a NP-hard problem, heuristics like 2-OPT were developed to find good, but not necessarily perfect, tours efficiently. The concept of the 2-OPT heuristic relies on replacing two crossing edges in the tour by two straight edges. An intuitive algorithm for this procedure runs in O(n²) time, but in recent research a new approach was presented solving 2-OPT in O(n log n) per iteration in the repeated setting. This approach uses multiple trees storing the current tour, one tree for each edge in the tour, which allows for a more efficient search for improving 2-OPT moves. The algorithm needs O(n²) time preprocessing and O(n²) storage space. In this thesis the theoretical runtimes of the new algorithm are confirmed by a practical implementation. Additionally, the new approach is being optimized for practical performance by reducing runtimes as well as memory usage.