Note About Art Gallery Problems

Prepared by:

Joseph Malkevitch
Department of Mathematics
York College (CUNY)
Jamaica, New York 11451

email:

malkevitch@york.cuny.edu

web page:

http://york.cuny.edu/~malk


We have seen that given any plane simple polygon P with n sides that it is possible to guard P with at most floor (n/3) (vertex) guards and that there are some n sided polygons that actually require floor (n/3) guards.

Polygons come in many flavors and work on art gallery theorems has expanded interest in creating definitions that distinguish between polygons on some interesting basis. Some examples of such polygons are monotone, vertically convex, staircase, etc. In particular, if all of the interior angles of the polygon are right angles or 270 degree angles, the polygon is known as an orthogonal polygon or rectilinear polygon. A typical example is shown below:

It turns out that this special class of polygons allows one to say more than one can for a general polygon. Using the fact what one can find a convex quadrilateralization (using existing vertices to subdivide the interior of the polygon into convex quadrilaterals) of an orthogonal polygon and that there is a way to extend Steve Fisk's 3-vertex-coloring of a triangulated polygon to a graph associated with a convex quadrilateralization of a simple polygon, one can prove:

Theorem (Jeffrey Kahn, Maria Klawe, and Daniel Kleitman, 1993)

If P is an orthogonal polygon with n sides, then floor ( n/4 ) vertex guards are sometimes necessary and always sufficient to guard the interior of P.

Reference:

Kahn, J. and M. Klawe, D. Kleitman, Traditional galleries require fewer watchmen, SIAM J. Alg. Disc. Math., 4 (1993) 194-206.