Wireless Localization within Orthogonal Polyhedra
Tobias Christ, Michael M. Hoffmann · 2013
In the wireless localization problem, given a polygon P ⊂ R 2, we have to place guards and fix their angular range such that P can be described using these guards. The guards describe P if for every point pair p ∈ P and q / ∈ P, there is a guard that sees p but does not see q. We consider the analogous problem in 3D: given a polyhedron P ⊂ R 3, place guards—which now are polyhedral cones—that collectively describe P. Generalizing a known result for 2-dimensional orthogonal polygons, we show that for any given 3-regular orthogonal polyhedron P ⊂ R 3 with n vertices, it suffices to put a natural vertex guard onto every other vertex. (A natural vertex guard is a guard that is placed at a vertex v of P and the defining cone coincides with P in a sufficiently small neighborhood of v.) Furthermore, we show how to describe P with 3n/8 (general) vertex guards. 1