Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Physical Sciences and Mathematics
Complexity Of Minimum Corridor Guarding Problems, Ning Xu
Complexity Of Minimum Corridor Guarding Problems, Ning Xu
Dissertations and Theses
"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"