DIMACS

Center for Discrete Mathematics & Theoretical Computer Science

DIMACS EDUCATIONAL MODULE SERIES

MODULE 03-3 Security Cameras and Floodlight Illumination

Date prepared: April 21, 2004

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

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

Lidia Luquet Department of Mathematics and Computer Science Saint Mary’s College of California Moraga, CA 94575-3517 email: lluquet@stmarys-ca.edu

Allison Wolf College of Computing Georgia Institute of Technology Atlanta, GA 30332-0280 email: awolf@cc.gatech.edu

DIMACS Center, CoRE Bldg., Rutgers University, 96 Frelinghuysen Road, Piscataway, NJ 08854-8018

TEL: 732-445-5928 • FAX: 732-445-5932 • EMAIL: center@dimacs.rutgers.edu

                         Web: http://dimacs.rutgers.edu/

Founded as a National Science Foundation Science and Technology Center and a Joint Project of Rutgers University, Princeton University, AT&T Labs - Research, Bell Labs, NEC Laboratories America and Telcordia Technologies with affiliated members Avaya Labs, HP Labs, IBM Research, Microsoft Research.

Module Description Information

• Title:

Security Cameras and Floodlight Illumination

• Author(s):

Marjorie Darrah

Nancy Hagelgans

Lidia Luquet

Allison Wolf

• 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.

• Target Audience:

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

• Prerequisites:

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

• 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.

• 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.

• 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.

• Contact Information:

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

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

Lidia Luquet Department of Mathematics and Computer Science Saint Mary’s College of California Moraga, CA 94575-3517 email: lluquet@stmarys-ca.edu

Allison Wolf College of Computing Georgia Institute of Technology Atlanta, GA 30332-0280 email: awolf@cc.gatech.edu

• Other DIMACS modules related to this module:

None at this time

TABLE OF CONTENTS

Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1 A surveillance camera problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Related problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Mathematical formulation of the camera problem . . . . . . . . . . . . . . . . . . . . 5 1.4 Mathematical formulation of other lighting problems . . . . . . . . . . . . . . . . . . 5

2 Mathematical Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3 The Floodlight Problem for Polygons . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.1 Convex Polygons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2 Orthogonal Polygons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.3 Arbitrary Polygons and Vertex π-Lights . . . . . . . . . . . . . . . . . . . . . . . . . 13

4 Triangulation and Meisters Two Ears Theorem . . . . . . . . . . . . . . . . . . . . . . 16

5 Other Illumination Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 5.1 Illuminating a stage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 5.2 Orthogonal polygons with holes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

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.

1 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.

1.1 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.

Figure 1.1

1.2 Related problems

There are several other problems related to the placement of security cameras. Figure 1.1 could be viewed as:

• a parking lot that should be lit with floodlights of a certain aperture to ensure the safety of the drivers and their cars,

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

• an art gallery that needs to be protected by guards standing in fixed positions.

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 ⌊n/3⌋, the greatest integer that is less than or equal to n/3, and in 1975 V. Chvá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.

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?

Figure 1.2

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?

Figure 1.3

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.

Figure 1.4

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

1.3 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:

How many corner cameras with a given viewing angle suffice to see all points of a given room?

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:

How many vertex cameras with a given aperture suffice to cover a polygon?

We will consider the problem as stated mathematically.

1.4 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.

Problems

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 α. 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?

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 α 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.

Figure 1.5

2 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 polygon is generally defined as an ordered sequence of at least three points v_{1}, v_{2}, …, v_{n} in the plane and the n line segments v_{1}v_{2}, v_{2}v_{3}, …, v_{n−1}v_{n}, and v_{n}v_{1}. The points are called vertices of the polygon, and the line segments are called edges of the polygon. The line segments taken together are also called the boundary of the polygon. A 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.

From this point on we use the term polygon to denote a simple polygon together with its interior.

Simple Polygon Non-simple Polygon Figure 2.1

Angles will be given in radian measure unless otherwise stated. Recall that:

π radians = 180 degrees.

A vertex of a polygon is reflex if its interior angle is strictly greater than π radians. A vertex is convex if its interior angle is less than or equal to π radians, and it is strictly convex if its interior angle is strictly less than π radians. A polygon is convex if, for each pair of points in the polygon, the line segment joining these points lies within the polygon. An orthogonal polygon is a polygon with adjoining sides that are perpendicular.

Figure 2.2

Exploratory Exercises 2.1 Identify any reflex vertices of each polygon in Figure 2.3 below

Figure 2.3

2.2 Sketch a convex polygon with 5 edges. 2.3 Sketch a polygon with 4 convex vertices and 2 reflex vertices. 2.4 Sketch an orthogonal polygon with 12 edges. 2.5 Sketch an orthogonal polygon with five sides or explain why none exists.

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

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.

Figure 2.4

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 α.

The function floor will be used in some of the theorems mentioned later in this module. Let n be a real number. Then the floor of n, denoted ⌊n⌋, is the integer k such that k ≤ n < k + 1. An alternate way to express this is that ⌊n⌋ is the greatest integer k such that k ≤ n.

Examples: ⌊5⌋ = 5, ⌊5.3⌋ = 5, ⌊−5.3⌋ = −6.

Problems

2.1 Simplify the following expressions.

a. ⌊8/3⌋
b. ⌊17/8⌋

2.2 Describe ⌊n/3⌋ where n is an integer that is a multiple of 3.

2.3 Can you guess the definition of the ceiling of an integer n? The ceiling is denoted ⌈n⌉.

3 The Floodlight Problem for Polygons

3.1 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.

Theorem 3.1 Any convex polygon can be illuminated by a single π-light.

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. ♢

Exploratory Exercises

3.1 Is a π-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.

Figure 3.1

3.2 Given an arbitrary convex polygon with vertices of angles α_{1}, α_{2}, …, α_{n}, what is the minimum angle β such that a single light of aperture β placed at a vertex of your choice is sufficient to illuminate the entire polygon? Explain your answer.

3.3 Sketch a convex polygon that cannot be illuminated by a single π/2-light. Explain your answer.

3.4 Calculate the number of vertex π/2-lights needed to illuminate the following figures.

a. regular quadrilateral

b. regular hexagon (6 sides)

c. regular decagon (10 sides)

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.

Theorem 3.2 Any convex polygon P can be illuminated by a pair of vertex π/2-lights.

Proof: If any vertex v of P has angle at most π/2, then by Exploratory Exercise 3.2, one π/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 π/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.

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 π/2-lights. ♢

Exploratory Exercises

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 π/2-lights? Explain your answer.

3.6 Show that any convex polygon can be illuminated by any pair of floodlights having apertures α_{1} and α_{2} such that α_{1} + α_{2} = π.

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) 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 π/2-floodlights.

a. Rotate the “floodlight” at the vertex v_{1} so that one side is flush against the edge v_{1}v_{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 π/2-lights at vertices v_{1} and v_{3}.

3.8 Can a convex polygon have many pairs of vertices for which π/2-lights fail to illuminate the polygon? Explain.

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 π. Although it takes quite a bit more work, we can generalize this idea to that of using three floodlights whose apertures sum to π to illuminate any convex polygon.

Theorem 3.3 (Urrutia [U]) Let α_{1} + α_{2} + α_{3} = π and consider any convex polygon P. Three floodlights of apertures α_{1}, α_{2}, and α_{3} can be placed on the vertices of P in such a way that the entire polygon is illuminated.

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.

Theorem 3.4 There is an integer n and a convex polygon P of n sides that cannot be illuminated by n π/n-lights placed one at each vertex.

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 π/k.

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 π/4-lights suffice to illuminate all convex polygons of four vertices.

Problems

3.1 Is there some angle α < π such that every convex polygon can be illuminated by a single floodlight having aperture α? Explain your answer.

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 α 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.

3.2 Orthogonal Polygons

In this section we will discuss an important subclass of polygons called 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 isothetic and 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:

Theorem 3.5 Every orthogonal polygon of n vertices can be illuminated with ⌊3(n − 1)/8⌋ vertex lights of aperture π/2.

For example, any polygon of 20 vertices can be illuminated by 7 vertex lights of aperture π/2 since we have that:

⌊3(20 − 1)/8⌋ = ⌊3(19)/8⌋ = ⌊57/8⌋ = ⌊7 + 1/8⌋ = 7.

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

Exploratory Exercises

3.8 Draw several orthogonal polygons with a. 4 sides, b. 6 sides, c. 10 sides.

3.9 Use the theorem to calculate the number of vertex π/2-lights sufficient to illuminate the polygons that you have drawn with: a. 4 sides, b. 6 sides, c. 10 sides.

3.10 Look at the polygons you have drawn for Exercise 3.8. How few vertex π/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.

We will see in the following example, which was originally produced by Abello, Estivill-Castro, Shermer and Urrutia in [ACSU], that in some cases ⌊3(n − 1)/8⌋ vertex lights of aperture π/2 are actually needed.

Theorem 3.6 ⌊3(n − 1)/8⌋ vertex lights of aperture π/2 are sometimes necessary to illuminate an orthogonal polygon with n vertices.

Proof: Consider the polygons in Figure 3.3. These are orthogonal polygons that require one π/2-vertex light for each prong. This sequence of examples shows that the bound is tight, i.e., sometimes necessary. ♢

Figure 3.3

�

The polygons of Figure 3.3 show that there are orthogonal polygons that do require the bound. However, not all orthogonal polygons require ⌊3(n − 1)/8⌋ 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 π/2. If you check the specifications of some security cameras you will see that this is a reasonable assumption.

Exploratory Exercises

3.11 According to Theorem 3.6, how many security cameras with viewing angle of π/2 suffice to ensure that all parts of the room in Figure 1.1 may be seen?

3.12 Examine Figure 1.1 of the bank’s main room, to determine the least number of cameras necessary. Explain your answer.

Problems

3.3 Try to illuminate the polygon in Figure 3.4 with π/4-floodlights positioned at each vertex. Can this be done? Explain.

Figure 3.4

3.4 Try increasing the floodlight aperture to π/3. Can you now illuminate the entire polygon?

3.5 Make a conjecture about how large the floodlights’ apertures must be to illuminate the entire polygon. Explain your conjecture.

3.3 Arbitrary Polygons and Vertex π-Lights

Now we turn to some illumination problems that involve floodlights with aperture of π 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 π-lights are sufficient to illuminate every polygon? (*)

2. Are there polygons that require this many vertex π-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 π-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.

Figure 3.5

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

Exploratory Exercise

3.14 In each polygon below, place as few vertex π-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.

Figure 3.6

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 π-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 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 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.

Figure 3.7

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.

Theorem 3.7 (Meisters Two Ears Theorem) Every polygon with more than three vertices has at least two nonoverlapping ears.

Exploratory Exercises

3.15 Shade at least two nonoverlapping ears on each of the polygons below.

3.16 Sketch a polygon with five nonoverlapping ears.

The next theorem gives us an upper bound on the number of vertex π-lights required to cover a polygon. This is the answer to the first question (*) posed at the beginning of this section.

Theorem 3.8 Every polygon P of n vertices can be illuminated by n − 2 vertex π-lights.

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 π-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 π-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 π-lights. Add a vertex π-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 π-lights. This completes the proof of the theorem. ♢

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 π-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 π-lights [U, Figure 21]

Figure 3.9

Exploratory Exercises

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.

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.

You may be interested to know why vertex π-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 π/2-lights placed at every vertex.

Exploratory Exercise

3.19 Show that the polygon in Figure 3.10 cannot be illuminated by vertex π/2-lights placed at every vertex.

Figure 3.10

4 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]

Exploratory Exercises

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.

Figure 4.1 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 π radians.) Is the vertex a convex in each polygon? Is it possible for the interior angle at vertex a to be exactly π radians? Explain.

4.3 Sketch at least three other polygons. Is the vertex a strictly convex in each polygon?

Lemma 4.1 Every polygon P has a strictly convex vertex , i.e., a vertex with interior angle of less than π radians.

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. ♢

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

Exploratory Exercises

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.

Figure 4.3

4.5 In which polygons of Figure 4.3 is the line segment ab a diagonal of the polygon?

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

4.6 Does the interior of the triangle avb contain any other vertices of the polygon? Explain your answer.

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.

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?

Figure 4.4

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.

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.

Lemma 4.2 Every polygon P with at least four vertices has a diagonal.

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. ♢

Exploratory Exercises

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 diagonals to 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.

Figure 4.5

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?

Lemma 4.3 (Existence of Triangulations) Every polygon P can be triangulated by adding zero or more diagonals.

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 ≥ 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. ♢

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.

Lemma 4.4 Every triangulation of a polygon P of n vertices requires n − 3 diagonals and results in n − 2 triangles.

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 ≥ 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. ♢

Exploratory Exercises

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?

Figure 4.6 4.13 Triangulate the polygons in Figures 4.6 and 4.7 in several different ways. Then answer the

questions of the preceding exercise.

Figure 4.7

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

Theorem 4.5 (Meisters Two Ears Theorem) Every polygon with more than three vertices has at least two nonoverlapping ears.

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:

0t_{0} + 1t_{1} + 2t_{2} = n, and thus t_{1} + 2t_{2} = n.

Then t_{1} + 2t_{2} = t_{0} + t_{1} + t_{2} + 2 so that

t_{2} = t_{0} + 2 ≥ 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. ♢

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.

Problems

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.

4.2 Answer the same questions for a polygon of 5 vertices.

4.3 Answer the same questions for a polygon of n vertices.

5 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.

5.1 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}, …, P_{n} on one side of the line segment AB that represents the stage. We indicate with α_{1}, α_{2}, …, α_{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:

∑_{i=1}^{n} α_{i}

is a minimum. The illumination with a minimum aperture sum is called an efficient illumination. The 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.

Figure 5.1

Exploratory Exercise

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. 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 α_{1} + α_{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 π/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.

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

Lemma 5.1 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}, …, P_{n} lie above both s and r. Let θ be the angle AQB, where Q is the intersection of the two lines. Assume that Q lies above the stage. If the apertures α_{1}, α_{2}, …, α_{n} are such that:

∑_{i=1}^{n} α_{i} ≥ θ,

then lights with the given apertures can be placed at the given points to light up the stage AB.

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 θ 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 θ > π/3 but we established in Exercise 5.1b that the minimum value of α_{1} + α_{2} is less than π/3.

Open Question There is an open question, a question that no one can answer yet: Is θ ever equal to the sum of the apertures in an efficient solution?

Exploratory Exercise

5.2 You are given the stage AB, and the points P_{1}, P_{2}, and P_{3} as in Figure 5.4.

Figure 5.4

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

b. Cut out wedges of apertures α_{1} = 20^{∘}, α_{2} = 15^{∘} and α_{3} = 10^{∘}. 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 ∑_{i=1}^{n} α_{i} < θ. 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?

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.

5.2 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 π/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?

Figure 5.5

Two π/2-lights, one placed at vertex A and the other at vertex B, will suffice; one π/2-light will not. So the minimum number is two. Are there any other locations from which two π/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 π/2-lights is needed, there is no known general method or algorithm to find the minimum number of vertex π/2-lights required to illuminate a given polygon. But it is possible to find an upper bound for the number of vertex π/2-lights that will be needed.

Exploratory Exercise

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 π/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.

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.

Theorem 5.2 For any orthogonal polygon with n vertices and h holes,

⌊\frac{3n + 4(h − 1)}{8}⌋

π/2-floodlights placed at vertices are always sufficient and sometimes necessary to illuminate the polygon.

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,

⌊\frac{3n + 4(h − 1)}{8}⌋ = ⌊\frac{3(12) + 0}{8}⌋ = 4.

According to the theorem four lights will suffice, but we know we can do better.

Exploratory Exercise

5.4 Can you find an orthogonal polygon with 12 sides and one hole that requires four π/2-lights?

In the case of Figure 5.6,

⌊\frac{3n + 4(h − 1)}{8}⌋ = ⌊\frac{3(32) + 0}{8}⌋ = 12.

This shows that the given number of lights is sometimes necessary.

Problems

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 π/2-lights in each case according to Theorem 5.1. Show how each polygon can be illuminated by at most M vertex π/2-lights.

5.2 Find the minimum number of vertex π/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.

Figure 5.7

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 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.

References

[ACSU] J. Abello, V. Estivil-Castro, T. Shermer, and J. Urrutia. “Illumination with Orthogonal Floodlights”, International Journal of Computational Geometry and Applications 8, pp. 25-38, 1998.

[BGK] P. Bose, L. Guibas, A. Lubiw, M. Overmars, D. Souvaine, J. Urrutia. “The Floodlight Illumination Problem,” International Journal of Computational Geometry and Applications 7, pp. 153-163, 1997.

[C] V. Chvátal. “A Combinatorial Theorem in Plane Geometry,” Journal of Combinatorial Theory, Ser B, 18, pp. 39-41 (1975).

[CRCU] J. Czygowicz, E. Rivera-Campo, and J.Urrutia. “Optimal Floodlight Illumination of Stages,” Proc. 5th Canadian Conference on Computational Geometry, pp. 393-398, 1993.

[EOUX] V. Estivill-Castro, J. O’Rourke, J. Urrutia, D. Xu. “Illumination of Polygons with Vertex Lights,” Information Processing Letters, 56, pp. 9-13, 1995.

[ECU] V. Estivill-Castro and J. Urrutia. “Two-Floodlight Illumination of Convex Polygons,” 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.

[EU] V. Estivill-Castro, and J. Urrutia. “Optimal Floodlight Illumination of Orthogonal Art Galleries,” Proc. 6th Canadian Conference on Computational Geometry, pp. 81-86, 1994.

[M] G. Meisters. “Polygons Have Ears”, Amer. Math. Monthly 82, pp. 648-51, 1975.

[O87] J. O’Rourke. Art Gallery Theorems and Algorithms, Oxford University Press, New York, 1987.

[O94] J. O’Rourke. Computational Geometry in C, Cambridge University Press, Cambridge, 1994.

[O97] J. O’Rourke. “Vertex π-lights for Monotone Mountains”, Proc. 9th Canadian Conference on Computational Geometry, pp. 1-5, 1997.

[OSS] J. O’Rourke, Thomas Shermer, and Ileana Streinu. “Illuminating Convex Polygons with Vertex Floodlights,” Proc. 7th Canadian Conference on Computational Geometry, pp. 151- 156, 1995.

[SS] W. Steiger, and I. Streinu. “Illumination by Floodlights”, Computational Geometry 10, pp.57-70, 1998.

[U] J. Urrutia. “Art Gallery and Illumination Problems”, Handbook of Computational Geometry, North-Holland, pp. 973-1027, 2000.