Non-orthogonal ray guarding
Ian Douglas Sanders · 1998
In an earlier paper the notion of a ray guard, a guard that can only see along a single ray, was introduced. Ray guarding means siting the fewest possible guards that guard all adjacencies (shared edges or parts of edges) in an orthogonal arrangement of adjacent nonoverlapping rectangles. In the earlier paper the problem was restricted by requiring that the direction of sight be parallel to one of the Cartesian axes. This problem was shown to be NP-Complete by a transformation from the vertex cover problem for planar graphs. This paper discusses the more general problem where the rays are not restricted to being orthogonal, the same ray can thus cut both horizontal and vertical adjacencies between adjacent rectangles. The problem is shown to be NP-Complete by a transformation from planar vertex cover. The problem of siting ray guards to cover the adjacencies between adjacent convex polygons is a more general case of the non-orthogonal ray guarding problem and the NP-Completeness proof c...