The Real Complexity of the Art Gallery Problem

Introduction

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.

Place the Guards

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">This gallery has 10 corners. First split it into triangles, then color every corner with one of three colors so no triangle repeats a color, and finally post a guard on every corner of the color used least — watch their triangle fans cover the whole room.</p>
<svg id="gallery" class="gallery" viewBox="0 0 188 190" xmlns="http://www.w3.org/2000/svg"></svg>
<div class="status" id="status">Click "Triangulate the room" to begin.</div>
<div class="btns">
  <button id="triangulate" type="button">Triangulate the room</button>
  <button id="color" type="button">3-color the corners</button>
  <button id="guard" type="button">Guard with the smallest color</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

// A fixed 10-corner "comb" gallery with three prongs, hardcoded as (x,y) pairs.
const P = [
  [20, 170], [20, 20], [56, 20], [66, 95], [76, 20],
  [112, 20], [122, 95], [132, 20], [168, 20], [168, 170],
];
const N = P.length;
const SVG_NS = 'http://www.w3.org/2000/svg';

// Basic 2D cross product, polygon winding, and point-in-triangle tests.
function cross(o, a, b) { return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]); }
let signedArea2 = 0;
for (let i = 0; i < N; i++) { const [x1, y1] = P[i], [x2, y2] = P[(i + 1) % N]; signedArea2 += x1 * y2 - x2 * y1; }
const CCW = signedArea2 > 0;
function isConvexVertex(prev, cur, next) {
  const c = cross(P[prev], P[cur], P[next]);
  return CCW ? c > 0 : c < 0;
}
function pointInTri(pt, a, b, c) {
  const d1 = cross(a, b, pt), d2 = cross(b, c, pt), d3 = cross(c, a, pt);
  const hasNeg = d1 < 0 || d2 < 0 || d3 < 0;
  const hasPos = d1 > 0 || d2 > 0 || d3 > 0;
  return !(hasNeg && hasPos);
}

// Ear-clipping triangulation, computed live from the polygon's own vertices.
function triangulate() {
  let idx = P.map((_, i) => i);
  const tris = [];
  let guardLoops = 0;
  while (idx.length > 3 && guardLoops < 1000) {
    guardLoops++;
    let earFound = false;
    for (let i = 0; i < idx.length; i++) {
      const iPrev = idx[(i - 1 + idx.length) % idx.length];
      const iCur = idx[i];
      const iNext = idx[(i + 1) % idx.length];
      if (!isConvexVertex(iPrev, iCur, iNext)) continue;
      let hasInside = false;
      for (const k of idx) {
        if (k === iPrev || k === iCur || k === iNext) continue;
        if (pointInTri(P[k], P[iPrev], P[iCur], P[iNext])) { hasInside = true; break; }
      }
      if (hasInside) continue;
      tris.push([iPrev, iCur, iNext]);
      idx.splice(i, 1);
      earFound = true;
      break;
    }
    if (!earFound) break;
  }
  if (idx.length === 3) tris.push([idx[0], idx[1], idx[2]]);
  return tris;
}
const TRIANGLES = triangulate();

// The triangulation's dual graph (triangles sharing an edge) — always a tree.
function sharedVerts(t1, t2) { return t1.filter(v => t2.includes(v)); }
const dual = Array.from({ length: TRIANGLES.length }, () => []);
for (let i = 0; i < TRIANGLES.length; i++) {
  for (let j = i + 1; j < TRIANGLES.length; j++) {
    if (sharedVerts(TRIANGLES[i], TRIANGLES[j]).length === 2) { dual[i].push(j); dual[j].push(i); }
  }
}

// Depth-first walk over the dual tree, coloring each new corner with a color unused by its triangle so far.
function threeColor() {
  const color = new Array(N).fill(-1);
  function colorTriangle(t) {
    const avail = [0, 1, 2].filter(c => !t.map(v => color[v]).includes(c));
    let ai = 0;
    t.forEach(v => { if (color[v] === -1) color[v] = avail[ai++]; });
  }
  const visited = new Array(TRIANGLES.length).fill(false);
  (function dfs(ti) {
    visited[ti] = true;
    colorTriangle(TRIANGLES[ti]);
    dual[ti].forEach(tj => { if (!visited[tj]) dfs(tj); });
  })(0);
  return color;
}

let colors = null;
let guardColorIdx = null;
let state = 'start'; // start | triangulated | colored | guarded

const svg = document.getElementById('gallery');
function el(tag, attrs) {
  const e = document.createElementNS(SVG_NS, tag);
  for (const k in attrs) e.setAttribute(k, attrs[k]);
  return e;
}

function render() {
  svg.innerHTML = '';
  // If guards are placed, fill every triangle that has a guard corner.
  if (state === 'guarded') {
    TRIANGLES.forEach(t => {
      if (t.some(v => colors[v] === guardColorIdx)) {
        const pts = t.map(v => P[v].join(',')).join(' ');
        svg.appendChild(el('polygon', { points: pts, class: 'fan on' }));
      }
    });
  }
  // Draw the triangulation diagonals (non-boundary triangle edges).
  const boundary = new Set();
  for (let i = 0; i < N; i++) boundary.add(i + ',' + ((i + 1) % N));
  TRIANGLES.forEach(t => {
    for (let a = 0; a < 3; a++) {
      const u = t[a], v = t[(a + 1) % 3];
      const key1 = u + ',' + v, key2 = v + ',' + u;
      if (!boundary.has(key1) && !boundary.has(key2)) {
        svg.appendChild(el('line', {
          x1: P[u][0], y1: P[u][1], x2: P[v][0], y2: P[v][1],
          class: 'diagonal' + (state !== 'start' ? ' on' : ''),
        }));
      }
    }
  });
  // Draw the polygon's outer walls on top.
  svg.appendChild(el('polygon', { points: P.map(p => p.join(',')).join(' '), class: 'wall' }));
  // Draw every corner, colored once 3-coloring has run.
  P.forEach((p, i) => {
    const cls = ['corner'];
    if (colors) cls.push('c' + colors[i]);
    if (state === 'guarded' && colors[i] === guardColorIdx) cls.push('guard');
    svg.appendChild(el('circle', { cx: p[0], cy: p[1], class: cls.join(' ') }));
  });
}

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t;
  s.className = 'status ' + (cls || '');
}

function doTriangulate() {
  state = 'triangulated';
  render();
  setStatus(i18nFmt('Split into %tris% triangles (dashed lines are the diagonals).', { tris: TRIANGLES.length }), '');
  document.getElementById('triangulate').disabled = true;
}
function doColor() {
  colors = threeColor();
  state = 'colored';
  render();
  setStatus('Every corner now has one of three colors — no triangle repeats a color.', '');
  document.getElementById('color').disabled = true;
}
function doGuard() {
  // Pick whichever color class has the fewest corners — that is the guard set.
  const counts = [0, 0, 0];
  colors.forEach(c => counts[c]++);
  guardColorIdx = counts.indexOf(Math.min(...counts));
  const guardCount = counts[guardColorIdx];
  state = 'guarded';
  render();
  setStatus(i18nFmt('Guards placed: %guards% (the least-used color) for %n% corners — never more than floor(%n%/3) = %bound%.', { guards: guardCount, n: N, bound: Math.floor(N / 3) }), 'ok');
  console.log('Guards used vs. floor(n/3) bound:', guardCount, '<=', Math.floor(N / 3));
  document.getElementById('guard').disabled = true;
}
function doReset() {
  colors = null; guardColorIdx = null; state = 'start';
  render();
  setStatus('Click "Triangulate the room" to begin.', '');
  document.getElementById('triangulate').disabled = false;
  document.getElementById('color').disabled = false;
  document.getElementById('guard').disabled = false;
}

document.getElementById('triangulate').addEventListener('click', doTriangulate);
document.getElementById('color').addEventListener('click', doColor);
document.getElementById('guard').addEventListener('click', doGuard);
document.getElementById('reset').addEventListener('click', doReset);
render();

<p class="hint">This gallery has 10 corners. First split it into triangles, then color every corner with one of three colors so no triangle repeats a color, and finally post a guard on every corner of the color used least — watch their triangle fans cover the whole room.</p>
<svg id="gallery" class="gallery" viewBox="0 0 188 190" xmlns="http://www.w3.org/2000/svg"></svg>
<div class="status" id="status">Click "Triangulate the room" to begin.</div>
<div class="btns">
  <button id="triangulate" type="button">Triangulate the room</button>
  <button id="color" type="button">3-color the corners</button>
  <button id="guard" type="button">Guard with the smallest color</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

// A fixed 10-corner "comb" gallery with three prongs, hardcoded as (x,y) pairs.
const P = [
  [20, 170], [20, 20], [56, 20], [66, 95], [76, 20],
  [112, 20], [122, 95], [132, 20], [168, 20], [168, 170],
];
const N = P.length;
const SVG_NS = 'http://www.w3.org/2000/svg';

// Basic 2D cross product, polygon winding, and point-in-triangle tests.
function cross(o, a, b) { return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]); }
let signedArea2 = 0;
for (let i = 0; i < N; i++) { const [x1, y1] = P[i], [x2, y2] = P[(i + 1) % N]; signedArea2 += x1 * y2 - x2 * y1; }
const CCW = signedArea2 > 0;
function isConvexVertex(prev, cur, next) {
  const c = cross(P[prev], P[cur], P[next]);
  return CCW ? c > 0 : c < 0;
}
function pointInTri(pt, a, b, c) {
  const d1 = cross(a, b, pt), d2 = cross(b, c, pt), d3 = cross(c, a, pt);
  const hasNeg = d1 < 0 || d2 < 0 || d3 < 0;
  const hasPos = d1 > 0 || d2 > 0 || d3 > 0;
  return !(hasNeg && hasPos);
}

// Ear-clipping triangulation, computed live from the polygon's own vertices.
function triangulate() {
  let idx = P.map((_, i) => i);
  const tris = [];
  let guardLoops = 0;
  while (idx.length > 3 && guardLoops < 1000) {
    guardLoops++;
    let earFound = false;
    for (let i = 0; i < idx.length; i++) {
      const iPrev = idx[(i - 1 + idx.length) % idx.length];
      const iCur = idx[i];
      const iNext = idx[(i + 1) % idx.length];
      if (!isConvexVertex(iPrev, iCur, iNext)) continue;
      let hasInside = false;
      for (const k of idx) {
        if (k === iPrev || k === iCur || k === iNext) continue;
        if (pointInTri(P[k], P[iPrev], P[iCur], P[iNext])) { hasInside = true; break; }
      }
      if (hasInside) continue;
      tris.push([iPrev, iCur, iNext]);
      idx.splice(i, 1);
      earFound = true;
      break;
    }
    if (!earFound) break;
  }
  if (idx.length === 3) tris.push([idx[0], idx[1], idx[2]]);
  return tris;
}
const TRIANGLES = triangulate();

// The triangulation's dual graph (triangles sharing an edge) — always a tree.
function sharedVerts(t1, t2) { return t1.filter(v => t2.includes(v)); }
const dual = Array.from({ length: TRIANGLES.length }, () => []);
for (let i = 0; i < TRIANGLES.length; i++) {
  for (let j = i + 1; j < TRIANGLES.length; j++) {
    if (sharedVerts(TRIANGLES[i], TRIANGLES[j]).length === 2) { dual[i].push(j); dual[j].push(i); }
  }
}

// Depth-first walk over the dual tree, coloring each new corner with a color unused by its triangle so far.
function threeColor() {
  const color = new Array(N).fill(-1);
  function colorTriangle(t) {
    const avail = [0, 1, 2].filter(c => !t.map(v => color[v]).includes(c));
    let ai = 0;
    t.forEach(v => { if (color[v] === -1) color[v] = avail[ai++]; });
  }
  const visited = new Array(TRIANGLES.length).fill(false);
  (function dfs(ti) {
    visited[ti] = true;
    colorTriangle(TRIANGLES[ti]);
    dual[ti].forEach(tj => { if (!visited[tj]) dfs(tj); });
  })(0);
  return color;
}

let colors = null;
let guardColorIdx = null;
let state = 'start'; // start | triangulated | colored | guarded

const svg = document.getElementById('gallery');
function el(tag, attrs) {
  const e = document.createElementNS(SVG_NS, tag);
  for (const k in attrs) e.setAttribute(k, attrs[k]);
  return e;
}

function render() {
  svg.innerHTML = '';
  // If guards are placed, fill every triangle that has a guard corner.
  if (state === 'guarded') {
    TRIANGLES.forEach(t => {
      if (t.some(v => colors[v] === guardColorIdx)) {
        const pts = t.map(v => P[v].join(',')).join(' ');
        svg.appendChild(el('polygon', { points: pts, class: 'fan on' }));
      }
    });
  }
  // Draw the triangulation diagonals (non-boundary triangle edges).
  const boundary = new Set();
  for (let i = 0; i < N; i++) boundary.add(i + ',' + ((i + 1) % N));
  TRIANGLES.forEach(t => {
    for (let a = 0; a < 3; a++) {
      const u = t[a], v = t[(a + 1) % 3];
      const key1 = u + ',' + v, key2 = v + ',' + u;
      if (!boundary.has(key1) && !boundary.has(key2)) {
        svg.appendChild(el('line', {
          x1: P[u][0], y1: P[u][1], x2: P[v][0], y2: P[v][1],
          class: 'diagonal' + (state !== 'start' ? ' on' : ''),
        }));
      }
    }
  });
  // Draw the polygon's outer walls on top.
  svg.appendChild(el('polygon', { points: P.map(p => p.join(',')).join(' '), class: 'wall' }));
  // Draw every corner, colored once 3-coloring has run.
  P.forEach((p, i) => {
    const cls = ['corner'];
    if (colors) cls.push('c' + colors[i]);
    if (state === 'guarded' && colors[i] === guardColorIdx) cls.push('guard');
    svg.appendChild(el('circle', { cx: p[0], cy: p[1], class: cls.join(' ') }));
  });
}

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t;
  s.className = 'status ' + (cls || '');
}

function doTriangulate() {
  state = 'triangulated';
  render();
  setStatus(i18nFmt('Split into %tris% triangles (dashed lines are the diagonals).', { tris: TRIANGLES.length }), '');
  document.getElementById('triangulate').disabled = true;
}
function doColor() {
  colors = threeColor();
  state = 'colored';
  render();
  setStatus('Every corner now has one of three colors — no triangle repeats a color.', '');
  document.getElementById('color').disabled = true;
}
function doGuard() {
  // Pick whichever color class has the fewest corners — that is the guard set.
  const counts = [0, 0, 0];
  colors.forEach(c => counts[c]++);
  guardColorIdx = counts.indexOf(Math.min(...counts));
  const guardCount = counts[guardColorIdx];
  state = 'guarded';
  render();
  setStatus(i18nFmt('Guards placed: %guards% (the least-used color) for %n% corners — never more than floor(%n%/3) = %bound%.', { guards: guardCount, n: N, bound: Math.floor(N / 3) }), 'ok');
  console.log('Guards used vs. floor(n/3) bound:', guardCount, '<=', Math.floor(N / 3));
  document.getElementById('guard').disabled = true;
}
function doReset() {
  colors = null; guardColorIdx = null; state = 'start';
  render();
  setStatus('Click "Triangulate the room" to begin.', '');
  document.getElementById('triangulate').disabled = false;
  document.getElementById('color').disabled = false;
  document.getElementById('guard').disabled = false;
}

document.getElementById('triangulate').addEventListener('click', doTriangulate);
document.getElementById('color').addEventListener('click', doColor);
document.getElementById('guard').addEventListener('click', doGuard);
document.getElementById('reset').addEventListener('click', doReset);
render();

Result

Console

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 Real Complexity

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.

Where It Matters

"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.

Conclusion

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."

Comments

Loading comments...

https://www.kipuhub.com/en/article/art-gallery-problem/Content licensed under CC BY-NC 4.0.

Cookies & privacy

The Art Gallery Problem

Watching every wall with as few eyes as possible