Date of Award
Computational Geomery, Computational Complexity, Corridor Guarding
"In this paper, the complexity of minimum corridor guarding problems is discussed. These problem can be described as: given a connected orthogo-nal arrangement of vertical and horizontal line segments and a guard with unlimited visibility along a line segment, find a tree or a closed tour with minimum total length along edges of the arrangement, such that if the guard runs on the tree or on the closed tour, all line segments are visited by the guard. These problems are proved to be NP-complete. Keywords: computational complexity, computational geometry, corridor guarding, NP-complete"
Xu, Ning, "Complexity of Minimum Corridor Guarding Problems" (2011). CUNY Academic Works.