\documentclass[11pt]{article}

\usepackage{dimacsmodules}

\setlength{\topmargin}{0in}     % top of paper to head (less one inch)
\setlength{\headheight}{0in}    % height of the head
\setlength{\headsep}{0in}       % head to the top of the body
\setlength{\textheight}{9.00in} % height of the body
\setlength{\oddsidemargin}{0mm} % left edge of paper to body (less one inch)
\setlength{\evensidemargin}{0mm} % ditto, even pages
\setlength{\textwidth}{6.5in}   % width of body
\setlength{\topskip}{0in}       % top of body to bottom of first line of text
%\setlength{\footheight}{0.25in} % height of footer
%\setlength{\footskip}{0.50in}   % bottom of text to bottom of foot



\newtheorem{them}{Theorem}[section]
\newtheorem{lem}[them]{Lemma}
\newtheorem{cor}[them]{Corollary}
\newtheorem{prop}[them]{Proposition}
\newtheorem{ex}{Example}[section]
\newtheorem{remark}{Remark}[section]
%%%%%%%%%%%%% MACROS OF AUTHORS
\def\ol{\overline}
\def\BOX{\rule{.1in}{.1in}}
\newenvironment{proof}{{\noindent\bfseries Proof:}}{$\BOX$ \medskip}         
\newenvironment{exercise}{\medskip\noindent}{\medskip}
\newenvironment{example}{\medskip\noindent}{\medskip}
%%%%%%%%%%%%%
\newcommand{\pinch}{\vspace{-9pt}}

\begin{document}

\begin{publicity}{}

\begin{center}

\vspace{.4in}

{\Large \bf DIMACS EDUCATIONAL MODULE SERIES}

\vspace{1.0in}

{\Large \bf MODULE 07-1}\\

{\Large \bf Art Gallery Theorems and Triangulations}\\

{\large \bf Date prepared: January 3, 2007}



\vspace{.5in}

%Mathematics Department\\
%
%Annapolis, MD 21402 \\
%\\
%\\
%Val Pinciu\\
%Mathematics Department\\
%\\ 
%New Haven, CT 06515 \\
%

{\bf T. S. Michael}\\
{\bf United States Naval Academy\\
Annapolis, MD 21402}\\
{\bf email: tsm@usna.edu}\\

\bigskip

{\bf Val Pinciu}\\
{\bf Southern Connecticut State University\\
New Haven, CT 06515}\\
{\bf email: pinciuv1@southernct.edu}\\


\end{center}

\vfill



\end{publicity}



\newpage



\begin{center}

{\large \bf Module Description Information}

\end{center}



\begin{itemize}

\item {\bf Title:}

Art Gallery Theorems and Triangulations

\item {\bf Authors:}

T. S. Michael, United States Naval Academy\\
Val Pinciu, Southern Connecticut State University

\item {\bf Abstract:}

The Art Gallery Problem asks for the maximum number of guards required to protect a polygonal art gallery with $n$ walls.
Fisk's beautiful solution of the problem relies on elementary ideas from geometry (triangulations of polygons)
and graph theory (vertex colorings). We discuss this background in detail and then present Fisk's proof.
We also explain how a similar coloring strategy was used
to treat orthogonal art galleries---those whose walls meet at right angles.


\item {\bf Informal Description:}

How many stationary guards are need to protect an art gallery?
We assume the floorplan of the gallery is any polygon with $n$ sides.
This geometric problem can be solved using notions from elementary graph theory.
Exercises are sprinkled throughout the module to reinforce ideas.
More substantial problems occur at the end of the module.
An annotated bibliography directs the reader to further resources.

\item {\bf Target Audience:}

This module is aimed at junior and senior mathematics and computer 
science majors taking a course in combinatorics or graph theory.

\item {\bf Prerequisites:}

The module assumes some familiarity with mathematical 
induction and basic notions of graph theory.


\item {\bf Mathematical Field:}

Graph Theory, Computational Geometry

\item {\bf Applications Areas:}

Art gallery theorems are studied in computational geometry, a branch of mathematics with applications
in such diverse areas such as computer vision, motion planning, and fingerprint identification methods.


\item {\bf Mathematics Subject Classification:}

05C15, 05C85, 68R10, 94C15


\item {\bf Contact Information:}

T. S. Michael\\
Mathematics Department\\
United States Naval Academy \\
Annapolis, MD 21402 \\
email: tsm@usna.edu\\
\\
Val Pinciu\\
Mathematics Department\\
Southern Connecticut State University \\ 
New Haven, CT 06515 \\
email: pinciuv1@southernct.edu

\item {\bf Other DIMACS modules related to this module:}

Module 03--3: Security Cameras and Floodlight Illumination

\end{itemize}

\newpage

\end{document}
