Consider a city with m parallel horizontal streets and n parallel vertical avenues. These lines cross in m × n intersections. On k ∈ {1, . . . , m × n} of these intersections, special checkpoints are placed. We want to place video cameras on a subset of the streets and of the avenues such that each checkpoint is in the visibility range of a camera. A camera allows to monitor all the checkpoints of an avenue or of a street. The subset of may contain both horizontal streets and vertical avenues. Clearly, you can always select all m + n of these streets and avenues. The challenge therefore is to select a smallest subset of these streets and avenues such that each checkpoint is in the visibility range of a camera.

Problem: Give an algorithm that finds such a smallest subset of streets and avenues where to place cameras in time polynomial in m and n. Prove that the algorithm is correct and provide an analysis of its running time.

  • 1
    What have you tried? Where did you get stuck? – dkaeae Dec 6 at 14:07
  • Welcome to Computer Science! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered. – Apass.Jack Dec 6 at 14:46

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.