\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage[table]{xcolor}
\usepackage[all,arc]{xy}
\usepackage{color, colortbl}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.15in}
\setlength{\evensidemargin}{.15in}
\setlength{\textwidth}{6.2in}
\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{8.6in}


\input{preamble.tex}

\begin{document}

\homework{4: The Art Gallery Problem}{Due Tuesday, week 5, at the start of class}


\section*{Checkdown/also extra-credit problem.}

So, this week is slightly weird.  To get credit for this problem, just work on it; i.e. think about it, write down ideas, and otherwise spend a hour or two trying to figure out what's going on.  Assignments that show effort (i.e. $>1/2$ page of work and writing, coherent thoughts, good questions for me) will get credit.  If you fully answer the problem, you get the extra-credit half-point as well!

\begin{enumerate}
\item (\textbf{Fortress problem.})  Take a polygon $P$ with $n$ sides.  Consider the following task: we want to station observers at the vertices of $P$, such that they can guard the entire ``outside'' of $P$.  In this situation, we assume that the guards cannot ``see through'' $P$'s walls, and can only look out from their positions.  For example, here is a polygon $P$ being guarded by four guards:
\begin{center}
\includegraphics[width=3in]{math137a_final_fortress.pdf}\\
\footnotesize A polygon with observers guarding its outside.  Observers are denoted by red vertices; sample sight lines are drawn in pale red. \normalsize
\end{center}

Basically, this is the art gallery problem, except we're guarding the outside instead of the inside!

Suppose that $P$ is an arbitrary polygon with $n$ vertices.  What is the maximum number of guards needed to guard the exterior of $P$?  Justify your answer; i.e. explain why you must be right!
\end{enumerate}




\end{document}