The Art Gallery Problem

The main mathematical news

1973: Václav Chvátal proves that ⌊n/3⌋ (the integer value 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 integer value 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 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.
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