The Art Gallery Problem

Picture a museum whose floor plan is a single, oddly-shaped polygon — full of alcoves and jutting corners, the kind an architect draws to make a building interesting. You must place security guards who never move, and every point on the walls has to be visible to at least one guard. Fewer guards means fewer salaries. How many do you need?

If the room were a plain rectangle, one guard in a corner would see everything. But real floor plans zigzag: a guard tucked into one alcove is blind to whatever is around the next corner. Add enough zigzags and it starts to feel like you might need a guard for practically every nook.

Remarkably, that fear is unfounded. No matter how bizarre the polygon, no matter how many corners it has, a surprisingly small number of guards is always enough — and there's a proof so visual you can literally color it in.

Below is a jagged gallery, already cut into triangles (a triangulation). Click 3-color the corners to see every corner painted with one of three colors so that no triangle repeats a color — always possible for a triangulated polygon. Then click Guard with the smallest color to place a guard on every corner of the least-used color and watch their visibility fans light up the whole room.

<p class="hint">{{hint_para}}</p>
<svg id="gallery" class="gallery" viewBox="0 0 188 190" xmlns="http://www.w3.org/2000/svg"></svg>
<div class="status" id="status">{{status_start}}</div>
<div class="btns">
  <button id="triangulate" type="button">{{btn_triangulate}}</button>
  <button id="color" type="button">{{btn_color}}</button>
  <button id="guard" type="button">{{btn_guard}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.gallery { width: 100%; max-width: 420px; height: auto; background: #f4f6f8; border: 1px solid #cdd9e3;
           border-radius: 10px; display: block; }
.wall { fill: none; stroke: #1d3557; stroke-width: 2.4; stroke-linejoin: round; }
.diagonal { stroke: #9fb2c8; stroke-width: 1; stroke-dasharray: 3 2; fill: none; opacity: 0; transition: opacity .3s; }
.diagonal.on { opacity: 1; }
.tri-fill { opacity: 0; transition: opacity .3s; }
.tri-fill.on { opacity: .16; }
.corner { r: 4.2; stroke: #1d3557; stroke-width: 1.2; fill: #fff; transition: fill .3s, r .2s; }
.corner.c0 { fill: #e63946; }
.corner.c1 { fill: #2a9d8f; }
.corner.c2 { fill: #f4a300; }
.corner.guard { r: 6.5; stroke: #111; stroke-width: 1.6; }
.fan { fill: #ffd166; opacity: 0; transition: opacity .4s; }
.fan.on { opacity: .35; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }

// Code not found

Watch the guard count. With $n$ corners split three ways, some color is used at most $\lfloor n/3 \rfloor$ times — and that's exactly the guarantee Chvátal's theorem makes: $\lfloor n/3 \rfloor$ guards always suffice, for any simple polygon whatsoever.

The result is precisely stated as: any simple polygon with $n$ vertices can always be guarded by $\lfloor n/3 \rfloor$ guards, and some polygons need exactly that many.

• Upper bound (sufficiency). Václav Chvátal proved it in 1975 with a case-heavy argument; two years later Steve Fisk found the gem of a proof used here. Triangulate the polygon (always possible, into $n-2$ triangles). The "dual graph" of shared edges between triangles is a tree, which makes the corners 3-colorable: no two corners joined by a triangulation edge ever share a color. Every triangle then has all three colors on its corners, so any single color class already sees every triangle — including the color used least, which appears at most $\lfloor n/3 \rfloor$ times.
• Lower bound (tightness). A "comb" polygon with prongs forces one guard per prong, and a comb with $n$ vertices needs exactly $\lfloor n/3 \rfloor$ of them — so the bound cannot be improved in general.
• Finding the true minimum is NP-hard. The coloring argument gives a fast guard placement that's never more than the worst case, but computing the smallest possible number of guards for a specific polygon is NP-hard, and even approximating it well is hard. That mirrors the split we keep meeting in P vs NP: a good-enough answer can be cheap even when the optimal one is out of reach.

So the elegance here is a bit like the guarantee behind the four color theorem: a clean coloring statement caps the worst case beautifully, even though pinning down the exact best answer for one specific instance stays hard.

"Cover every point of a region with as few watchers as possible" is a template that shows up well beyond actual art galleries:

• Sensor and camera placement: security systems, cell towers, and Wi-Fi access points all face the same coverage-with-fewest-units question.
• Robotics: a robot mapping or patrolling a room needs to know which vantage points let its sensors see the whole space.
• Computer graphics: visibility and occlusion computations — deciding what a virtual camera can "see" through a scene — build on the same triangulation and visibility-graph machinery.
• Path and motion planning: guaranteeing an agent can always observe a target links directly to guard-set arguments.

Learn the triangulate-and-color trick here and you've picked up a tool that reappears anywhere "coverage" meets "geometry," including neighbors like triangulation and the four color theorem.

The Art Gallery Problem turns a vague architectural worry into a clean guarantee: cut the room into triangles, three-color the corners, post a guard on the smallest color — and you have never used more than $\lfloor n/3 \rfloor$ guards, no matter how twisted the walls.

The catch is the usual one in this field: a beautiful, cheap bound on the worst case doesn't hand you the exact minimum for your particular gallery — that part is NP-hard, just like so many close cousins living near P vs NP. Sometimes the honest, useful answer is "good enough and provably close," not "optimal."