Lesson 9. The Art Gallery Problem
I628E – Information Processing Theory

Giovanni Viglietta
johnny@jaist.ac.jp

JAIST – January 20, 2020

Art Gallery Problem
Klee, 1973: Given a polygon, choose a minimum number ofpoints (called “guards”) that collectively see its whole interior.

Art Gallery Problem
Klee, 1973: Given a polygon, choose a minimum number ofpoints (called “guards”) that collectively see its whole interior.

Art Gallery Problem
Klee, 1973: Given a polygon, choose a minimum number ofpoints (called “guards”) that collectively see its whole interior.

Chvátal’s lower boundChvátal, 1975: For every n, there are polygons with n vertices
where n3 guards are necessary:

No point in this polygon can see the tip of more than one “spike”.
Hence we need at least one guard per spike.

Fisk’s solution
Fisk, 1978: For every polygon with n vertices,
are sufficient.

n3vertex guards

Fisk’s solution
Fisk, 1978: For every polygon with n vertices,
are sufficient.

n3Step 1: triangulate the polygon.

vertex guards

Fisk’s solution
Fisk, 1978: For every polygon with n vertices,
are sufficient.

n3vertex guards

Step 2: since the dual graph of the triangulation is a tree,
we can inductively 3-color the vertices.

Fisk’s solution
Fisk, 1978: For every polygon with n vertices,
are sufficient.

n3vertex guards

Step 3: choose the vertices of the less frequent color as guards.

Guarding orthogonal polygons
What if the polygon is orthogonal (i.e., its edges meet at rightangles)? Can we guard it with fewer guards?
 
Chvátal’s lower bound of n3 guards no longer holds...
But the following example shows that there are orthogonal
polygons with n vertices where n4 guards are necessary:

Are

n
4

guards sufficient for every orthogonal polygon?

Guarding orthogonal polygons
Kahn et al., 1983: For every orthogonal polygon with n vertices,n
4 vertex guards are sufficient.

Indeed, any orthogonal polygon can be decomposed into convex
quadrilaterals, which induce a 4-coloring of the vertices.

Guarding orthogonal polygons
We give an alternative proof, essentially due to O’Rourke:

Any orthogonal
polygon with r reflex vertices can be decomposed
into 2r + 1 L-shaped pieces, each of which requires only 1 guard.

Guarding orthogonal polygons
Are the two statements equivalent? Isr
2+ 1 the same as

n
4

?

Observation: In any orthogonal polygon, n = 2r + 4.
Indeed, recall that the sum of the internal angles of a polygon withn vertices is π(n − 2).
Each of the r reflex vertices gives a contribution of 3π/2,
Each of the n − r convex vertices gives a contribution of π/2.
So, π(n − 2) = r · 3π/2 + (n − r) · π/2.
Solving for n, we get n = 2r + 4.
Now,

n
4

=

 2r+4 
4

=

r
2

+ 1.

Guarding orthogonal polygons
Here goes O’Rourke’s proof:

We draw horizontal cutlines at reflex vertices, subdividing thepolygon into rectangles. We reason by induction on r...

Guarding orthogonal polygons
If two reflex vertices are endpoints of the same cutline, we can cut
the polygon and work on the two resulting subpolygons separately:

P

P1
P2

Indeed, if P , P1 , P2 have r, r1 , r2 reflex vertices respectively, thenr = r1 + r2 + 2 (two reflex vertices are resolved by the cutline).
  
By induction, P1 and P2 can be guarded by r21 + 1 and r22 + 1 
guards, respectively. In total, this is r1 +r22 +2 + 1 = 2r + 1.
 
So, P can be guarded by 2r + 1 guards.

Guarding orthogonal polygons
Therefore, we may assume that each cutline contains only one
reflex vertex:

Note that each rectangle has at most 2 neighboring rectangles
above and at most 2 below. (Why?)Guarding orthogonal polygons
A cutline is odd if it splits the polygon in two parts, one of whichcontains an odd number of reflex vertices:

Odd cutlines turn out to be very desirable!

Guarding orthogonal polygons
Why are odd cutlines desirable?
Because, if we cut a polygon P along an odd cutline, we can workon the two resulting subpolyongs P1 and P2 separately.
Indeed, if P , P1 , P2 have r, r1 = 2k + 1, r2 reflex vertices, thenr = 2k + r2 + 2 (one reflex vertex is resolved by the cutline).
 
By induction, P1 and P2 can be guarded by r21 + 1 = k + 1 and
j
k
r 
 
2k+r2 +2
2+
1
guards.
In
total,
thisis+ 1 = 2r + 1.
22
 
So, P can be guarded by 2r + 1 guards.

Guarding orthogonal polygons
Why are odd cutlines desirable?
Because, if we cut a polygon P along an odd cutline, we can workon the two resulting subpolyongs P1 and P2 separately.
Indeed, if P , P1 , P2 have r, r1 = 2k + 1, r2 reflex vertices, thenr = 2k + r2 + 2 (one reflex vertex is resolved by the cutline).
 
By induction, P1 and P2 can be guarded by r21 + 1 = k + 1 and
j
k
r 
 
2k+r2 +2
2+
1
guards.
In
total,
thisis+ 1 = 2r + 1.
22
 
So, P can be guarded by 2r + 1 guards.
Observation: If r is even, then every cutline of P is odd.
Indeed, a cutline resolves one reflex vertex, so r1 + r2 must be odd,
implying that either r1 or r2 is odd.

Guarding orthogonal polygons
Observation: If a rectangle has exactly one neighboring rectangle
above and exactly one below, then there is an odd cutline.

even cutline
odd cutline

Guarding orthogonal polygons
The only case left to consider is the one where there is an odd
total number of reflex vertices, and no rectangle has exactly one
neighboring rectangle above and exactly one below:

Guarding orthogonal polygons
The only case left to consider is the one where there is an odd
total number of reflex vertices, and no rectangle has exactly one
neighboring rectangle above and exactly one below:

To guard this type of polygon, we sort the reflex vertices
horizontally, and we place guards on the odd ones.

NP-hardness
So far we have given optimal bounds on the number of guards that
hold for every (orthogonal) polygon.
But certainly, for most polygons, much fewer than n3 guards are enough!
What if we wanted to find an optimal positioning of guards forevery given polygon?
Lee and Lin, 1986: The problem of computing the minimum
number of guards for any given polygon is NP-hard.
The original proof reduces from 3-SAT. We will give a reduction
from Vertex Cover, essentially due to Katz and Roisman, which
has the advantage of producing orthogonal polygons.
Art Gallery Problem (decision version):
Input: An orthogonal polygon P and an integer k.
Output: YES if P can be guarded by at most k guards placed on
its boundary. NO otherwise.

NP-hardness: Vertex Cover
The reduction is from the NP-complete problem Vertex Cover:Vertex Cover (decision version):
Input: a graph G = (V, E) and an integer k.
Output: YES if there is a subset U ⊆ V of exactly k vertices suchthat each edge in E has at least one endpoint in U . NO otherwise.

k=3

NP-hardness: edge gadget
We represent an edge (vi , vj ) by this gadget:vi

vj

At least 3 guards need to be placed within the gadget.
But placing 3 guards leaves a small triangle uncovered,
which requires an “external contribution” from a 4th guard.

NP-hardness: edge gadget
We represent an edge (vi , vj ) by this gadget:vi

vj

At least 3 guards need to be placed within the gadget.
But placing 3 guards leaves a small triangle uncovered,
which requires an “external contribution” from a 4th guard.

NP-hardness: edge gadget
We represent an edge (vi , vj ) by this gadget:vi

vj

At least 3 guards need to be placed within the gadget.
But placing 3 guards leaves a small triangle uncovered,
which requires an “external contribution” from a 4th guard.

NP-hardness: representing vertices
This “contribution” must come from an external guard placed at a
specific location, which represents an endpoint of the edge.

vj

vi

vi

vj

To minimize guards, we would like the same external guard tocontribute to many edge gadgets...

NP-hardness: representing vertices
This “contribution” must come from an external guard placed at a
specific location, which represents an endpoint of the edge.

vj

vi

vi

vj

To minimize guards, we would like the same external guard tocontribute to many edge gadgets...

NP-hardness: representing vertices
This “contribution” must come from an external guard placed at a
specific location, which represents an endpoint of the edge.

vj

vi

vi

vj

To minimize guards, we would like the same external guard tocontribute to many edge gadgets...

NP-hardness: full construction
We tweak each edge gadget so that it can receive contributions
only from the two locations corresponding to its endpoints in G.
v1

v2

v3

v4

v5

edge gadgets

This polygon can be guarded by 3|E| + k guards
if and only if the edges of G can be covered by k vertices.

3-dimensional art galleries
What if our art gallery is not a 2D polygon but a 3D polyhedron?
Do the previous results generalize to 3D shapes?

In this setting, we consider both vertex guards and edge guards.

Convex partitions of polyhedra
Most 2D techniques involve decomposing polygons into a linear
number of convex parts, and then placing a guard in each part.
Unfortunately, no such partitions are possible in 3D.
Chazelle, 1984: There are polyhedra with n vertices that can only
be partitioned into Ω(n2 ) convex parts:
Although in this polyhedron all edges are straightline segments, the central
warped region has the shapeof a hyperbolic paraboloid.
A convex set can only havea small part of its volume
inside this region.

Vertex-guarding orthogonal polyhedra
The Art Gallery Problem for vertex guards may be unsolvable,
even in some orthogonal polyhedra:

Some points in the central region are invisible to all vertices!
(Hence this polyhedron is not even decomposable into tetrahedra.)

Point-guarding orthogonal polyhedra
So, we must consider point guards that do not lie on vertices.
√
But there are orthogonal polyhedra that require Ω(n n) guards!

outer view

cross section

Paterson and Yao, 1992: Every orthogonal polyhedron yields a√
BSP tree of size O(n n), hence this many guards suffice.

Edge-guarding polyhedra
Edge guards are more effective than vertex guards:
placing an edge guard on every (reflex) edge is sufficient. (Why?)Can we do better? What about orthogonal polyhedra?

Placing edge guards only on theedges oriented in one of the 3 directions is sufficient (indeed, the crosssections orthogonal to the chosen
direction are collections of polygons
whose vertices hold guards).

Choosing
the direction with fewest edges yields an upper bound of
m
edge
guards, where m is the total number of edges.
3
Can we refine this strategy?

Edge-guarding polyhedra
Edge guards are more effective than vertex guards:
placing an edge guard on every (reflex) edge is sufficient. (Why?)Can we do better? What about orthogonal polyhedra?

Placing edge guards only on theedges oriented in one of the 3 directions is sufficient (indeed, the crosssections orthogonal to the chosen
direction are collections of polygons
whose vertices hold guards).

Choosing
the direction with fewest edges yields an upper bound of
m
edge
guards, where m is the total number of edges.
3
Can we refine this strategy?

Edge-guarding polyhedra
Edge guards are more effective than vertex guards:
placing an edge guard on every (reflex) edge is sufficient. (Why?)Can we do better? What about orthogonal polyhedra?

Placing edge guards only on theedges oriented in one of the 3 directions is sufficient (indeed, the crosssections orthogonal to the chosen
direction are collections of polygons
whose vertices hold guards).

Choosing
the direction with fewest edges yields an upper bound of
m
edge
guards, where m is the total number of edges.
3
Can we refine this strategy?

Guarding with parallel edges
V., 2011: In the cross sections, instead of placing guards on allvertices, it is sufficient to choose vertices of only 3 “types”:

This selection of guards remains consistent through cross sections.

Guarding with parallel edges
There are 8 types of vertices in total, and we picked only 3 of them:
α

β

γ

δ

α′

β′

γ′

δ′

This selection works because, for every point p, we can shoot a ray
upward and then shift it to the left until we hit a vertex v: thisvertex is of one of the 3 chosen types, and therefore guards p:
v

v

q

q

q

p

p

p

v

Guarding with parallel edges
Let mx be the total number of edges oriented in direction x.
Each of these edges is of one of the 8 types, so we have
α + β + γ + δ + α0 + β 0 + γ 0 + δ 0 = mx .
There are 4 symmetric ways of choosing 3 edge types to obtain avalid guard placement:
α + β0 + γ0,

The sum isδ + β0 + γ0,
β + α0 + δ 0 ,γ + α0 + δ 0 .

α + β + γ + δ + 2α0 + 2β 0 + 2γ 0 + 2δ 0 ≤ 2mx .
 Hence, one of the 4 choices yields at most m2x edges.
Byselecting the direction x that minimizes mx , we place at mostm
6 parallel edge guards, where m is the total number of edges.

Edge guards: lower bound for orthogonal polyhedra
 
So, m
6 edge guards are always m sufficient, and there areorthogonal polyhedra where 12 edge guards are necessary:Open problem: Arem
12edge guards always sufficient?

Edge-guarding general polyhedra
For general polyhedra, there are examples where
are necessary:m
6edge guards

Is there a non-trivial upper bound?
Urrutia et al., 2012: For every polhedron with m edges,edge guards are sufficient.

 27 
32 m

Edge-guarding general polyhedra
Each edge e may be of one of 4 classes based on the position of its
two incident faces with respect to the vertical plane α through e:
1. Both incident faces areon the left side of α.
e2

e1

e1

e3

e4

2. Both incident faces areon the right side of α.
3. The incident faces areon opposite sides of α,
and the polyhedronlies above e.

e2

e3

e4

4. The incident faces areon opposite sides of α,
and the polyhedronlies below e.

Edge-guarding general polyhedra
Lemma: If a point p in the polyhedron does not see any vertex,
then p sees edges of at least 2 different classes.
Proof: By contradiction.
Case 1: p sees only edges of class 1.

pConsider a vertical crosssection through p, and partition it into subpolygons
by shooting rays along theangle bisectors of the reflex vertices corresponding
to edges of class 1.

p lies in a convex subpolygon (why?), hence it sees its leftmost
vertex, which must correspond to an edge of class 2.
Contradiction!

Edge-guarding general polyhedra
Case 2: p sees only edges of class 3 and no vertices.

pPartition the polyhedron
into cells by drawing a vertical “wall” through eachedge. Note that each cell
has exactly two non-verticalfaces: “floor” and “ceiling”.

If the cell of p is convex, its floor must be a face of thepolyhedron, and so p sees all its vertices. If the cell of p is
non-convex, then p sees one of its vertical reflex edges, whose
bottom vertex must be a vertex of the polyhedron. Contradiction!

Edge-guarding general polyhedra

Strategy: Pick an edge set that covers all vertices and, among
the remaining edges, pick the ones in the 3 smallest classes.
 Lemma: The vertex set is covered by 38 m edges.
Proof: By classical matching theory (details omitted).
 So, we pick 83 m edges to cover all vertices,plus at most 34 of the remaining edges.
  
 
 27 
≤ 32
m edges.
In total, we picked 83 m + 34 m − 38 m
Open problem: Arem
6edge guards always sufficient?

Summary
We established some general bounds on the number of guards
for several 2D and 3D Art Gallery Problems:
General 2D polygons:

n

Orthogonal 2D polygons:

n

Orthogonal 3D polyhedra:

General 3D polyhedra:

3

vertex guards

vertex guards√
Θ(n n) point guards m  m
12 ∼ 6 edge guards m   27 
6 ∼ 32 m edge guards
4

We also showed that computing the minimum number of guards
is NP-hard, even for orthogonal polygons.

References
J. O’Rourke
Art gallery theorems and algorithms
Oxford University Press, 1987
M. J. Katz and G. S. Roisman“On guarding the vertices of rectilinear domains”
Computational Geometry vol. 39, 2008
G. Viglietta
Guarding and seraching polyhedra
Ph.D. Thesis, University of Pisa, 2012
J. Cano, C. D. Tóth, and J. Urrutia“Edge guards for polyhedra in 3-space”
In Proceedings of CCCG 2012

Assignment 1
Let the ground be the horizontal plane z = 0 in R3 .
A tower is defined as an orthogonal polyhedron T whose vertices
lie on the ground (z = 0) or above it (z > 0), such that theintersection between T and any vertical line is either empty or asegment with one endpoint on the ground.

z=0

We want to guard the external surface of a tower (above ground,i.e., excluding its “base”) by placing point guards at some of its
vertices. Give a good asymptotic lower bound on the number ofvertex guards required for a tower with n vertices.