Art Gallery Problem
The Art Gallery Problem: How Many Security Guards Do We Need?
Key concepts
Simple Polygon: A polygon without holes or intersecting edges
Visibility & line of sight: A guard sees a point if the line segment between them lies entirely inside the polygon.
Convex Polygon: A simple polygon where every interior angle measures less than 180 degrees
How many guards do you think are needed for a convex polygon?
Applet by Alfred Estberg: https://www.geogebra.org/m/hFWCcgrR
Convex vs Concave Polygons and New Challenges
For convex polygons, only one guard is ever needed, no matter how many vertices the polygon has.
- In a convex gallery, placing a single guard at any point (even in the interior) means they can see every other point in the gallery because:
- No walls "block" their vision (no reflex angles).
- Every straight line from the guard to any wall remains entirely inside the polygon.
Applet by Alfred Estberg: https://www.geogebra.org/m/hFWCcgrR
Lemma
Every polygon can be triangulated because any polygon with n vertices can be divided into n-2 triangles by adding non-intersecting diagonals.
Why do you think we are choosing to triangulate the polygon?
What is the purpose?
A guard placed at the vertex of a triangle (which is also a vertex of the polygon) can oversee the whole triangle. This is because a triangle is a convex shape: the straight line connecting any two points in the triangle is entirely contained within the triangle. So if we place a guard at a vertex of each triangle then our problem is solved. Each guard will oversee the corresponding triangle, and since the triangles together cover the whole polygon, we have ensured that the whole polygon is guarded.
Triangulate Steps
Triangulate: Break the polygon into triangles without adding new vertices (only drawing inside edges)
- Select the Segment Tool
- Connect non-adjacent points with adjacent points with segments - but only inside the polygon
- Try to divide the shape into triangles
3-Colouring Steps
Let's try and colour the vertices using three different colours so that every individual triangle has no two vertices with the same colour.
3-Colouring: Assign one of three colours to each vertex so no two connected vertices share a colour.
- Right-click on a vertex - object properties - colour tab
- Choose one of three colours (for ex: red,blue,green)- Colour vertices manually following 3-colouring rules:
- No two connected points (sharing an edge) can have the same colour
Tip: Start at one vertex, assign red, then neighbors get Blue/Green
Let's say we place a guard at each vertex with the same colour. Since every triangle has exactly one vertex with that colour, this gives us one guard for each triangle, so this placement of guards makes sure they can together see the whole gallery.
Try Triangulating and 3-Colouring this Polygon
But how many guards does this require?
The colouring partitions the collection of vertices into three groups; one for each colour. Since we are trying to minimize the number of guards, we are interested in the smallest of these three groups. A bit of thought will convince you that this smallest group will never contain more than n/3 vertices. So we will never need more than n/3 guards to supervise the gallery.
Try Triangulating and 3-Colouring this Polygon
Applet by Alfred Estberg: https://www.geogebra.org/m/hFWCcgrR
Chvátal's Theorem
"To guard a simple polygon with 
vertices,
guards are always sufficient and sometimes necessary."
vertices, guards are always sufficient and sometimes necessary."Applications
The problem's solution has broader implications. The techniques used to solve it, such as triangulation and vertex colouring, are applicable in:
- Robotics: Determining optimal paths and positions for robots navigating obstacle-filled environments.
- Image Processing: Algorithms for image segmentation and object recognition can draw inspiration from visibility considerations.
- Infrastructure Planning: Optimizing the placement of security cameras or warning systems in large areas.