The Art Gallery Theorem: ⌊n/3⌋ Guards Always Suffice for a Simple Polygon with n Walls

What the art gallery theorem says

Model the gallery as a simple polygon P: a closed region bounded by n straight walls that meet only at their shared endpoints, with no holes and no self-crossings. A guard is a point of P. Guard g sees a point q when the whole segment gq lies in P — vision is 360°, range is unlimited, and walls are opaque. A set of guards covers the gallery when every point of P is seen by at least one of them.

Chvátal's theorem has two halves, and both matter:

• Sufficiency. For every simple polygon with n ≥ 3 vertices there is a set of at most ⌊n/3⌋ vertices that covers it. Guards may be restricted to corners without losing anything in the worst case.
• Necessity. For every n ≥ 3 there is a simple polygon with n vertices that cannot be covered by fewer than ⌊n/3⌋ guards — not even by guards placed freely anywhere inside.

Small cases are a good sanity check. A triangle, a quadrilateral and a pentagon all have ⌊n/3⌋ = 1, and indeed every simple polygon with at most five vertices is covered by a single guard. For the pentagon the reason is pretty: two diagonals cut it into three triangles, and two non-crossing diagonals of a pentagon always share an endpoint, so the cut is a fan from one corner — and that corner is a corner of all three triangles, so it sees the whole room. Note that it need not be a reflex corner, and that standing on just any reflex corner is not enough: a pentagon with two reflex corners can have one of them that misses a sliver. The first genuine difficulty appears at n = 6, where ⌊6/3⌋ = 2 and a two-pronged comb really does need two guards. A 12-wall gallery is guaranteed by 4 guards, a 100-wall gallery by 33, a 1000-wall gallery by 333.

The word always is doing the work. ⌊n/3⌋ is a promise about the worst floor plan with n walls, not a prediction about yours. The 12-wall gallery in the animation has colour classes of sizes 5, 4 and 3, so Fisk's construction hands back three guards where the theorem only promised four — and three is itself one too many. Two of its corners already cover it between them, and no single point of it sees the whole floor: two of its walls face away from each other, and a guard who can see one of them must stand on a strip of the plan that the other strip never touches, so the polygon's kernel — the set of points that see everything — is empty. Its true minimum is therefore exactly two. Promise four, construct three, need two.

Fisk's proof in four moves

Steve Fisk's 1978 argument is one paragraph long and every step is visible in the animation.

1. Triangulate. Cut P into triangles using only diagonals — segments between two vertices that stay inside the polygon and cross nothing. A simple polygon with n vertices always admits such a cut, and it always produces exactly n − 2 triangles and n − 3 diagonals. The gallery in the video has 12 walls, so 10 triangles and 9 diagonals, every time, whichever triangulation you pick.
2. Three-colour the corners. Treat the walls and diagonals as the edges of a graph on the n vertices. This graph is 3-colourable: colour one triangle's three corners 1, 2, 3, then walk outward across diagonals. Each new triangle shares a diagonal — hence two already-coloured corners — with a triangle you have finished, so its third corner is forced to the one remaining colour. The walk never returns to a coloured triangle from a new direction, because the dual graph of the triangulation is a tree (see the next section), so no conflict can ever arise.
3. Every triangle gets all three colours. That is not an extra assumption; it is what a proper colouring of a triangle means. A triangle's three corners are pairwise joined by walls or diagonals, so they must carry three different colours.
4. Pigeonhole. The three colour classes partition the n vertices. If their sizes are a ≤ b ≤ c with a + b + c = n, then 3a ≤ n, so a ≤ n/3, and because a is a whole number, a ≤ ⌊n/3⌋. Post a guard on every vertex of the smallest class.

Why that finishes it. Every triangle of the triangulation contains a vertex of the smallest colour class. A triangle is convex and lies inside P, so a guard at one of its corners sees all of it. The triangles cover P. Therefore the guards cover P, using at most ⌊n/3⌋ of them.

Worked on the video's gallery: n = 12, the colour classes come out at 5, 4 and 3, and min(5, 4, 3) = 3 ≤ ⌊12/3⌋ = 4. The three chosen corners sit on 3, 3 and 4 triangles respectively — 3 + 3 + 4 = 10, the whole triangulation, with no triangle counted twice.

What the picture proves and what it assumes. The animation runs one honest instance of the argument: a real ear-clipping triangulation, a real proper 3-colouring, a real count. It does not prove the two general facts it leans on — that a triangulation always exists, and that the dual is a tree. Those are theorems, and they are the subject of the next section.

Why every simple polygon can be triangulated

The triangulation step looks obvious and is not. It fails in three dimensions: Schönhardt's twisted prism (1928) is a non-convex polyhedron with six vertices that cannot be cut into tetrahedra without adding new points, which is one reason the art gallery theorem has no clean three-dimensional analogue.

In the plane it is true, and the cleanest route is Meisters' two ears theorem (G. H. Meisters, “Polygons have ears,” American Mathematical Monthly 82 (1975), 648–651). An ear is a vertex whose two neighbours can be joined by a diagonal. Meisters proved that every simple polygon with n ≥ 4 vertices has at least two non-overlapping ears. Clip one ear off, and you are left with a simple polygon on n − 1 vertices; induct. Each clip removes one vertex and adds one triangle and one diagonal, which is where n − 2 triangles and n − 3 diagonals come from — and it matches the Euler count for a disc cut into triangles.

The dual graph is a tree. Build a graph with one node per triangle and an edge whenever two triangles share a diagonal. Each diagonal is shared by exactly two triangles, so the dual has (n − 2) nodes and (n − 3) edges. It is connected, because the polygon is connected. A connected graph with one fewer edge than nodes is a tree, so the dual has no cycles. That acyclicity is the whole reason the greedy 3-colouring never paints itself into a corner: you meet every triangle exactly once, across a single already-coloured diagonal.

Where it breaks. Add a hole — a pillar, a courtyard, a sealed-off office — and the region is no longer simply connected. The dual graph picks up a cycle, the greedy colouring can come back around and find a contradiction, and a triangulation of a polygon with holes need not be 3-colourable at all. That is why the bound degrades once h holes are present. The easy repair cuts each hole open with an extra diagonal and splits its two endpoints in two, restoring simple-connectivity at a cost of 2h extra vertices — which is exactly O'Rourke's ⌊(n + 2h)/3⌋ of 1983. Pushing that down to the tight ⌊(n + h)/3⌋ needed a much more careful argument, and another decade.

The comb: why ⌊n/3⌋ cannot be improved

Sufficiency alone would be a weak theorem — maybe ⌊n/4⌋ is also enough. The comb, Chvátal's own example, closes that door.

Take k thin spikes joined by a narrow corridor. Counting carefully, the comb with k prongs has exactly 3k vertices: two outer corners, one apex per prong, and two corridor corners between consecutive prongs, with the two outermost corridor corners absorbed into the end walls. The animation uses k = 4, so n = 12 and ⌊n/3⌋ = 4.

The lower-bound argument is a disjointness statement, and it is what the travelling probe in the video is testing:

• Pick a point t_i just inside the tip of prong i.
• The set of points that can see t_i is a narrow wedge: it is pinched between the prong's own two walls and, once it leaves the prong, bounded by the rays through the two reflex corners at the prong's base. Make the prongs thin enough and the corridor shallow enough and that wedge, extended all the way across the corridor, stays inside a slab of its own.
• For the comb rendered in the video, a Monte-Carlo sweep of 115,099 interior sample points found zero points lying inside two wedges. The wedges are pairwise disjoint.
• So a single guard — anywhere in the gallery, corner or not — can see at most one tip. Covering k tips needs k guards.

Since the comb has n = 3k vertices, it needs n/3 = ⌊n/3⌋ guards, and the upper bound is attained. For n = 3k + 1 or 3k + 2, glue one or two extra vertices onto a wall of the comb: the spikes are untouched, k guards are still forced, and ⌊n/3⌋ is still k. So the bound is tight for every n ≥ 3, not just for multiples of three.

Note what is not being claimed. The comb shows there exists a bad polygon for each n. It says nothing about a polygon you hand me — the animation's 12-wall gallery is covered by three guards, and the same 12 walls arranged as a comb need four.

Klee, Chvátal, Fisk: how the proof got short

The problem was posed in 1973 by Victor Klee, who asked Václav Chvátal how many guards a gallery with n walls could possibly require. Chvátal answered within weeks and published “A combinatorial theorem in plane geometry,” Journal of Combinatorial Theory, Series B 18 (1975), 39–41. His proof is an induction on n: find a diagonal that splits the polygon into two pieces with controlled vertex counts, apply the hypothesis to each, and check the arithmetic case by case. It works, it is about two pages, and it is not memorable.

Steve Fisk, then at Bowdoin College, published the replacement in “A short proof of Chvátal's watchman theorem,” Journal of Combinatorial Theory, Series B 24 (1978), 374 — a single page, most of it white space. Triangulate, 3-colour, count. It is the version every textbook now carries, and it is the opening chapter of Martin Aigner and Günter Ziegler's Proofs from THE BOOK under the title “How to guard a museum.”

Fisk's proof also changed what the theorem is for. Chvátal's induction certifies a number; Fisk's argument is an algorithm. Run a triangulator, run a depth-first colouring of the dual tree, take the smallest class — and you have not just the bound but an explicit guard set, in the time it takes to triangulate. Joseph O'Rourke's Art Gallery Theorems and Algorithms (Oxford University Press, 1987) collected the field that grew out of it, and it is still the standard reference.

Variants: right angles, holes, mobile guards and fortresses

Change the gallery or change the guard, and the constant moves in ways that are often surprising.

• Orthogonal galleries need fewer watchmen. If every wall is horizontal or vertical — which describes most real buildings — the answer drops to ⌊n/4⌋. Jeff Kahn, Maria Klawe and Daniel Kleitman proved it in “Traditional galleries require fewer watchmen,” SIAM Journal on Algebraic and Discrete Methods 4 (1983), 194–206. The proof mirrors Fisk's one step up: every orthogonal simple polygon can be cut into convex quadrilaterals, the resulting graph is 4-colourable, and the rarest of four classes holds at most ⌊n/4⌋ vertices. An axis-parallel comb with n = 4k vertices shows it is tight.
• Holes cost you. For a polygon with h holes and n vertices in total, ⌊(n + h)/3⌋ guards always suffice — conjectured by Thomas Shermer and proved by Frank Hoffmann, Michael Kaufmann and Klaus Kriegel (1991) and by Inge Bjorling-Sachs and Diane Souvaine (1995). It improves O'Rourke's earlier ⌊(n + 2h)/3⌋ (1983) and is known to be tight for one and two holes.
• Let the guard walk. A mobile guard patrols a segment inside the polygon and sees everything visible from any point of it. O'Rourke showed in “Galleries need fewer mobile guards,” Geometriae Dedicata 14 (1983), 273–283, that ⌊n/4⌋ mobile guards always suffice for a simple polygon, and that this too is tight. Movement is worth exactly one factor of 4/3 here.
• Guard the outside instead. The fortress problem asks for guards covering the unbounded exterior. The answer is ⌈n/2⌉ — a ceiling, not a floor, and a different constant — with the convex polygon as the hard case, since a guard outside a convex wall sees only a bounded arc of it. O'Rourke and Derick Wood settled it in 1983.
• Edge guards. A guard patrolling a whole wall is the one classical variant still open. Toussaint conjectured ⌊n/4⌋ edge guards suffice for n ≥ 6; it remains unproved in general, with ⌊(3n + 4)/16⌋ known to be necessary for some polygons.

Computing guards: an easy bound, a very hard optimum

Fisk's proof is constructive, so the ⌊n/3⌋ guarantee is cheap. Triangulating a simple polygon takes O(n log n) by the classical sweep of Garey, Johnson, Preparata and Tarjan (1978), and O(n) by Bernard Chazelle's linear-time algorithm, “Triangulating a simple polygon in linear time,” Discrete & Computational Geometry 6 (1991), 485–524 — famously correct and famously unimplemented. Colouring the dual tree and picking the smallest class is then linear. This is the whole pipeline, and it is what produced the guard set in the animation:

def fisk_guards(poly):
    """poly: CCW list of (x, y). Returns <= floor(n/3) vertex indices
    covering the polygon, by Fisk's 1978 proof."""
    tris = ear_clip(poly)                 # n - 2 index triples

    # dual graph: two triangles are adjacent iff they share a diagonal
    share, adj = {}, {t: [] for t in range(len(tris))}
    for t, tri in enumerate(tris):
        for a, b in ((tri[0], tri[1]), (tri[1], tri[2]), (tri[2], tri[0])):
            share.setdefault((min(a, b), max(a, b)), []).append(t)
    for ts in share.values():
        if len(ts) == 2:                  # a diagonal, not a wall
            adj[ts[0]].append(ts[1]); adj[ts[1]].append(ts[0])

    colour = [None] * len(poly)
    for c, v in enumerate(tris[0]):       # seed one triangle
        colour[v] = c
    seen, stack = {0}, [0]
    while stack:                          # DFS over the dual TREE
        for u in adj[stack.pop()]:
            if u in seen:
                continue
            seen.add(u); stack.append(u)
            free = [v for v in tris[u] if colour[v] is None]
            if free:                      # exactly one uncoloured corner
                used = {colour[v] for v in tris[u] if colour[v] is not None}
                colour[free[0]] = ({0, 1, 2} - used).pop()

    sizes = [colour.count(c) for c in range(3)]
    rarest = sizes.index(min(sizes))      # min(sizes) <= len(poly) // 3
    return [i for i, c in enumerate(colour) if c == rarest]

The optimum is another matter entirely. Asking for the fewest guards is the art gallery problem, and it is hard at every level:

• NP-hard. D. T. Lee and A. K. Lin, “Computational complexity of art gallery problems,” IEEE Transactions on Information Theory 32 (1986), 276–282, proved minimising vertex guards NP-hard, and the same for point guards.
• Hard to approximate. Stephan Eidenbenz, Christoph Stamm and Peter Widmayer, “Inapproximability results for guarding polygons and terrains,” Algorithmica 31 (2001), 79–113, showed the problem is APX-hard for simple polygons — no polynomial-time algorithm gets within some fixed constant factor unless P = NP — and Ω(log n)-inapproximable once holes are allowed.
• Not even a rational answer. Mikkel Abrahamsen, Anna Adamaszek and Tillmann Miltzow exhibited a polygon with integer vertex coordinates whose optimal point-guard set requires irrational coordinates (“Irrational guards are sometimes needed,” SoCG 2017), then proved the point-guard problem ∃ℝ-complete (“The Art Gallery Problem is ∃ℝ-complete,” STOC 2018; Journal of the ACM 69 (2022)). ∃ℝ sits between NP and PSPACE, so the problem is not even known to be in NP: you cannot in general write down an optimal solution in a polynomial number of bits.

That gap is the practical shape of the theorem. A guaranteed answer is linear-time and often three or four times larger than necessary; the exact answer is, in the strongest formal sense available, out of reach.

One theorem, five galleries: how many guards are always enough?

Gallery or guard model	Guards that always suffice	Tight example	Result and date
Convex polygon, n vertices	1	Every convex polygon	Immediate — in a convex region every point sees every other
Simple polygon, n vertices	⌊n/3⌋	The comb with k = n/3 prongs	Chvátal 1975; Fisk's colouring proof 1978
Orthogonal (right-angled) simple polygon, n vertices	⌊n/4⌋	An axis-parallel comb with n = 4k vertices	Kahn, Klawe & Kleitman 1983, via convex quadrilateralization
Polygon with h holes, n vertices in total	⌊(n + h)/3⌋	Tight for h = 1 and h = 2	Hoffmann, Kaufmann & Kriegel 1991; Bjorling-Sachs & Souvaine 1995
Guarding the outside (the fortress problem)	⌈n/2⌉	Every convex polygon	O'Rourke & Wood 1983 — note the ceiling, and the different constant