The Art Gallery Problem

1973: Václav Chvátal proves that n/3 (the floor of n/3) is the upper bound for the number of guards needed to watch a one store museum whose floor plan is an n-sided-polygon.

1978: Steve Fisk gives an algorithm for positioning the guards in n/3 (the floor of n/3) of the n vertices

• If the floor plan of the museum is a convex polygon, it suffices to position a single camera at one of its vertices.
• Every polygon can be triangulated, usually, in at least one way.
• Coloring in three different colors the three vertices of any triangle in a triangulation of a polygon, determine the coloring of the rest of the vertices such that in each triangle the vertices are colored in three different colors.

Plane and solid geometry (MSC2010#97G40)

* Right prism

* Convex/Concave polygon

* Triangulation of polygon

*  Line of sight

*  Computational Geometry

*  The floor function

*  Algorithm

*  Upper bound

Logic (MSC2010#97E30)

* Necessary/ Sufficient conditions

* Proof by Induction

* Multiple proofs