Not homework (from the telly): A gallery takes a concave polygon shape with a square pillar in the centre. security cameras can do a 360 degree sweep but they can't see around corners. The cameras have to be attached to the walls. What is the fewest number of cameras such that they can see everywhere in the gallery?
I got as far as drawing it in Maple.
there is an algorithm -which supposedly finds the optimal solutuion- breaking the object into triangular shapes. that gets an answer: 4 cameras.
this is based on Fisk's short proof. See Markiyan's wiki ref below.
1.first stand on on a corner and scan clockwise around the room. Any two corners passed creates one triangle.
Repeat for every corner
2. Pick three colours and allocate each color to each corner of each triangle.
sometimes you will end up with a triangle which has 2 corners of the same colour. This one has two blue corners
This triangle must be broken in two and add a green dot
3.finally the algorithm places cameras on the colour which occurs least.
But by experimenting with more complex shapes (convex polygons) you can cover the gallery with 3.
In Maple anyone?