[Mittagsseminar TI] Fwd: [i-prof] Einladung zur Verteidigung meiner Masterarbeit

[Wolfgang Mulzer <mulzer@inf.fu-berlin.de>]

-------- Forwarded Message --------
Subject: [i-prof] Einladung zur Verteidigung meiner Masterarbeit
Date: Tue, 28 Mar 2017 11:23:05 +0200
From: Jonas Cleve <jonascleve@mi.fu-berlin.de>
To: i-prof@inf.fu-berlin.de, i-wimi@inf.fu-berlin.de,
i-studi@inf.fu-berlin.de
CC: diana.schueler@fu-berlin.de, SeraRenee.Zentiks@fu-berlin.de

Sehr geehrte Damen und Herren,

hiermit lade ich Sie zur Verteidigung meiner Masterarbeit mit dem Titel
„Combinatorics of Beacon-based Routing and Guarding in Three Dimensions“
ein.

Die Präsentation findet am

	Donnerstag, den 30.03.2017 um 12:00 s.t. im Raum SR 055

im Rahmen des Mittagsseminars der Theoretischen Informatik statt.
Die Arbeit wurde von Prof. Dr. Wolfgang Mulzer betreut, Zweitgutachter
ist Dr. Frank Hoffmann.

Mit freundlichen Grüßen
Jonas Cleve

*Abstract:*

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.

Attachment: smime.p7s
Description: S/MIME Cryptographic Signature