Complexity of minimum corridor guarding problems
In this paper, the complexity of minimum corridor guarding problems is discussed. These problems can be described as: given a connected orthogonal arrangement of vertical and horizontal line segments and a guard with unlimited visibility along a line segment, find a tree or a closed walk with minimum total length along edges of the arrangement, such that if the guard runs on the tree or on the closed walk, all line segments are visited by the guard. These problems are proved to be NP-complete. (c) 2012 Elsevier B.V. All rights reserved.
corridor guarding computational complexity computational geometry np-complete