The Art Gallery Problem

The main mathematical news

1973: Václav Chvátal proves that  (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  (the floor of n/3) of the n vertices

To the MNS presentation
Additional Theorems / conjectures / Open questions

*     If the floor plan of the museum is a convex polygonit 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.

To the MNS presentation
The main mathematical concepts / Principles

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

To the MNS presentation

To start the presentation click anywhere in the 1st slide.
To move to the next slide use the keyboard arrows