# Art Gallery Problem for the Castro's $24$-sided room

Art Gallery Theorem. If the walls of an art gallery are made up of $n$ straight line segments, then the entire gallery can always be supervised by $\lfloor{\frac{n}{3}}\rfloor$ watchmen placed in corners.

How can I find $\lfloor{\frac{24}{3}}\rfloor=8$ points (corners) in the Castro's room according the Art Gallery Theorem?

Castro24 = {{1, 0}, {1, 1}, {2, 1}, {2, 2}, {3, 1}, {3, 0}, {4, 0}, {3, -1},
{3, -1}, {2, -1}, {2, -2}, {1, -1}, {0, -1}, {0,-2}, {-1, -1}, {-2, -2},{-2, -1},
{-3, -1}, {-4, 0}, {-3, 0}, {-3, 1},  {-2, 2}, {-2, 1}, {-1, 1}, {-1, 0}, {1, 0}};

Graphics[{Blue, Line[First[#]]} & /@ {{Castro24}}] Thank you in advance to any one who may be able to give me some ideas

• Creating a graph which shows which corners can supervise which other corners is likely helpful. – C. E. Apr 3 '17 at 9:33
• Couldn't you do it in three? i.stack.imgur.com/jf7AM.png – Szabolcs Apr 3 '17 at 9:39
• I think RegionWithin is buggy. I get True for RegionWithin[Polygon[Castro24], Line[{Castro24[[{19, 21}]]}]] but look at Graphics[{LightBlue, Polygon[Castro24], Red, Line[{Castro24[[{19, 21}]]}]}]. Am I missing something? – Szabolcs Apr 3 '17 at 9:52
• related: Agent Navigates Maze – Kuba Apr 3 '17 at 11:33

A constructive application of Fisk's short proof: triangulate the polygon, 3-colour its vertices, and pick the smallest colour set.

triangulation = DiscretizeRegion[Polygon[Castro24], MaxCellMeasure -> ∞];
Needs["Combinatorica"];
vertices = MeshCoordinates[triangulation] /. {x_, y_} :> {{x, y}};
edges = MeshCells[triangulation, 1] /. Line[{a_, b_}] :> {{a, b}};
graph = CombinatoricaGraph[edges, vertices];
colouring = MinimumVertexColoring[graph, 3];
colour = 6 - Total@Commonest[colouring, 2]; (* least common of {1, 2, 3} *)
ShowGraph[Highlight[graph, Flatten@Position[colouring, colour]]] 