I read this problem in Computational Geometry:Algorithms and Applications.
Consider a art gallery whose shape is a 2D simple polygon without any hole. One is asked to put minimum number of 360° surveillance cameras such that every wall (every edge of the polygon) can be seen from at least one of the cameras.
The book provides a upperbound of on the minimum number of cameras as well as an algorithm to compute the solution. The method, which is based on triangulation, is the following. Decomposing the polygon into triangles gives us an outerplanar graph which guarantees a 3-coloring. Observe that 3 vertices in one triangle must have 3 different colors. Thus installing cameras on vertices with one of the three colors is sufficient. The complexity follows from the fact that triangulation for simple polygon can be done in and finding a 3-coloring in outerplanar graph takes linear time.
Note that section 3.4 of Computational Geometry:Algorithms and Applications contains useful comments. There is even a book on the art gallery guardian problem. In section 1.4 the author discussed convex partition which is partly what i’m thinking about while reading that CG book.
Note that only one camera is needed for any convex polygon. So the minimum number of convex decomposition is also an upperbound for the art gallery guardian problem. However, I can only find bounds for optimal convex decomposition with respect to the number of reflex vertices(degree > π)…