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.
In fact, the red dot in the top left isn’t 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’s 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.
First Appeared on
Source link
