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.