Non-orthogonal ray guarding

Abstract

In an earlier paper the notion of a ray guard --'- a guard that can only see along a single ray, was introduced. The ray guarding problem is in siting the fewest possible such guards so that they guard all adjacencies (shared edges or parts of edges) in an orthogonal arrangement of adjacent non-overlapping 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 pla­nar 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 can be extended to this problem as well. Current work is on devel­oping heuristic algorithms for non-orthogonal ray guarding of adjacent rectangles and for the non-orthogonal ray guarding of convex polygons.