Theses
Do you want to write your BSc or MSc thesis with our group? Please contact Prof. Kevin Buchin to inquire about potential research topics.
-
If you plan to write your BSc thesis in our group, you should have successfully completed Effiziente Algorithmen (EA) (and DAP2) and ideally a Fachproject or Proseminar on Algorithms.
-
If you plan to write your MSc thesis in our group, you should have successfully completed Algorithmen und Datenstrukturen (AuD) and ideally a specialized course and a seminar in the area of algorithms/algorithm engineering.
Past Theses
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.4312n)) and Hamiltonian (Ω(2.0886n)) 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(n2) 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(n2) time preprocessing and O(n2) 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.