Art Gallery Problem and Polygon Triangulation

Ying Xiao, Jianyu Wang Department of Mathematics and Statistics Carleton University

Due Date: April 25, 1997 Submitted as the final project of the course 95.508

Abstract In this paper, We will examine the original art gallery theorem and its two different proofs. One of the proof leads to a discussion of Polygon triangulation. We will also discuss how to guard traditional art gallery and discuss the problem of flipping edges in polygon triangulations.

1 Introduction and Definitions

In 1973, Victor Klee posed the problem of determining the minimun number of guards sufficient to cover the interior of an n-wall art gallery room. Vasek Chvatal soon established what was become known as “Chvatal’s Art Gallery Theorem: [n/3] guards are occasionally necessary and always sufficient to cover a polygon of n vertices”(see [4]). This simple and beautiful theorem has since been extended by mathematicians in several directions, and has been further developed by computer scientists studying partitioning algorithms.

Triangulation is a catchword for the more general problem of subdividing a complex domain into a disjoin collection of “simple” objects. The simplest region into which one can decompose plane is a triangle. Depending on the application, other definitions of “simple” can be applied as well. Triangulation or domain decomposition is typically the first step in any one of a number of algorithms, which then iterate some operation over all triangles of the domain.

The simplist proof(due to S. Fisk, see [5]) of the original art gallery problem can be seen a cute example of the problem of triangulating polygons.

A polygonal curve is a finite sequence of line segments, called edges joined end to end. the endpoints of the edges are vertices. A polygonal curve is closed if the last endpoint equals the first endpoint. A polygonal curve is simple if it is not self-intersecting. The famous Jordan curve theorem states that every simple closed plane curve divides the plane into two regions(the interior and the exterior). A polygon P is the region of the plane bounded by a simple, closed polygonal curve, the corresponding curve is refered to as the boundary of P, denoted by ∂P.

A point x ∈ P sees or covers a point y ∈ P if the line segment xy is a subset of P, i.e. xy ⊆ P. Note xy may touch ∂P at one or more points. For any polygon P, define G(P) to be the minimum number of points of P, {x_{1}, x_{2}, ..., x_{n}}, so that, for any y ∈ P, some x_{i}(1 ≤ i ≤ k), covers y. Finally, define g(n) to be the maximum value of G(P) over all polygons of n vertices.

Klee’s original art gallery problem was to determine g(n): the covering points are guards who can survey 360^{∘} about their fixed position, and the art gallery room is a polygon. The function g(n) represents the maximum number of guards that are ever needed for an n-gon: g(n) guards always suffice, and g(n) guards are necessary for at least one polygon of n vertices.

Let us consider some examples. For n = 3(the smallest possible simple polygon) the answer is obviously g(3) = 1. Also g(4) = 1 is easy to check, a 4-sided polygon has at most 1 reflex vertex, that is, a vertex whose interior angle is strictly greater than π (other vertices are called convex vertices), by placing the guard at or near this point it suffices. A 5-sided polygon can have 2 reflex vertices, we can also check g(5) = 1 by consider two cases(whether the reflex vertices are adjacent or not). For n = 6, there are two shapes that need two guards(see page 3 of [1]), then we can check that g(6) = 2. The second shape easily generalizes to a “comb” of k prongs and n = 3k edges that requires k guards. This establishes that g(n) ≥ ⌊n/3⌋.

In section 2 and section 3, we will give two methods to show that ⌊n/3⌋ guards suffice to cover any polygon with n vertices. In section 4, we will discuss the algorithm of The Art Gallery Problem. The critical step of the algorithm is the triangulation of a simple polygon, this can be done in linear time!(see [10])

In the original Art Gallery Problem, an art gallery is a simple polygon on the plane. In a more realistic setting, a traditional art gallery is housed in a rectangular building subdivided into rectangular rooms. Assume that any two adjacent rooms have a door connecting them. For this problem, we will show in section 5 that any traditional art gallery with n rooms can be guarded with exactly ⌈n/2⌉ guards.

Notice in general a polygon can have many distinct triangulations. For example, the number of the triangulations of a convex polygon is the Catalan number. Is there any connection among these triangulations? In section 6, we will give some idea about flipping edge on triangulations and show that the graph of triangulations of a simple polygon is connected, and the diameter of it is at most O(n + k^{2}), here k is the number of reflex vertices in the polygon.

2 Fisk’s proof for sufficient:

The first step in Fisk’s proof is to triangulate the polygon P by adding internal diagonals between vertices until no more can be added. We need to prove that triangulation exist, and then try to get some good algorithms for constructing a triangulation.

Lemma 1: Every polygon contains at least one strictly convex(a vertex whose interior angle is strictly less than π).

Proof: Consider the lowest vertex v in P (the minimum y-coordinate vertex). If there are more than one such vertices just consider the rightmost. Consider a horizontal line L passing through v. The vertices adjacent to v lie on or above L, the vertices following v must lie strictly above L. Hence the interior angle at v is less than π.

Lemma 2: Every polygon of n ≥ 4 vertices has at least one diagonal. Proof: Let v be a strictly convex vertex. Let a and b be the vertices

adjacent to v. If ab is a diagonal then we are done. If not, since n ≥ 4, the closed triangle avb contains at least one vertex of P. Let L be the line through ab. Move a line paralled to L through v upwards, and let x be the first vertex hit this line within the triangle. The portion of the triangle swept by the line is empty of the boundary of P, so the segment xv is a diagonal.

Theorem 1(Triangulation theorem): A polygon of n vertices may be partitioned into n−2 triangles by the addition of n−3 internal diagonals.

Proof: Using Lemma 2, this theorem can be proven easyily by induction on n.

Lemma 3: The dual graph of a triangulation of a polygon, with a node for each triangle and an arc connecting two nodes whose triangles share a diagnol, is a tree with each node of degree at most 3.

Proof: Since a triangle has only 3 sides, so each node has degree no greater than 3. If the graph is not a tree, it must have a cycle. This cycle encloses some vertices of the polygon, therefore it encloses points exterior to the polygon. this contradicts the definition of a polygon.

Three consecutive vertices v_{1}, v_{2}, v_{3} form an ear of a polygon P at v_{2}, if the segment v_{1}v_{3} is completely interior to P. Two ears are non-overlapping if the triangle interiors are disjoint.

Lemma 4(Meister’s Two Ears theorem): Every polygon of n ≥ 4 vertices has at least two non-overlapping ears.

Proof: Leaves in the dual of a triangulation correspond to ears, and every tree of two or more nodes must have at least two leaves.

The second step is to show that the graph of triangulates polygon can be 3−colored. A k−coloring of a graph is an assignment of colors to the nodes, one color per node, using no more than k colors, such that no two adjacent nodes are assigned the same color. Because a triangulation graph is planar, it is 4−colorable by the Four Color Theorem. But for the triangulation graph, we can do more.

Theorem 2: Let T be the triangulation graph of a triangulation of a simple polygon. Then T is 3−colorable.

Proof: By induction. Using lemma 2, we can cut off an ear triangle from the graph, 3−color the remainder by induction, and put back the removed triangle, coloring its degree 2 tip vertex the color not used on the cut diagnol.

The third step is to note that one of the three colors must be used no more than 1/3 of the time. this is just the Pegionhole Principle.

Let the least frequently used color be red. the last step is to placeguards at every red node. Since a triangle is the complete graph on three nodes, each triangle has all three colors at its vertices. Thus every triangle has a red node and thus a guard in one of of its corners. Moreover, since the triangles form a partitions are convex, every point is covered by a red guard. Thus the guards cover the entire polygon, and there are at most ⌊n/3⌋ of them.

Hence ⌊n/3⌋ guards are sufficient to cover the interior of an arbitrary polygon. Together with the necessity shown earlier, we have that g(n) = ⌊n/3⌋.

3 Chvatal’s Proof for Sufficient:

This is the first proof of Chvatal’s Art Gallery Theorem. This proof also starts with a triangulation of the polygon, but does not use graph coloring. The theorem is proven directly by inductoin.

Define a fan as a triangulation with one vertex(the fan center) shared by all triangles. Chvatal took as his induction hypothesis this statement:

Induction Hypothesis: Every triangulation of an n-gon can be partitioned into g ≤ ⌊n/3⌋ fans.

For the basis, note that n ≥ 3 since we start with an n−gon, and that there is just a single triangulation possible when n = 3, 4, 5, each of which is a fan. Thus the induction hypothesis holds for n < 6.

Given a triangulation with n ≥ 6, the approach will be to remove part of the triangulation, apply the induction hypothesis, and then put back the deleted piece. But in order to make induction work with the formula [n/3], we have to reduce n by at least 3 so the induction hypothesis will yield less than g fans, allowing the grouping of the removed triangles into a fan. Does there always exists a diagonal that partitions off 4 edges of the polygon, and therefore reduces n by 3? The answer is no, we have counterexample(see [1] page 7). Chvatal’s brilliant stroke was to realize that there is always a diagonal that cuts off 4 or 5 or 6 edges.

Lemma 5 For any triangulation of an n-gon with n ≥ 6, there always exists a diagonal d that cuts off exactly 4, 5, or 6 edges.

Proof: Choose d to be a diagonal that separates off a minimum number of polygon edges that is at least 4. Let k ≥ 4 be the minimum number, and label the vertices of the polygon 0, 1, ..., n − 1 such that d is (0, k); d must support a triangle T whose apex is at some vertex t with 0 ≤ t ≤ k. Since (0, t) and (k, t) each cut off fewer than k edges, by the minimality of k we have t ≤ 3 and k − t ≤ 3. Adding these two inequalities yields k ≤ 6.

The rest of the proof is to apply the induction hypothesis to the portion on the other side of the special diagonal d. Let G_{1} be the triangulation partitioned off by d, it has k + 1 boundary edges and hence is a (k + 1)-gon. Let G_{2} be the remainder of the original triangulation, sharing d; it has (n − k + 1) vertices. The induction hypothesis tell us that G_{2} maybe partitioned into g′ = ⌊(n−k+1)/3⌋ fans. Since k = 4, 5, 6, g′ ≥ ⌊(n−3)/3⌋ = ⌊n/3⌋−1, then we only need to show that G_{1} need only add one more fan to the partition, the rest of the proof is to check in each case(k = 4, k = 5, k = 6) this statement is true.

For more detail of the proof, see [1].

4 The Algorithm of Original Art Gallery Problem

Following the main steps of Fisk’s proof, Avis and Toussaint give the following algorithm:

Algorithm:

(1) Triangulate P, obtaining a graph G.

(2) Three-color the nodes of G.

(3) Place guards at the nodes assigned the least-frequently used color.

Step (1) is a difficult problem, we will see that it can be accomplished in linear time. Step (2) is easy if you assume that complete triangle adjacency information is contained in the data structure for G output from step (1). As the triangulation algorithm normly were unconcerned with this issue, Avis and Toussaint assume only that a list of the diagonals of the triangulation is available. Under these minimal assumption 3-coloring is not so trivial. They propose to 3-color by a divide-and-conquer strategy. Their divide step partitions the polygon into two pieces, each of at least ⌊n/4⌋ vertices(see [12]). Recursively assuming that each piece is 3-colored, the merge steps makes a 3-coloring of the whole by relabeling if necessary. Both the divide and the merge steps require only O(n) time, hence T (n) = 2T (n/2) + O(n), whose solution is T (n) = O(n log n). Step (3) of the algorithm takes just linear time, hence the total complexicity of the algorithm is O(n log n).

Now, we give some idea about the algorithm of the triangulation of a polygon. The proof of theorem 1 leads directly to an algorithm for constructing a triangulation, but the complexity of that is O(n^{2}). Obtaining an optimal algorithm for triangulation is an outstanding problem in computational geometry. In 1978, Garey etc.(see [6]) gave an O(n log n) time algorithm for triangulation a simple n-gon. Tarjan and Van Wyk([7]) discover an O(n log log n) time algorithm. Kirkpatrick gave a conceptially simplier O(n log log n) time algorithm([9]). In [10], Chazellc gave a linear time deterministic algorithm for triangulating a simple polygon. the method he used is to mix bottom-up and top-down approaches together. For detail of this linear time algorithm, please see [10].

5 Guarding Traditional Art Galleries:

A traditional art gallery is housed in a rectangular building subdivided into rectangular rooms, any two adjacent rooms have a door connecting them. How many guards need to be stationed in the gallery so as to guard all its rooms? If a guard is stationed at a door connecting two rooms, he will be able to guard both rooms, since no guard can guard three rooms, it follows that for the gallery which has n rooms, we need at least ⌈n/2⌉. We will prove ⌈n/2⌉ is also sufficient. In order to do that, we need introduce Tutte’s result in matching theory.

Given a graph G, a matching M of G is a subset of edges such that no two edges of M have a common vertex. A matching M of G is called perfect if each vertex of G is a vertex of an edge in M.

Given a graph G and a subset S of the vertices of G, we define Odd(S) to be the number of components of G − S with an odd number of vertices. The following result due to Tutte(see [15]) provides necessary and sufficient conditions for the existence of perfect matchings:

Theorem 3: A graph G has a perfect matching if and only if for every subset S of V (G), Odd(G − S) ≤ |S|.

Now, we begin to prove the following theorem, which is originally from [16]:

Theorem 4: Any rectangular art gallery with n rooms can be guarded with exactly ⌈n/2⌉ guards.

Proof: Given a rectangular art gallery T with n rooms R_{1}, ..., R_{n}, we can associate to it a dual graph G(T) by representing each room R_{i} of T by a vertex v_{i} in G(T), two vertices being adjacent if their corresponding rectangles share a line segment in their common boundary. The outmost boundary of the union of the rectangles corresponding to the vertices of any connected subgraph of G(T) form an orthogonal polygon.

Now, we show that if G(T) has an even number of vertices, G(T) has a pefect matching M. This is enough to prove our rsult since our ⌈n/2⌉ points can now be chosen using M as follows: for every edge v_{i}v_{j} of G(T) in M station a guard at the door connecting R_{i} and R_{j}. Clearly these guards will cover all of the subrectangles of T. the case when G(T) has an odd number of vertices follows by subdividing any room of T into two.

So we can assume that G(T) has even number of vertices. To prove that G(T) has a perfect matching, we will show that it satisfies tha condition of Theorem 3, i.e for any subset S of the vertices of G(T) the number of odd components of G(T) − S does not exceed |S|. Let k be the number of connected components of G(T) − S. Each connected component C_{i} of G(T) − S is represented by an orthogonal subpolygon P_{i} of T. Each such polygon has at least four corner points, and thus the total number of corner points generated by the k components in G(T) − S is at least 4k.

When a rectangle represented by a point in S is now replaced, at most four cornor poins will disappear. Once all rectangles in S are replaced, all the corner points generated by the components of G(T) − S will disappear, except for the four corner points of T. It follows that k ≤ |S| + 1. Also, it is easy to verify that if k = |S| + 1, then at least one of the components of G(T) − S is even. Hence we have proven k ≤ |S|.

Theorem 4 is proven.

6 Flipping Edges on Triangulations:

Let Q_{n} be a simple polygon with n vertices, T is a triangulation of Q_{n}. We say that an edge e of T can be flipped if e is contained in the boundary of two triangles t_{i} and t_{j} of T and C = t_{i} ∪ t_{j} is a convex quadrilateral. By flipping e we mean the operation of removing e from T and replacing it by the other diagonal of C.

Given a simple polygon Q_{n}, we define the graph G_{T} (Q_{n}), the graph of triangulations of Q_{n}, to be the graph such that the vertices of G_{T} (Q_{n}) are the triangulations of Q_{n}, two triangulations being adjacent if one can be obtained from the other by flipping an edge. The vertices of Q_{n} will always be assumed to be labeled v_{1}, v_{2}, ..., v_{n} in the clockwise direction.

If a polygon Q_{n} is convex, then the diameter of G_{T} (Q_{n}) is at most 2(n − 3). G_{T} (Q_{n}) is isomorphic to the rotation graph RG(n − 2). The vertex set of RG(n − 2) is the set of all binary trees with n − 2 vertices(see [13] or [14]).

It is also known that the graph of triangulations of a simple polygon Q_{n} with n vertices is connected and that its diameter is at most O(n^{2})(see [14]). Here we give a simple proof of this result which is given in [11].

Let T be a triangulation of a polygon Q_{n}, v_{i}, v_{j} are vertices of Q_{n} such that the line segment v_{i}v_{j} connecting them is not an edge of T. We say that v_{i}v_{j} can be inserted in T by flipping k − 1 edges if there is a sequence of triangulations T_{1} = T, ..., T_{k} such that v_{i}v_{j} is an edge of T_{k} and T_{i+1} can be obtained from T_{i} by flipping an edge of it(i = 1, 2, ..., k − 1). We say that a vertex v_{i} of Q_{n} is exposed if it lies in the convex hull of Q_{n}. Consider the two vertices v_{i−1} and v_{i+1} of Q_{n} adjacent to v_{i}, the shortest polygonal chain joining v_{i−1} to v_{i+1} totally contained in Q_{n} will be denoted by P_{i−1,i+1}.

The visibility graph of Q_{n} is the graph with vertex set v_{1}, v_{2}, ..., v_{n}. Two vertices v_{i} and v_{j} of Q_{n} are adjacent in the visibility graph of Q_{n} if the line segment joining tham is contained in Q_{n}.

Lemma 6: Let Q_{n} be a simple polygon, v_{i} an exposed vertex of Q_{n} and T a triangulation of Q_{n}. Then it is always possible to insert all edges of P_{i−1,i+1} into T using exactly as many flips as the number of edges of T, not in P_{i−1,i+1}, that intersect P_{i−1,i+1}.

Proof: Suppose that at least one edge e of P_{i−1,i+1} is not in T. Consider the polygon P_{e} formed by the union of all triangles of T intersected by e and the chain of vertices of P_{e} joining the endpoints of e. At least one of these vertices, say w, is a convex vertex of P_{e}, and thus the edge joining v_{i} to w can be flipped decreasing the number of edges of T that intersect e by one. Lemma 6 follows.

Theorem 5: The graph of triangulations G_{T} (Q_{n}) of a simple polygon is connected. Moreover, the diameter of G_{T} (Q_{n}) is at most the number of edges of the visibility graph of Q_{n}.

Proof: Let v_{i} be an exposed vertex of Q_{n}, T_{1} and T_{2} are two triangulations of Q_{n}. By Lemma 6, we can insert in each of T_{1} and T_{2} all the edges of P_{i−1,i+1} to obtain two new triangulations T̄_{1} and T̄_{2} of Q_{n}. Delete from Q_{n} the subpolygon bounded by the vertices of P_{i−1,i+1} and v_{i}. This will result in a collection of simple polygons with disjoint interiors. Each of these polygons has two triangulations induced by T̄_{1} and T̄_{2} respectively and fewer vertices than Q_{n}. Our result now follows by induction on the number of vertices of Q_{n}. This augument actually gives a diameter of twice the number of edges of visibility graph of Q_{n}. After a simple modification, we can obtain the claimed bound. Also notice that each edge of the visibility graph of Q_{n} incident to v_{i} may be used twice; the first time while inserting P_{i−1,i+1} into T_{1} and the second time when insert T_{2} into P_{i−1,i+1}. Once we delete v_{i} fr

The bound on the diameter of G_{T} (Q_{n}) given in Theorem 3 can be bad in general case. For example, when Q_{n} is a convex polygon, the visibility graph of Q_{n} has O(n^{2}) edges, while the diameter of G_{T} (Q_{n}) is at most 2(n − 3). But if the visibility graph of Q_{n} has very few edges, theorem 3 can give us an efficient method to transform one triangulation into another one.

¿From now on, we try to prove the following result:

If Q_{n} is a polygon with k reflex vertices, then the diameter of the graph of G_{T} (Q_{n}) is Ω(n + k^{2}), i.e. the diameter of the graph of triangulations of a polygon depends heavily on the number of its reflex vertices!

In order to prove this result, we need some definitions and lemmas first. Two vertices v_{i} and v_{j} of a polygon Q_{n} are called c-connected if they

are visible and the vertices v_{i+1}, ..., v_{j−1} of Q_{n} are all convex, addition taken mod n. If in addition, v_{i} and v_{j} are reflex vertices of Q_{n}, we call v_{i} and v_{j} are consecutive reflex vertices of Q_{n}.

Let v_{i}v_{j} be the line segment joining vertices v_{i} and v_{j}. If v_{i}v_{j} is such that, for each edge e of T intersecting v_{i}v_{j}, the end vertex of e below v_{i}v_{j} is a convex vertex of Q_{n}, or for each edge e of T intersecting v_{i}v_{j} the end vertex of e above v_{i}v_{j} is a convex vertex of Q_{n}, we call v_{i}v_{j} a proper diagonal of T.

Lemma 7: Let v_{i}v_{j} be a proper diagonal of triangulation T of a polygon Q_{n}. Then if v_{i}v_{j} is intersected by t edges of T, v_{i}v_{j} can be inserted in T using at most 2t flips.

Proof: Let v_{i}v_{j} be a proper diagonal of T. Assuming that (W.L.O.G.)for each edge e of T intersecting v_{i}v_{j}, the end vertex of e below v_{i}v_{j} is a convex vertex of Q_{n}. Let Q_{i,j} be the subpolygon of Q_{n} obtained by joining all the triangles of T intersected by v_{i}v_{j} and consider the triangulation T̄ of Q_{i,j} induced by T in Q_{i,j}. Suppose that v_{i}v_{j} is intersected by t edges of T̄, t ≥ 1. We now show that v_{i}v_{j} can be inserted in T̄ by flipping at most 2t edges. To show this, it is enough to show that by flipping at most two edges of T̄ we can obtain a new triangulation of Q_{i,j} in which v_{i}v_{j} is intersected by t − 1 edges. Let u_{1}, u_{2}, ..., u_{m} be the vertices of Q_{i,j} between v_{i} and v_{j} in the clockwise direction. At least one of these vertices, say u_{l}, is a convex vertex of Q_{i,j}; otherwise, v_{i} and v_{j} would not be visible in Q_{n}. If in T̄,

Suppose Q_{n} has k reflex vertices labelled v_{i_{1}}, ..., v_{i_{k}} such that i_{1} < i_{2} < ... < i_{k}. For each j = 1, 2, ..., k let R_{j} be the shortest polygonal chain contained in Q_{n} joining v_{i_{j}} to v_{i_{j+1}}, addition taken mod k. Finally let R = R_{1} ∪ ... ∪ R_{k}.

A polygon Q_{n} is called a spiral polygon if the vertices of Q_{n} can be labelled v_{1}, v_{2}, ..., v_{s}, v_{s+1}, ..., v_{n} such that v_{1}, v_{2}, ..., v_{s} are reflex vertices of Q_{n} and v_{s+1}, ..., v_{n} are convex vertices of Q_{n}. We can prove the following lemma 8 and lemma 9. We omit their proof here, for detail, see [11].

Lemma 8: Let Q_{n} be a spiral polygon, then the diameter of G_{T} (Q_{n}) is at most 2n − 6.

Lemma 9: Any edge joining two vertices of Q_{n} intersects at most two edges of R. Moreover, if e is an edge of R and T is any triangulation of Q_{n} , then either e is an edge of T or e is a proper diagonal of T.

Lemma 10: Let T be any triangulation of Q_{n}, then all the edges of R can be inserted in T using at most 4(n − 3) flips.

Proof: Let T be any triangulation of Q_{n}, w be any edge of T. Using Lemma 9, we know that w intersects at most two edges of R. Since T has n − 3 edges, the number of intersections between the edges of T and those of R is at most 2(n − 3). But all edges of R are proper edges of T, each of these intersections can be removed by flipping at most two edges. After flipping at most 4(n − 3) edges we can insert in T all the edges of R.

Theorem 6: Let Q_{n} be a simple polygon with k reflex vertices. then the diameter of G_{T} (P_{n}) is at most O(n + k^{2}).

Proof: Let T and T̄ be any two triangulation of Q_{n}. Using Lemma 10, by flipping at most 4(n − 3) edges, we can transform each of them into triangulations T_{1} and T̄_{1} respectively of Q_{n} such thet each of them contains all the edges of R. The edges of R induce a partition of Q_{n} into a set of polygons of either one of these two types:

(1) At most k convex or spiral polygons Q^{1}, ..., Q^{m}, m ≤ k bounded by edges of Q_{n} and edges of R.

(2) A set of polygons R_{1}, ..., R_{s} bounded by the edges of R such that the total number of edges of these polygons is at most k.

Notice that the total number of edges bounding Q^{1}, ..., Q^{m} is at most n + k. Both of T_{1} and T̄_{1} induce triangulations of Q^{1}, ..., Q^{m} which may be different. Since each Q^{1}, ..., Q^{m} is a spiral or a convex polygon, using Lemma 8 we know the triangulations induced by T_{1} in Q^{1}, ..., Q^{m} can be transformed into those induced by T̄_{1} in Q^{1}, ..., Q^{m} using at most 2((n + k) − 3) flips. Since the total number of edges bounding all the polygons in R_{1}, ..., R_{s} is at most k, using theorem 3, the triangulations induced in them by T_{1} and T̄_{1} can be transformed into each other with at most O(k^{2}) flips. Theorem 4 follows.

References

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

[2] T. Shermer, Recent results in Art Galleries. Proceedings of the IEEE. 1384-1399, 1992

[3] J. Urrutia, Art Gallery and Illumination Problems. To appear in Handbook on Computational Geometry.

[4] V. Chvatal, A Combinatorial Theorem in Plane Geometry. J, Combin. Theory ser. B, 39-41, 18(1975)

[5] S. Fisk, A Short Proof of Chvatal’s Watchman Theorem, J.Combin. Theory ser. B, 374, 24(1978)

[6] M. R. Garey, D. S. Johnson, F. P. Preparate, R. E. Tarjan, Triangulating a Simple Polygon. Info. Proc. Let., 175-179, 7(1978)

[7] R. E. Tarjan, C. J. Van Wyk, An O(n log log n) time Algorithm for Triangulatiing Simple Polygons. SIAM Journal on Computing, 143-178, 17(1988)

[8] B. Chazelle, J. Incerpi, Triangulating a Polygon by divide-and-conguer. Proc. 21st Allerton Conf., Monticello, 447-455, 1983

[9] D. G. Kirkpatrick, M. M. Klawe, R. E. Tarjan, O(n log log n) Polygon Triangulation with Simple Data Structures. Proc. 6th Ann. ACM Symp. Comput. Geom., 34-43, 1990

[10] B. Chazelle, Triangulating a Simple Polygon in Linear Time. Discrete and Computational Geometry 6, 485-524, 1991

[11] F. Hurtato, M. Noy, J. Urrutia, Flipping Edges on Triangulations, to appear

[12] D. Avis, G. T. Toussaint, An efficient Algorithm for Decomposing a Polygon into Star-Sharped Pieces, Pattern Recognition, 295-298, 131(1981a)

[13] D. D. Sleator, R. E. Tarjan, W. P. Thurstan, Rotation distance, Triangulations and Hyperbolic Geometry, J. Am. Math. Soc. 1: 647-682, 1988

[14] F. Hurtado, M. Noy, The Graph of Triangulations of a Convex Polygon, Report MA2-IR-94-13, Universitat Politecnica de Catalunya

[15] W. T. Tutte, The factorization of a planar graph. J. London Math. 22, 107-111, 1947

[16] J. Czyzowicz, E. Rivera-Campo, N. Santoro, J. Urrutia, J. Zaks, Guarding rectangular art galleries. Discrete Mathematics 50, 149-157, 1994