Art Gallery Theorem, in depth: Chvatal's floor(n/3) bound, Fisk's 3-colouring proof as code, variants and minimum guard placement

The problem, stated precisely

The room is a simple polygon P: n straight edges that do not cross, no holes, boundary included. A guard g sees x when the closed segment gx lies inside P, possibly along the boundary. Guards cover P when every point is seen by one of them.

Point guards may stand anywhere in P; vertex guards only on vertices, so they never need fewer. For simple polygons both worst cases are floor(n/3); with holes they separate.

Guards in this model see in all directions at unlimited distance. Real cameras do not, which a later section addresses. The model isolates the geometric difficulty: reflex corners, with interior angle above 180 degrees, are the only thing that stops one guard seeing a whole room. A convex polygon needs one guard, and r reflex vertices never need more than max(1, r) guards.

Why floor(n/3) can be necessary: the comb

Some polygons really need floor(n/3) guards. The witness is Chvatal's comb: k tall, narrow triangular prongs on a thin strip, with gaps between them. A point that sees apex i must lie in a narrow cone from the apex through the base of prong i. With tall prongs and wide gaps those cones are disjoint, so no guard sees two apexes and k guards are needed.

The comb in this article's test code has two strip corners plus three vertices per prong, so n = 3k + 2 and floor(n/3) = k: the bound is attained and cannot be improved for all simple polygons. It says nothing about a particular room, most of which need far fewer guards.

Why floor(n/3) always suffices: Fisk's proof

Now sufficiency: every simple polygon can be covered by floor(n/3) vertex guards. Fisk's proof uses three facts.

1. Every simple polygon can be triangulated by non-crossing diagonals into n - 2 triangles. By the two-ears theorem every polygon with more than three vertices has an ear, a convex corner whose neighbours a diagonal can join; clip it and recurse.
2. The triangulation graph is 3-colourable. Build the dual graph: one node per triangle, an edge when two triangles share a diagonal. Because every diagonal splits the polygon in two, the dual graph is a tree. Colour the first triangle's corners 0, 1 and 2. Walk the tree; each new triangle shares an edge, and so two already-coloured vertices, with a triangle already visited, and its third vertex takes the remaining colour. The tree structure rules out conflicts.
3. Each colour class guards everything. Every triangle has one vertex of each colour, a triangle is convex, and a guard at any corner of a convex region sees all of it. So placing guards on every vertex of one colour covers every triangle, which is all of P.

The three classes partition n vertices, so by pigeonhole the smallest has at most floor(n/3) vertices. The proof gives a constructive placement, computed in the time it takes to triangulate, but no claim that the smallest colour class is near optimal for your room.

From proof to code

The proof translates directly into code. The version below favours clarity: ear clipping that rescans for an ear after each clip, and a breadth-first walk of the dual tree for colouring. It was run on an L-shaped room and on combs with 1 to 6 prongs; on every comb it returned exactly k guards, matching the lower bound.

from collections import deque

def cross(o, a, b):
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def signed_area2(poly):
    n = len(poly)
    return sum(poly[i][0] * poly[(i + 1) % n][1] - poly[(i + 1) % n][0] * poly[i][1]
               for i in range(n))

def in_triangle(p, a, b, c):            # closed test, a-b-c counter-clockwise
    return cross(a, b, p) >= 0 and cross(b, c, p) >= 0 and cross(c, a, p) >= 0

def triangulate(poly):
    """Ear clipping, O(n^3) worst case as written. Returns vertex-index triples."""
    idx = list(range(len(poly)))
    if signed_area2(poly) < 0:
        idx.reverse()                     # work counter-clockwise
    tris = []
    while len(idx) > 3:
        m = len(idx)
        for k in range(m):
            i, j, l = idx[k - 1], idx[k], idx[(k + 1) % m]
            a, b, c = poly[i], poly[j], poly[l]
            if cross(a, b, c) <= 0:
                continue                  # reflex or flat corner: not an ear
            if any(in_triangle(poly[q], a, b, c) for q in idx if q not in (i, j, l)):
                continue                  # a vertex blocks the diagonal a-c
            tris.append((i, j, l))
            idx.pop(k)
            break
        else:
            raise ValueError("no ear found: polygon is not simple")
    tris.append(tuple(idx))
    return tris

def three_color(n, tris):
    """Colour 0/1/2 so every triangle uses all three, by walking the dual tree."""
    by_edge = {}
    for t, (a, b, c) in enumerate(tris):
        for u, v in ((a, b), (b, c), (c, a)):
            by_edge.setdefault(frozenset((u, v)), []).append(t)
    color = [-1] * n
    a, b, c = tris[0]
    color[a], color[b], color[c] = 0, 1, 2
    seen, queue = {0}, deque([0])
    while queue:
        t = queue.popleft()
        a, b, c = tris[t]
        for u, v in ((a, b), (b, c), (c, a)):
            for s in by_edge[frozenset((u, v))]:
                if s not in seen:
                    seen.add(s)
                    w = next(x for x in tris[s] if x not in (u, v))
                    color[w] = 3 - color[u] - color[v]   # the colour that is left
                    queue.append(s)
    return color

def place_guards(poly):
    color = three_color(len(poly), triangulate(poly))
    classes = [[i for i, col in enumerate(color) if col == k] for k in range(3)]
    return min(classes, key=len)

The colouring walk is O(n). This ear clipping is O(n^3) worst case because it rescans every corner; keeping a list of ears and testing only reflex vertices gives O(n^2), which most libraries ship. Chazelle proved O(n) triangulation in 1991, but that algorithm is impractical; for rooms with hundreds of vertices O(n^2) is instant.

Robustness is where real implementations fail. The <= 0 and >= 0 comparisons treat collinear points as blocking, but near-collinear floats can flip a sign. Use integer coordinates where you can, remove duplicate and collinear vertices, and check that there are n - 2 triangles whose areas sum to the polygon area. Predicates are covered in 2D Geometry Algorithms, in depth, and ear clipping with its variants in Polygon Algorithms, in depth.

Worked example: an L-shaped room

Take the L-shaped room with vertices v0 (0,0), v1 (4,0), v2 (4,1), v3 (1,1), v4 (1,4) and v5 (0,4). It has six vertices and one reflex corner, v3. Ear clipping finds the ear at v1 first and clips triangle (v0, v1, v2), then (v0, v2, v3), then (v5, v0, v3), leaving (v3, v4, v5): four triangles, which is n - 2. The colouring gives v0 and v4 colour 0, v1 and v3 colour 1, v2 and v5 colour 2.

All three classes have two vertices, which equals floor(6/3), so the algorithm places two guards, at v0 and v4. The placement is correct. It is not optimal. The unit square where the two arms overlap is the polygon's kernel: every segment from a point in it to any point of the room stays inside. v0 and the reflex corner v3 both lie in that square, so either one alone guards the whole room, and the guard at v4 is pure waste. Fisk's construction spent twice the optimum here.

That is the practical lesson: floor(n/3) is a worst-case guarantee, and colour classes are a starting point to prune, not an answer to ship. A redundancy pass that drops any guard already covered by the others would remove v4 here.

Variants and their bounds

Real buildings rarely match the textbook model, and several variants have their own tight bounds. State which guard type you mean whenever you quote one.

The orthogonal case matters most because floor plans are mostly rectilinear; its proof colours a convex quadrilateralisation with four colours. Holes model pillars and display cases. The colouring in these proofs is easy only because triangulation graphs are always 3-colourable; for general graphs that is not true, as Graph Coloring, in depth explains, which is part of why the geometric case is so pleasant.

Minimising guards is a different problem

Bounding the worst case is easy; finding the minimum number of guards for a given polygon is not. Lee and Lin showed in 1986 that the minimum vertex-guard problem is NP-hard, and Abrahamsen, Adamaszek and Miltzow showed in 2018 that the point-guard version is complete for the existential theory of the reals, a class believed to be harder than NP. Optimal point guards can require irrational coordinates even for polygons with integer vertices. Do not expect an exact, fast general algorithm.

What works in practice is discretisation plus set cover. Choose candidate guard positions (all vertices, plus points on a grid or at the intersections of extended edges), choose witness points that must be seen (a fine sample of the interior and boundary), compute which candidates see which witnesses, and solve set cover. Greedy set cover gives a logarithmic approximation and is often within one or two guards of optimal on floor plans; an integer program solved with an off-the-shelf solver gives the optimum for the chosen candidates and witnesses.

def greedy_cover(cands, witnesses, sees):
    uncovered = set(range(len(witnesses)))
    vis = {g: {w for w in uncovered if sees(cands[g], witnesses[w])} for g in range(len(cands))}
    chosen = []
    while uncovered:
        g = max(vis, key=lambda g: len(vis[g] & uncovered))
        if not vis[g] & uncovered:
            raise ValueError("a witness is visible from no candidate")
        chosen.append(cands[g])
        uncovered -= vis[g]
    return chosen

The visibility test is the fragile part: segments through a reflex vertex or along an edge are where implementations disagree. Computing each candidate's visibility polygon and testing witnesses with point-in-polygon is sound. Include Fisk's colour classes as candidates and keep the smaller of the cover and the best class, so you never exceed floor(n/3), and verify the result by comparing the union of visibility polygons with the room's area, because a finite witness set can miss a sliver.

From theorem to real sensor placement

Camera placement, lighting, robot inspection routes and game visibility all start from the theorem and then absorb physical constraints.

• Limited range. Clip each visibility polygon to the useful range before the set cover; the floor(n/3) guarantee then no longer holds.
• Field of view. A 90-degree lens sees a wedge, not a polygon. Model each candidate as several oriented sensors and pick among the orientations in the cover.
• Three dimensions. Shelving blocks lines of sight a floor plan omits; guard per height band.
• Redundancy. To survive one failed camera, require each witness to be covered twice.

Failure modes

The common ways an implementation goes wrong, and how to catch each:

• Clockwise input. Without the signed-area reversal every convex corner looks reflex.
• Duplicate or collinear vertices. Zero-area ears break the colouring walk's assumptions. Clean the input first.
• Non-simple input. A self-touching outline from a CAD export has no valid triangulation. Validate simplicity before triangulating.
• Trusting witness coverage. Verify by area union, not by sample counts.

Trade-offs

What to do next

1. Implement triangulate and three_color from this article and test them on an L-shape and a comb; assert n - 2 triangles, area conservation, and that every triangle has three colours.
2. Add a visibility-polygon routine and a redundancy pass that drops guards whose regions are covered by the others.
3. Build a candidates-and-witnesses set cover, seed it with the three colour classes, and verify the result by area union.
4. Add range clipping and field-of-view wedges, then compare the guard count with the floor(n/3) bound to see how much the physics costs.
5. For rectilinear plans, check your result against floor(n/4) as a sanity bound.
6. Read about convex hulls in Andrew's Monotone Chain, in depth to practise the orientation predicate that every step above relies on.