It took a mere eight minutes. In those 480 seconds, thieves trundled their way upwards on a mechanical platform to reach a first-floor balcony of the Louvre museum in Paris before cutting their way through a window in broad daylight. Once inside, they broke into two glass display cases and then escaped with eight priceless Napoleonic-era crown jewels. It was a "daring heist" that has shaken France to its core. 

Seven suspects have now been arrested over the theft. One of the lingering questions that has dogged the robbery investigation, however, is why the thieves were not spotted sooner.

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.

Security system must be reinforced

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. 

While there is no doubt that modern museum security is a complex and expensive affair, there is also an intriguing 50-year-old mathematical problem that deals with this very issue.

It asks, what is the minimum number of guards – or equivalently 360-degree CCTV cameras – needed in order to keep a whole museum under observation? It is known as the museum problem, or the art gallery problem. The solution is an elegant one. 

A polygon

We will assume that all the walls of our imaginary museum are straight lines so that the floorplan is what mathematicians call a polygon, a shape with hard edges and corners. The cameras must be at fixed positions, but they can see in all directions. To ensure the whole museum is covered, we should be able to draw a straight line from any point in the floorplan to at least one of the cameras.

Take the hexagon-shaped gallery on the left of the diagram below. No matter where you place the camera, you will be able to see floor and walls of the entire space. When every position can be seen from every other in this way, we call the gallery shape a convex polygon.

The L-shaped gallery in the middle is non-convex, which means you are limited in your camera placement, but we can still find spots from where a single camera can see all of the gallery. A Z-shaped gallery needs two cameras to cover it – there are always spots that one camera alone will miss. 

It is possible to find camera positions which cover every point in the left two galleries, but no single camera can cover the whole of the right-hand gallery. Image: Kit Yates.

For more interesting floorplans (check out the unusual 15-sided floorplan below) it is far harder to know how many cameras will be needed or where they should be placed. Fortunately for cash-strapped museum directors, graph theorist Václav Chvátal solved the museum problem in general terms soon after it was posed in 1973.

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 works even for complex shapes like our weird, 15-sided gallery below. In this case there are 15 corners, so 15 divided by three equals five. 

Complex shapes make it harder to work out where best to place cameras to monitor a gallery. Image: Kit Yates.

This even works if the number of corners is not 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 would never need more than six cameras in a 20-sided room.  

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 a mere 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. 

By dividing a complex gallery shape into triangles and assigning one of three colours to each corner of the triangle, you can see where to position cameras. Image: Kit Yates.

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 is the best part. 

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

Temporary blind spots

In fact, the red dot in the top left is not necessary, because the next red camera can cover its entire surveillance space. So we could even get away with three cameras for this gallery. This is particularly true if we were fitting modern omnidirectional cameras, rather than the old school, wide-angle CCTV feeds that would need to sweep across an area to provide full coverage, creating temporary blind spots.

But, it is worth remembering that many traditional museums like the Louvre have mostly rectangular rooms. Fortunately, a variant of the art gallery problem shows that when walls meet at right angles, we only need one camera to cover the whole room.

In her testimony, Des Cars also acknowledged that the Louvre’s perimeter cameras do not cover all external walls. "We did not spot the arrival of the thieves early enough... the weakness of our perimeter protection is known," she said.

Fortunately, there are versions of the problem, known as 'the fortress problem' or 'the prison problem', that solve the camera coverage issue for the exterior of a building too. 

What both variants reveal, however, is that finding the right vantage points is essential. But it is important to acknowledge that thieves who enter through public galleries are not the only threat faced by museums. The British Museum in London, for example saw a Cartier ring worth £760,000 go missing in 2011 from a collection that was not on public display. Gems from the museum were found on sale on eBay in 2020 after allegedly been taken by one of the museum's own curators.

Alongside theft, museums also have to protect their collections from vandalism, fire and other forms of destruction.

Even so, the art gallery problem is worth the attention of those outside the hallowed halls of museums. It has applications in a range of fields where visibility and coverage are critical.

Robotics

In robotics, for example, it helps autonomous systems improve efficiency and prevent collisions. In urban planning, it informs the positioning of radio antennae, mobile phone transmission stations or pollution detectors to ensure comprehensive coverage of public spaces. 

Disaster management strategies use similar principles to position drones to survey large-scale disaster sites from the air or to situate medical field stations. In image editing and computer vision, the art gallery problem can aid in identifying visible regions within a scene. It can help ensure performers are always illuminated on stage and even help museums ensure their galleries are appropriately lit.

The Louvre did not respond to questions from the BBC about whether it was aware of the solutions offered by the museum problem – it undoubtedly has more pressing issues to deal with. But as museums and art galleries around the world look again at their own security in the wake of the Louvre heist, it can do no harm to be reminded of the lessons this 50-year-old mathematical problem has to offer. 

Author: Kit Yates. This article first appeared on BBC.com