How to solve this problem?

The following question is taken from EPI book (it is a variant of the interval covering problem):

You are responsible for the security of a castle. The castle has a circular perimeter. A total of z robots Patrol the perimeter---each robot is responsible for a closed connected subset of the perimeter, i.e., an arc. (The arcs for different robots may overlap.) You want to monitor the robots by installing cameras at the center of the castle that look out to the perimeter. Each camera can look along a ray. To save cost, you would like to minimize the number of cameras. Find the minimum number of cameras required to cover all the robots.

See Figure, for an example:

image

Comments (1)