Combinatorics of Beacon-based Routing in Three Dimensions
| Autor: | Cleve, Jonas, Mulzer, Wolfgang |
|---|---|
| Rok vydání: | 2017 |
| Předmět: | |
| Zdroj: | Computational Geometry: Theory and Applications (CGTA), 91, 2020, Article 101667 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1016/j.comgeo.2020.101667 |
| Popis: | 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 polyhedra can be used to route point-like objects from one location to another. A second use case is to cover a polyhedron such that every point-like object at an arbitrary location in the polyhedron can reach at least one of the beacons once the latter is activated. The notion of beacon-based routing and guarding was introduced by Biro et al. [FWCG'11] in 2011 and covered in detail by Biro in his PhD thesis [SUNY-SB'13], which focuses on the two-dimensional case. We extend Biro's result to three dimensions by considering beacon routing in polyhedra. We show that $\lfloor\frac{m+1}{3}\rfloor$ beacons are always sufficient and sometimes necessary to route between any pair of points in a given polyhedron $P$, where $m$ is the number of tetrahedra in a tetrahedral decomposition of $P$. This is one of the first results that show that beacon routing is also possible in three dimensions. Comment: v1 published in "LATIN 2018: Theoretical Informatics"; v2 to be published in "Computational Geometry - Theory and Application" |
| Databáze: | arXiv |
| Externí odkaz: |
|