The ROM Crystal

While roaming the Royal Ontario Museum (or ROM for short) with friends at Nuit Blanche in Toronto, I told them about the Art Gallery Problem. The problem is to station guards in the museum so they can see everywhere. For simplicity, a guard can see 360 degrees unless she is blocked by a wall.

In a museum with a square shape, this is easy: one guard can see everything from any point in the museum. In fact, this is true for any museum with a convex shape. If we consider the shape formed by the walls of the museum, then we have a polygon. A polygon is convex if a line segment between any two points of it remain in the polygon. So a triangle or square are convex, and one guard suffices.

The ROM, however, has a striking, non-convex architecture, with lots of oddly sloped walls. They call it the ROM Crystal for a reason! The image below depicts the floor plans of the ROM, where you can see Crystal growing out of the architecture of the historical building.

 

The Art Gallery Problem

If a museum doesn’t have a convex shape, then how best to guard it?  If you had an unusual museum shaped like a comb with five teeth, then it is not difficult to see you need at least five guards: one for each tooth of the comb. In fact, five is enough, which you can see by placing the guards at the bottom of each triangle.

A solution to the Art Gallery Problem was given by mathematician Václav Chvátal in 1975: in a museum with n walls, then ⌊ n/3 ⌋ guards can guard it. Here, ⌊ n/3 ⌋ is the floor of n/3, the least integer less than or equal to n/3. So for example, if n = 16, then five guards suffice.

We’ll call this the Art Gallery Theorem. Here is the journal citation.

V. Chvátal, A combinatorial theorem in plane geometry, Journal of Combinatorial Theory, Series B, 18 (1975) 39–41.

Proof of the Art Gallery Theorem

The proof of the theorem is short and elegant.

First, we take our polygon P with its n walls and n vertices and triangulate it. In other words, split up the interior into triangles, so the vertices of the triangle correspond to vertices (i.e. corners) of the polygon. We can always do this at least in one way, and I’ll discuss that part later. This makes the polygon into something called a planar graph, where the vertices of the graph are vertices of the polygon, the edges of the graph are the lines of the triangulation, and the faces are the triangles.

The famous Four Color Theorem tells us that every planar graph can be 4-colored: we can color the vertices with four colors so no two adjacent ones have the same color. But we can do better in art galleries, using only three colors.

The proof is by induction on the number of vertices, n: if we can 3-color polygons with n or fewer vertices (our induction hypothesis), then we can 3-color an (n+1)-sided one.

If we have n = 3, then we have a triangle, and we can 3-color that by assigning distinct colors to the vertices. Now suppose you have n + 1 sides to your polygon, where n > 3. Choose some diagonal connecting two vertices x and y of the polygon. In other words, x and y are not adjacent vertices in the polygon. Break the polygon into two smaller ones along the diagonal connecting x and y.

We are now poised to use induction.  The two smaller polygons have n or fewer vertices so we can 3-color each of them by induction hypothesis. By shuffling the colors if needed in these smaller polygons, we can ensure both x and y are colored the same colors. Now glue the two polygons together again and we have a 3-coloring of all the vertices of P.

We’ve split the vertices into three groups, defined by their colors, and say that the colors are red, blue, and green. One of these groups has size no bigger than ⌊ n/3 ⌋; otherwise, if each group were bigger, than we would have more than n vertices in total, which is a contradiction. Say the red group of vertices has size at most ⌊ n/3 ⌋.

Say the red group of vertices has size at most ⌊ n/3 ⌋. Put a guard on each red vertex. That guard is sitting in a triangle and so can see everything in it. As there is a guard on each triangle and the museum is completely tiled with triangles, we can see the whole museum with our ⌊ n/3 ⌋ guards.

This proof is so lovely. We only need a few things from geometry to make it perfectly precise.

1. Each polygon has a convex vertex: a vertex with interior angle at most 180 degrees.
2. We can triangulate every polygon.

I’m leaving these as exercises. The hint for (2) is to use induction.

Variations

There are many variations on the Art Gallery Problem. For example, we can allow holes inside the polygon or insist its walls be perpendicular. The guards can be mobile or you can consider polygonal shapes in three or more dimensions.

All of these variations take us into the field of computational geometry, where the Art Gallery Problem is a fundamental area of research. As the name suggests, computational geometry synthesizes algorithmic ideas and geometric ones.

There are applications of these kinds of mathematical problems to designing video games and computer vision, where algorithms analyze visual data. As such, computational geometry is relevant to CGI and the hot field of self-driving cars.

The moral of the story: be careful letting mathematicians loose in an art gallery. You never know what kind of theorems they will uncover.

Anthony Bonato