"Heist of the Century" - could a simple maths problem have foiled the Louvre robbery
Mathematician have a well-known problem about how to efficiently protect galleries - it's even called "The museum problem"
It took just 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.
Two suspects have now been arrested over the theft. One of the lingering questions that has dogged the investigation into the robbery, 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 CCTV 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.
While there’s 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’s 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.
We’ll assume that the walls of our imaginary museum are straight lines so that the floorplan is what mathematicians call a polygon. The cameras must be at fixed positions, but 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 floor plan to at least one of the cameras.
As we can see in the diagram below, for a hexagon-shaped gallery, wherever we place the camera we can see the 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. An L-shaped gallery is non-convex but we can still find spots from where we can see all of the gallery. Conversely a Z-shaped gallery needs two cameras to cover it – there are always spots that one camera alone will miss.
For more interesting floorplans (check out the unusual 15-sided floorplan below) it’s far harder to know how many cameras will be needed or where they should be placed. Fortunately 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” – which is the same as the number of walls. If there are N vertices then you will never need more than N/3 cameras to cover the whole gallery. If N isn’t easily divisible by three then we only need the whole number in the answer. For a 20-sided gallery, for example, 20/3 = 6 and 2/3, so we will need no more than 6 cameras.
For the 15-sided gallery below, we will never need more than 15/3 =5 cameras.
In 1978 Steve Fisk, a mathematics professor at Bowdoin college in Maine, US, came up with a proof – considered to be 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 each vertex of each triangle could be coloured with one of three colours such that all the triangles had three different coloured vertices (see the right image of the figure below for an example). This is known as a three-colouring of the vertices.
Triangles are convex polygons, so a camera positioned at any vertex (or indeed anywhere in the triangle) can see every point in that triangle. Because every triangle has vertices with each of the three colours, if we pick just one of the colours and place cameras at those positions they will be able to see every part of every triangle and hence every part of the gallery.
Each of the three colours provides camera positions that would cover the gallery, so we are free to choose the colour with the fewest dots as the positions for our cameras. In the 15-sided gallery above, by choosing the red dots, we can get away with only four cameras. In fact, the left-most red camera’s surveillance area is completely covered by its red neighbour, so we could even get away with three cameras for this gallery.
Which makes us wonder whether we might get away with even fewer cameras in general. Sadly there are galleries like the 12-sided ‘comb’ gallery below, which really do need all 12/3 = 4 cameras. To see the pinnacles of each tooth of the comb a camera must be positioned within each of the green triangles. Since the triangles don’t overlap we really do need all four cameras to cover the space.
Many traditional museums like the Louvre have mostly rectangular rooms. A variant of the art gallery problem shows that when walls meet at right angles, the number of cameras needed drops to the whole number part of N/4.
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 admitted.
Fortunately, there are versions of the problem, known as “the fortress problem” or “the prison problem”, that solve the camera coverage problem for the exterior of a building too.
What both variants reveal, however, is that finding the right vantage points is essential. But it’s 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 ($950,000) go missing in 2011 from a collection not on public display and 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 destruction, according to the International Council of Museums.
Even so, the museum problem is worth the attention of people other than gallery owners and museum directors as it has applications in a range of fields where visibility and coverage are critical. 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 my questions 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.
This piece is adapted from a piece I wrote that originally appeared on BBC Future.