Art gallery problems

Katie Steckles

You know when you have a real-world problem, and you realise there might be a mathematical approach to solving it? The other day, when I was building an art gallery, that’s exactly what happened to me. (Possibly not a completely true story).

If you’re building a room, or set of connected rooms, that you plan to fill with valuable items like works of art, it makes sense to install a state-of-the-art (no pun intended) security system in order to keep an eye on all your wonderful valuables. The rooms might be odd-shaped, and have corridors or funny-shaped sections, since you’d like your art gallery to have separate parts for different art styles, and for visitors to enjoy wandering around.

The problem with this is that even though they’re state-of-the-art, your security cameras can’t see through walls. You plan to mount the cameras in the corners where walls meet – and you could just mount one in every corner, then you’d definitely be able to see it all. But the cameras are pretty expensive, so you’d ideally like to use as few cameras as possible to cover the whole gallery. 

Given these constraints, mathematics is your friend – this is a well-known problem, called the Art Gallery problem, and it turns out the answer to this question has been known since the 1970s. To explain, we’ll need to define a few things.

If your gallery walls are all straight lines, the top-down view of the room will be in the form of a polygon – a many-sided shape (let’s say an n-sided shape, or n-gon). Our assumption is that if you draw a dot to mark a camera, that camera can see in all directions, and anywhere you can draw a straight line to/from the camera without passing through a wall is visible to that camera.

Some shapes of art galleries will make this job easier than others. A convex polygon (above) is one where each corner points outward – all the interior angles are less than 180 degrees, and no part of the boundary points in towards the middle. Most of the regular polygons you know the names of (squares, regular hexagons etc.) are convex polygons. For these shapes, you just need one camera placed at any corner, and you’re done!

Since we’d like our art gallery to have funky-shaped rooms, it’s clear it’ll likely be a non-convex polygon. For example, this L-shaped art gallery has an internal corner. If we wanted to cover this with cameras, we could again do it with one camera – positioned on that internal corner, it can see everywhere. (There are places I can put the camera that can’t see everywhere, as in the second picture, but we’re looking for a minimal set of cameras). So let’s look at some more complicated examples.

These galleries definitely all can’t be covered by a single camera.

So, assuming we’re positioning the cameras at the corners of a polygon, how can we determine which subset of these corners to use? And how many will be needed?

Light Camera Action

The question of how many was solved in 1975, when mathematician Václav Chvátal proved the Art Gallery theorem:

For an n-sided polygonal art gallery, the number of cameras needed will be at most ⌊n/3⌋.

Here, ⌊n/3⌋ is called the ‘floor’ of n/3 – this is the largest whole number less than n/3 (so, ⌊2.8⌋ = 2, and ⌊1⌋ = 1). This result means that for a 7-sided art gallery we’ll need at most 2 cameras, and for a 30-sided art gallery we might get away with as few as 10. Importantly, the result doesn’t guarantee you need as many as that – but this is a number of cameras which will definitely be sufficient, and might sometimes also be necessary.

The proof of this result is quite complicated – but luckily, in 1978, mathematician Steve Fisk came up with a much simpler proof of the theorem. In fact, the proof is considered by many to be a great example of a simple, elegant mathematical proof – it’s been described as ‘breathtaking’, and was included in a 1998 collection of maths’ most beautiful proofs, called ‘Proofs from the Book’.

It goes like this:

  1. Given a polygon, it’ll always be possible to divide it into triangles, without creating any extra points inside the shape. Below are some examples of polygons that have been triangulated – this is possible for any simple polygon (convex or non-convex), and can also be done with non-simple polygons (ones with holes in).
  1. Once you’ve done this, you’ll have a graph (a network) of nodes joined by lines. Assign a colour to each node, so that any two adjacent nodes (joined by a line) are different colours. This will always be possible to do using exactly three colours if the graph you’re colouring is a triangulation. If you’d like to try doing this for yourself, have a play with this triangulation colouring gadget I made.

(If you’re wondering why this is always possible, roughly: Any triangulation can be built up starting from a single triangle, and if your original triangle had three corners all coloured different colours, each time you add a corner it’ll be connected to two others that are different colours, so it can always be coloured the third colour).

  1. Of the three colours you’ll have used in your colouring, pick one that occurs least often (there might be multiple colours tied for this) – for example, in the colouring below, there are two blue nodes, two red and three green, so I could pick red or blue.
  1. Placing your camera at the points coloured with this colour will allow every point in the polygon to be in line of sight of at least one camera, using at most ⌊n/3⌋ cameras.

This simple method will always work and give you a subset of the corners that’s no more than a third of the total number of corners (which is the same as the number of sides on the polygon). However, this set is not necessarily optimal: for example, in this case the minimal set is the 3 blue nodes, but the same polygon can be guarded by only two guards.

Nobody puts baby in a corner

You might wonder if this still works if your cameras don’t have to be attached to the corners of the room – or even if they could be replaced by human (or robot, if you prefer) guards that stand in the centre of the room. It makes sense to use corners – since triangles are convex polygons, a camera or guard standing in a convex polygon can see all parts of the shape, but if we split a non-convex shape into triangles, putting cameras at the corners of triangles means they can see all parts of multiple triangles at once.

But if you’re not limited to corners, this maths still works – Chvátal’s upper limit of ⌊n/3⌋ remains true if the restriction to cameras in the corners is loosened to cameras/guards at any point inside the polygon. It’s also possible to extend this problem (and its proof) by considering particular types of shape.

For example, if you can divide your shape into a set of connected four-sided shapes (quadrilateralise it, as opposed to triangulating it), you can cover it using a mere ⌊n/4⌋cameras. This is true in particular of any polygon whose corners are all right angles, known as an orthogonal polygon.

There’s even a class of polygons called star-shaped polygons, which despite being non-convex, contain at least one point from which every part of the shape can be ‘seen’ by a camera positioned there – these shapes need only one camera, positioned at that focal point – that’ll really keep your camera budget down. Now if only I could convince the architects designing my art gallery that this is a great shape to make the room!

The post Art gallery problems originally appeared on the HLFF SciLogs blog.

Back