Orthogonal ray guarding of adjacencies between orthogonal rectangles

Abstract

Guarding and covering problems have great importance in Computational Geometry. In this article the notion of' a ray guard, a guard that can only 'see' along a single ray, is introduced. The problem of siting the fewest possible such guards so that they guard all adjacencies in an orthogonal arrangement of adjacent non-overlapping rectangles is discussed. The problem is farther restricted by requiring that the direction of sight be parallel to an axis and that the guards cannot 'see' outside the rectangles. The problem is motivated by applications in architecture and urban planning. This article shows that the problem is NP-Complete because of the locally indeterminate choice which can be introduced in positioning guards.