Lecture 6: Polygon Triangulation: The Art Gallery Problem
Reading: Chapter 3 in the 4M's.
Simple Polygons: Today we begin study of the problem of triangulating
polygons. We introduce this problem by way of a cute example in the
field of combinatorial geometry. We begin with some definitions. A
polygonal curve is a finite sequence of line segments, called edges
joined end to end. The endpoints of the edges are vertices. For
example, let v(0), v(1), ... ,v(n) denote the set of n + 1 vertices,
and let e(1), e(2), ... , e(n) denote a sequence of n edges, where e(i)
= v(i-1) to v(i) . A polygonal curve is closed if the last endpoint
equals the first v(0) = v(n) . A polygonal curve is simple if it is not
self intersecting. More precisely this means that each edge e(i) does
not intersect any other edge, except for the endpoints it shares with
its adjacent edges.
Figure 23: Polygonal curves, (left) a polygonal curve (middle) closed
curve (right) simple, closed curve
The famous
Jordan curve theorem states that every simple closed plane
curve divides the plane into two regions (the interior and the
exterior). (Although the theorem seems intuitively obvious, it is
quite difficult to prove.) We define a polygon to be the region of the
plane bounded by a simple, closed polygonal curve. The term simple
polygon is also often used to emphasize the simplicity of the
polygonal curve. We will assume that the vertices are listed in
counterclockwise order around the boundary of the polygon.
Art Gallery Problem: We say that two points x and y in a simple
polygon can see each other (or x and y are visible) if the open line
segment xy lies entirely within the interior of P . If we think of a
polygon as the floor plan of an art gallery, consider the problem of
where to place ``guards'', and how many guards to place, so that every
point of the gallery can be seen by some guard. Victor Klee posed the
following question: Suppose we have an art gallery whose floor plan
can be modeled as a polygon with n vertices. As a function of n, what
is the minimum number of guards that suffice to guard such a gallery?
Observe that are you are told about the polygon is the number of
sides, not its actual structure. We want to know the fewest number of
guards that suffice to guard all polygons with n sides.
Before getting into a solution, let's consider some basic facts. Could
there be polygons for which no finite number of guards suffice? It
turns out that the answer is no, but the proof is not immediately
obvious. You might consider placing a guard at each of the
vertices. Such a set of guards will suffice in the plane. But to show
how counterintuitive geometry can be, it is interesting to not that
there are simple nonconvex polyhedra in 3 space, such that even if you
place a guard at every vertex there would still be points in the
polygon that are not visible to any guard. (As a challenge, try to
come up with one with the fewest number of vertices.)
An interesting question in combinatorial geometry is how does the
number of guards needed to guard any simple polygon with n sides grow
as a function of n? If you play around with the problem for a while
(trying polygons with n = 3, 4, 5, 6 ... sides, for example) you will
eventually come to the conclusion that floor(n/3) is the right
value. The figure above shows a worst case example, where floor(n/3)
guards are required. A cute result from combinatorial geometry is that
this number always suffices. The proof is based on three concepts:
polygon triangulation, dual graphs, and graph coloring. The remarkably
clever and simple proof was discovered by Fisk.
Figure 24: Guarding sets.
Theorem: (The Art Gallery Theorem) Given a simple polygon with n
vertices, there exists a guarding set with at most floor(n/3) guards.
Before giving the proof, we explore some aspects of polygon
triangulations. We begin by introducing a triangulation of P . A
triangulation of a simple polygon is a planar subdivision of (the
interior of) P whose vertices are the vertices of P and whose faces
are all triangles. An important concept in polygon triangulation is
the notion of a diagonal, that is, a line segment between two vertices
of P that are visible to one another. A triangulation can be viewed as
the union of the edges of P and a maximal set of noncrossing
diagonals.
Lemma: Every simple polygon with n vertices has a triangulation
consisting of n - 3 diagonals and n - 2 triangles.
We'll leave the proof as an exercise. The proof is based on the fact
that given any n vertex polygon, with n >= 4 it has a diagonal. (This
may seem utterly trivial, but actually takes a little bit of work to
prove. In fact it fails to hold for polyhedra in 3 space.) The
addition of the diagonal breaks the polygon into two polygons, of say
m 1 and m 2 vertices, such that m(1) +m(2) = n + 2 (since both share
the vertices of the diagonal). Thus by induction, there are (m(1) - 2)
+ (m(2) - 2) = n + 2 - 4 = n - 2 triangles total. A similar argument
holds for the case of diagonals.
It is a well known fact from graph theory that any planar graph can be
colored with 4 colors. (The famous 4 color theorem.) This means that
we can assign a color to each of the vertices of the graph, from a
collection of 4 different colors, so that no two adjacent vertices
have the same color. However we can do even better for the graph we
have just described.
Lemma: Let T be the triangulation graph of a triangulation of a simple
polygon. Then T is 3 colorable.
Proof: For every planar graph G there is another planar graph G'
called its dual. The dual G' is the graph whose vertices are the faces
of G, and two vertices of G' are connected by an edge if the two
corresponding faces of G share a common edge. Since a triangulation
is a planar graph, it has a dual, shown in the figure below. (We do
not include the external face in the dual.) Because each diagonal of
the triangulation splits the polygon into two, it follows that each
edge of the dual graph is a cut edge,
Figure 25: Polygon triangulation and a 3 coloring.
meaning that its deletion would disconnect the graph. As a result it
is easy to see that the dual graph is a free tree (that is, a
connected, acyclic graph), and its maximum degree is 3. (This would
not be true if the polygon had holes.)
Figure 26: Dual graph of triangulation.
The coloring will be performed inductively. If the polygon consists of
a single triangle, then just assign any 3 colors to its vertices. An
important fact about any free tree is that it has at least one leaf
(in fact it has at least two). Remove this leaf from the tree. This
corresponds to removing a triangle that is connected to the rest
triangulation by a single edge. (Such a triangle is called an ear.) By
induction 3 color the remaining triangulation. When you add back the
deleted triangle, two of its vertices have already been colored, and
the remaining vertex is adjacent to only these two vertices. Give it
the remaining color. In this way the entire triangulation will be 3
colored. We can now give the simple proof of the guarding theorem.
Proof: (of the Art Gallery Theorem:) Consider any 3 coloring of the
vertices of the polygon. At least one color occurs at most n/3
time. (Otherwise we immediately get there are more than n vertices, a
contradiction.) Place a guard at each vertex with this color. We use
at most floor(n/3) guards. Observe that every triangle has at least one
vertex of each of the three colors (since you cannot use the same color
twice on a triangle). Thus, every point in the interior of this
triangle is guarded, implying that the interior of P is guarded. A
somewhat messy detail is whether you allow guards placed at a vertex
to see along the wall. However, it is not a difficult matter to push
each guard infinitesimally out from his vertex, and so guard the
entire polygon.
---------------------------------------------------------------
The Polygon Triangulation Problem: Triangulating simple polygons is an
operation used in many other applications where complex shapes are to
be decomposed into a set of disjoint simpler shapes. There are many
applications in which the shapes of the triangles is an im portant
issue (e.g. skinny triangles should be avoided) but there are equally
many in which the shape of the triangle is unimportant. We will
consider the problem of, given an arbitrary simple polygon, compute
any triangulation for the polygon.
This problem has been the focus of computational geometry for many
years. There is a simple naive polynomial time algorithm, based on
adding successive diagonals, but it is not partic ularly
efficient. There are very simple O(n log n) algorithms for this
problem that have been known for many years. A longstanding open
problem was whether there exists an O(n) time algorithm. The problem
was solved by Chazelle in 1991, but the algorithm is so amazingly
intricate, it could never compete with the practical but
asymptotically slower O(n log n) algorithms. In fact, there is no
known algorithm that runs in less than O(n log n) time, that is really
practical enough to replace the standard O(n log n) algorithm, which
we will discuss.
We will present one of many known O(n log n) algorithms. The approach
we present today is a two step process (although with a little
cleverness, both steps can be combined into one algorithm). The first
is to consider the special case of triangulating a monotone
polygon. After this we consider how to convert an arbitrary polygon
into a collection of disjoint monotone polygons. Then we will apply
the first algorithm to each of the monotone pieces. The former
algorithm runs in O(n) time. The latter algorithm runs in O(n log n)
time.
Monotone Polygons: A polygonal chain C is said to be strictly monotone
with respect to a given line L, if any line that is orthogonal to L
intersects C in at most one point. A chain C is monotone with respect
to L if each line that is orthogonal to L intersects C in a single
connected component. Thus it may intersect, not at all, at a single
point, or along a single line segment. A polygon P is said to be
monotone with respect to a line L if its boundary, d(P) , can be split
into two chains, each of which is monotone with respect to L.
Figure 27: Monotonicity.
Henceforth, let us consider monotonicity with respect to the x
axis. We will call these polygons horizontally monotone. It is easy to
test whether a polygon is horizontally monotone. How?
(a) Find the leftmost and rightmost vertices (min and max x
coordinate) in O(n) time.
(b) These vertices split the polygon's boundary into two chains, an
upper chain and a lower chain. Walk from left to right along each
chain, verifying that the x coordinates are nondecreasing.
This takes O(n) time.
As a challenge, consider the problem of determining whether a polygon
is monotone in any (unspecified) direction. This can be done in O(n)
time, but is quite a bit harder.
This course is modeled on the Computational Geometry Course taught by
Dave Mount, at the University of Maryland. These notes are
modifications of his Lecture Notes, which are copyrighted as follows:
Copyright, David M. Mount, 2000, Dept. of Computer Science,
University of Maryland, College Park, MD, 20742. These lecture notes
were prepared by David Mount for the course CMSC 754, Computational
Geometry, at the University of Maryland, College Park. Permission to
use, copy, modify, and distribute these notes for educational purposes
and without fee is hereby granted, provided that this copyright notice
appear in all copies.