The idle ramblings of a Jack of some trades, Master of none

Okay, so I attended a Gresham College lecture on Monday. It was good fun although I did drop off briefly, much to the consternation of the oldies who had filled the auditorium of the Royal College of Surgeons. What can I say? After the (interesting) theory, the practical applications became a bit long-winded and repetitive, and on a stuffed stomach, it was difficult to focus.

At any rate, as I said, it was good fun. John D. Barrow is an engaging speaker, and he started off with a cheery anecdote of a visit he had made a decade or so ago to a museum in Milan that showcased art fraud. On various floors of the museum, one could see both genuine and fake artefacts from the past few centuries. The experts and curators there had expertise in manifold fields - physics, biology, mathematics - and they worked on techniques to isolate fraud. Imagine, said Dr Barrow, that you could model the pattern of cracks on paint in an artwork. You could tell, then, if a given painting - even if executed in old paint on old parchment with an old brush - had aged as much a genuine contemporary painting. The curators organised a seminar to discuss this and other techniques, and found that it attracted quite a varied audience. Then they received a phone call from Milan's Chief of Police.

"It's wonderful you have arranged this programme," said the Chief. "But we are a bit concerned at the audience - there are many members of Northern Italy's crime families among them!"

The curators didn't hold another such seminar again.

"But that shouldn't stop us from discussing techniques to detect fraud!" added Dr Barrow cheerfully.

Of course, not all the lecture was about forgeries. He started by explaining that the triangle was the only linear shape in the plane that was rigid - that is, could not be deformed without breakage. A square can be pushed into a rhombus, and any other polygon can be modified as well. This explains why gates, for example, have triangular struts built onto them, and electric pylons are a network of triangular meshes as well. In 3 dimensions, though, all convex polyhedrons are rigid, and only the rare non-convex linear surface is not.

From the idea of the rigid triangle, Dr Barrow moved onto triangulation - that is, the splitting up of a general polygonal shape into triangles. It is immediately apparent that each of the sides of every triangle is visible from any point within it. So, if you have the following problem - what is the maximum number of guards one needs to be able to cover all the interior walls of a museum? - it is obvious: as many as the number of triangles in the triangulation. Essentially, if there are n walls, you need at most n - 2 guards.

Even better, stick a guard on a diagonal formed by one of the interior sides of each triangle. Such a guard can look into two triangles, and so you can reduce the number of minions by a half. Or how about you place a guard at a vertex of the polygon? Colour each vertex of the triangles a different colour such that no two coloured vertices are on the same line. You only need three colours to do this. Assigning a guard to a corner with a particular colour - say, blue - enables you to reduce your employees to the integer part of (n / 3).

And that, ladies and gents, is the Chvátal Art Gallery Theorem:
For a simple polygon with n corners, [n/3] cameras are sufficient and sometimes necessary to have every interior point visible from at least one of the cameras.
Dr Barrow then went on to show lower bounds on the number of guards under various conditions: the guards don't move, or they can only move along a wall, extending the coverage area to interior and exterior walls, ... It was at this point that I fell asleep.

Check out the lecture here.


Post a Comment