\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}


%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Introduction}

\subsection{The Scorpio Art Gallery}

The director of an art gallery wants to post guards so that
every point in the gallery is  visible to at least one guard.
Naturally, the director wishes to employ as few guards as possible.
What is the smallest number of guards needed? The answer depends
on the shape of the art gallery and the powers of the guards, of course.

The Scorpio Art Gallery in Figure~\ref{Figure_ScorpioGallery} has eighteen sides and is 
protected by five guards 
at the indicated positions.
Every point in the gallery is visible to at least one guard. 
%%%
%%%  FIGURE: Scorpio Art Gallery
%%%
\input epsf
\begin{figure}[hb]
\begin{center}
\epsfbox{Figure_1.eps}
\caption{The Scorpio Art Gallery
\label{Figure_ScorpioGallery}
}
\end{center}
\end{figure}
%%%
%%%
%%%
Guards are stationary, but can rotate $360^{\circ}$ in place
to view the surrounding portions of the gallery not blocked 
off by walls. 
A guard at a corner of the gallery can see along the walls.
In Figure~\ref{Figure_ScorpioGallery} none of the five guards can be removed
without leaving some part of the gallery unprotected.
Nonetheless, it is possible to protect the gallery with just four guards.

\begin{exercise}{\bfseries Exercise 1.1: }
Indicate the positions of four guards that protect the Scorpio Art Gallery.
\end{exercise}

Can the art gallery director get by with just three guards in the Scorpio Art Gallery?
Evidently not; no guard can simultaneously view any two of the
four corners $w$, $x$, $y$, and $z$, and so at least four guards are
required.

\subsection{The Art Gallery Problem}

Now suppose the gallery director knows that the gallery is a polygon
with 18 sides, but cannot remember
the exact shape. How many guards must be hired to guarantee 
that the entire gallery can be protected, regardless of its shape? 
The Scorpio Art Gallery shows that at least four
guards are needed, but is there a gallery that requires more guards? Yes!
The Crown Gallery in Figure~\ref{Figure_CrownGallery} has 18 sides requires six guards.
%%%
%%%  FIGURE:  "Crown" Art Gallery
%%%
\input epsf
\begin{figure}[htb]
\begin{center}
\epsfbox{Figure_2.eps}
\caption{The Crown Gallery has eighteen sides and
can be protected by six guards, but no fewer.
\label{Figure_CrownGallery}
}
\end{center}
\end{figure}
%%%
%%%
%%%

\begin{exercise}{\bfseries Exercise 1.2: }
\begin{list}{}{\itemsep 0in \parsep 0in}
\item[(a) ] Explain why the Crown Gallery requires six guards.
\item[(b) ] Exhibit the positions of six guards that protect the gallery.
\end{list}
\end{exercise}

Some experimentation suggests that no 18-sided gallery requires more than
six guards, but a rigorous proof is not easy to produce. 

In general, we seek  the 
minimum number of guards that are guaranteed to be able to protect any $n$-sided
polygon.  (We always assume that our art galleries have polygonal floor plans.)
We let $g(n)$ denote the maximum number of guards required among
all $n$-sided art galleries. 
We have shown that $g(18)\geq 6,$ and we suspect that equality holds.
The general problem of evaluating $g(n)$ was posed by Victor Klee in 1973. % check year

\medskip

\noindent
{\bfseries The Art Gallery Problem: }
{\sl 
Let $n$ be an integer with $n\geq 3.$
What is the maximum number of guards required to protect 
a polygonal art gallery with $n$ sides? 
In other words, what is the value of $g(n)?$
}

\begin{exercise}{\bfseries Exercise 1.3: }
\begin{list}{}{\itemsep 0in \parsep 0in}
\item[(a) ] Explain why $g(3)=1.$
\item[(b) ] Explore examples and guess the values of $g(4)$ and $g(5).$
\item[(c) ] Show that $g(6)\geq 2.$
\item[(d) ]The following
partially completed table summarizes our deductions about $g(n)$ so far.
Fill in as much information as you can in the table.
$$
\begin{array}{r||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
n   &\,\,3\,\,&\,\,4\,\,&\,\,5\,\,&6&\,\,7\,\,&\,\,8\,\,&\,\,9\,\,&\,10\,&\,11\,&\,12\,&\,13\,&14& 15 & 16 & 17 & 18 \\  \hline
g(n)&1& & &\geq 2& & & &  &  &  &   & & & & &\geq 6
\end{array}
$$
\item[(e) ] Can you conjecture a formula for $g(n)$ based on a pattern you see in the table?
\end{list}
\end{exercise}

Klee's Art Gallery Problem was solved by Chv\'{a}tal in 1975.
In 1978, Fisk produced a short, elegant proof of Chv\'{a}tal's
Theorem. A number of variations of the Art Gallery Problem 
have been studied since then.
For instance, we may consider obstacles in the interior of
the art gallery that block the lines of sight of the guards.
Or we may require that adjacent walls of the art gallery 
meet perpendicularly.
All such variations are classified as {\bfseries art gallery problems.}

\subsection{Organization of the Module}

In this module we focus on Fisk's proof of Chv\'{a}tal's Theorem.
The mathematics involved is appealing and elementary,
although the arguments require some ingenuity.
Along the way we will encounter a 
pleasant mix of ideas from graph theory and geometry;
in Section 2 we recall some background material from these subjects.
Section 3 discusses triangulations, a key idea in Fisk's proof of Chv\'{a}tal's
Theorem, while Section 4 presents the proof itself.
In Section 5 we discuss and solve a variant known as the Orthogonal Art Gallery Problem.
Problems appear near the end of the module.
Exercises embedded within the text are meant to be worked as the reader encounters them
to reinforce the definitions and ideas.
We have also included some notes on the references.

%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Background and Review}
 
\subsection{Graph Theory}
We assume that the reader has been exposed to some graph theory.
In this section we recall the graph-theoretic concepts needed in 
Fisk's proof of Chv\'{a}tal's Theorem. 
A {\bfseries graph} $G=(V,E)$ 
consists of a finite, non-empty {\bfseries vertex set} $V$
and an {\bfseries edge set} $E$ of unordered pairs of distinct vertices.
If $(u,v)$ is an edge, then we say that vertices $u$ and $v$ are
{\bfseries adjacent.}
We often represent a graph by assigning its vertices to points in the plane
and letting curves or line segments join pairs of adjacent vertices.

\begin{example}{\bfseries Example 2.1: } 
Let $G=(V,E)$ be the graph 
with 
\[
\begin{array}{rl}
\mbox{vertex set}   & V=\{v_1,v_2,v_3,v_4\}\qquad \hbox{and} \\ [0.1in]
\mbox{edge set}      & E=\{ (v_1,v_2), (v_1,v_3), (v_1,v_4), (v_2,v_3)\}.
\end{array}
\]
Figure~\ref{Figure_Graphs} shows two drawings of $G.$
\end{example}
%%%
%%%  FIGURE: Graph Example
%%%
\input epsf
\begin{figure}[htb]
\begin{center}
\epsfbox{Figure_3.eps}
\caption{\label{Figure_Graphs}
(a) A drawing of the graph $G$ in Example 2.1. (b) A planar representation of $G$.}
\end{center}
\end{figure}
%%%
%%%
%%%

A graph $G$ is {\bfseries planar}
provided $G$ can be drawn in the plane with no edges that intersect, except
possibly at common end-vertices.
Such a drawing is  a {\bfseries planar representation} of $G.$
To prove that a graph is planar, we only need to display a planar
representation.  For instance, the graph in Example~2.1 is planar.

Let $G=(V,E)$ be a graph, and let $\lambda$ be a positive integer.
A {\bfseries $\lambda$-coloring} of $G$  is a function $f$ from $V$ to the {\bfseries color set}
$\{1,2,\ldots,\lambda\}$ such that no two adjacent vertices are mapped to the same color.
In other words, if $f(v)=f(w),$ then vertices $v$ and $w$ are not adjacent.
We think of  the function $f$ as assigning the color $k$
to the vertices in $V_k$ $(k=1,\ldots,\lambda)$, 
and define the $k$-th {\bfseries color class} as the set $V_k = \{v\in V:\,\,f(v)=k\}$.
Note that some color classes may be empty.
Of course, $V_1\cup V_2\cup \cdots \cup V_{\lambda} = V$ and 
$V_h\cap V_k = \emptyset$ for $h\neq k$,
and thus the color classes partition the vertex set of $G.$
We usually define a $\lambda$-coloring by exhibiting the color classes
$V_1$, $V_2$, $\ldots,$  $V_{\lambda}$,
instead of the function $f.$
For instance, the graph $G$ in Example 2.1 has a $4$-coloring 
in which $V_k = \{v_k\}$
for $k=1$, $2$, $3$, $4.$ 
Also, $G$ has a $3$-coloring with $V_1=\{v_1\}$, $V_2=\{v_2,v_4\}$,
and $V_3 =\{v_3\}.$ However, $G$ does not have a $2$-coloring. (Why not?)

We now state one of the most famous theorems in graph theory.

\medskip

\noindent
{\bfseries The Four-Color Theorem: }
{\sl Every planar graph has a $4$-coloring.} 

\medskip

The proof of the Four-Color Theorem is long and difficult; 
we refer the reader to the references at the end of this module for further information.
In Section 3 we shall see that a key step (Theorem 3.6) in the proof of the Art Gallery Theorem
can be shortened if we make use of the Four-Color Theorem. We shall also give a proof of
Theorem 3.6 that does not rely on this deep result.

Let $G=(V,E)$ be a graph.
A {\bfseries walk} in $G$ is a sequence of vertices 
$
v_0,\,\,v_1,\,\,\ldots,\,\, v_t
$ 
such that each pair of consecutive vertices $(v_{i-1},v_i)$ is an edge 
$(i=1,\ldots t).$ 
We say that the walk {\bfseries connects} $v_0$ and $v_t.$ 
The graph $G$ is {\bfseries connected} provided every pair
of vertices is connected by a walk.
We say that a walk $v_0$, $v_1$, $\ldots,$ $v_t $ is a {\bfseries simple circuit}
provided all its vertices are distinct, except that $v_0=v_t$.

\medskip

\noindent
{\bfseries Theorem 2.1: }
{\sl Let $T=(V,E)$ be a graph with $n$ vertices and $m$ edges.
If any two of the following statements are true, then all three statements
are true:
\begin{list}{$\bullet$}{\itemsep 0in \parsep 0in}
\item $T$ is connected;
\item $T$ has no simple circuits;
\item $m=n-1.$
\end{list}
} 

\medskip

The proof of Theorem 2.1 can be found in many texts on graph
theory or discrete mathematics.
A graph that satisfies the three conditions in Theorem 2.1 is called a
{\bfseries tree}.
A vertex of a tree $T$ is a {\bfseries leaf} provided it is adjacent to exactly one
other vertex of $T$. 
For example, the graph in Figure~\ref{Figure_Tree} is a tree with
seven vertices and five leaves.

%%%
%%%  FIGURE 4:  A tree
%%%
\input epsf
\begin{figure}[htb]
\begin{center}
\epsfbox{Figure_4.eps}
\caption{\label{Figure_Tree}A tree with seven vertices and five leaves.
}
\end{center}
\end{figure}

The proof of the following lemma is left to the reader.
\medskip

\noindent
{\bfseries Lemma 2.2: }
{\sl Every tree with at least two vertices has at least two leaves.} 
\medskip


\subsection{Geometry} 
We assume that the reader is familiar with basic notions in plane Euclidean
geometry.
Let us recall some terminology.
We let $xy$ denote the line determined by the distinct points $x$ and $y$, and
let $\ol{xy}$  denote the line segment with endpoints $x$ and $y$.
A subset $S$ of the Euclidean plane is {\bfseries convex} provided the
segment $\ol{xy}$ is a subset of $S$ for every pair of points $x$ and $y$ in
$S$.

\begin{exercise}{\bfseries Exercise 2.1: }
Prove that the intersection of two convex sets is convex.
\end{exercise}

A {\bfseries polygon} is an ordered sequence $[v_1,v_2,\ldots,v_n]$ 
of $n$ distinct points in the plane
$(n\geq 3)$, together with the $n$ line segments 
$\ol{v_1 v_2}$, $\ol{v_2 v_3}$, $\ldots,$ $\ol{v_{n-1} v_n}$, $\ol{v_n v_1}$.
The points $v_1$, $v_2$, $\ldots,$ $v_n$ are the {\bfseries vertices} of the polygon, 
and line segments $\ol{v_1 v_2}$, $\ol{v_2 v_3}$, $\ldots,$ $\ol{v_{n-1} v_n},$
$\ol{v_n v_1}$ are the {\bfseries sides.}
The order of the vertices of a polygon may be cyclically permuted without
changing the polygon.
For instance, the polygon $[v_1,v_2,v_3,v_4]$ is the same as the polygon
$[v_3,v_4,v_1,v_2].$

The polygons we discuss in this module represent our art galleries, of course,
and we shall use the term with a somewhat special meaning:
We require that our polygons be {\bfseries simple,} that is, 
no two non-consecutive sides have a point in common.
Each simple polygon is the boundary of a finite region in the plane,
and we use the word ``polygon" to mean the union
of the polygon and its interior region.
Thus our polygons represent the walls {\slshape and} the interior of an art gallery.
Figure~\ref{Figure_Polygons}(a) shows a convex polygon.
Note that one guard is enough to guard a convex polygon, but 
that a non-convex polygon with many sides
may require more guards. 
We will allow three or more consecutive vertices of our polygons to
be collinear since this convention simplifies one of our proofs.

%%%
%%%  FIGURE 5:  Polygons
%%%
\input epsf
\begin{figure}[htb]
\begin{center}
\epsfbox{Figure_5.eps}
\caption{\label{Figure_Polygons} (a) a convex polygon (b) a polygon with four reflex angles
}
\end{center}
\end{figure}


Let $v$ be a vertex of polygon $P$.
Then $v$ is a {\bfseries strictly convex} vertex provided the interior
angle of $P$ at $v$ is less than $180^{\circ}$, 
and $v$ is a {\bfseries reflex} vertex provided the interior angle at $v$ 
is greater than $180^{\circ}.$ 
The polygon in Figure~\ref{Figure_Polygons}(b) has four reflex angles.

\begin{exercise}{\bfseries Exercise 2.2: }
Prove that a polygon with a reflex angle cannot be convex.
\end{exercise}

The following lemma confirms the obvious
fact that every polygon has a strictly convex vertex.

\medskip

\noindent
{\bfseries Lemma 2.3: }
{\sl Every polygon has at least one strictly convex vertex.} 
\medskip

\begin{proof}
Let $P$ be a polygon with vertices $v_1$, $v_2$, $\ldots,$ $v_n$.
Introduce a Cartesian coordinate system, and let $(x_i,y_i)$ 
be the Cartesian coordinates of vertex $v_i$ $(i=1,\ldots,n).$
Let $v_k = (x_k,y_k)$ be the leftmost vertex, i.e.,
the vertex with smallest $x$-coordinate.
If there are several vertices that tie for the leftmost, then from these we choose
the lowest, i.e., the one  with smallest $y$-coordinate. 
The vertices of $P$ adjacent
to $v_k$ are $v_{k-1}$ and $v_{k+1}$,  and these fall either
strictly to the right of $v_k$, or on the same vertical line as $v_k$, but
strictly above $v_k$. (See Figure~\ref{Figure_Leftmost}.)
It follows that the angle at $v_k$ is less than $180^{\circ}$ and hence that
$v_k$ is a strictly convex vertex. 
%%%
%%% FIGURE 6. Proof of Lemma 2.3
%%%
\input epsf
\begin{figure}[htb]
\begin{center}
\epsfbox{Figure_6.eps}
\caption{\label{Figure_Leftmost} In the proof of Lemma~2.3, $v_k$ is lowest among the leftmost vertices}
\end{center}
\end{figure}
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Triangulations of Polygons}

\subsection{Basic Concepts}
Fisk's proof of Chv\'{a}tal's Theorem relies on a
triangulation of the  art gallery, that is, a decomposition
of the polygon into triangles by means of diagonals.
In this subsection we introduce and study triangulations.

Let $v$ and $w$ be two non-consecutive vertices of polygon $P$. 
Then the line segment $\ol{vw}$ is a {\bfseries diagonal} of $P$ provided every 
interior point of the segment $\ol{vw}$ is in the interior of $P$.
In Figure~\ref{Figure_Diagonals}(a) segments $\overline{uy}$ and $\overline{vx}$ 
are diagonals of the polygon.
However, $\overline{uw}$ and $\overline{uz}$ are not diagonals.

%%%
%%% Figure 7. Diagonals of polygon
%%%
\input epsf
\begin{figure}[htb]
\begin{center}
\epsfbox{Figure_7.eps}
\caption{\label{Figure_Diagonals} (a) Diagonals of a polygon (b) The proof of Proposition 3.1}
\end{center}
\end{figure}


\begin{exercise}{\bfseries Exercise 3.1: }
Explain why any two non-consecutive vertices 
are the endpoints of a diagonal in a convex polygon. 
\end{exercise}

Clearly, no triangle has a diagonal. 
However, every polygon with more than three sides does have a diagonal.

\medskip

\noindent
{\bfseries Proposition 3.1: }
{\sl 
Every polygon with at least four sides has a diagonal.}

\medskip
\begin{proof}
Let $P$ be a polygon with at least four sides.
Lemma 2.3 tells us that $P$ has a strictly convex vertex $v$.
Let $u$ and $w$ be the two vertices of $P$ adjacent to $v$. 
Let $S$ denote the set of vertices $P$ that lie inside or on the boundary of
triangle $\triangle uvw$. Thus $\{u,v,w\}\subseteq S.$
If $S$ contains no other vertices, then $\ol{uw}$ is a diagonal of $P$. 
If $S$ does contain  a point other than $u$, $v$, and $w$, then consider the set
of all lines
that are parallel to $uw$, passing through at least one point of $S$ other than $v$.
(See Figure~\ref{Figure_Diagonals}(b).)
The line in this set that is closest to $v$ must contain a point $x$ of $P$
such that $\ol{vx}$ is a diagonal of $P$.
\end{proof}

Two diagonals of a polygon $P$ are {\bfseries non-crossing} 
provided they are disjoint or intersect only at an endpoint.
The polygon $P$ in Figure~\ref{Figure_Diagonal_Triangulation}(a) is decomposed into triangles by some non-crossing
diagonals. We say that $P$ is triangulated. Triangulations are the crucial
notion in Fisk's proof of Chv\'{a}tal's Theorem. Let us define them more
precisely.
Let $P$ be a polygon, and let $S$ be a set of non-crossing diagonals of $P$.
The diagonals in $S$ partition $P$ into smaller polygons $P_1, \ldots, P_t$.
We say that the set of polygons $\{P_1,\ldots,P_t\}$ forms a 
{\bfseries decomposition} of the polygon $P$.
The vertices of the polygons $P_1$, $\ldots,$ $P_t$ are vertices of the original polygon
$P$ because  no new vertices have been added.
Two polygons in the decomposition are either
disjoint,
or else meet in a point (a vertex of $P$) or in a line segment (a diagonal
of $P$).
If each of the polygons $P_1$, $\ldots,$ $P_t$ contains exactly three vertices of $P$, then we say that
the decomposition is a {\bfseries triangulation}.

Note that if we remove diagonal $\overline{ty}$ from Figure~\ref{Figure_Diagonal_Triangulation}(a),
then we no longer have a triangulation. This is because the four vertices $t$, $u$, $y$, and $z$
form a quadrilateral in which the vertices $u$, $y$, and $z$ are collinear, and therefore $\triangle tuz$ contains
a fourth point of $P$ on its boundary.

%%%
%%%   FIGURE 8: Triangulation of a polygon
%%%
\input epsf
\begin{figure}[htb]
\begin{center}
\epsfbox{Figure_8.eps}
\caption{\label{Figure_Diagonal_Triangulation} (a) A decomposition of a polygon into triangles by non-crossing diagonals.
(b) A single diagonal gives a decomposition of a polygon into two smaller polygons $P_1$ and $P_2$.}
\end{center}
\end{figure}
%%%
%%%
%%%

\medskip

\noindent
{\bfseries Theorem 3.2: }
{\sl
Every polygon has a triangulation.
}

\medskip

\begin{proof}
We will prove this statement by mathematical induction on $n,$
the number of sides of the polygon $P.$
In the base case ($n=3$) the polygon is a triangle,
and the result is certainly true.
We now assume that $n\geq 3$ and that the statement is true for all polygons with
at most $n$ sides. 
Let $P$ be a polygon with $n+1$ sides. 
We must show that $P$ has a triangulation.
By Proposition 3.1 the polygon $P$ has a diagonal. 
This diagonal gives a natural 
decomposition of $P$ into two polygons $P_1$ and $P_2$ with $n_1$ and
$n_2$ sides, respectively. (See Figure~\ref{Figure_Diagonal_Triangulation}(b).)
Now the endpoints of our diagonal are the
only common vertices of $P_1$ and $P_2$, and hence $n_1 + n_2 = n+3$. 
This equality and the conditions $n_1\geq 3$ and $n_2\geq 3$ imply that $n_1\leq n$
and $n_2\leq n$.
We apply the induction hypothesis 
to obtain triangulations of $P_1$ and $P_2,$ which together
give a triangulation of the original polygon $P$.
\end{proof}

The argument in the previous proof may be adapted to show the following result.

\medskip

\noindent
{\bfseries Proposition 3.3: }
{\sl 
Every triangulation of a polygon with $n$ sides uses exactly $n-3$ diagonals
and contains $n-2$ triangles.
}

\medskip

A proof of Proposition 3.3 is requested in the Problems at the end of this
module. 

The angles in a triangle sum to $180^{\circ}$,
and thus Proposition 3.3 implies a basic result in geometry:

\medskip

\noindent
{\bfseries Corollary 3.4: }
{\sl
The sum of the interior angles of a polygon with $n$ sides
equals $(n-2)180^{\circ}$.
}

\subsection{Triangulation Graphs and the Dual Tree}

Let ${\cal T}$ be a triangulation of a polygon $P.$
The  {\bfseries triangulation graph} $G_{\cal T}$ has vertex set equal to the
vertices of $P.$
Two vertices are adjacent in $G_{\cal T}$ provided they correspond to 
consecutive vertices in the polygon $P$ or to the endpoints of a diagonal 
in the triangulation ${\cal T}.$
For instance, Figure~\ref{Figure_Triangulation_Dual} shows 
the triangulation graph for the polygon from Figure~\ref{Figure_Diagonal_Triangulation}.

%%%
%%% Figure 9
%%%
\input epsf
\begin{figure}[htb]
\begin{center}
\epsfbox{Figure_9.eps}
\caption{\label{Figure_Triangulation_Dual} A triangulation graph and its dual tree}
\end{center}
\end{figure}
%%%
%%%
%%%

We define the  {\bfseries dual tree} $\hbox{\rm dual}(G_{\cal T})$
of ${\cal T}$
to be the following graph:
For each triangle of ${\cal T}$, we have a corresponding vertex in 
$\hbox{\rm dual}(G_{\cal T})$, and two vertices of $\hbox{\rm dual}(G_{\cal T})$
are adjacent provided the corresponding triangles in ${\cal T}$ meet along a
diagonal of $P$. Figure~\ref{Figure_Triangulation_Dual} shows a triangulation graph of a polygon and the
corresponding dual tree.
The next lemma confirms that the dual tree of a triangulation
is indeed a tree.

\medskip
\noindent
{\bfseries Lemma 3.5: }
{\sl 
The dual tree of a triangulation of a polygon is 
a tree with each vertex adjacent to at most three others.
}

\medskip

\begin{proof}
Let ${\cal T}$ be a triangulation of a  polygon $P$ with $n$ vertices,
and let $G_{\cal T}$ be the corresponding triangulation graph.
We first note that $\hbox{\rm dual}(G_{\cal T})$ must be connected
by the manner in which it is constructed from $P.$
Now the number of vertices
of $\hbox{\rm dual}(G_{\cal T})$ equals the number of triangles in 
${\cal T},$ which equals $n-2$ by Proposition 3.3.
Moreover, the number of edges
in $\hbox{\rm dual}(G_{\cal T})$ equals the number of diagonals in the
${\cal T},$ which equals $n-3$ by Proposition 3.3.
Hence $\hbox{\rm dual}(G_{\cal T})$ 
is a connected graph with $n-2$ vertices and $n-3$ edges.
Therefore $\hbox{\rm dual}(G_{\cal T})$ is a tree by Theorem 2.1.
Finally, every vertex of $\hbox{\rm dual}(G_{\cal T})$ 
corresponds to a triangular face in
${\cal T}$, and hence is adjacent to most three
other vertices  in $\hbox{\rm dual}(G_{\cal T})$.
\end{proof}

Three consecutive vertices $u$, $v$, and $w$ of a polygon form an {\bfseries ear}
provided the segment $\ol{uw}$ is a diagonal.
The ears $[u_1,v_1,w_1]$ and $[u_2,v_2,w_2]$
are {\bfseries non-overlapping} provided the triangles $\triangle u_1v_1w_1$
and $\triangle u_2v_2w_2$ have disjoint interiors.
The polygon in Figure~\ref{Figure_Diagonal_Triangulation}(a) has three ears,
one of which is $\triangle vwx$. Also, $\triangle xyu$ is not an ear because the vertices
are not consecutive. No two of the three ears in the polygon overlap.

\begin{exercise}{\bfseries Exercise 3.2: } 
Find the other two ears of the polygon in Figure~\ref{Figure_Diagonal_Triangulation}(a).
\end{exercise}

\noindent
{\bfseries Two Ears Theorem} (Meisters):
{\sl 
Every polygon with $n$ vertices $(n\geq 4)$ has at least two non-overlapping ears.
}

\medskip

\begin{proof}
Let $G_{\cal T}$ be a triangulation graph for the polygon $P,$ and
$\hbox{\rm dual}(G_{\cal T})$ be the dual tree of ${\cal T}$.
The number of vertices of the dual tree is at least 2 because $n\geq 4$.
By Lemma 2.2 the dual tree has at least two leaves, say $v_1$ and $v_2.$
Now $v_1$ and $v_2$ correspond to triangles in $G_{\cal T}$ whose interiors
are disjoint, and which share at most a line segment as a boundary.
Thus $v_1$ and $v_2$ correspond to non-overlapping ears of 
the polygon $P$.
\end{proof}

\subsection{Colorings of Triangulations}

We have seen that every polygon has a triangulation.
Fisk's proof of Chv\'{a}tal's Theorem hinges on the existence of 
$3$-colorings of triangulations of polygons.
In Figure~\ref{Figure_Coloring} we construct a $3$-coloring of the triangulation
graph from Figure~\ref{Figure_Triangulation_Dual}.
%%%
%%% Figure 10:  Coloring of triangulations
%%%
\input epsf
\begin{figure}[htb]
\begin{center}
\epsfbox{Figure_10.eps}
\caption{\label{Figure_Coloring} Coloring a triangulation graph with three colors}
\end{center}
\end{figure}
%%%
%%%
%%%
We start by assigning three different colors to the vertices of any triangle.
In Figure~\ref{Figure_Coloring} we assigned the three colors to vertices $r$, $s$, and $t$.
Now vertex $z$ is adjacent to $r$ and $t$, and hence must be assigned
the same color as vertex $s$. 
Similarly, $y$ is adjacent to $t$ and $z$, and therefore must be the same color as $r$.
We proceed in this manner through all the triangles in the graph.
The color of every vertex is forced,
and we eventually obtain the three  color classes shown in Figure~\ref{Figure_Coloring}: 
\[
V_1=\{r,v,y\},\qquad
V_2=\{s,u,w,z\},\qquad
V_3=\{q,t,x\}.
\]

The general situation is treated in the following theorem.

\medskip
\noindent
{\bfseries Theorem 3.6: }
{\sl 
Every triangulation graph of a polygon is $3$-colorable.
}

\medskip

We give two proofs of this theorem.
The first uses induction
and relies on the Two Ears Theorem.
It formalizes the ``forced" $3$-coloring scheme given above.

\medskip

\noindent
{\bfseries First Proof: }
Let ${\cal T}$ be a triangulation of a polygon $P$ with $n$ vertices $(n\geq 3).$
We induct on $n.$
In the base case $n = 3$, the polygon is a triangle, and the corresponding
triangulation graph is certainly $3$-colorable.
Now assume that $n\geq 4$ and that a triangulation graph 
arising from any polygon with fewer
than $n$ vertices is $3$-colorable.
By the Two Ears Theorem we know that the triangulation ${\cal T}$
includes a
triangle $[u,v,w]$ that is an ear of $P.$
Remove vertex $v$ and the two sides $\ol{uv}$ and $\ol{vw}$ from $P$
and then insert the new side $\ol{uw}$
to obtain a polygon $P'$ with $n-1$ vertices. The polygon $P'$ inherits
a triangulation ${\cal T}'$ from the triangulation ${\cal T};$ simply
delete $\triangle uvw$ from ${\cal T}.$
By the induction hypothesis the triangulation graph $G_{{\cal T}'}$ may be 
$3$-colored. From a $3$-coloring of $G_{{\cal T}'}$ we
now obtain a $3$-coloring of the original triangulation graph
by assigning the color to vertex $v$ that is different from the colors
assigned to vertices $u$ and $w.$
$\BOX$

\medskip
The second proof relies on the Four-Color Theorem.

%%%
%%% Figure 11: 
%%%
\input epsf
\begin{figure}[htb]
\begin{center}
\epsfbox{Figure_11.eps}
\caption{\label{Figure_Coloring_4_Color_Theorem} A point $p$ in the exterior of a polygon is joined to each
vertex of a triangulation to form a planar graph $G'$}
\end{center}
\end{figure}
%%%
%%%
%%%

\medskip
\noindent
{\bfseries Second Proof: } Let $P$ be a polygon with a triangulation ${\cal T}.$ 
Choose any point $p$ in the exterior of $P$.
Now let $G'$ be the graph obtained as follows:
Start with the triangulation graph $G_{\cal T}$, adjoin a new vertex $p$,
and let $p$ be adjacent to every vertex in $G_{\cal T},$ that is,
we join $p$ by an edge to each vertex of the polygon $P.$
(See Figure~\ref{Figure_Coloring_4_Color_Theorem}).
It is clear that $G'$ is a planar  graph.
By the Four-Color  Theorem, $G'$ has a $4$-coloring.
Vertex $p$ is adjacent to all other vertices in $G',$
and hence vertex $p$ is assigned a different color from the other vertices.
Thus  the $4$-coloring of $G'$ gives us a 3-coloring
of the triangulation graph $G_{\cal T}$. 
$\BOX$
 

%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Chv\'{a}tal's Art Gallery Theorem}

\subsection{Strategy}

We are now ready to present Fisk's proof of Chv\'{a}tal's Art Gallery Theorem.
Embedded in the proof is an algorithm that tells us where to place the guards
in the art gallery.
Suppose we are given a polygon $P$ with $n$ sides. 
Here is the strategy of the proof.

\begin{list}{$\bullet$}{\itemsep 0in   \parsep 0in}
\item Find a triangulation ${\cal T}$ of the polygon $P$.
\item Find a $3$-coloring of the triangulation graph $G_{\cal T}.$
\item Use the $3$-coloring of $G_{\cal T}$ to position at most $\lfloor n/3
\rfloor$ guards that cover all of $P$.
\end{list}

Let $p$ be a point in a polygon $P.$
We say that the point $q$ is {\bfseries visible} from $p$ provided the line segment 
$\overline{pq}$ does not intersect the exterior of $P$.
For instance, in Figure~10 the points $t$ and $w$ are both visible from the
point $x$,
but $t$ and $w$ are not visible from one another.
By definition the polygon $P$ is convex if and only if every point in $P$ is
visible from every other point in $P.$
Let $V^*$ denote a set of points in a polygon $P$. 
Then we say that $V^*$ {\bfseries covers} $P$ provided that for every point $q$ in
$P$ there exists a point $p$ in $V^*$ such that $q$ is visible from $p$. 
A set $V^*$ that covers $P$ is a suitable set of guard locations. 
Of course, we seek to minimize the number of points in $V^*$.

\subsection{Theorem and Proof}

\noindent
{\bfseries Chv\'{a}tal's Art Gallery Theorem: }
{\sl 
Let $n$ be an integer with $n\geq 3.$
Then the maximum number of guards needed to cover a polygon with $n$ sides
is $\lfloor n/3 \rfloor.$
In other words, 
$$
g(n) = \bigg\lfloor {n\over 3} \bigg\rfloor.
$$
}

\begin{proof} (Fisk)
Let $P$ be a polygon with $n$ sides and vertex set $V.$
We shall show that $\lfloor n/3 \rfloor$ guards are sufficient to cover $P.$
By Theorem 3.2, $P$ has a triangulation ${\cal T}.$
Now consider the corresponding triangulation graph $G_{\cal T}.$
Theorem 3.6 implies that $G_{\cal T}$ has a $3$-coloring, say, with color classes
$V_1$, $V_2$, and $V_3.$
Because there are $n$ vertices altogether, 
we know that one of the color classes, say
$V_i,$ contains at most $\lfloor n/3 \rfloor$ vertices. 
We place guards at the vertices in $V_i$.
We claim that these guards cover all of $P$. 
The key observation is that each triangle of ${\cal T}$ has one vertex of each
of the three colors.
Now every point of a triangle is visible from each of its three vertices, and the
triangulation ${\cal T}$
is a decomposition of the polygon $P$. 
It follows that $V_i$ covers $P$.
For example, in the three-coloring for the triangulation of a polygon in Figure~\ref{Figure_Coloring}.
we may post guards at the three vertices the color class $\{r,v,y\}$, and the whole polygon is guarded.
We have now shown that 
\[
g(n)\leq \bigg\lfloor {n\over 3} \bigg\rfloor.
\]

It remains to show that some polygons with $n$ sides requires $\lfloor n/3\rfloor$ guards.
Suppose that $n$ is a multiple of $3,$ say $n=3t$.
Then a suitable crown-shaped polygon with $t$ tines is readily shown to require $t$
guards. (See Figure~\ref{Figure_CrownGallery}).
Now suppose that $n-1$ is a multiple of $3,$ say $n=3t+1$. 
Then we merely ``dent" the crown, replacing one corner by two nearby corners,
to produce a polygon that requires $t$ guards.
When $n-2$ is a multiple of $3$, we put two dents in the crown.
These constructions show that 
\[
g(n)\geq \bigg\lfloor {n\over 3} \bigg\rfloor.
\]
Our two inequalities now imply that $g(n) = \lfloor n/3 \rfloor$.
\end{proof}

\medskip

We remark that Fisk's coloring argument does not necessarily produce the smallest possible guard set to cover
the gallery. For instance, the polygon in Figure~\ref{Figure_Coloring} can be covered by just two guards at
points $r$ and $x$.

%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Orthogonal Art Galleries}

\subsection{Definitions}

A polygon is {\bfseries orthogonal} provided each interior angle is
either $90^{\circ}$ or $270^{\circ}.$
In an orthogonal polygon
the two sides alternate between two 
perpendicular orientations, say, horizontal and vertical.
Figure~\ref{Figure_OrthogonalGallery} displays an orthogonal polygon.

%%%
%%%  Figure 12:  Orthogonal Gallery
%%%
\input epsf
\begin{figure}[htb]
\begin{center}
\epsfbox{Figure_12.eps}
\caption{{An orthogonal polygon}
\label{Figure_OrthogonalGallery}
}
\end{center}
\end{figure}
%%%
%%%
%%%

\begin{exercise}{\bfseries Exercise 5.1: }
Let $P$ be an orthogonal polygon with $n$ sides.
\begin{list}{}{\itemsep 0in \parsep 0in}
\item[(a) ]
Prove that the number of $90^{\circ}$ angles in $P$ equals $(n+4)/2.$
{\bfseries Hint: } Use Corollary 3.4.
\item[(b) ] 
Prove that $n$ must be even.
\end{list}
\end{exercise}

We let $g_{\perp}(n)$ denote the maximum number of guards required among all $n$-sided orthogonal
art galleries. The notation is pronounced ``$g$ perp of $n$,'' and the subscript serves as a visual reminder of the
perpendicularity of the gallery's walls. Orthogonal galleries represent more typical floorplans of actual buildings.

\medskip
\noindent
{\bfseries The Orthogonal Art Gallery Problem: }
{\sl 
Determine the maximum number $g_{\perp}(n)$ of guards required to protect
any orthogonal polygon with $n$ sides.}

\begin{exercise}{\bfseries Exercise 5.2: }
\begin{list}{}{\itemsep 0in \parsep 0in}
\item[(a) ] Prove that $g_{\perp}(4)=1.$
\item[(b) ] Prove that $g_{\perp}(8)\geq 2.$
\end{list}
\end{exercise}

\begin{exercise}{\bfseries Exercise 5.3: } 
Let $m$ be a positive integer. 
Exhibit an orthogonal polygon that requires 
$m$ guards and has:
\begin{list}{}{\itemsep 0in \parsep 0in}
\item[(a) ]  $4m$ sides;
\item[(b) ] $4m+2$ sides.
\end{list}
In other words, show that $g_{\perp}(4m)\geq m$ and $g_{\perp}(4m+2)\geq m.$
\end{exercise}

\subsection{Theorem and Proof}

The Orthogonal Art Gallery Problem was completely solved in 1980.

\medskip

\noindent
{\bfseries Orthogonal Art Gallery Theorem: } 
(Kahn, Klawe, and Kleitman, 1980)  
{\sl Let $n$ be an even integer with $n\geq 4.$
Then the maximum number of guards needed to protect an  orthogonal polygon
with $n$ sides is 
$\lfloor n/4\rfloor.$
In other words, 
\[
g_{\perp}(n)=\bigg\lfloor {n\over 4} \bigg\rfloor.
\]
}

Note that the result of Exercise 5.3 implies that there
exist orthogonal polygons with $n$ sides
that require at least $\lfloor n/4\rfloor$ guards.
The difficult part is to show that $\lfloor n/4 \rfloor$
guards always suffice.

There are several proofs of the Orthogonal Art Gallery Theorem.
We shall discuss one with a strategy that is similar to Fisk's proof of 
Chv\'atal's
Art Gallery Theorem:

\begin{list}{$\bullet$}{\itemsep 0in   \parsep 0in}
\item Partition the art gallery into convex quadrilaterals.
\item Color the vertices of  a graph associated with the quadrilateral
partition.
\item Post the guards in positions according to the coloring.
\end{list}

The first step is the most difficult, and we shall not give the details. 

A {\bfseries quadrangulation} of a polygon $P$ is a decomposition 
$\{P_1,\ldots,P_t\}$ obtained by inserting diagonals
of $P$ so that each of the polygons $P_1$,$ \ldots,$ $P_t$
contains exactly four vertices of $P$ on its boundary. 
The quadrangulation is {\bfseries convex} provided each quadrilateral is convex.
Figure~\ref{Figure_Quadrangulated} shows two quadrangulations of a polygon, one of which is a convex
quadrangulation.

%%%
%%%  FIGURE 13:  Orthogonal Gallery
%%%
\input epsf
\begin{figure}[htb]
\begin{center}
\epsfbox{Figure_13.eps}
\caption{{(a) a non-convex quadrangulation (b) a convex quadrangulation}
\label{Figure_Quadrangulated}
}
\end{center}
\end{figure}
%%%
%%%
%%%

\begin{exercise}{\bfseries Exercise 5.4: }  
Suppose that a polygon with $n$ sides has a 
quadrangulation.  
\begin{list}{}{\itemsep 0in \parsep 0in}
\item[(a) ] Show that $n$ must be even.
\item[(b) ] How many quadrilaterals are there as a function of $n$?
\end{list}
\end{exercise}

\begin{exercise}{\bfseries Exercise 5.5: }
Give an example of a polygon with six sides that does
not have a convex quadrangulation.
\end{exercise}

The following result completes the first step of the proof strategy
and was the key step in the first proof of the Orthogonal
Art Gallery Theorem.

\medskip 

\noindent
{\bfseries Proposition 5.1: } (Kahn, Klawe, Kleitman, 1980)
{\sl  
Every orthogonal polygon has a convex quadrangulation.
}

\medskip 
One approach to prove Proposition 5.1 is by induction on the number of
vertices. A diagonal decomposes the orthogonal polygon into two polygons
with fewer sides, but these smaller polygons are not necessarily orthogonal
since the diagonal may be ``slanted."
Thus the induction hypothesis does not apply. 
One way to get around this difficulty
is to show that any polygon with at most one ``slanted" side
has a convex quadrangulation.
We omit the proof, and refer the reader to the references and notes
at the end of this module.

We now proceed to the second step of our proof strategy.


Let ${\cal Q}$ be a quadrangulation of a polygon $P.$
The  {\bfseries quadrangulation graph} $G_{\cal Q}$ has vertex set equal to the
vertex set of $P.$
Two  vertices are adjacent in $G_{\cal Q}$ provided they occur together in a
quadrilateral in ${\cal Q}.$ 
Thus the edges in $G_{\cal Q}$ arise from three sources:
consecutive vertices in the polygon $P;$ diagonals of $P$ that serve as sides
of quadrilaterals in ${\cal Q};$ diagonals of $P$ that are also diagonals of
quadrilaterals in ${\cal Q}.$
See Figure~\ref{Figure_Coloring_4}. 

%%%
%%%  FIGURE 14:  Quadrangulation graph
%%%
\input epsf
\begin{figure}[htb]
\begin{center}
\epsfbox{Figure_14.eps}
\caption{{A quadrangulation of a polygon, the corresponding quadrangulation graph, a 4-coloring, and a planar representation}
\label{Figure_Coloring_4}
}
\end{center}
\end{figure}
%%%
%%%
%%%
\begin{exercise}{\bfseries Exercise 5.6: }
Suppose an orthogonal polygon with $n$ sides has a convex quadrangulation
${\cal Q.}$ 
How many edges are there in the quadrangulation graph $G_{\cal Q}?$
\end{exercise}


\medskip 

\noindent
{\bfseries Lemma 5.2: }
{\sl Suppose that a polygon has a convex quadrangulation ${\cal Q.}$
Then the quadrangulation graph $G_{\cal Q}$ is $4$-colorable.
}

\medskip 

We outline two proofs and ask the reader to fill in the details
in the Problems.

\medskip

\noindent
{\bfseries Outline of First Proof: }
We may define a  dual tree of the quadrangulation ${\cal Q}$ of a polygon
as we did for triangulations.
Delete a leaf of this tree to obtain a quadrangulation of a polygon
with two fewer vertices and proceed by induction.
$\BOX$

\medskip

\noindent
{\bfseries Outline of Second Proof: }
We may show that $G_{\cal Q}$ is planar
by moving one internal diagonal from each quadrilateral to the
exterior face, thereby eliminating all edge-crossings.
(See Figure~\ref{Figure_Coloring_4} for instance.)
The Four-Color Theorem then implies that $G_{\cal Q}$ is $4$-colorable.
$\BOX$

\medskip 

We are now ready to prove the Orthogonal Art Gallery Theorem.

\medskip 

\noindent
{\bfseries Proof of the Orthogonal Art Gallery Theorem: }
Suppose we have an orthogonal polygon with $n$ sides.
By Proposition 5.1 we may form a convex quadrangulation ${\cal Q}$.
By Lemma 5.2 the corresponding quadrangulation graph $G_{\cal Q}$
is $4$-colorable. Notice that every quadrilateral uses
exactly one vertex of each of the four colors.
One color class $V_i$ contains at most $\lfloor n/4\rfloor$ of the vertices.
Post guards at each vertex of $V_i$ in the orthogonal art gallery.
Every point in the art gallery occurs in a convex quadrilateral,
and this quadrilateral necessarily contains a vertex from $V_i$.
Therefore every point in the orthogonal art gallery is visible from a guard.
We have shown that $g_{\perp}(n)\leq \lfloor n/4\rfloor$.
Exercise~5.3 gives the reverse inequality $g_{\perp}(n)\geq \lfloor n/4\rfloor$.
$\BOX$

%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Problems}

\begin{enumerate}
\setlength{\itemsep}{-0.5ex}   % this closes up some space between problems

\item
Prove Theorem 2.1.

\item
Prove Lemma 2.2.

\item
Prove that every polygon has at least three strictly convex angles.


\item\begin{enumerate}\item
Find all triangulations of the polygon in Figure~5(b).

\item
Find a polygon with seven sides that has exactly one triangulation.
\end{enumerate}

\item
Prove Proposition 3.3.

\item
Find a triangulation of a suitable polygon whose dual tree is the tree in Figure~4.

\item
Prove that a convex polygon with $n$ sides has exactly $n(n-3)/2$ diagonals.

\item
Let $P$ be a polygon with $n$ sides.
Lemma 2.3 asserts that some interior angle of $P$ has measure less than
$180^{\circ}.$
Prove the stronger result that some interior angle has measure at most
$\left(1-{2\over n}\right)180^{\circ}.$

\item 
Let $G_{\cal T}$ be a triangulation graph for a polygon with $n$ vertices.
How many $3$-colorings does $G$ have using the color set $\{1,2,3\}$?

\item
Triangulate the Scorpio Art Gallery in Figure~\ref{Figure_ScorpioGallery} and give a $3$-coloring of the 
resulting triangulation graph.

\item
Prove that a polygon with at most one reflex angle can be covered by one guard.

\item Suppose that $r\geq 1$.
\begin{enumerate}
\item Show that a polygon with $r$ reflex angles can be covered by $r$ guards.
\item Exhibit a polygon with $r$ reflex angles that requires $r$ guards.
\end{enumerate}

\item
Let $P$ be a polygon with exactly three strictly convex vertices.

\begin{enumerate}
\setlength{\itemsep}{-0.5ex} 
\item Prove that $P$ can be covered with one guard if the three strictly convex vertices are consecutive.
\item What if the three strictly convex vertices are not consecutive?
\end{enumerate}

\item
Give an example of a polygon $P$ and a guard set $V^*$ such that
$V^*$ covers every point on the boundary of $P,$ but does not cover $P.$

\item 
\begin{enumerate}
\setlength{\itemsep}{-0.5ex} \item Complete the first proof of Lemma 5.2.
\item Complete the second proof of Lemma 5.2.
\end{enumerate}

\item
Let $G=(V,E)$ be a graph, and let $\lambda$ be a positive integer.
Suppose that the vertices of $G$ are labeled $v_1$, $v_2$, $\ldots,$ $v_n$
so that for each $i>\lambda$ the vertex $v_i$ is adjacent to fewer than 
$\lambda$ vertices with smaller subscripts.

\begin{enumerate}
\setlength{\itemsep}{-0.5ex} 
\item Prove that $G$ is $\lambda$-colorable.
\item How does the result in (a) relate to Theorem 3.6 and Lemma 5.2?
\end{enumerate}

\item
Show that any polygon with seven sides can be guarded with two guards that are visible
to each another.
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Notes and References}

The classic reference for art gallery theorems
is the book by O'Rourke~\cite{ORourke87}.
Shermer~\cite{Shermer} wrote an updated survey.
The excellent handbook~\cite{Urrutia} on computational geometry contains 
a recent survey by Urrutia on art gallery problems.

The Art Gallery Theorem was first proved by Chv\'atal~\cite{Chvatal},
and Fisk's proof~\cite{Fisk} appeared a short time later.
Kahn, Klawe, and Kleitman~\cite{KKK} first proved the Orthogonal
Art Gallery Theorem; different proofs were provided by 
O'Rourke~\cite{ORourke83} and Gy\H{o}ri~\cite{Gyori}. 
Lubiw~\cite{Lubiw} proved that orthogonal polygons have convex quadrangulations,
from which the Orthogonal Art Gallery Theorem follows.

The graph theory background used in this module can be found
in many texts, including those by  Chartrand and Lesniak~\cite{Chartrand}
and Roberts~\cite{Roberts}.
The books by Saaty and Kainen~\cite{Saaty} and Wilson~\cite{Wilson} discuss the Four-Color Theorem and its proof.

\begin{thebibliography}{99}

\bibitem{Chartrand}
G. Chartrand and L. Lesniak,
{\sl Graphs and Diagraphs.}
2nd ed. Wadsworth and Brooks/Cole, 1986.

\bibitem{Chvatal}
V. Chv\'atal,
A combinatorial theorem in plane geometry,
{\sl J. Combin. Theory Ser. B}, 
{\bfseries 18} (1975), 39-41.

\bibitem{Fisk}
S. Fisk,
A short proof of Chv\'atal's watchman theorem.
{\sl J. Combin. Theory Ser. B}, 
{\bfseries 24} (1978), 374.

\bibitem{Gyori}
E. Gy\H{o}ri,
A short proof of the rectilinear art gallery theorem
{\sl SIAM J. Alg. Disc. Meth.,} {\bfseries 7} (1986) 452-454.

\bibitem{KKK}
J. Kahn, M. Klawe, and D. Kleitman,
Traditional galleries require fewer watchmen,
{\sl SIAM J. Alg. Disc. Meth.,} {\bfseries 4} (1983) 194-206.
 
\bibitem{Lubiw}
A. Lubiw,
Decomposing polygonal regions into convex quadrilaterals,
{\sl Proc. 1st ACM Symp. Comput. Geom.,} Baltimore (1985) 97-106.

\bibitem{Roberts}
F. S. Roberts,
{\sl Applied Combinatorics. }
Prentice-Hall, New Jersey, 1984.

\bibitem{ORourke83}
J. O'Rourke,
An alternate proof of the rectilinear art gallery theorems,
{\sl J. of Geometry,} {\bfseries 21} (1983), 118-130.

\bibitem{ORourke87}
J. O'Rourke,
{\sl Art Gallery Theorems.} Oxford University Press, 1987.

\bibitem{Saaty}
T. L. Saaty and P. C. Kainen, 
{\sl The Four-Color Problem: Assaults and Conquest.}
Dover Publications, New York, 1986. 

\bibitem{Shermer}
T. C. Shermer,
Recent results in art gallery theorems,
{\sl Proc. IEEE,} {\bfseries 80} (1992), 1384-1399.

\bibitem{Urrutia}
J. Urrutia,
Art gallery and illumination problems, in: {\sl Handbook of Computational Geometry,}
J.-R Sack and J. Urrutia (eds.) Elsevier Science B.V. 1999, pp 973--1027.

\bibitem{Wilson}
R. Wilson, 
{\sl Four-Colors Suffice.}
Princeton University Press, New York, 2002. 

\end{thebibliography}

\end{document}
