02.04.2025, 14.15 Uhr
Vortragender: Matthias Artmann

Title: On the Shape Containment Problem within the Amoebot Model with Reconfigurable Circuits

Abstract: In programmable matter, we consider a large number of tiny, primitive computational entities called particles that run distributed algorithms to control global properties of the particle structure. In this paper, we study the shape containment problem, where the particles are given a description of a shape S and have to find maximally scaled representations of S within their initial configuration. We use the geometric amoebot model for programmable matter with its reconfigurable circuit extension, which allows the instantaneous transmission of primitive signals on connected subsets of particles.
We first prove a lower runtime bound of Omega(sqrt(n)) synchronous rounds for the general problem, where n is the number of particles. Then, we construct the class of snowflake shapes and its subclass of star convex shapes, and present solutions for both. Let k be the maximum scale of the considered shape in a given amoebot structure. If the shape is star convex, we solve it within O(log^2 k) rounds. If it is a snowflake but not star convex, we solve it within O(sqrt(n) log n) rounds.
In this talk, I will give a brief overview of the shape containment problem and the construction of snowflake shapes.

23.07.2025, 14.00 Uhr
Vortragender: Henning Hillebrandt 

Title: A New Algorithm for Exact SSSP in Hybrid Networks

Abstract: Computing Single-Source Shortest Paths (SSSP) is a fundamental problem in distributed computing and an important building block for many distributed algorithms. In this talk, I present a new algorithm for solving the exact SSSP problem in the HYBRID network model. The algorithm computes exact shortest paths in weighted, directed graphs in time Õ(n^(1/3)), with high probability, matching the best-known result by Censor-Hillel et al. [STACS '21] despite only needing a local capacity of λ = Θ(|E|/n^(1/3)). It builds upon the SSSP framework from Forster and Nanongkai [FOCS '18], which was originally designed for the CONGEST model. The result is obtained through an efficient HYBRID implementation of their generic SSSP algorithm. To this end, I show how to compute a (1+o(1))-approximate solution of the h-hop-limited k-Source-Shortest Paths problem in weighted, directed graphs in time Õ(k + h^(1/2)), with high probability.

06.08.2025, 14.00 Uhr
Vortragender: Alexander Nickel, Antrittsvortrag Master bei M. Fischer 

Title: Know Your Limit - Frame Time Estimation for 3D Realtime Applications

Abstract: In dieser Arbeit soll ein Algorithmus entwickelt werden, der im Rahmen der folgenden Technologien und Hardware, die Renderingzeit (GPU Zeit) eines beliebigen Frames, einer beliebigen Szene, in einer beliebigen Anwendung auf einem beliebigen Computer abschätzt. Die Technologien, die untersucht werden, sind die Texturen Verarbeitung, Lichtberechnung, Schattenberechnung, Ray Tracing und Antialiasing. Diese Eigenschaften werden mithilfe der Grafik Engine Software Godot untersucht. Eine moderne und beliebte Open Source Grafik Engine neben Unreal Engine und Unity die Grafik-APIs wie Vulkan verwendet. Für die Untersuchung werden im ersten Schritt nur die Computer eingesetzt, die mir von der Arbeitsgruppe „Algorithmen und Komplexität“ bereitgestellt wurden. Des Weiteren werden die Technologien, die in meiner Bachelorarbeit „Entwicklung und Analyse von Formeln zur Abschätzung der Renderingzeit eines Frames“ untersucht wurden, mit untersucht. Hierbei handelt es sich um eine Formel, die mithilfe von Knoten, Dreiecken, Vertex-Buffer-Objects (VBOs) und Surfels eine Framezeit (GPU Zeit) abschätzen kann.
 

06.08.2025, 14.30 Uhr
Vortragender: Thilo Berger, Antrittsvortrag Master 

Title: Comparing Existing Methods to Efficiently Place Drones to Connect Isolated Communication Clusters

Abstract: The problem setting is the following: we have many nodes which are randomly distributed over some space and which are able to communicate with each other if they are in close proximity. These distributed communication cluster have to be separately connected via edges to enable global communication. Our goal is to minimize the resulting cost. My masterthesis aims to implement and compare different approaches for the resulting sub-problems.

20.08.2025, 14.00 Uhr
Vortragende: Priyanka Giri

Title: Near-Shortest Path Routing in Hybrid Communication Networks Using Python

Abstract: This thesis presents a grid-based abstraction framework to optimize pathfinding in large-scale hybrid networks, where nodes operate over hybrid communication network. By mapping complex Unit Disk Graph (UDG) topologies to structured grid graphs, the study significantly reduces computational complexity while preserving essential connectivity. The work evaluates Dijkstra’s, Bellman-Ford, and A* algorithms using Python’s NetworkX, analyzing metrics such as path efficiency, computation time, scalability, and packet transmission success rate. Results show that the proposed approach enhances routing performance and scalability without compromising path quality, offering practical applications in vehicular networks, IoT systems, and large-scale wireless infrastructures.

27.08.2025, 14.00 Uhr
Vortragender: Ibrahim Abdul Rahman, Antrittsvortrag Bachelor, bei Matthias Fischer

Title: Effiziente Datenstrukturen und Algorithmen für die Kollisionserkennung im zweidimensionalen Raum 

Abstract: Diese Arbeit untersucht und vergleicht drei etablierte Datenstrukturen – Quadtrees, Bounding Volume Hierarchies (BVH) und Uniform Grids – im Kontext der 2D-Kollisionserkennung. Ziel ist es, ihre Effizienz, Anpassungsfähigkeit und Skalierbarkeit in unterschiedlichen Anwendungsszenarien zu analysieren, etwa bei vielen kleinen oder wenigen großen Objekten. Dazu wird eine eigens in C++ entwickelte 2D-Spielplattform als Testumgebung eingesetzt, die präzise Messungen von Laufzeit und Speicherverbrauch ermöglicht. Die Experimente erlauben eine differenzierte Bewertung der Stärken und Schwächen der einzelnen Ansätze und zeigen gezielte Optimierungspotenziale auf. Die Ergebnisse liefern nicht nur wissenschaftliche Erkenntnisse, sondern auch praxisrelevante Empfehlungen zur Wahl geeigneter Datenstrukturen in Echtzeitanwendungen.