Art Gallery Guards: Why n/3 Suffice
About this app
A museum floor plan falls apart into triangles, the corners get three colours, and guards on the rarest colour see everything. This makes Fisk’s proof visible that ⌊n/3⌋ guards always suffice. In free mode you drag corners, place guards yourself and see exactly what nobody sees yet.
With explain mode: an AI tutor walks you through the app, points out what matters in the scene and answers your questions.
Chvátal’s theorem and Fisk’s proof
A museum has a floor plan with n corners whose walls never cross. Guards stand still and see along straight lines; only walls block the view. Václav Chvátal proved in 1975 that ⌊n/3⌋ guards always suffice. Steve Fisk found a proof of a few lines in 1978. Split the floor plan into triangles by diagonals and colour the corners with three colours so that every triangle carries all three. The rarest colour occurs at most ⌊n/3⌋ times. Put a guard on each of its corners, and every triangle has one guard who sees all of it.
What the app shows
A museum with walls, a floor and paintings comes apart step by step: diagonals cut off triangles ear by ear, then the corners get their colours backwards, also shown as circle, square and triangle. A counting card stacks the corners per colour and shows the line at n/3. Guards appear on the rarest colour, their light floods the room triangle by triangle, and hatching shows what nobody sees yet. The comb proves that the bound is sharp: each prong tip can only be seen from inside its own prong.
Try it yourself
In free mode you drag corners, add new ones on a wall or delete them; the app never allows crossing walls and recolours live. You place and move guards yourself, their visibility region is computed exactly, and a readout gives the seen share in percent. Presets are gallery, comb, star, L-hall with an alcove, spiral and random. In the star and the L-hall a single guard is enough, in the comb every prong needs its own.
Frequently asked questions
- What is the art gallery problem?
- The art gallery problem asks how many stationary guards a room with n corners needs so that every point is seen by at least one guard. Victor Klee posed it in 1973, and Václav Chvátal answered it in 1975: ⌊n/3⌋ guards always suffice, and some floor plans need that many.
- How does Fisk’s proof work?
- The floor plan is split by diagonals into n − 2 triangles. The corners can be coloured with three colours so that every triangle has all three colours. One of the three colours occurs at most ⌊n/3⌋ times. Guards on those corners see every triangle completely, because every triangle has a corner of that colour.
- Do you always need n/3 guards?
- No. ⌊n/3⌋ is the worst case. A convex room or a star needs a single guard, and alcoves do not each need their own. The bound is reached for example by the comb: each prong tip is visible only from inside its own prong, so k prongs need k guards.
- What can I try in the app?
- Watch Fisk’s proof in eight steps, load floor plans such as gallery, comb, star or spiral, drag, add and delete corners, place guards yourself and read off from the percentage and the hatching whether everything is guarded.
Subject: From Erdős's BOOK
More from From Erdős's BOOK
A VisuApp by heyprof: interactive, free in your browser, no sign-up. What is a VisuApp? · All apps