DIMACS

Center for Discrete Mathematics & Theoretical Computer Science

DIMACS EDUCATIONAL MODULE SERIES

MODULE 07-1 Art Gallery Theorems and Triangulations

Date prepared: January 3, 2007

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

Val Pinciu Southern Connecticut State University New Haven, CT 06515 email: pinciuv1@southernct.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, Georgia Institute of Technology, HP Labs, IBM Research, Microsoft Research,

Rensselaer Polytechnic Institute, and Stevens Institute of Technology.

Module Description Information

• Title:

Art Gallery Theorems and Triangulations

• Authors:

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

• Abstract:

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

• Informal Description:

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

• Target Audience:

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

• Prerequisites:

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

• Mathematical Field:

Graph Theory, Computational Geometry

• Applications Areas:

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

• Mathematics Subject Classification:

05C15, 05C85, 68R10, 94C15

• Contact Information:

T. S. Michael Mathematics Department United States Naval Academy Annapolis, MD 21402 email: tsm@usna.edu

Val Pinciu Mathematics Department Southern Connecticut State University New Haven, CT 06515 email: pinciuv1@southernct.edu

• Other DIMACS modules related to this module:

Module 03–3: Security Cameras and Floodlight Illumination

1 Introduction

1.1 The Scorpio Art Gallery

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

The Scorpio Art Gallery in Figure 1 has eighteen sides and is protected by five guards at the indicated positions. Every point in the gallery is visible to at least one guard. Guards are

Figure 1: The Scorpio Art Gallery

stationary, but can rotate 360^{∘} in place to view the surrounding portions of the gallery not blocked off by walls. A guard at a corner of the gallery can see along the walls. In Figure 1 none of the five guards can be removed without leaving some part of the gallery unprotected. Nonetheless, it is possible to protect the gallery with just four guards.

Exercise 1.1: Indicate the positions of four guards that protect the Scorpio Art Gallery.

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

1.2 The Art Gallery Problem

Now suppose the gallery director knows that the gallery is a polygon with 18 sides, but cannot remember the exact shape. How many guards must be hired to guarantee that the entire gallery can be protected, regardless of its shape? The Scorpio Art Gallery shows that at least four guards are needed, but is there a gallery that requires more guards? Yes! The Crown Gallery in Figure 2 has 18 sides requires six guards.

Exercise 1.2:

(a) Explain why the Crown Gallery requires six guards.

(b) Exhibit the positions of six guards that protect the gallery.

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

In general, we seek the minimum number of guards that are guaranteed to be able to protect any n-sided polygon. (We always assume that our art galleries have polygonal floor plans.) We Figure 2: The Crown Gallery has eighteen sides and can be protected by six guards, but no fewer.

let g(n) denote the maximum number of guards required among all n-sided art galleries. We have shown that g(18) ≥ 6, and we suspect that equality holds. The general problem of evaluating g(n) was posed by Victor Klee in 1973.

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

Exercise 1.3:

(a) Explain why g(3) = 1.

(b) Explore examples and guess the values of g(4) and g(5).

(c) Show that g(6) ≥ 2.

(d) The following partially completed table summarizes our deductions about g(n) so far. Fill in as much information as you can in the table.

\begin{matrix}n & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 \\ g(n) & 1 & & & ≥ 2 & & & & & & & & & & & & ≥ 6 \end{matrix}

(e) Can you conjecture a formula for g(n) based on a pattern you see in the table?

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

1.3 Organization of the Module

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

2 Background and Review

2.1 Graph Theory

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

Example 2.1: Let G = (V, E) be the graph with

vertex set V = {v_{1}, v_{2}, v_{3}, v_{4}}  and
edge set E = {(v_{1}, v_{2}), (v_{1}, v_{3}), (v_{1}, v_{4}), (v_{2}, v_{3})}.

Figure 3 shows two drawings of G.

Figure 3: (a) A drawing of the graph G in Example 2.1. (b) A planar representation of G.

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

Let G = (V, E) be a graph, and let λ be a positive integer. A λ-coloring of G is a function f from V to the color set {1, 2, …, λ} such that no two adjacent vertices are mapped to the same color. In other words, if f(v) = f(w), then vertices v and w are not adjacent. We think of the function f as assigning the color k to the vertices in V_{k} (k = 1, …, λ), and define the k-th color class as the set V_{k} = {v ∈ V : f(v) = k}. Note that some color classes may be empty. Of course, V_{1} ∪ V_{2} ∪ ⋯ ∪ V_{λ} = V and V_{h} ∩ V_{k} = ∅ for h ≠ k, and thus the color classes partition the vertex set of G. We usually define a λ-coloring by exhibiting the color classes V_{1}, V_{2}, …, V_{λ}, instead of the function f. For instance, the graph G in Example 2.1 has a 4-coloring in which V_{k} = {v_{k}} for k = 1, 2, 3, 4. Also, G has a 3-coloring with V_{1} = {v_{1}}, V_{2} = {v_{2}, v_{4}}, and V_{3} = {v_{3}}. However, G does not have a 2-coloring. (Why not?)

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

The Four-Color Theorem: Every planar graph has a 4-coloring.

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

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

Theorem 2.1: Let T = (V, E) be a graph with n vertices and m edges. If any two of the following statements are true, then all three statements are true:

• T is connected;

• T has no simple circuits;

• m = n − 1.

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

Figure 4: A tree with seven vertices and five leaves.

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

Lemma 2.2: Every tree with at least two vertices has at least two leaves.

2.2 Geometry

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

Exercise 2.1: Prove that the intersection of two convex sets is convex.

A polygon is an ordered sequence [v_{1}, v_{2}, …, v_{n}] of n distinct points in the plane (n ≥ 3), together with the n line segments \overline{v_{1}v_{2}}, \overline{v_{2}v_{3}}, …, \overline{v_{n−1}v_{n}}, \overline{v_{n}v_{1}}. The points v_{1}, v_{2}, …, v_{n} are the vertices of the polygon, and line segments \overline{v_{1}v_{2}}, \overline{v_{2}v_{3}}, …, \overline{v_{n−1}v_{n}}, \overline{v_{n}v_{1}} are the sides. The order of the vertices of a polygon may be cyclically permuted without changing the polygon. For instance, the polygon [v_{1}, v_{2}, v_{3}, v_{4}] is the same as the polygon [v_{3}, v_{4}, v_{1}, v_{2}].

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

Figure 5: (a) a convex polygon (b) a polygon with four reflex angles

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

Exercise 2.2: Prove that a polygon with a reflex angle cannot be convex.

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

Lemma 2.3: Every polygon has at least one strictly convex vertex.

Proof: Let P be a polygon with vertices v_{1}, v_{2}, …, v_{n}. Introduce a Cartesian coordinate system, and let (x_{i}, y_{i}) be the Cartesian coordinates of vertex v_{i} (i = 1, …, n). Let v_{k} = (x_{k}, y_{k}) be the leftmost vertex, i.e., the vertex with smallest x-coordinate. If there are several vertices that tie for the leftmost, then from these we choose the lowest, i.e., the one with smallest y-coordinate. The vertices of P adjacent to v_{k} are v_{k−1} and v_{k+1}, and these fall either strictly to the right of v_{k}, or on the same vertical line as v_{k}, but strictly above v_{k}. (See Figure 6.) It follows that the angle at v_{k} is less than 180^{∘} and hence that v_{k} is a strictly convex vertex.

Figure 6: In the proof of Lemma 2.3, v_{k} is lowest among the leftmost vertices

3 Triangulations of Polygons

3.1 Basic Concepts

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

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

Figure 7: (a) Diagonals of a polygon (b) The proof of Proposition 3.1

Exercise 3.1: Explain why any two non-consecutive vertices are the endpoints of a diagonal in a convex polygon.

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

Proposition 3.1: Every polygon with at least four sides has a diagonal.

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

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

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

Theorem 3.2: Every polygon has a triangulation.

Proof: We will prove this statement by mathematical induction on n, the number of sides of the polygon P. In the base case (n = 3) the polygon is a triangle, and the result is certainly true. We Figure 8: (a) A decomposition of a polygon into triangles by non-crossing diagonals. (b) A single diagonal gives a decomposition of a polygon into two smaller polygons P_{1} and P_{2}.

now assume that n ≥ 3 and that the statement is true for all polygons with at most n sides. Let P be a polygon with n + 1 sides. We must show that P has a triangulation. By Proposition 3.1 the polygon P has a diagonal. This diagonal gives a natural decomposition of P into two polygons P_{1} and P_{2} with n_{1} and n_{2} sides, respectively. (See Figure 8(b).) Now the endpoints of our diagonal are the only common vertices of P_{1} and P_{2}, and hence n_{1} + n_{2} = n + 3. This equality and the conditions n_{1} ≥ 3 and n_{2} ≥ 3 imply that n_{1} ≤ n and n_{2} ≤ n. We apply the induction hypothesis to obtain triangulations of P_{1} and P_{2}, which together give a triangulation of the original polygon P.

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

Proposition 3.3: Every triangulation of a polygon with n sides uses exactly n − 3 diagonals and contains n − 2 triangles.

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

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

Corollary 3.4: The sum of the interior angles of a polygon with n sides equals (n − 2)180^{∘}.

3.2 Triangulation Graphs and the Dual Tree

Let T be a triangulation of a polygon P. The triangulation graph G_{T} has vertex set equal to the vertices of P. Two vertices are adjacent in G_{T} provided they correspond to consecutive vertices in the polygon P or to the endpoints of a diagonal in the triangulation T . For instance, Figure 9 shows the triangulation graph for the polygon from Figure 8.

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

Lemma 3.5: The dual tree of a triangulation of a polygon is a tree with each vertex adjacent to at most three others.

Proof: Let T be a triangulation of a polygon P with n vertices, and let G_{T} be the corresponding triangulation graph. We first note that dual(G_{T}) must be connected by the manner in which it

Figure 9: A triangulation graph and its dual tree

is constructed from P. Now the number of vertices of dual(G_{T}) equals the number of triangles in T , which equals n − 2 by Proposition 3.3. Moreover, the number of edges in dual(G_{T}) equals the number of diagonals in the T , which equals n − 3 by Proposition 3.3. Hence dual(G_{T}) is a connected graph with n − 2 vertices and n − 3 edges. Therefore dual(G_{T}) is a tree by Theorem 2.1. Finally, every vertex of dual(G_{T}) corresponds to a triangular face in T , and hence is adjacent to most three other vertices in dual(G_{T}).

Three consecutive vertices u, v, and w of a polygon form an ear provided the segment \overline{uw} is a diagonal. The ears [u_{1}, v_{1}, w_{1}] and [u_{2}, v_{2}, w_{2}] are non-overlapping provided the triangles △u_{1}v_{1}w_{1} and △u_{2}v_{2}w_{2} have disjoint interiors. The polygon in Figure 8(a) has three ears, one of which is △vwx. Also, △xyu is not an ear because the vertices are not consecutive. No two of the three ears in the polygon overlap.

Exercise 3.2: Find the other two ears of the polygon in Figure 8(a).

Two Ears Theorem (Meisters): Every polygon with n vertices (n ≥ 4) has at least two nonoverlapping ears.

Proof: Let G_{T} be a triangulation graph for the polygon P, and dual(G_{T}) be the dual tree of T . The number of vertices of the dual tree is at least 2 because n ≥ 4. By Lemma 2.2 the dual tree has at least two leaves, say v_{1} and v_{2}. Now v_{1} and v_{2} correspond to triangles in G_{T} whose interiors are disjoint, and which share at most a line segment as a boundary. Thus v_{1} and v_{2} correspond to non-overlapping ears of the polygon P.

3.3 Colorings of Triangulations

We have seen that every polygon has a triangulation. Fisk’s proof of Chvátal’s Theorem hinges on the existence of 3-colorings of triangulations of polygons. In Figure 10 we construct a 3-coloring of the triangulation graph from Figure 9. We start by assigning three different colors to the vertices of any triangle. In Figure 10 we assigned the three colors to vertices r, s, and t. Now vertex z is adjacent to r and t, and hence must be assigned the same color as vertex s. Similarly, y is adjacent to t and z, and therefore must be the same color as r. We proceed in this manner through all the triangles in the graph. The color of every vertex is forced, and we eventually obtain the three color classes shown in Figure 10:

V_{1} = {r, v, y},  V_{2} = {s, u, w, z},  V_{3} = {q, t, x}.

The general situation is treated in the following theorem.

Figure 10: Coloring a triangulation graph with three colors

Theorem 3.6: Every triangulation graph of a polygon is 3-colorable.

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

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

The second proof relies on the Four-Color Theorem.

Figure 11: A point p in the exterior of a polygon is joined to each vertex of a triangulation to form a planar graph G′

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

�

4 Chvátal’s Art Gallery Theorem

4.1 Strategy

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

• Find a triangulation T of the polygon P.

• Find a 3-coloring of the triangulation graph G_{T} .

• Use the 3-coloring of G_{T} to position at most ⌊n/3⌋ guards that cover all of P.

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

4.2 Theorem and Proof

Chvátal’s Art Gallery Theorem: Let n be an integer with n ≥ 3. Then the maximum number of guards needed to cover a polygon with n sides is ⌊n/3⌋. In other words,

g(n) = ⌊\frac{n}{3}⌋.

Proof: (Fisk) Let P be a polygon with n sides and vertex set V. We shall show that ⌊n/3⌋ guards are sufficient to cover P. By Theorem 3.2, P has a triangulation T . Now consider the corresponding triangulation graph G_{T} . Theorem 3.6 implies that G_{T} has a 3-coloring, say, with color classes V_{1}, V_{2}, and V_{3}. Because there are n vertices altogether, we know that one of the color classes, say V_{i}, contains at most ⌊n/3⌋ vertices. We place guards at the vertices in V_{i}. We claim that these guards cover all of P. The key observation is that each triangle of T has one vertex of each of the three colors. Now every point of a triangle is visible from each of its three vertices, and the triangulation T is a decomposition of the polygon P. It follows that V_{i} covers P. For example, in the three-coloring for the triangulation of a polygon in Figure 10. we may post guards at the three vertices the color class {r, v, y}, and the whole polygon is guarded. We have now shown that

g(n) ≤ ⌊\frac{n}{3}⌋.

It remains to show that some polygons with n sides requires ⌊n/3⌋ guards. Suppose that n is a multiple of 3, say n = 3t. Then a suitable crown-shaped polygon with t tines is readily shown to require t guards. (See Figure 2). Now suppose that n − 1 is a multiple of 3, say n = 3t + 1. Then we merely “dent” the crown, replacing one corner by two nearby corners, to produce a polygon that requires t guards. When n − 2 is a multiple of 3, we put two dents in the crown. These constructions show that

g(n) ≥ ⌊\frac{n}{3}⌋.

Our two inequalities now imply that g(n) = ⌊n/3⌋.

We remark that Fisk’s coloring argument does not necessarily produce the smallest possible guard set to cover the gallery. For instance, the polygon in Figure 10 can be covered by just two guards at points r and x.

5 Orthogonal Art Galleries

5.1 Definitions

A polygon is orthogonal provided each interior angle is either 90^{∘} or 270^{∘}. In an orthogonal polygon the two sides alternate between two perpendicular orientations, say, horizontal and vertical. Figure 12 displays an orthogonal polygon.

Figure 12: An orthogonal polygon

Exercise 5.1: Let P be an orthogonal polygon with n sides.

(a) Prove that the number of 90^{∘} angles in P equals (n + 4)/2. Hint: Use Corollary 3.4.

(b) Prove that n must be even.

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

The Orthogonal Art Gallery Problem: Determine the maximum number g_{⊥}(n) of guards required to protect any orthogonal polygon with n sides.

Exercise 5.2:

(a) Prove that g_{⊥}(4) = 1.

(b) Prove that g_{⊥}(8) ≥ 2.

Exercise 5.3: Let m be a positive integer. Exhibit an orthogonal polygon that requires m guards and has:

(a) 4m sides;

(b) 4m + 2 sides.

In other words, show that g_{⊥}(4m) ≥ m and g_{⊥}(4m + 2) ≥ m.

5.2 Theorem and Proof

The Orthogonal Art Gallery Problem was completely solved in 1980.

Orthogonal Art Gallery Theorem: (Kahn, Klawe, and Kleitman, 1980) Let n be an even integer with n ≥ 4. Then the maximum number of guards needed to protect an orthogonal polygon with n sides is ⌊n/4⌋. In other words,

g_{⊥}(n) = ⌊\frac{n}{4}⌋.

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

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

• Partition the art gallery into convex quadrilaterals.

• Color the vertices of a graph associated with the quadrilateral partition.

• Post the guards in positions according to the coloring.

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

A quadrangulation of a polygon P is a decomposition {P_{1}, …, P_{t}} obtained by inserting diagonals of P so that each of the polygons P_{1},…, P_{t} contains exactly four vertices of P on its boundary. The quadrangulation is convex provided each quadrilateral is convex. Figure 13 shows two quadrangulations of a polygon, one of which is a convex quadrangulation.

Figure 13: (a) a non-convex quadrangulation (b) a convex quadrangulation

Exercise 5.4: Suppose that a polygon with n sides has a quadrangulation.

(a) Show that n must be even.

(b) How many quadrilaterals are there as a function of n?

Exercise 5.5: Give an example of a polygon with six sides that does not have a convex quadrangulation.

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

Proposition 5.1: (Kahn, Klawe, Kleitman, 1980) Every orthogonal polygon has a convex quadrangulation.

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

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

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

Figure 14: A quadrangulation of a polygon, the corresponding quadrangulation graph, a 4-coloring, and a planar representation

Exercise 5.6: Suppose an orthogonal polygon with n sides has a convex quadrangulation Q. How many edges are there in the quadrangulation graph G_{Q}?

Lemma 5.2: Suppose that a polygon has a convex quadrangulation Q. Then the quadrangulation graph G_{Q} is 4-colorable.

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

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

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

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

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

6 Problems

1. Prove Theorem 2.1.

2. Prove Lemma 2.2.

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

4. (a) Find all triangulations of the polygon in Figure 5(b).

(b) Find a polygon with seven sides that has exactly one triangulation.

5. Prove Proposition 3.3.

6. Find a triangulation of a suitable polygon whose dual tree is the tree in Figure 4.

7. Prove that a convex polygon with n sides has exactly n(n − 3)/2 diagonals.

8. Let P be a polygon with n sides. Lemma 2.3 asserts that some interior angle of P has measure less than 180^{∘}. Prove the stronger result that some interior angle has measure at most (1 − \frac{2}{n}) 180^{∘}.

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

10. Triangulate the Scorpio Art Gallery in Figure 1 and give a 3-coloring of the resulting triangulation graph.

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

12. Suppose that r ≥ 1.

(a) Show that a polygon with r reflex angles can be covered by r guards.

(b) Exhibit a polygon with r reflex angles that requires r guards.

13. Let P be a polygon with exactly three strictly convex vertices.

(a) Prove that P can be covered with one guard if the three strictly convex vertices are consecutive.

(b) What if the three strictly convex vertices are not consecutive?

14. Give an example of a polygon P and a guard set V^{∗} such that V^{∗} covers every point on the boundary of P, but does not cover P.

15. (a) Complete the first proof of Lemma 5.2.

(b) Complete the second proof of Lemma 5.2.

16. Let G = (V, E) be a graph, and let λ be a positive integer. Suppose that the vertices of G are labeled v_{1}, v_{2}, …, v_{n} so that for each i > λ the vertex v_{i} is adjacent to fewer than λ vertices with smaller subscripts.

(a) Prove that G is λ-colorable.

(b) How does the result in (a) relate to Theorem 3.6 and Lemma 5.2?

17. Show that any polygon with seven sides can be guarded with two guards that are visible to each another.

7 Notes and References

The classic reference for art gallery theorems is the book by O’Rourke [9]. Shermer [11] wrote an updated survey. The excellent handbook [12] on computational geometry contains a recent survey by Urrutia on art gallery problems.

The Art Gallery Theorem was first proved by Chvátal [2], and Fisk’s proof [3] appeared a short time later. Kahn, Klawe, and Kleitman [5] first proved the Orthogonal Art Gallery Theorem; different proofs were provided by O’Rourke [8] and Győri [4]. Lubiw [6] proved that orthogonal polygons have convex quadrangulations, from which the Orthogonal Art Gallery Theorem follows.

The graph theory background used in this module can be found in many texts, including those by Chartrand and Lesniak [1] and Roberts [7]. The books by Saaty and Kainen [10] and Wilson [13] discuss the Four-Color Theorem and its proof.

References

[1] G. Chartrand and L. Lesniak, Graphs and Diagraphs. 2nd ed. Wadsworth and Brooks/Cole, 1986.

[2] V. Chvátal, A combinatorial theorem in plane geometry, J. Combin. Theory Ser. B, 18 (1975), 39-41.

[3] S. Fisk, A short proof of Chvátal’s watchman theorem. J. Combin. Theory Ser. B, 24 (1978), 374.

[4] E. Győri, A short proof of the rectilinear art gallery theorem SIAM J. Alg. Disc. Meth., 7 (1986) 452-454.

[5] J. Kahn, M. Klawe, and D. Kleitman, Traditional galleries require fewer watchmen, SIAM J. Alg. Disc. Meth., 4 (1983) 194-206.

[6] A. Lubiw, Decomposing polygonal regions into convex quadrilaterals, Proc. 1st ACM Symp. Comput. Geom., Baltimore (1985) 97-106.

[7] F. S. Roberts, Applied Combinatorics. Prentice-Hall, New Jersey, 1984.

[8] J. O’Rourke, An alternate proof of the rectilinear art gallery theorems, J. of Geometry, 21 (1983), 118-130.

[9] J. O’Rourke, Art Gallery Theorems. Oxford University Press, 1987.

[10] T. L. Saaty and P. C. Kainen, The Four-Color Problem: Assaults and Conquest. Dover Publications, New York, 1986.

[11] T. C. Shermer, Recent results in art gallery theorems, Proc. IEEE, 80 (1992), 1384-1399.

[12] J. Urrutia, Art gallery and illumination problems, in: Handbook of Computational Geometry, J.-R Sack and J. Urrutia (eds.) Elsevier Science B.V. 1999, pp 973–1027.

[13] R. Wilson, Four-Colors Suffice. Princeton University Press, New York, 2002.