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.

► We study a building with corridors patrolled by a guard with unlimited scope. ► The minimum corridor guarding problem is to find the optimal motion plan. ► We prove this problems is NP-complete, even all corridors are orthogonal.