Here is a problem: One should position the least amount of cameras in an art gallery. The walls in the gallery are represented only by horizontal and vertical line segments.
I am trying to find the least amount of cameras possible at first. Given that the gallery is represented as a graph it seems that I should place n/4 cameras, where n is a number of vertices in the graph. And I am struggling around it.
What I know how to do is how to triangulate the gallery. I suspect it can help immensely.
So, how can I show that n/4 cameras at most are needed to cover such a gallery?