# Oberseminar

## Wintersemester 2019/2020

##### Jannik Castenow

#### October 16, 2019, 14:00 pm, F1.110

**Stretching a Communication Chain of Oblivious Mobile Robots — The Continuous Case**

In the talk, we consider the problem of arranging a communication of n robots on a straight line of length n-1. The robots have a limited viewing range of 1, do not agree on a coordinate system or compass and are oblivious. In contrast to previous talks about this problem, we consider the continuous time model in which robots can continuously observe their environment and can immediately adjust their own trajectory based on their observations. We introduce the Max-Move-On-Bisector strategy, analyze its behavior in one-dimensional configurations and give insights about the current state of research about two-dimensional configurations.

##### Sascha Brandt

#### October 09, 2019, 14:00 pm, F1.110

**Visibility-Aware Progressive Farthest Point Sampling on the GPU**

In this talk, I present the first algorithm for progressive sampling of 3D surfaces with blue noise characteristics that runs entirely on the GPU. The performance of the algorithm is comparable to state-of-the-art GPU Poisson-disk sampling methods, while additionally producing ordered sequences of samples where every prefix exhibits good blue noise properties.

The basic idea is, to reduce the 3D sampling domain to a set of 2.5D images which we sample in parallel utilizing the rasterization hardware of current GPUs. This allows for simple visibility-aware sampling that only captures the surface as seen from outside the sampled object, which is especially useful for point-based level-of-detail rendering methods. However, the method can be easily extended for sampling the entire surface without changing the basic algorithm. I provide a statistical analysis of our algorithm and show that it produces good blue noise characteristics for every prefix of the resulting sample sequence and analyze the performance of the method compared to related state-of-the-art sampling methods.

## Sommersemester 2019

##### Michael Braun

#### October 02, 2019, 14:00 pm, F1.544

**Local Gathering of Mobile Robots in Three Dimensions**

In the future, large groups of inexpensive robots might be used to collectively perform a variety of tasks. In order to facilitate this, there has been a considerable interest in the investigation of related algorithmic and complexity problems.

One particular problem that has been studied is robot-gathering in which all robots have to meet at some (non-specified) point in a Euclidean space, starting from an arbitrary configuration. Furthermore, it is typically assumed that the robots only have a limited vision range, share no information and have to act in a distributed fashion.

In this setting and under a synchronous, discrete time model, Ando et al. presented an algorithm called Go-to-the-Center, that solves this problem. Degener et al. could then show that this takes \theta(n^2) rounds. Under a continuous time model, Podlipyan described the class of contracting algorithms, for which he could show a gathering time of O(nd), where d is the initial diameter of the configuration. Kempkes et al. could show that a member of this class known as Move-on-Bisector can solve gathering in time O(n) in the continuous time setting.

However, all of these results have so far only been established in the two-dimensional Euclidean space. The goal of my master's thesis is therefore to attempt to find generalizations of these results for three or even higher dimensions.

(Introductory presentation Master's thesis)

##### Project group DragRace

#### September 30, 2019, 2:00 pm, F1.110

**Dynamic Rendering And Generation of Real-time Adaptive Complex Environments**

In this presentation we will give an overview over the work of the DRAGRACE project group. We have created a 3D-environment generator capable of dynamically generating randomized landscapes during runtime in virtually arbitrary size featuring among other things cities, different vegetation and various terrain types. The generator has a server component enabling multiple users to explore these landscapes at the same time. Our work has been implemented using the PADrend platforms to provide easily extendable rendering functions.

(Final presentation)

##### Ansgar Mährlein

#### August 14, 2019, 2:00 pm, F1.110

**Performance Optimization for FlightSimulation through CullingAlgorithms**

In the final presentation of my master thesis, i will present occlusion culling algorithms for flight simulation. Scenes encountered in flight simulators are usually quite flat with a viewpoint high above the scene. However, when simulating low enough flight in alpine regions, the undulating terrain can provide a high level occlusion. Additionally, the three-dimensional cockpit model of some simulators can also occlude large parts of the scenery. I will present two algorithms that take advantage of the occlusion in the two aforementioned cases, and show that performance gains of up to 400% are attainable in flight simulation use cases in mountainous regions.

(Final presentation Master's thesis)

##### Sören Möllers

#### May 08, 2019, 14:15, F1.110

**Effiziente prozedurale Generierung von Flüssen und Seen mithilfe lokaler Simulation von Erosion**

Prozedural Generierung virtueller Landschaften ist für viele Computerspiele und Simulationen essentieller Bestandteil. Oft werden Erosionsprozesse von Wasser simuliert, die Flüsse und Seen produzieren und die Landschaft natürlicher wirken lassen. Diese Methoden bauen auf regulären Gittern als Repräsentation der Landschaft auf und führen unnötige Berechnungen aus auch in Bereichen, die nicht von Erosion betroffen sind. Um diese aufwändigen Simulationen zu beschleunigen, wird eine Methode vorgeschlagen, die die Simulationsgitter in einer hierarchischen Datenstruktur, genauer einer Art von Quadtree, speichert und so die Simulation auf Bereiche starker Erosion beschränkt. Dabei passt sich der Algorithmus adaptiv der Verteilung von Wasser an und erhöht in entsprechenden Regionen die Auflösung der Landschaft. Die Evaluation zeigt, dass eine solche adaptive Datenstruktur die Perfomance in einigen Situationen tatsächlich verbessern kann ohne die Simulationsqualität merklich zu mindern.

##### Simon Pukrop

#### May 08, 2019, 14:45, F1.110

**Scheduling Algorithms for Multi-Operation Jobs with Setups on a Single Machine**

In this final presentation of my master thesis, we will have a look at a realistic, but not much researched, scheduling setting. In the problem class we consider composed jobs represented by a set of operations, which themselves are ordered into different families. When scheduling operations of different families back to back one induces additional costs in the form of a setup time. We describe the quality of a schedule by its total completion time. I will present and explain our new (and first known) approach that yields polynomial time constant factor approximations for this NP-hard problem.