Real MATHEMATICS – Geometry #18

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:

20190328_130114.jpg

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:

20190328_123117.jpg

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:

20190328_123216.jpg

If we have a room plan as following:

20190328_123606.jpg

In such room, one guard doesn’t give enough coverage:

20190328_123732.jpg
Guard can’t see the blackened area.

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:

20190328_124639.jpg
We used 3 colors: 1, 2 and 3.

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:

20190328_124931.jpg

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:

20190328_130612.jpg

Next, we should color the vertices of the triangles:

20190328_130833.jpg

Three colors were used as follows:

20190328_131241.jpg

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…

  1. What would the answer be if there were columns inside the classroom as shown below?
    20190328_131619.jpg
  2. Can you find a relationship between the number of vertices of the polygon and number of guards?

M. Serkan Kalaycıoğlu

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s