Fisk's proof
Triangulate. 3-color triangulation vertices (any triangulated planar graph is 3-colorable). Choose smallest color class → guards.
Advertisement
Constructive
Triangulation → 3-coloring → color class of size ≤ ⌊N/3⌋. Every triangle covered by its 3-colored vertex → whole polygon covered.
Advertisement
Comb polygon
N = 3k prongs. Requires exactly k guards. Shows bound tight.
Complexity
O(N log N) via triangulation. Chazelle O(N) triangulation → O(N) art gallery.