A system to place observers on a polyhedral terrain in polynomial time

The Art Gallery Problem deals with determining the number of observers necessary to cover an art gallery room such that every point is seen by at least one observer. This problem is well known and has a linear time solution for the 2D case, but little is known in the 3D case. In this paper we present a polynomial time solution for the 3D version of the Art Gallery Problem. Because the problem is NP-hard, the solution presented is an...