Protect the Cake
Holy cake is coming to the school today. It will be open for visit in one of the classrooms. You are responsible for the protection of the holy cake. But you have limited people under your command which is why you should use minimum number of guards to protect the holy cake.
About the guards: A museum guard stays at a fixed point and observes the art piece(s) from that point. Obviously guard can see every angle around him/herself by simply rotating.
Floor plan of the classroom is like the following:
Find the minimum number of guards needed in order to protect the holy cake in this room.
Polygonal Rooms
First we will be examining the simplest polygon.
Example 1: Triangle room.
Assume that holy cake is inside a triangle room. One guard is enough for protecting the cake as he/she will be able to see every part of the room:
Example 2: Rectangle room.
Again one guard will be enough:
Q: Is one guard enough for all polygon-shaped rooms?
Convex-Concave: A polygon is convex if each of its internal angles is less than 180 degrees. Otherwise that polygon is called concave.
As we can see above, all convex polygons can be protected by a single guard. Although it can’t be said for all concave polygons.
Now we know that the room of holy cake is a concave polygon. Let’s examine a simple concave polygon first:
It is possible to protect the room if we place the guard right on the vertex of the angle that is greater than 180 degrees:
If we have a room plan as following:
In such room, one guard doesn’t give enough coverage:
Art Gallery Problem
Before moving on the more complex room plans, we have to check if there is any algorithm for finding the necessary number of guards in concave polygons. This problem was first posed by a mathematician named Victor Klee in 1973 and is called art gallery problem. In order to find the necessary number of guards in a room, we should use a method called triangulation.
Triangulation: Basically it is a process that enables us to divide any polygon into triangles.
Let’s take a concave polygon as an example. First we should use triangulation:
Then we should color the vertices of the triangles. In any triangle vertices must have different colors:
Number of guards is the least used vertex color. If guards take positions at those vertices, they will be able to see the room completely:
Least numbered colors are 2 and 3. Placing guards on either of them is enough to cover the whole room. If, let’s say, we choose to place two guards on the color 3, room will be protected.
Solution
We are finally ready to solve the holy cake problem. First we should triangulate the floor plan of the classroom:
Next, we should color the vertices of the triangles:
Three colors were used as follows:
The least used colors are 1 and 3. This gives us the number of guards needed (that is 6) in order to protect the holy cake. If, let’s say we choose to place the guards on the vertices with color 1, room will be covered completely.
One wonders…
- What would the answer be if there were columns inside the classroom as shown below?
- Can you find a relationship between the number of vertices of the polygon and number of guards?
M. Serkan Kalaycıoğlu
kmatematikatolyesi.com 