\documentclass[11pt]{article}
\usepackage{dimacsmodules}
\usepackage{graphics}  %%invoke this if graphics won't work otherwise
\usepackage{theorem}
\input amssym.def

\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

%--------------from the book style file----------------------

\newcommand{\bC}{{\bf C}}
%\textwidth 16.2cm
%\evensidemargin 2mm
%\oddsidemargin 2mm
\newcommand{\sk}{\medskip}
\newcommand{\bsk}{\bigskip}
%\special{papersize=8.5in,11in}
%\newtheorem{thm}{Theorem}[chapter]
\newtheorem{thm}{Theorem}[section]
\newtheorem{thrm}{Theorem}%[chapter]
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{coro}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}

%\theoremstyle{definition}
\theorembodyfont{\rmfamily}
\newtheorem{defn}[thm]{Definition}
\newtheorem{examp}[thm]{Example}
\newtheorem{xca}[thrm]{Exercise}

%\theoremstyle{remark}
\newtheorem{rmk}[thm]{Remark}

%\numberwithin{section}{chapter}
%\numberwithin{equation}{chapter}
%%\numberwithin{thm}{section}
%\numberwithin{table}{section}
%%\numberwithin{figure}{section}

%\renewcommand{\include}{\input}

\parindent2em
\newcommand{\nsk}{\addvspace{-5ex}}
\newcommand{\bt}{\begin{thm}}
\newcommand{\et}{\end{thm}}
\newcommand{\bl}{\begin{lemma}}
\newcommand{\el}{\end{lemma}}
\newcommand{\br}{\begin{rmk}}
\newcommand{\er}{\end{rmk}}
\newcommand{\bc}{\begin{coro}}
\newcommand{\ec}{\end{coro}}
\newcommand{\bd}{\begin{defn}}
\newcommand{\ed}{\end{defn}}
\newcommand{\bex}{\begin{examp}}
\newcommand{\eex}{\end{examp}}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\bp}{\begin{prop}}
\newcommand{\ep}{\end{prop}}
\newcommand{\bce}{\begin{center}}
\newcommand{\ece}{\end{center}}
\newcommand{\bxc}{\begin{xca}}
\newcommand{\exc}{\end{xca}}
\newcommand{\ul}{\underline}
\newcommand{\ol}{\overline}
\newcommand{\ink}{\rule{.8ex}{1.5ex}}   %end of proof marker
\newcommand{\Llr}{\Longleftrightarrow}
\newcommand{\Lr}{\Leftrightarrow}
\newcommand{\imp}{\Longrightarrow}
\newcommand{\sm}{\setminus}
\newcommand{\seq}{\subseteq}
%\newcommand{\C}{\mathfrak c}
\newcommand{\C}{\frak c}
%\renewcommand{\chaptername}{SECTION}
%\renewcommand{\appendixname}{APPENDIX}
%\renewcommand{\bibname}{REFERENCES}
\renewcommand{\contentsname}{TABLE OF CONTENTS}

\renewcommand{\thefigure}{\thesection.\arabic{figure}}
\renewcommand{\thetable}{\thesection.\arabic{table}}

%--------------from the book format----------------------

%\newcommand{\pinch}{\vspace{-9pt}}
\pagenumbering{roman}

\begin{document}
\begin{publicity}%{}


\begin{center}
\vspace{.4in}
{\Large \bf DIMACS EDUCATIONAL MODULE SERIES}

\vspace{.8in}

{\Large \bf MODULE 03-3}\\
{\Large \bf Security Cameras and Floodlight Illumination}\\
{\large \bf Date prepared:} \today

\vspace{.3in}
{\bf Marjorie Darrah}\\
{\bf  Senior Scientist}\\
{\bf Institute for Scientific Research}\\
{\bf P.O. Box 2720}\\
{\bf Fairmont, WV 26554-2720}\\
{\bf email: MDarrah@isr.us}

\vspace{.15in}

{\bf Nancy Hagelgans}\\
{\bf Department of Mathematics and Computer Science} \\
{\bf Ursinus College} \\
{\bf Collegville, PA 19426}\\
{\bf email: NHagelgans@Ursinus.edu}

\vspace{.15in}
{\bf Lidia Luquet}\\
{\bf Department of Mathematics and Computer Science}\\
{\bf Saint Mary's College of California}\\
{\bf Moraga, CA 94575-3517}\\
{\bf email: lluquet@stmarys-ca.edu}
\vspace{.15in}

{\bf Allison Wolf}\\
{\bf College of Computing} \\
{\bf Georgia Institute of Technology}\\
{\bf Atlanta, GA 30332-0280}\\
{\bf email: awolf@cc.gatech.edu}
\end{center}
\vfill

\end{publicity}

\setcounter{page}{0}
\newpage

\begin{center}
{\large \bf Module Description Information}
\end{center}

\begin{itemize}
\item {\bf Title:}

\textbf {Security Cameras and Floodlight Illumination}

\item{\bf Author(s):}

Marjorie Darrah

Nancy Hagelgans

Lidia Luquet

Allison Wolf

\item {\bf Abstract:}

This module leads students to investigate several geometrical aspects
of illumination: the effectiveness of various types of floodlights
placed in polygonal rooms either with or without holes as well as
problems related to lighting a stage.  An optional Section 4 for more
advanced students provides formal statements and proofs of some
intuitive ideas used in the applications.  Exploratory exercises occur
throughout the text to encourage students to reflect on new concepts
as they are introduced.  In addition, more challenging problems are
provided.

\item {\bf Target Audience:}

The module is written for advanced high school students and lower
level college students.

\item {\bf Prerequisites:}

The prerequisites are high school geometry and proof by mathematical
induction.

\item {\bf Topics:}

The topics of this module include security cameras and floodlight
illumination of polygons and of stages.  The floodlight problems
addressed involve determining the maximum of the smallest number of
floodlights required to illuminate regions under certain specified
restrictions.  For example, the floodlights may be required to be
placed only at the polygon's vertices and to have the same aperture;
the polygons under consideration may be required to have the same
number of vertices.  Polygons both with and without holes are
examined.

\item {\bf Goals:}

One goal is to introduce students to some fundamental ideas of
computational geometry through applications to illumination problems.
Another goal is promote the idea that mathematics is a growing body of
knowledge with easily stated unsolved problems.

\item {\bf Anticipated Number of Class Meetings:}

The module requires three class meetings if Section 4 is omitted; two
additional class meetings are needed for Section 4.  Advanced students
may study the module independently with no class meetings.

\item {\bf Contact Information:}

Marjorie Darrah \\
Senior Scientist \\
Institute for Scientific Research \\
P.O. Box 2720\\
Fairmont, WV 26554-2720 \\
email: MDarrah@isr.us

\vspace{.15in}
Nancy Hagelgans \\
Department of Mathematics and Computer Science \\
Ursinus College \\
Collegville, PA 19426 \\
email: NHagelgans@Ursinus.edu

\vspace{.15in}
Lidia Luquet \\
Department of Mathematics and Computer Science\\
Saint Mary's College of California\\
Moraga, CA 94575-3517\\
email: lluquet@stmarys-ca.edu

\vspace{.15in}
Allison Wolf \\
College of Computing \\
Georgia Institute of Technology \\
Atlanta, GA 30332-0280 \\
email: awolf@cc.gatech.edu

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

None at this time

\end{itemize}
 
\newpage

\setcounter{page}{0}
\pagenumbering{arabic}
\tableofcontents

\newpage
\section*{ABSTRACT}
\addcontentsline{toc}{section}{Abstract}
This module leads students to investigate several geometrical aspects
of illumination: the effectiveness of various types of floodlights
placed in polygonal rooms either with or without holes as well as
problems related to lighting a stage.  An optional Section 4 for more
advanced students provides formal statements and proofs of some
intuitive ideas used in the applications.  Exploratory exercises occur
throughout the text to encourage students to reflect on new concepts
as they are introduced.  In addition, more challenging problems are
provided.

\newpage
\setcounter{section}{0}

\section{Introduction}

We begin our examination of simplified lighting problems by
considering some examples that indicate the wide applicability of the
concepts related to illumination.  We usually restrict our attention
to the case of two dimensions.

\subsection{A surveillance camera problem}
Median Bank is planning to upgrade its security system with new
surveillance cameras.  The officers of the bank want to use as few
cameras as possible to keep costs low and to ensure that the cameras'
presence is unobtrusive.  They want to know how many cameras are
needed, what camera features are helpful, and where the cameras should
be placed.  These cameras must survey every part of the bank's main
room.  The problem is complicated further by the shape of the room as
shown below.
\begin{center}
\resizebox*{!}{1.5in}{\includegraphics{fig11.eps}}
\vspace{.3cm}

Figure 1.1
\end{center}

\subsection{Related problems}
There are several other problems related to the placement of security
cameras.  Figure 1.1 could be viewed as:
\begin{itemize}
\item a parking lot that should be lit with floodlights of a certain
aperture to ensure the safety of the drivers and their cars,

\item a lawn that requires watering in its entirety with sprinklers that
only rotate through a given angle, or

\item an art gallery that needs to be protected by guards standing in
fixed positions.  
\end{itemize}
The problem in each case is to find the smallest number of cameras,
floodlights, sprinklers, or guards that survey, illuminate, water, or
observe the required region.  We will investigate only some of the
related problems.

All these problems are considered to be variations of the major class
of problems collectively called the Art Gallery Problems.  Victor Klee
posed the original Art Gallery Problem in 1973 about guards who can
turn to see 360 degrees but who are standing in one location.  We
think of these guards as points.  In this problem, the art gallery
room is assumed to have a floor shaped like a polygon with $n$
vertices.  For each such room there is a minimum number of these
guards needed to observe the entire room.  The problem is to find the
maximum of these minimum numbers for every fixed value of $n$.  Klee
conjectured that this number is $\lfloor n/3\rfloor$, the greatest
integer that is less than or equal to $n/3$, and in 1975 V. Chv\'{a}tal
published a proof of this conjecture [C].  We relate this original
problem to illumination problems by considering point sources of light
instead of guards and regions illuminated by lights rather than
regions surveyed by guards.

{\bf Exploratory Exercises}

1.1 In the room below in Figure 1.2, one camera with viewing angle
(aperture) of 90 degrees is placed in the upper left corner.  The
region surveyed by the camera is shaded.  We assume that the camera
surveys this region's boundaries as well as its interior.  How many
additional cameras with aperture of 90 degrees are needed to survey
the entire room?  Where should these cameras be placed?

\begin{center}
\resizebox*{2.5in}{!}{\includegraphics{fig12.eps}}
\vspace{.3cm}

Figure 1.2
\end{center}

1.2 Suppose that you have three surveillance cameras.  In addition,
you know that each camera has viewing angle (aperture) of 90 degrees.
Try to place the three cameras in corners of each of the rooms below
so that the cameras survey the entire room, and indicate the region
surveyed by each camera.  In which rooms will fewer than three cameras
suffice?  In which rooms is it impossible to survey the entire room
with these three cameras?

\begin{center}
\resizebox*{1.3in}{!}{\includegraphics{fig13-1.eps}}\hspace{0.3in}
\resizebox*{1.7in}{!}{\includegraphics{fig13-2.eps}}

\resizebox*{1.8in}{!}{\includegraphics{fig13-3.eps}}\hspace{0.3in}
\resizebox*{1.9in}{!}{\includegraphics{fig13-4.eps}}
\vspace{.3cm}

Figure 1.3
\end{center}

1.3 Use the following method to find the viewing angle (aperture) of
your camera.  Select two vertical lines on a wall, such as the
vertical sides of a window or the vertical edges of a large picture.
Measure the distance $y$ between these vertical lines.  Let $AB$ be a
horizontal line segment between these vertical lines on the wall.  As
you look into your camera, step back and forth along the line
perpendicular to the wall at the midpoint of the line segment $AB$.
You want to line up the vertical edges of the camera's viewing window
with the selected vertical lines on the wall.  When you see the
vertical edges of the camera's viewing window coincide with the
vertical edges on the wall, measure your distance $x$ from the wall.
Make a sketch similar to the one in Figure 1.4 below.  Make the sketch
to scale with great accuracy.  Then use a protractor to measure the
camera's aperture, the angle $ACB$.

\begin{center}
\includegraphics{fig14.eps}
\vspace{.3cm}

Figure 1.4
\end{center}

1.4 What are the advantages and disadvantages of placing a camera of
aperture 90$^\circ$ in a room at a corner, along a side, or in the interior?

\subsection{Mathematical formulation of the camera problem}
As we translate the problem of security cameras into mathematics, we
should note that this problem has not been entirely solved by anyone
in the world today.  We will explain the part of the problem that has
been solved and will explore the part that is still yet to be solved.
To explain the results that have already been found about the optimal
placement of the security cameras we will have to impose a restriction
on the problem.  Mathematicians have approached the problem of camera
placement by allowing the cameras to be placed only in the corners of
the room.  The general problem of considering the cameras placed
anywhere in the room or anywhere along the walls of the room has not
been fully explored.  Thus, for the most part, we will treat the
problem in the following form since this is the form that has been
studied extensively in the mathematical literature:
\begin{quote}{\em
How many corner cameras with a given viewing angle suffice to see all
points of a given room?}
\end{quote}
In mathematical terms, the room translates to a polygon, the corners
to the vertices of a polygon, the camera angle to an aperture, the
region viewed by the camera to a wedge, and seeing all points of the
room to covering the polygon.  Now the problem can be stated in a more
mathematical way as follows:
\begin{quote}{\em
How many vertex cameras with a given aperture suffice to cover a
polygon?}
\end{quote}
We will consider the problem as stated mathematically.

\subsection{Mathematical formulation of other lighting problems}
A wide range of applications can be mathematically formulated as
lighting problems similar to the examples for the security cameras in
the introduction.  Below you will find some applications that fit
within this range.

\medskip

{\flushleft \bf Problems} 
\begin{enumerate}
\item[1.1] We are designing a garden within a wall that has already
been built, and we wish to water the garden using as few sprinklers as
possible.  The range of each sprinkler is greater than the diameter of
the garden, but each sprinkler has limited angle of rotation $\alpha$.
Since the walls are solid, they block the spray.  In order to save
money, we would like to install the smallest possible number of
sprinklers.

a.  For a general polygonal garden with $n$ vertices, formulate the
problem of watering the lawn in the most economical fashion in
mathematical terms.  How does this problem differ from the security
camera problem?

b.  Is this model a realistic way to address the problem of installing
a sprinkler system economically?  What other concerns might affect the
cost?

c.  How does the problem change if the garden is already well
established and the owner would like to avoid digging it up?

\item[1.2] We wish to illuminate the complete area of a parking lot by
means of overhead lights.  The lights are on posts $k$ feet tall, and
each light illuminates a cone of vertex angle $\alpha$ as shown in
Figure 1.5 below.  To do this in the most economical form, we would
like to use the minimum number of lights.

a.  For a general polygonal parking lot and the restrictions given
above, formulate the problem of lighting the parking lot in the most
economical fashion using mathematical terms.  (For now, don't attempt
to solve the problem, just try to describe it.)  How does this problem
differ from the security camera problem and the problem of watering
the garden?  Why are three dimensions involved rather than only two
dimensions?

b.  Is it realistic to assume that we only want the area of the
parking lot illuminated?  If so, explain why.  If not, explain how the
statement of the problem could be changed in order to make it more
realistic.

\begin{center}
\includegraphics{fig15.eps}
\vspace{.3cm}

Figure 1.5
\end{center}
\end{enumerate}

\section{Mathematical Background}
	
As you investigate and study the problem of illumination, you will
need to understand and use some mathematical terms.  In this section,
we define most of the terms that you will need in the rest of the
module.

A {\em polygon} is generally defined as an ordered sequence of at
least three points $v_1,v_2, \dots,v_n$ in the plane and the $n$ line
segments $v_1v_2, v_2v_3,\dots,v_{n-1}v_n$, and $v_nv_1$.  The points
are called {\em vertices} of the polygon, and the line segments are
called {\em edges} of the polygon.  The line segments taken together
are also called the {\em boundary} of the polygon.  A {\em simple
polygon} is a polygon with the constraint that nonconsecutive edges do
not intersect.  A simple polygon divides the plane into two regions,
an unbounded exterior and a bounded interior.

{\em From this point on we use the term polygon to denote a simple
polygon together with its interior.}
\begin{center}
\resizebox*{1.6in}{!}{\includegraphics{fig21-1.eps}}\hspace{0.6in}
\resizebox*{1.6in}{!}{\includegraphics{fig21-2.eps}}

Simple Polygon\hspace{1.2in}
Non-simple Polygon

\vspace{.3cm}

Figure 2.1
\end{center}

Angles will be given in radian measure unless otherwise stated.
Recall that:
\[
\pi\mbox{ radians} = 180\mbox{ degrees}.
\]
A vertex of a polygon is {\em reflex} if its interior angle is
strictly greater than $\pi$ radians.  A vertex is {\em convex} if its
interior angle is less than or equal to $\pi$ radians, and it is {\em
strictly convex} if its interior angle is strictly less than $\pi$
radians.  A polygon is {\em convex} if, for each pair of points in the
polygon, the line segment joining these points lies within the
polygon.  An {\em orthogonal polygon} is a polygon with adjoining
sides that are perpendicular.
\begin{center}
\includegraphics{fig22.eps}
\vspace{.3cm}

Figure 2.2
\end{center}

{\bf Exploratory Exercises}
\begin{enumerate}
\item[2.1] Identify any reflex vertices of each polygon in Figure 2.3
below

\begin{center}
\includegraphics{fig23.eps}

Figure 2.3
\end{center}

\item[2.2] Sketch a convex polygon with 5 edges.

\item[2.3] Sketch a polygon with 4 convex vertices and 2 reflex
vertices.

\item[2.4] Sketch an orthogonal polygon with 12 edges.

\item[2.5] Sketch an orthogonal polygon with five sides or explain why
none exists.
\end{enumerate}

Now we go on to some definitions that are related to floodlights
placed in polygonal rooms.  A {\em wedge} is the set of points that
are interior to an angle. The vertex of the wedge is called the {\em
apex}.  A {\em floodlight of angle} $\alpha$ is a wedge of light of
aperture at most $\alpha$ and such a floodlight is called an {\em
$\alpha$-light}.  A floodlight placed in a simple polygon with its
apex at a vertex is called a {\em vertex floodlight}.  The {\em
aperture} of a floodlight is its angle.  A point is {\em illuminated}
if it lies within some floodlight's wedge or on the boundary of some
floodlight's wedge.

{\em For the purpose of this paper, no vertex may have more than one
floodlight, and each floodlight is placed in one position and then
does not move.  Note that the aperture of a floodlight may exceed the
angle where it is placed.}

\begin{center}
\resizebox*{!}{2in}{\includegraphics{fig24.eps}}
\vspace{.3cm}

Figure 2.4
\end{center}

Figure 2.4 above illustrates some of the previous definitions.  The
vertex is $x$, and the apex of the illuminated wedge is at $x$.  The
point $y$ is illuminated.  The patterned wedge in the figure indicates
a vertex floodlight of aperture $\alpha$.

The function floor will be used in some of the theorems mentioned
later in this module.  Let $n$ be a real number.  Then the {\em floor
of $n$}, denoted $\lfloor n\rfloor$, is the integer $k$ such that $k
\leq n < k + 1$.  An alternate way to express this is that $\lfloor
n\rfloor$ is the greatest integer $k$ such that $k \leq n$.

Examples: $\lfloor 5\rfloor = 5$, $\lfloor 5.3\rfloor = 5$, $\lfloor
-5.3\rfloor = -6$.

\medskip

{\flushleft \bf Problems}
\begin{enumerate}
\item[2.1] Simplify the following expressions.

a.  $\lfloor 8/3\rfloor$

b.  $\lfloor 17/8\rfloor$

\item[2.2] Describe $\lfloor n/3\rfloor$ where $n$ is an integer that
is a multiple of $3$.

\item[2.3] Can you guess the definition of the ceiling of an integer
$n$?  The ceiling is denoted $\lceil n\rceil$.
\end{enumerate}

\section{The Floodlight Problem for Polygons}

\subsection{Convex Polygons}
 Many rooms take the form of convex polygons.  Since convex polygons
have no reflex vertices and no holes, they have no internal barriers.
This property makes them relatively easy to illuminate.  In fact,
given a single light with large enough aperture it is possible to
illuminate any convex polygon.

\begin{thm}
Any convex polygon can be illuminated by a single $\pi$-light.
\end{thm}
{\it Proof:\ } Let $P$ be a convex polygon, and let $v$ be any vertex
of the polygon.  Rotate the floodlight so that both edges of the
polygon containing $v$ fall within the wedge of light.  Let $x$ be any
point in $P$.  By the definition of a convex polygon, the entire line
segment from $v$ to $x$ must lie in $P$ and therefore be illuminated
by the floodlight.  $\diamondsuit$

\medskip

{\bf \flushleft Exploratory Exercises} 
\begin{enumerate}
\item[3.1] Is a $\pi$-light necessary to illuminate the polygon $P$ in
Figure 3.1?  If not, what aperture is necessary for a floodlight
placed on a vertex of $P$ to illuminate the entire polygon?  Use a
protractor to measure the angle at each vertex.  Explain your answer.
\begin{center}
\resizebox*{!}{0.8in}{\includegraphics{fig31.eps}}
\vspace{.3cm}

Figure 3.1
\end{center}

\item[3.2] Given an arbitrary convex polygon with vertices of angles
$\alpha_1$, $\alpha_2$, $\dots$, $\alpha_n$, what is the minimum angle
$\beta$ such that a single light of aperture $\beta$ placed at a
vertex of your choice is sufficient to illuminate the entire polygon?
Explain your answer.
	
\item[3.3] Sketch a convex polygon that cannot be illuminated by a
single $\pi/2$-light.  Explain your answer.
	
\item[3.4] Calculate the number of vertex $\pi/2$-lights needed to
illuminate the following figures.

a.  regular quadrilateral

b.  regular hexagon (6 sides)

c.  regular decagon (10 sides)
\end{enumerate}

If we use more lights, it is possible for each floodlight to have a
smaller aperture than would be possible for a single light to
illuminate the entire polygon alone.  This is illustrated in the
following theorem.

\begin{thm}
Any convex polygon $P$ can be illuminated by a pair of vertex
$\pi/2$-lights.
\end{thm}
{\it Proof:\ } If any vertex $v$ of $P$ has angle at most $\pi/2$,
then by Exploratory Exercise 3.2, one $\pi/2$-light with its apex at
$v$ is sufficient to illuminate the entire polygon.  The second
floodlight can be placed at any vertex of your choice with the
exception of $v$.

Now we assume that every vertex of the polygon $P$ has angle greater
than $\pi/2$.
Consider any edge $AB$ of the polygon $P$.  Rotate $P$ so that the
edge $AB$ is horizontal and so that this edge is the bottom edge of
the polygon.  Draw $x$- and $y$-axes so that the edge $AB$ lies on the
$x$-axis.  We will assume that $A = (a, 0)$, $B = (b, 0)$ and $a < b$.
Place one of the floodlights at the vertex $A$ and the other at the
vertex $B$ so that one side of the wedge illuminated by each light is
flush against $AB$ as shown in Figure 3.2.  Note that any point
in $P$ not illuminated by the floodlight at $A$ has $x$-coordinate
less than $a$ and any point in $P$ not illuminated by the floodlight
at $B$ has $x$-coordinate greater than $b$.
\begin{center}
\resizebox*{!}{1.6in}{\includegraphics{fig32.eps}}
\vspace{.3cm}

Figure 3.2
\end{center}

Let $X = (x, y)$ be any point in the polygon $P$ not illuminated by
the floodlight whose apex lies at the vertex $A$.  Then $x < a$, and
thus, since $x < a$ and $a < b$, we have that $x < b$.  Therefore the
point $X$ is illuminated by the floodlight whose apex lies at the
vertex $B$.  By an analogous argument, any point in $P$ not
illuminated by the floodlight whose apex lies at $B$ is illuminated by
the floodlight whose apex lies at $A$.  Thus we see that every point
of the convex polygon $P$ can be illuminated by a pair of vertex
$\pi/2$-lights.  $\diamondsuit$

\medskip
{\flushleft \bf Exploratory Exercises}
\begin{enumerate}
\item[3.5] Suppose that you are given a convex polygon $P$ and that
you must purchase a pair of floodlights that will light the region.
Both floodlights must have the same aperture.  Must the lights be
$\pi/2$-lights?  Explain your answer.

\item[3.6] Show that any convex polygon can be illuminated by any pair
of floodlights having apertures $\alpha_1$ and $\alpha_2$ such that
$\alpha_1 + \alpha_2 = \pi$.

\item[3.7] Let $P$ be the convex polygon with vertices:
\[
v_0 = (0,-2) , v_1 = (4,-1) , v_2 = (5,0) , v_3 = (4,1)\mbox{ and }v_4
= (0,2).
\]

Make an accurate sketch of the polygon $P$, and label its vertices.
Cut off two corners of a new sheet of paper (no round-edged notebook
paper, please), and pin the vertices of the right angles of the
cut-off corners to the vertices $v_1$ and $v_3$.  These bits of paper
will represent the wedges of light cast by two $\pi/2$-floodlights.

a.  Rotate the ``floodlight'' at the vertex $v_1$ so that one side is
flush against the edge $v_1v_2$.  Can you rotate the ``floodlight'' at
the vertex $v_3$ in such a way that the entire polygon $P$ is covered?
Explain your answer.

b.  Rotate the ``floodlight'' at the vertex $v_1$ so that one side is
flush against the edge $v_1 v_0$.  Can you rotate the ``floodlight''
at the vertex $v_3$ in such a way that the entire polygon $P$ is
covered?  Explain your answer.

c.  Explain why it is impossible to illuminate the polygon $P$ with a
pair of $\pi/2$-lights at vertices $v_1$ and $v_3$.

\item[3.8] Can a convex polygon have many pairs of vertices for which
$\pi/2$-lights fail to illuminate the polygon?  Explain.
\end{enumerate}

Note that while Theorem 3.2 holds for convex polygons, it does not
hold for general polygons such as the nonconvex polygon in Figure 2.2.
We have considered only the case where we have a pair of floodlights
with the sum of their apertures equal to $\pi$.  Although it takes
quite a bit more work, we can generalize this idea to that of using
three floodlights whose apertures sum to $\pi$ to illuminate any
convex polygon.

\begin{thm} (Urrutia [U])
Let $\alpha_1 + \alpha_2 + \alpha_3 = \pi$ and consider any convex
polygon $P$.  Three floodlights of apertures $\alpha_1$, $\alpha_2$,
and $\alpha_3$ can be placed on the vertices of $P$ in such a way that
the entire polygon is illuminated.
\end{thm}

It is tempting to try to generalize the previous two theorems, but in
the end it turns out to be a fruitless endeavor, as shown by O'Rourke,
Shermer and Streinu in [OSS] in the following theorem.

\begin{thm}
There is an integer $n$ and a convex polygon $P$ of $n$ sides that
cannot be illuminated by $n$ $\pi/n$-lights placed one at each vertex.
\end{thm}

The proof of this theorem uses a polygon with a very large number of
vertices, and it is not known what is the smallest integer $k$ for
which there is a convex polygon that cannot be illuminated by $k$
floodlights each having aperture $\pi/k$.

\medskip
{\flushleft \bf Open Question}

We now can state an open question, a question that no one has been able
to answer: It is not even known if four
$\pi/4$-lights suffice to illuminate all convex polygons of four
vertices.

\medskip
{\flushleft \bf Problems}
\begin{enumerate}
\item[3.1] Is there some angle $\alpha < \pi$ such that every convex
polygon can be illuminated by a single floodlight having aperture
$\alpha$?  Explain your answer.

\item[3.2] In this section, we have assumed that floodlights must be
placed on vertices of the polygon.  Suppose that we still wish to use
only floodlights of aperture $\alpha$ to illuminate a polygon, but
that we allow the floodlights to be placed anywhere within the polygon
or on the boundary of the polygon.  Are we likely to need more lights,
fewer lights, or the same number of lights?  Explain your answer.
Discuss what your answer means using the mathematical terms necessary
or sufficient.
\end{enumerate}

\subsection{Orthogonal Polygons}
In this section we will discuss an important subclass of polygons
called {\it orthogonal polygons}.  Recall from the definition
(Section 2) that an orthogonal polygon is a polygon with adjoining
sides that are perpendicular.  These types of polygons are sometimes
referred to as {\it isothetic} and {\it rectilinear} polygons in the
mathematical literature.  Orthogonal polygons arise in many
applications because of the ease in which they are created and
manipulated.  The first polygon shown in this module, Median Bank's
main room in Figure 1.1, is an orthogonal polygon.

Again the problem is posed to find the minimum number of lights of a
certain aperture that will illuminate a polygon of a given type.  The
idea of illuminating orthogonal polygons with vertex floodlights was
first discussed in 1994 by Estivill-Castro and Urrutia in a paper
called ``Optimal Floodlight Illumination of Orthogonal Art Galleries"
[EU].  In that paper the following theorem appears:

\begin{thm}
Every orthogonal polygon of $n$ vertices can be illuminated with
$\lfloor 3(n-1)/8\rfloor$ vertex lights of aperture $\pi/2$.
\end{thm}

For example, any polygon of $20$ vertices can be illuminated by $7$
vertex lights of aperture $\pi/2$ since we have that:
\[
\lfloor 3(20-1)/8\rfloor = \lfloor 3(19)/8 \rfloor = \lfloor
57/8\rfloor = \lfloor7 + 1/8\rfloor = 7.
\]

Notice that Theorem 3.5 does not say that we will always need $\lfloor
3(n-1)/8\rfloor$ $\pi/2$-lights to illuminate an orthogonal polygon
with $n$ vertices.  It simply says that $\lfloor 3(n-1)/8\rfloor$ such
lights will always be enough to do the job.  There are many orthogonal
polygons with $n$ vertices that do not require $\lfloor 3(n-1)/8\rfloor$
of these lights.  Theorem 3.6 below states that $\lfloor
3(n-1)/8\rfloor$ lights are necessary for some particular orthogonal
polygons with $n$ vertices.

\medskip
{\flushleft \bf Exploratory Exercises}
\begin{enumerate}
\item[3.8] Draw several orthogonal polygons with

a. 	4 sides,

b. 	6 sides,

c. 	10 sides.

\item[3.9] Use the theorem to calculate the number of vertex
$\pi/2$-lights sufficient to illuminate the polygons that you have
drawn with:

a. 	4 sides, 		

b. 	6 sides,		

c. 	10 sides.		

\item[3.10] Look at the polygons you have drawn for Exercise 3.8.  How
few vertex $\pi/2$-lights would actually illuminate the polygons?  For
each polygon, find the minimum number of such lights needed, and
compare this number with the numbers you found in Exercise 3.9 above.
Explain your results.
\end{enumerate}

We will see in the following example, which was originally produced by
Abello, Estivill-Castro, Shermer and Urrutia in [ACSU], that in some
cases $\lfloor 3(n-1)/8\rfloor$ vertex lights of aperture $\pi/2$ are
actually needed.
 
\begin{thm}
$\lfloor 3(n-1)/8\rfloor$ vertex lights of aperture $\pi/2$ are
sometimes necessary to illuminate an orthogonal polygon with $n$
vertices.
\end{thm}
{\it Proof:\ } Consider the polygons in Figure 3.3.  These are
orthogonal polygons that require one $\pi/2$-vertex light for each
prong.  This sequence of examples shows that the bound is tight,
i.e., sometimes necessary. $\diamondsuit$
\begin{center}
\includegraphics{fig33.eps}

\nopagebreak

Figure 3.3
\end{center}

The polygons of Figure 3.3 show that there are orthogonal polygons
that do require the bound.  However, not all orthogonal polygons
require $\lfloor 3(n-1)/8\rfloor$ lights to illuminate them.  Let us
return to the problem that motivated our discussion, the Median Bank's
main room that needs security cameras (Figure 1.1).  Let us also
suppose that the cameras have a viewing angle of $\pi/2$.  If you
check the specifications of some security cameras you will see that
this is a reasonable assumption.

\medskip
{\flushleft \bf Exploratory Exercises}
\begin{enumerate}
\item[3.11] According to Theorem 3.6, how many security cameras with
viewing angle of $\pi/2$ suffice to ensure that all parts of the room in
Figure 1.1 may be seen?

\item[3.12] Examine Figure 1.1 of the bank's main room, to determine
the least number of cameras necessary.  Explain your answer.
\end{enumerate}

\medskip
{\flushleft \bf Problems}
\begin{enumerate}
\item[3.3] Try to illuminate the polygon in Figure 3.4 with
$\pi/4$-floodlights positioned at each vertex.  Can this be done?
Explain.

\begin{center}
\resizebox*{!}{0.8in}{\includegraphics{fig34.eps}}

Figure 3.4
\end{center}

\item[3.4] Try increasing the floodlight aperture to $\pi/3$.  Can you
now illuminate the entire polygon?

\item[3.5] Make a conjecture about how large the floodlights'
apertures must be to illuminate the entire polygon.  Explain your
conjecture.
\end{enumerate}

\subsection{Arbitrary Polygons and Vertex $\pi$-Lights}
Now we turn to some illumination problems that involve floodlights
with aperture of $\pi$ radians.  In these problems, we require that the
floodlights be placed at vertices in a polygonal room and that at most
one floodlight be placed at each vertex.  We consider arbitrary
polygons, which are polygons with no extra conditions imposed, and we
ask two questions:

1.  How many vertex $\pi$-lights are sufficient to illuminate every
polygon? (*)

2.  Are there polygons that require this many vertex $\pi$-lights?
    (**)

Some examples show that such a floodlight placed at a reflex vertex
may be rotated to various positions to illuminate different regions,
but the light will be in a fixed position for any particular solution.
In each of the two polygons in Figure 3.5 a vertex $\pi$-light is
located at the middle vertex $v$ on the left side of the polygon, and
the region illuminated by that light is darkened.  In the left
polygon, the light is pointed downward; in the right polygon, the
light is pointed to the right.

\begin{center}
\resizebox*{!}{0.9in}{\includegraphics{fig35.eps}}
\vspace{.3cm}

Figure 3.5
\end{center}

These examples show that, in any solution to a vertex $\pi$-light
problem, the direction of each floodlight at a reflex vertex as well
as its vertex must be specified.

\medskip {\flushleft \bf Exploratory Exercise}
\begin{enumerate}
\item[3.14] In each polygon below, place as few vertex $\pi$-lights as
possible so that the entire polygon is illuminated.  Indicate the
region illuminated by each light.  Count the number of vertices of the
polygon and the number of lights used.

\begin{center}
\resizebox*{!}{0.8in}{\includegraphics{fig36-1.eps}}\hspace{1in}
\resizebox*{!}{1.2in}{\includegraphics{fig36-2.eps}}
\vspace{.3cm}

Figure 3.6
\end{center}
\end{enumerate}

We will use Gary Meisters's Two Ears Theorem [M] in the proof of 
the theorem that answers the first question (*) listed above: How many
vertex $\pi$-lights are sufficient to illuminate every polygon?  A
proof of the Two Ears Theorem appears in [O94] on page 15.  We will give a
different proof in Section 4.

Suppose that vertices $a$, $b$, and $c$ of a polygon are consecutive.
Then the {\em polygon has an ear at vertex $b$} whenever the line
segment $ac$ lies within the polygon.  If the interiors of the
triangles formed by two ears are disjoint, we say that the ears are
{\em nonoverlapping}.  A polygon with two shaded nonoverlapping ears
and a polygon with two striped overlapping ears are shown in Figure 3.7.  
The overlap has the stripes of both ears.
\begin{center}
\includegraphics{fig37.eps}

Figure 3.7
\end{center}

In fact, according to Meisters Two Ears Theorem, any polygon other
than a triangle has at least two nonoverlapping ears.  Recall that
this theorem is proved in Section 4.

\begin{thm}{\bf (Meisters Two Ears Theorem)}
Every polygon with more than three vertices has at least two
nonoverlapping ears.
\end{thm}

\medskip {\flushleft \bf Exploratory Exercises}
\begin{enumerate}
\item[3.15] Shade at least two nonoverlapping ears on each of the polygons
below.

\begin{center}
\includegraphics{fig38.eps}

Figure 3.8
\end{center}

\item[3.16] Sketch a polygon with five nonoverlapping ears.
\end{enumerate}

The next theorem gives us an upper bound on the number of vertex
$\pi$-lights required to cover a polygon.  This is the answer to the
first question (*) posed at the beginning of this section.
 
\begin{thm}
Every polygon $P$ of $n$ vertices can be illuminated by $n - 2$ vertex
$\pi$-lights.
\end{thm}
{\it Proof:\ } The proof is by mathematical induction on $n$.  Let $n
= 3$ so that $P$ is a triangle.  Then $P$ can be illuminated by a
single vertex $\pi$-light placed at any vertex.

Now let $k$ be an integer greater than $2$, and assume that any
polygon with $k$ vertices can be illuminated by $k-2$ vertex
$\pi$-lights.  Let $P$ be a polygon with $k+1$ vertices.  Then $P$ has
an ear by Meisters Two Ears Theorem.  Let $x$, $y$, and $z$ be the
three consecutive vertices of the ear.  Construct a polygon $P'$ from
$P$ by removing vertex $y$, removing the two edges meeting $y$, and
adding the edge $xz$.  Then $P'$ is a polygon with $k$ vertices, and
thus by the induction hypothesis, $P'$ can be illuminated by $k-2$
vertex $\pi$-lights.  Add a vertex $\pi$-light at vertex $y$ in $P$ to
illuminate the removed ear.  Then this light along with the $k-2$
lights for $P'$ illuminate all of $P$.  Thus $P$ can be illuminated by
$k-1 = (k+1) -2$ vertex $\pi$-lights.  This completes the proof of the
theorem.  $\diamondsuit$
			
\medskip {\flushleft \bf Open Question} The second question (**) is an open question: For
every integer $n > 2$, are there polygons of $n$ vertices that require
$n - 2$ vertex $\pi$-lights?

F. Santos, a Spanish mathematician at the University of Cantabria,
discovered the polygons in Figure 3.9.  These polygons are examples in
a family of polygons with $5j + 1$ vertices that require $3j$ vertex
$\pi$-lights [U, Figure 21]
\begin{center}
\includegraphics{fig39.eps}

Figure 3.9
\end{center}

\medskip {\flushleft \bf Exploratory Exercises}
\begin{enumerate}
\item[3.17] Count the vertices in each of the two polygons in Figure
  3.9.  Locate the $3j$ required floodlights, and indicate the region
  illuminated by each floodlight.

\item[3.18] Sketch at least one other member of this family of
polygons.  Locate the $3j$ required floodlights, and indicate the
region illuminated by each floodlight.
\end{enumerate}
You may be interested to know why vertex $\pi$-lights are considered
rather than floodlights with smaller aperture: there are certain
polygons that cannot be illuminated by vertex floodlights with smaller
aperture even if a floodlight is placed at every vertex [EOUX].  For
example, the polygon in Figure 3.10 cannot be illuminated by vertex
$\pi/2$-lights placed at every vertex.

\medskip {\flushleft \bf Exploratory Exercise}
\begin{enumerate}
\item[3.19] Show that the polygon in Figure 3.10 cannot be illuminated
by vertex $\pi/2$-lights placed at every vertex.

\begin{center}
\resizebox*{!}{1.1in}{\includegraphics{fig310.eps}}
\vspace{.2cm}

Figure 3.10
\end{center}

\end{enumerate}

\section{Triangulation and Meisters Two Ears Theorem}
Triangulation, subdividing a polygon into triangles whose vertices are
the vertices of the polygon, is a basic method used to study polygons
inductively.  In many cases, one triangle, such as an ear, can be
deleted from a polygon, or a polygon may be subdivided into
triangulated subpolygons, so that the inductive hypothesis can be
applied.  For example, deletion of an ear, whose existence is
guaranteed by Meisters Two Ears Theorem, results in a polygon to which
the inductive hypothesis can be applied.  We used The Two Ears Theorem
this way in the proof of Theorem 3.8.

Several lemmas are used in the proof that every polygon can be
triangulated. [O94, pages 11 – 13]

\medskip {\flushleft \bf Exploratory Exercises}
\begin{enumerate}
\item[4.1] Give names to the vertices of each of the three polygons in
Figure 4.2 as follows.  Find the lowest vertices on the page
(or the lowest vertex
if there is only one such vertex), and write an $a$ beside the rightmost
of these vertices.  Then, as you go around the boundary of the polygon
in a counterclockwise direction, label the next vertex $b$, the vertex
after that $c$, and so on until all the vertices of the polygons have
been labeled.  An example is shown in Figure 4.1.
\begin{center}
\includegraphics{fig41.eps}

\nopagebreak

Figure 4.1
\end{center}
\begin{center}
\includegraphics{fig42.eps}

Figure 4.2
\end{center}

\item[4.2] In each of the three polygons of Figure 4.2, find any
convex vertices that are not collinear with their two adjacent
vertices.  (Recall that a vertex is convex if its interior angle is
less than or equal to $\pi$ radians.)  Is the vertex $a$ convex in each
polygon?  Is it possible for the interior angle at vertex $a$ to be
exactly $\pi$ radians?  Explain.
	
\item[4.3] Sketch at least three other polygons.  Is the vertex $a$
strictly convex in each polygon?
\end{enumerate}

\begin{lemma}
Every polygon $P$ has a strictly convex vertex , i.e., a vertex with
interior angle of less than $\pi$ radians.
\end{lemma}
{\it Proof:\ } Let $a$ be the rightmost vertex of those vertices of
the polygon $P$ that are lowest.  In a counterclockwise traversal of
the vertices of $P$, the next vertex $b$ adjacent to $a$ lies above
vertex $a$, and the other vertex adjacent to $a$ either lies above or
at the same level as $a$.  Therefore vertex $a$ is a strictly convex
vertex of the polygon $P$.  $\diamondsuit$

\medskip
The next exercises illustrate the method that is used to show that
every polygon other than a triangle has a \emph{diagonal},
a line segment that joins two vertices and that lies in the
polygon's interior except for its endpoints.

\medskip {\flushleft \bf Exploratory Exercises}
\begin{enumerate}
\item[4.4] In each polygon of Figure 4.3, a strictly convex vertex $v$
is indicated.  Find the vertices adjacent to $v$, and label them $a$
and $b$.  Sketch the line segment $ab$.
\begin{center}
\includegraphics{fig43.eps}

Figure 4.3
\end{center}

\item[4.5] In which polygons of Figure 4.3 is the line segment $ab$ a
diagonal of the polygon?
\end{enumerate}

{\flushleft Answer questions 4.6-4.8 for each polygon of Figure 4.3
where the line segment $ab$
is {\em not} a diagonal.  An example is given in Figure 4.4.}

\begin{enumerate}
\item[4.6] Does the interior of the triangle $avb$ contain any other
vertices of the polygon?  Explain your answer.

\item[4.7] Sketch a line through the vertex $v$ that is parallel to
the line segment $ab$.  Think of moving this line away from $v$
towards the line segment $ab$ without changing its slope, i.e., move
the line parallel to itself.  Stop moving the line when you first
encounter a vertex (or possibly several vertices) within triangle
$avb$.  Label this vertex (or one of the vertices met) with an $x$.
Now sketch a line $L$ parallel to the line segment $ab$ and through
vertex $x$.  Is it possible that the line $L$ contains the line
segment $ab$?  If so, give an example.

\item[4.8] Shade the half plane that has boundary the line $L$ and
that contains the vertex $v$. Further darken  the region $R$ of the
plane that is the intersection of this half plane with the interior of
triangle $avb$.  Does the region $R$ contain any points of the
boundary of the polygon $P$?  Is the line segment $vx$ a diagonal of
the polygon $P$?  Why?
\begin{center}
\includegraphics{fig44.eps}

Figure 4.4
\end{center}

\item[4.9] Sketch four other polygons, each with a strictly convex
vertex $v$ and line segment $ab$ that is not a diagonal.  Answer
questions 4.6-4.8 for these polygons.
\end{enumerate}

These examples illustrate a method for finding a diagonal in any
polygon of at least four vertices.  Lemma 4.2
 assures us that every
polygon has a strictly convex vertex, and the next lemma uses the
method illustrated to find a diagonal with the strictly convex vertex
as one of its endpoints.

\begin{lemma}
Every polygon $P$ with at least four vertices has a diagonal.
\end{lemma}
{\it Proof:\ } Suppose that $P$ is a polygon of $n$ vertices, where $n
> 3$.  Then, by Lemma 4.1, the polygon $P$ has a strictly convex
vertex $v$.  Let $a$ and $b$ be the vertices adjacent to $v$.  If the
line segment $ab$ is a diagonal, we are finished.

Now suppose that the line segment $ab$ is not a diagonal. Then the
closed triangle $avb$ contains at least one vertex of the polygon $P$
other than the three vertices $v$, $a$, and $b$.  
We move the line through vertex $v$ and parallel to $ab$ until
a vertex $x$ in the polygon $p$ is encountered, as described in
Exercise 3.7.

Let $L$ be the line through the vertex $x$ parallel to $ab$.  Let $R$
be the region of the plane that is the intersection of the interior of
triangle $avb$ with the half plane containing $v$ and bounded by $L$.
The region $R$ does not contain any points of the boundary of the
polygon $P$.  Then $vx$ intersects the boundary of $P$ only at $v$ and
$x$, and thus $vx$ is a diagonal.  $\diamondsuit$

\medskip {\flushleft \bf Exploratory Exercises}
\begin{enumerate}
\item[4.10] In each polygon below, sketch a line segment between two
vertices such that this line segment lies entirely within the interior
of the polygon except for the two vertices.  Then sketch another such
line segment that does not cross the first line segment, except
possibly at a vertex.  Continue drawing these noncrossing line
segments between vertices until the polygon is subdivided into
triangles.  (You have drawn {\em diagonals} to {\em triangulate} each
polygon.)  Count the number of vertices of each polygon and, for each
triangulation, the number of diagonals used and the number of
triangles.
\begin{center}
\includegraphics{fig42.eps}

Figure 4.5
\end{center}

\item[4.11] Sketch and triangulate at least four other polygons.  Make
several copies of each of the polygons and find different
triangulations for each copy.  Count the number of vertices of each
polygon and, for each triangulation, the number of diagonals used and
the number of triangles.  What relationships do you observe among
these three numbers?
\end{enumerate}

\begin{lemma}{\bf (Existence of Triangulations)}
Every polygon $P$ can be triangulated by adding zero or more
diagonals.
\end{lemma}
{\it Proof:\ } Suppose that $P$ is a polygon of $n$ vertices.  The
proof is by induction on $n > 2$.  If $n = 3$, then $P$ is a triangle,
and thus $P$ is already triangulated.

Now let $k$ be an integer $\geq 3$.  Assume that any polygon with $k$ or
fewer vertices is either a triangle or can be subdivided into
triangles by adding diagonals.  Let $P$ be a polygon with $k + 1$
vertices.  By Lemma 2, $P$ has a diagonal $ab$.  This diagonal
partitions $P$ into two subpolygons that share the edge $ab$.  Each of
these subpolygons can be triangulated by the induction hypothesis, and
thus $P$ can be triangulated.  $\diamondsuit$

As you have seen with your own sketches, there may be several
different ways to triangulate a polygon.  However, as you have
observed, every triangulation of a given polygon involves the same
number of diagonals and the same number of triangles.  The following
lemma states the relationship between each of these numbers and the
number of vertices of a polygon.

\begin{lemma}
Every triangulation of a polygon $P$ of $n$ vertices requires $n - 3$
diagonals and results in $n - 2$ triangles.
\end{lemma}
{\it Proof:\ } Suppose that the polygon $P$ has $n$ vertices.  As in the
preceding lemma, the proof is by induction on $n > 2$.

If $n = 3$, then the polygon is a triangle.  The trivial triangulation
requires zero diagonals and results in one triangle.  Thus the lemma
is true in the case where $n = 3$.

Now let $k$ be an integer $\geq 3$, and assume that any polygon of $k$
or fewer vertices satisfies the lemma.  Let $P$ be a triangulated polygon of $k
+ 1$ vertices.  A diagonal used in the triangulation partitions the
polygon $P$ into two triangulated subpolygons, each with $k$ or fewer
vertices.  Suppose that these subpolygons have $r$ and $s$ vertices,
respectively.  Then since the subpolygons share two vertices,
\[
 r + s  = (k + 1) + 2 = k + 3.  
\]
By the induction hypothesis, one subpolygon's triangulation requires
$r - 3$ diagonals and results in $r - 2$ triangles, and the other
subpolygon's triangulation requires $s - 3$ diagonals and results in
$s - 2$ triangles.  Thus, since the two polygons use one of $P$'s
diagonals as their common edge, the number of diagonals in $P$'s
triangulation is:
\[
(r - 3)  + (s - 3) + 1 = (r + s) - 5 = (k  + 3) - 5 = (k + 1) - 3.
\]
Furthermore, the number of polygons in $P$'s triangulation is:
\[
(r - 2) + (s - 2) = (r + s) - 4 = (k + 3) - 4 = (k + 1) - 2.
\]
Therefore, the polygon $P$ of $k + 1$ vertices satisfies the
requirements of the lemma.  $\diamondsuit$

\medskip {\flushleft \bf Exploratory Exercises}
\begin{enumerate}
\item[4.12] Answer the following questions for the triangulated
polygon $P$ of Figure 4.6.

a.  Count the number $t_0$ of triangles that share no edges with $P$.

b.  Count the number $t_1$ of triangles that share exactly one edge
with $P$.

c.  Count the number $t_2$ of triangles that share exactly two edges
with $P$.

d.  Count the number $n$ of vertices of the polygon $P$.

e.  Check that $t_0 + t_1 + t_2 = n-2$.  Explain why this equation
holds

f.  Does each triangle that shares exactly two edges with the polygon
$P$ determine an ear of this polygon?  Are any two of these ears
overlapping?  Does the polygon have other ears?
\begin{center}
\resizebox*{4in}{!}{\includegraphics{fig46.eps}}
\vspace{.3cm}

Figure 4.6
\end{center}
			
\item[4.13] Triangulate the polygons in Figures 4.6 and 4.7 in several
different ways.  Then answer the questions of the preceding exercise.
\begin{center}
\resizebox*{2in}{!}{\includegraphics{fig47-1.eps}}\hspace{0.8in}
\resizebox*{2in}{!}{\includegraphics{fig47-2.eps}}
\vspace{.3cm}

Figure 4.7
\end{center}
\end{enumerate}

Now we apply the previous lemmas to prove the Meisters Two Ears
Theorem, which we used earlier in Section 3.

\begin{thm}{\bf (Meisters Two Ears Theorem)}
Every polygon with more than three vertices has at least two
nonoverlapping ears.
\end{thm}
{\it Proof:\ } [M, pages 650-651] Let $P$ be a polygon of $n$ vertices
with $n > 3$.  Then there is a triangulation $T$ of $P$ using
diagonals by Lemma 4.3.  Let $t_0$ be the number of triangles in the
triangulation $T$ that share no edge with $P$, let $t_1$ be the number
of triangles of $T$ that share exactly one edge with $P$, and let
$t_2$ be the number of triangles of $T$ that share exactly two edges
with $P$.

A triangle that shares exactly two edges with the polygon $P$ is an
ear of $P$, and no two triangles in the triangulation overlap.  We
will show that there are at least two of these triangles in order to
show that there are at least two nonoverlapping ears.

Since by Lemma 4.4 the triangulation results in $n-2$ triangles, we
have the equation:
\[
t_0 + t_1 + t_2 = n-2.
\]
Also, since the polygon has $n$ edges, we count edges shared with the
triangles to find that:
\[
0 t_0 +1 t_1 +2 t_2 = n,\mbox{ and thus }t_1 +2 t_2 = n.
\]
Then $t_1 +2 t_2 = t_0 + t_1 + t_2 + 2$ so that
\[
t_2  = t_0 + 2 \geq 2.
\]
Therefore, the number of triangles that share exactly two sides with
the polygon is at least two, and thus the number of non-overlapping ears
is at least two.  $\diamondsuit$

In his paper [M], Meisters provides another proof of the theorem as well
as the proof above.  This second proof does not use triangulation of
the polygon. This allows the use of the Two Ears Theorem to inductively
prove the existence of a triangulation for a polygon by removing an
ear.

We have covered two very useful techniques in studying polygons:
triangulating a polygon and removing an ear from a polygon.  The
theorems assure us that we can apply these techniques to every polygon
other than a triangle, and usually triangles can be readily addressed.

\medskip {\flushleft \bf Problems}
\begin{enumerate}
\item[4.1] What is the smallest number of ears possible for a polygon
of 4 vertices?  What is the largest number of ears possible for a
polygon of 4 vertices?  Explain your answers and sketch examples.

\item[4.2] Answer the same questions for a polygon of 5 vertices.

\item[4.3] Answer the same questions for a polygon of $n$ vertices.
\end{enumerate}

\section{Other Illumination Problems}
In this section we present other questions that are in a league with
the problems previously discussed in that they ask for the most
efficient way of illuminating an object given certain constraints on
the sources of light.  In each case the object and the constraints
must be clearly defined and the term efficient must be made precise.

\subsection{Illuminating a stage}
We will consider a vertical section of a stage, in which the stage
appears as the segment $AB$ as shown in Figure 5.1.  Floodlights may
be located at points $P_1$, $P_2$, $\dots$, $P_n$ on one side of the
line segment $AB$ that represents the stage.  We indicate with $\alpha_1$,
$\alpha_2$, $\dots$, $\alpha_n$ the apertures of the wedges of light of the
available floodlights.  Each of the lights can be placed at any of the
points.  In particular, two lights may be placed at the same point.
Each wedge can be rotated around its apex. The stage illumination
problem asks to illuminate the stage (object) in such a way that the
sum of the apertures:
\[
\sum_{i=1}^n \alpha_{i}
\]
is a minimum.  The illumination with a minimum aperture sum is called
an {\em efficient} illumination. The {\em one-on-one} stage
illumination problem asks to find an efficient illumination with the
data given above, in such a way that exactly one light is placed at
each point.
\begin{center}
\resizebox*{3.5in}{!}{\includegraphics{fig51.eps}}
\vspace{.3cm}

Figure 5.1
\end{center}

\medskip {\flushleft \bf Exploratory Exercise}
\begin{enumerate}
\item[5.1] We wish to illuminate the stage $AB$ with lights placed
somewhere on the segment $RS$, where these line segments are both
horizontal and have the same length. Furthermore $RS$ lies directly
above $AB$.  The proportions are as indicated in the Figure 5.2 below.
\begin{center}
\includegraphics{fig52.eps}

Figure 5.2
\end{center}

a.  Assume that only one floodlight is allowed, and it must be placed
on the segment $RS$.  Where should the light be placed if we wish the
aperture to be as small as possible, and what is the minimum aperture?

b.  Assume that two floodlights placed on the segment $RS$ are
allowed.  Where should they be placed if we want the sum $\alpha_1 +
\alpha_2$ of their apertures to be a minimum?  What is this minimum
value?

c.  Show that a single floodlight placed on the segment $RS$ with an
aperture of $\pi/10$ radians cannot illuminate the given stage.

d.  Show that a single floodlight with aperture greater than 33
degrees can light $AB$ when placed at any position on the line segment
$RS$.
\end{enumerate}

The following Lemma gives a condition that guarantees the existence of
a solution to the stage illumination problem when many lights are
involved.

\begin{lemma}
Let $s$ be a line through the point $A$, and let $r$ be a line through
the point B such that the points $P_1, P_2, \dots, P_n$ lie above both
$s$ and $r$.  Let $\theta$ be the angle $AQB$, where $Q$ is the
intersection of the two lines. Assume that Q lies above the stage.
 If the apertures $\alpha_1, \alpha_2,
\dots,\alpha_n$ are such that:
\[
\sum_{i=1}^n\alpha_{i}\geq\theta,
\]
then lights with the given apertures can be placed at the given points
to light up the stage $AB$.
\end{lemma}

\begin{center}
\resizebox*{4.5in}{!}{\includegraphics{fig53_1.eps}}


Figure 5.3
\end{center}


This Lemma follows from the solution to the second problem in [SS].
While this Lemma
gives a sufficient condition for the existence of a solution to the
illumination problem, the value of $\theta$ will in general be larger
than the sum of the apertures in an efficient solution. In fact,
drawing the diagonals of the rectangle $ABSR$ in Figure 5.2 shows that
$\theta > \pi/3$ but we established in Exercise 5.1b 
that the minimum value of
$\alpha_1 + \alpha_2$ is less than $\pi/3$.

\medskip
{\flushleft \bf Open Question} There is an open question, a question that 
no one can answer yet: Is $\theta$ ever equal to the sum of the apertures in
an efficient solution?

\medskip {\flushleft \bf Exploratory Exercise}
\begin{enumerate}
\item[5.2] You are given the stage $AB$, and the points $P_1$, $P_2$,
and $P_3$ as in Figure 5.4.
\begin{center}
\resizebox*{3.5in}{!}{\includegraphics{fig54.eps}}

\nopagebreak
Figure 5.4
\end{center}

a.  Find approximately the smallest value of the angle $\theta$
mentioned in Lemma 5.1 for this particular configuration.  (Use ruler
and protractor.)

b.  Cut out wedges of apertures $\alpha_1 = 20^\circ$, $\alpha_2 =
15^\circ$ and $\alpha_3 = 10^\circ$.  By pinning the apexes of the
wedges to the points of your choice and rotating them, find a solution
to the one-on-one stage illumination problem for this set of data.
Express your solution with the accuracy afforded by your protractor.

c.  Verify that in this case $\sum_{i=1}^n\alpha_{i} < \theta$.  Does
this inequality contradict Lemma 5.1?  Explain your answer.

d.  Assume that exactly one light must be placed at each point.  How
many ways can you assign three apertures to three points?  How many
ways can you assign $n$ apertures to $n$ points?
\end{enumerate}

We see that a one-on-one stage illumination problem with $n$ points
and $n$ lights involves not only checking $n!$ cases, but also
identifying the $n$ angles that specify how each wedge of light is
positioned at each point.

\subsection{Orthogonal polygons with holes}
An orthogonal hole appears in the orthogonal polygon of Figure
5.5. This hole acts as a barrier; light rays cannot go through it.
From here on we will restrict light sources to $\pi/2$-lights placed
at the vertices of the polygon under consideration.  What is the
minimum number of these lights needed to illuminate the polygon in
Figure 5.5?
\begin{center}
\resizebox*{1.8in}{!}{\includegraphics{fig55.eps}}
\vspace{.2cm}

Figure 5.5
\end{center}

Two $\pi/2$-lights, one placed at vertex $A$ and the other at vertex
$B$, will suffice; one $\pi/2$-light will not.  So the minimum number
is two.  Are there any other locations from which two $\pi/2$-lights
suffice?  The polygon in the figure has $12$ vertices; the vertices of
the hole count.

Although in this case we can prove that a minimum of two vertex
$\pi/2$-lights is needed, there is no known general method or
algorithm to find the minimum number of vertex $\pi/2$-lights required
to illuminate a given polygon.  But it is possible to find an upper
bound for the number of vertex $\pi/2$-lights that will be
needed.

\medskip {\flushleft \bf Exploratory Exercise}
\begin{enumerate}
\item[5.3] The polygon of Figure 5.6 has $32$ vertices and one hole.
Each of the corners is similar to those of the polygons of Figure 3.3.
A total of $12$ $\pi/2$-lights is needed to illuminate the polygon.
Sketch a large version of this polygon, and show the placement and
region illuminated by each light.
\begin{center}
\resizebox*{2.5in}{!}{\includegraphics{fig56.eps}}
\vspace{.2cm}

Figure 5.6
\end{center}
\end{enumerate}

The illumination problem for orthogonal polygons with holes is to find
the minimum number of lights needed to illuminate any orthogonal
polygon with $n$ vertices and $h$ holes. This minimum number must be
sufficient for any such polygon and necessary for at least one of
these polygons.

The preceding examples illustrate the following theorem, which solves
the stated illumination problem for orthogonal polygons.

\begin{thm}
For any orthogonal polygon with $n$ vertices and $h$ holes,
\[
\left\lfloor\frac{3n+4(h-1)}{8}\right\rfloor
\]
$\pi/2$-floodlights placed at vertices are always sufficient and
sometimes necessary to illuminate the polygon.
\end{thm}

The proof of this theorem can be found in [ACSU ].  We will apply the
theorem to each of the two preceding examples.  In the case of Figure
5.5,
\[
\left\lfloor\frac{3n+4(h-1)}{8}\right\rfloor=
\left\lfloor\frac{3(12)+0}{8}\right\rfloor=4.
\]
According to the theorem four lights will suffice, but we know we can
do better.

\medskip {\flushleft \bf Exploratory Exercise}
\begin{enumerate}
\item[5.4] Can you find an orthogonal polygon with 12 sides and one
hole that requires four $\pi/2$-lights?
\end{enumerate}

In the case of Figure 5.6,
\[
\left\lfloor\frac{3n+4(h-1)}{8}\right\rfloor=
\left\lfloor\frac{3(32)+0}{8}\right\rfloor=12.
\]
This shows that the given number of lights is sometimes necessary.

\medskip {\flushleft \bf Problems}
\begin{enumerate}
\item[5.1] Sketch at least 3 orthogonal polygons with holes.  Count
the number of vertices and number of holes in each of these orthogonal
polygons, and then compute the upper bound $M$ on the number of vertex
$\pi/2$-lights in each case according to Theorem 5.1.  Show how each
polygon can be illuminated by at most $M$ vertex $\pi/2$-lights.

\item[5.2] Find the minimum number of vertex $\pi/2$-lights required
to illuminate the polygon in Figure 5.7.  Show the placement of the
lights.  Do your results contradict Theorem 5.1?  Explain.
\begin{center}
\resizebox*{2in}{!}{\includegraphics{fig57.eps}}
\vspace{.2cm}

Figure 5.7
\end{center}
\end{enumerate}

We have answered the exercise questions by observing polygons.
Theorem 5.1 gives information about the number of vertex floodlights
needed but not about the {\em location of the vertices}.  There is in
[ACSU] an algorithm to find the location of a number of vertex
floodlights for a given polygon that satisfies the bounds of Theorem
5.1.  This algorithm applies four rules.  Each rule produces a set of
vertex floodlights. The set with the minimum number of floodlights is
the one chosen by the algorithm as a solution to the illumination
problem.  But there is no claim in the paper that this algorithm
produces the minimum number of vertex floodlights for a given polygon.

\begin{thebibliography}{EOUX}
\addcontentsline{toc}{section}{\numberline{}References\dotfill}

\bibitem[ACSU]{ACSU} J. Abello, V. Estivil-Castro, T. Shermer, and
J. Urrutia. ``Illumination with Orthogonal Floodlights'', {\em
International Journal of Computational Geometry and Applications} 8,
pp. 25-38, 1998.

\bibitem[BGK]{BGK} P. Bose, L. Guibas, A. Lubiw, M. Overmars,
D. Souvaine, J. Urrutia.  ``The Floodlight Illumination Problem,"
International {\em Journal of Computational Geometry and Applications}
7, pp. 153-163, 1997.

\bibitem[C]{C} V. Chv\'{a}tal. ``A Combinatorial Theorem in Plane
Geometry," {\em Journal of Combinatorial Theory}, Ser B, 18, pp. 39-41
(1975).

\bibitem[CRCU]{CRCU} J. Czygowicz, E. Rivera-Campo, and
J.Urrutia. ``Optimal Floodlight Illumination of Stages," {\em Proc. 5th
Canadian Conference on Computational Geometry}, pp. 393-398, 1993.

\bibitem[EOUX]{EOUX} V. Estivill-Castro, J. O'Rourke, J. Urrutia,
D. Xu. ``Illumination of Polygons with Vertex Lights," {\em
Information Processing Letters}, 56, pp. 9-13, 1995.

\bibitem[ECU]{ECU} V. Estivill-Castro and J. Urrutia. ``Two-Floodlight
Illumination of Convex Polygons," {\em Proceedings of the Fourth
Workshop on Algorithms and Data Structures WADS-95 Kingston},
Ont. Canada. Springer Verlag Lecture Notes in Computer Science 955,
pp. 62-73, 1995.

 \bibitem[EU]{EU} V. Estivill-Castro, and J. Urrutia.  ``Optimal
Floodlight Illumination of Orthogonal Art Galleries," {\em Proc. 6th
Canadian Conference on Computational Geometry}, pp. 81-86, 1994.

\bibitem[M]{M} G. Meisters. ``Polygons Have Ears", {\em
Amer. Math. Monthly} 82, pp. 648-51, 1975.

\bibitem[O87]{O87} J. O'Rourke. {\em Art Gallery Theorems and
Algorithms}, Oxford University Press, New York, 1987.

\bibitem[O94]{O94} J. O'Rourke. {\em Computational Geometry in C},
Cambridge University Press, Cambridge, 1994.

\bibitem[O97]{O97} J. O'Rourke. ``Vertex $\pi$-lights for Monotone
Mountains", {\em Proc. 9th Canadian Conference on Computational
Geometry}, pp. 1-5, 1997.

\bibitem[OSS]{OSS} J. O'Rourke, Thomas Shermer, and Ileana
Streinu. ``Illuminating Convex Polygons with Vertex Floodlights," {\em
Proc. 7th Canadian Conference on Computational Geometry}, pp. 151-
156, 1995.

\bibitem[SS]{SS} W. Steiger, and I. Streinu. ``Illumination by Floodlights'',
\emph{Computational Geometry 10}, pp.57-70, 1998.

\bibitem[U]{U} J.  Urrutia. ``Art Gallery and Illumination Problems'',
{\em Handbook of Computational Geometry}, North-Holland, pp. 973-1027,
2000.

\end{thebibliography}
\end{document}