Orthogonal art gallery problem.

$\begingroup$

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?

$\endgroup$ 5 Sorted by: Reset to default

Know someone who can answer? Share a link to this question via email, Twitter, or Facebook.

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy