The Geometry Problem That Could Have Protected the French Royal Jewels

Imagine you’re in charge of placing security cameras inside a gallery filled with valuable objects. Your boss is willing to pay to put in as many cameras at it will take to protect the gallery’s contents, provided you meet two conditions:

1. The cameras must collectively provide 100% visual coverage of the entire area of the gallery.
2. You have to determine the minimum number of cameras that will be needed to do the job.

Believe it or not, this is a famous 50-year old geometry problem that’s known as the art gallery problem. In the following 50-minute video, CC Academy describes how the problem can be solved using graph theory for any strangely shaped floorplan:

Kit Yates discusses why the recent heist of the French royal jewels from the Louvre Museum in Paris brings home the importance of this geometry problem:

At a hearing in front of the French Senate in the immediate aftermath of the robbery, Laurence des Cars, the director of the world famous museum, admitted that the museum had “failed to protect” the crown jewels. She admitted that the only camera covering the balcony the thieves used was facing the wrong way and a preliminary report revealed one in three rooms in the Denon wing where the thieves struck had no security cameras. More generally Des Cars acknowledged that cuts in surveillance and security staff had left the museum vulnerable and insisted that the Louvre’s security system must be reinforced to “look everywhere“.

Alarms at the museum apparently sounded as they should, according to the French culture ministry. Yet it is the third high profile theft from French museums in two months, which have left the ministry implementing new security plans across France.

As they should, if for no other reason than because their security scheme has been shown to have gaping holes that thieves an easily drive a Böcker Agilo truck-mounted moving lift through.

But more to the point, had those responsible for overseeing the Louvre’s security solved their specific version of the art gallery problem, the thieves’ plans might have been thwarted. Yates concisely explains how to quickly determine how many cameras you might need using only geometric principles:

The answer, it turns out, depends on the number of corners (or, as mathematicians call them, “vertices”), as there will be as many walls as there are corners in a room. Some simple division helps us work out how many cameras are needed.

By dividing the number of corners in a room by three, that will tell us how many cameras are needed to cover it, assuming they have a full 360 degree field of view….

This even works if the number of corners isn’t neatly divisible by three. For a 20-sided gallery, for example, the answer works out at six and two thirds. In these cases you can take the whole number – so we’d never need more than six cameras in a 20-sided room.

Yates continues by getting into the graph theory that tells where those 360-degree view cameras can then be optimally placed.

In 1978 Steve Fisk, a mathematics professor at Bowdoin college in Maine, US, came up with a proof – considered one of the most elegant in all of mathematics – of this lower limit on the number of cameras needed.

His strategy was to divide the gallery up into triangles (check out the left image of the figure below). He then proved that you can pick just three colours – say red, yellow and blue – and assign a different colour to the corners of each triangle. This would mean that every triangle in your gallery has a different colour in its three corners (See the right image of the figure below for an example). This is known as “three-colouring” the corners.

Triangles are one of those “convex” polygons we mentioned earlier, so a camera positioned at any corner (or indeed anywhere in the triangle) can see every point in that shape. Every triangle has corners with each of the three colours. That means you can pick just one of the colours and place cameras at those positions. Those cameras will be able to see every part of every triangle, and hence every part of the gallery. But here’s the best part.

The beauty of Fisk’s proof is you can just choose the colour with the fewest dots, and you’ll still cover the whole gallery. In the 15-sided shape above, by choosing the red dots, we can get away with only four cameras.

What are the chances that all of France’s art gallery security problems are now homework assignments for the country’s undergraduate math students taking courses in either geometry or graph theory?

Image credit: Art Gallery Problem sample with 4 cameras by Rocchini on Wikimedia Commons Creative Commons CC BY 3.0 Attribution 3.0 Unported Deed.