9
$\begingroup$

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}}]

enter image description here

Thank you in advance to any one who may be able to give me some ideas

$\endgroup$
  • $\begingroup$ Creating a graph which shows which corners can supervise which other corners is likely helpful. $\endgroup$ – C. E. Apr 3 '17 at 9:33
  • 8
    $\begingroup$ Couldn't you do it in three? i.stack.imgur.com/jf7AM.png $\endgroup$ – Szabolcs Apr 3 '17 at 9:39
  • 1
    $\begingroup$ 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? $\endgroup$ – Szabolcs Apr 3 '17 at 9:52
  • $\begingroup$ related: Agent Navigates Maze $\endgroup$ – Kuba Apr 3 '17 at 11:33
6
$\begingroup$

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 = Combinatorica`Graph[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]]]

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.