Finding the Minimum Number of Face Guards is NP-Hard
Chuzo IWAMOTO, Yusuke KITAGAKI, Kenichi Morita · IEICE Transactions on Information and Systems · 2012
We study the complexity of finding the minimum number of face guards which can observe the whole surface of a polyhedral terrain. Here, a face guard is allowed to be placed on the faces of a terrain, and the guard can walk around on the allocated face. It is shown that finding the minimum number of face guards is NP-hard.