ICCG 2022, Sharif UT, February 24, 2022

Guarding Weakly-Visible Polygons with Half-Guards
Hannah Miller Hillberg∗

Erik Krohn†

Alex Pahlow‡

Abstract
We consider a variant of the art gallery problem where
all guards are limited to seeing to the right inside aweakly-visible polygon. Guards that can only see in
one direction are called half-guards. In this paper, wegive a polynomial time approximation scheme for vertex
guarding a weakly-visible polygon with half-guards. We
then show NP-hardness for vertex guarding a weaklyvisible polygon with half-guards.
1

Introduction

An instance of the original art gallery problem takes as
input a simple polygon P . A polygon P is defined bya set of points V = {v1 , v2 , . . . , vn }. There are edges
connecting (vi , vi+1 ) where i = 1, 2, . . . , n − 1. There isalso an edge connecting (v1 , vn ). If these edges do notintersect other than at adjacent points in V (or at v1
and vn ), then P is called a simple polygon. The edges ofa simple polygon give us two regions: inside the polygon
and outside the polygon. For any two points p, q ∈ P ,we say that p sees q if the line segment pq does not
go outside of P . The art gallery problem seeks to finda guarding set of points G ⊆ P such that every pointp ∈ P is seen by a point in G. In this paper, we study
the vertex guarding problem which says that guards
are only allowed to be placed at the vertices V . The
optimization problem is defined as finding the smallest
such G.
1.1

Previous Work

There are many results about guarding art galleries.
Several results related to hardness and approximations
can be found in [1, 5, 6, 10].
Additional Structure. Due to the inherent difficultyin fully understanding the art gallery problem for simple
polygons, there has been some work done guarding polygons with additional structure, see [3, 8] for example. In
this paper we consider weakly-visible polygons that we∗ Department of Computer Science, University of Wisconsin Oshkosh, Oshkosh, Wisconsin, USA hillbergh@uwosh.edu† Department of Computer Science, University of Wisconsin Oshkosh, Oshkosh, Wisconsin, USA krohne@uwosh.edu
Supported by the Faculty Development Sabbatical Program at the
University of Wisconsin - Oshkosh.
‡ Department of Computer Science, University of Wisconsin Oshkosh, Oshkosh, Wisconsin, USA pahloa45@uwosh.edu

Figure 1: A WV-polygon where p sees q and every pointin the polygon is seen by a point on e = [l, r] or sees apoint on e.
will describe below. Motivated by the fact that manycameras/sensors cannot sense in 360°, referred to as fullguards in this paper, we study guards that can sense in
180°, referred to as half-guards. We restrict the problem
even further by only allowing these half-guards to see tothe right. Even with these restrictions, the problem isdifficult to solve.
1.2

Definitions

A weakly-visible polygon (WV-polygon) P contains anedge e = (l, r) such that every point in P sees at least
one point on edge e. The usual definition of sees saysthat for any two points p and q inside of the polygon, if
the line segment connecting p and q does not go outsideof the polygon, then p sees q. Let p.x be the x-coordinate
for point p. In this paper, for a point p to see a point
q, it must be the case that p.x ≤ q.x, see Figure 1. The
definition of a WV-polygon is slightly modified to saythat it contains an edge e = (l, r) such that every point
in P sees (or is seen by) at least one point on edge e.
1.3

Our Contribution

NP-hardness has been shown for many variants of theart gallery problem. In many of those reductions, guards
are allowed to see in all directions. If the problem isrestricted enough, it can become polynomially time solvable, for example, see [4, 9]. If the polygon is restricted
to be a WV-polygon, restrict guards to be at the vertices
and only allow them to see to the right, we show thateven with these many restrictions, the problem is still
NP-hard.

5th Iranian Conference on Computational Geometry

Figure 2: A WV-polygon that requires Ω(n) half-guards
that see to the right.
Ashur et al. [2] give a polynomial time approximation
scheme (PTAS) for minimum dominating set in terrainlike graphs, which we will describe later. They then showthat several families of polygons have a visibility graphthat is terrain-like. One such family is WV-polygons.
However, their analysis does not imply that the visibility
polygon of vertex guarding a WV-polygon with halfguards is terrain-like. We provide additional observationsin this paper that show the visibility polygon is terrainlike. There are WV-polygons P that can be completely
guarded with one full-guard but require Ω(n) half-guards
considered in this paper, see Figure 2.
The remainder of the paper is organized as follows.
Section 2 provides a PTAS for vertex guarding a WVpolygon using half-guards. Section 3 shows NP-hardness
for vertex guarding a WV-polygon using half-guards.
Finally, Section 4 gives a conclusion and future work.
2

PTAS for Vertex Guarding a WV-Polygon with
Half-Guards

In this section, we show that the visibility graph of a WVpolygon with half-guards is terrain-like. The visibility
graph is a graph G = (V, E) such that V corresponds tovertices in the WV-polygon and the edges E correspondto vertices that can be seen by other vertices. Then we
use Theorem 1 from [2], see Appendix, to show that a
PTAS exists for vertex guarding a WV-polygon withhalf-guards.
Using the definition from [2], a graph G = (V, E) is
terrain-like if one can assign a unique integer from therange [1, |V |], where |V | is the number of vertices in thepolygon, to each vertex in V , such that, if both (i, k)and (j, l) are in E, for any i < j < k < l, then so is (i, l).
Much of the proof from [2] assumes that the WVpolygon lies above the WV-edge by placing guards at l
and r and cutting off the portion of the polygon beneaththe WV-edge, see Figure 3(left). When every vertex
under consideration lies above this WV-edge, the orderclaim holds and the visibility graph is terrain-like. However, consider doing the same thing for a WV-polygon
using half-guards that see to the right. In this case, theremaining portion of the polygon cannot be assumed to
be above the WV-edge. As shown in the shaded partsof Figure 3(right), the regions to the left of the placed
guards are not seen. More so, a guard placed at l will

Figure 3: On the left, a full-guard placed at l and r
cuts off the polygon below the WV-edge. On the right,
the shaded regions are still unseen after half-guards areplaced at l and r.

Figure 4: Example of vx and Lemma 1.
not dominate a guard placed in the shaded region to
the left of l. If the guards were full-guards, these regions would be seen and the l guard would dominate
any optimal guard placed in this region. We show thateven though these portions of the polygon are unseen
and optimal guards can lie in these regions, the visibility
graph connecting vertices to the guards that see them isstill terrain-like.
2.1

Visibility Polygon is Terrain-Like

We will prove that the visibility polygon of the vertices is
terrain-like by using the following modified order claim
in WV-polygons that applies to full-guards as well as
half-guards. Order the vertices walking in clockwiseorder starting from l: (v1 = l, v2 , v2 , . . . , vn = r).
Modified Order Claim: Assume that guards are placed atl and r and then consider the remaining unseen vertices.
If 4 vertices are in order such that a < b < c < d, thenif a sees c and b sees d, then a sees d.
As shown in [2], if all of a, b, c and d lie above the WVedge, then the order claim holds and a sees d. If botha and d are below the WV-edge and both see l or bothsee r, then the same arguments from [2] hold for why amust see d.
The following lemmas are given for WV-polygons that
apply to full-guards. For simplicity of the arguments, we
assume that the WV-edge is parallel to the x-axis. Letvx be the vertex such that every vertex [vx+1 , vn−1 ] isbelow the WV-edge. If no vertex meets this requirement,
then vx = vn = r. In other words, vx is the last vertex
that is above the WV-edge when walking clockwise froml to r, see Figure 4(left).

ICCG 2022, Sharif UT, February 24, 2022

Returning to the discussion with respect to half-guards.
Lemma 5 applies to full-guards. A modification ofLemma 5 is given to apply to half-guards:
Lemma 6 If the order claim is broken, then at least
one of a, b, c or d is seen by either l or r.

Figure 5: If a is blocked from d, then the blocker mustbe either l or r.
Lemma 1 If vi ∈ [v1 , vx ], then no vertex vk ∈ [vi+1 , vn ]can block vi from l.
Proof. Assume that vk blocks vi from seeing l. If thishappens, then vk is to-the-left (when looking from l)of the lvi line segment, see Figure 4(right). Let x be
any point on the WV-edge that vi sees. The xvi line
segment is to the right (when looking from l) of thelvi line segment. This line segment is also blocked by
vk which means vi does not see any point on the WVedge. The polygon is not weakly-visible and we have acontradiction.
□
Corollary 2 Let vw be the vertex such that every vertex[v2 , vw−1 ] is below the WV-edge. If no vertex meets thisrequirement, then vw = v1 = l. If vi ∈ [vw , vn ], then novertex vk ∈ [v1 , vi−1 ] can block vi from r.
Lemma 3 Consider 4 vertices in a WV-polygon suchthat a < b < c < d, a sees c, b sees d and a does notsee d. If a is below the WV-edge and d is above theWV-edge, then a and d must both see l.
Proof. Since a is below the WV-edge, a must see l. If
a does not see l, then the polygon is not weakly-visible.
If d does not see l, then by Lemma 1, the vi blocker
for d must lie in the (l, d) range. If vi ∈ (b, d), then vi
would block b from d. If vi = (a, b], then a would notsee c. It is not possible for vi = a since a is below theWV-edge. Lastly, if that vertex vi ∈ (l, a), then it would
block a from seeing l, see Figure 5(left). Since there is
no way to block d from l, d must see l.
□Corollary 4 Consider 4 vertices in a WV-polygon suchthat a < b < c < d, a sees c, b sees d and a does notsee d. If a is above the WV-edge and d is below theWV-edge, then a and d must both see r.
This brings us to our final Lemma with full-guards:
Lemma 5 If the order claim is broken, then a sees
either l or r and also, d sees either l or r.
Proof. If a < b < c < d, a sees c, b sees d, a does notsee d and a and d are both below the WV-edge, thena sees l and d sees r. This, along with Lemma 3 andCorollary 4, cover the remaining cases.
□

The complete proof of Lemma 6 is given in the appendix. In short, if the order claim is broken, at least
one of a, b, c or d must lie to the right of l or r and will
necessarily be seen by one of l or r.
The analysis from [2] is now used to show a PTAS
exists. First, one checks to see if the polygon can be
guarded with a constant number of guards of some appropriate size. If an optimal guarding set of this size
does not exist, then the first step of the algorithm is toplace guards at l and r and remove the vertices that lor r see from consideration as they are already guarded.
By Lemma 6, an order claim violation is not possible
since at least one of the vertices involved in breaking theorder claim has already been guarded by l or r and will
not be in the modified problem instance. In other words,
the visibility graph connecting vertices to the guards
that see them are vertices that are not seen by l nor r.
Since the order claim cannot be broken, when looking at
the visibility graph of vertices connected to the leftmost
and rightmost guards that see them, if i < j < k < l,(i, k) ∈ E and (j, l) ∈ E, then (i, l) ∈ E. With this claim,
the visibility graph for vertex guarding WV-polygons
with half-guards that see to the right is terrain-like.
It should also be noted that the orientation of thepolygon does not matter. For example, consider a polygon where the WV-edge is parallel to the y-axis andthe “main” part of the polygon is to the right of the
WV-edge, see Figure 6(left). In this instance, guards
placed at l and r still cause the order claim to not be
broken in the unguarded vertices that remain. Figure 6
shows polygons where the order claim will not be broken.
No matter the orientation of the WV-edge, Lemma 6
holds for half-guards as well as full-guards.
Since the visibility graph is terrain-like, we use Theorem 1 from [2] to state the following:
Theorem 7 There exists a PTAS for vertex guarding a
weakly-visible polygon with half-guards where half-guards
can only see to the right.

3

NP-hardness for Vertex Guarding a WV-Polygon
with Half-Guards

In this section, we provide a sketch for showing thatvertex guarding a WV-polygon with half-guards is NPhard. NP-hardness for terrain guarding with full-guards
was shown in [7], however, the entire terrain is not seen if
guards are only allowed to look down. In the appendix,

5th Iranian Conference on Computational Geometry

Figure 6: Shows the portion of the polygon “below” theWV-edge that is not seen by l or r.

see to the right. Such a proof works for all instances
except when the WV-edge is parallel to the y-axis andthe “inside” of the polygon is to the left of the WV-edge.
Whether or not this problem is NP-hard is left as an open
problem. Future work might include finding a better
approximation for the point guarding version of thisproblem. Insights provided in this paper may help withguarding polygons where the guard can choose to see
either left or right, or in other natural directions. One
may also be able to use these ideas when allowing guards
to see 180° but guards can choose their own direction,i.e. 180°-floodlights.
References[1] A. Aggarwal. The art gallery theorem: its variations, applications and algorithmic aspects. PhD
thesis, The Johns Hopkins University, 1984.

Figure 7: An overview of NP-hardness for WV-polygons.
we provide several new and updated gadgets to the
reduction from [7] to show that vertex guarding a terrain
with half-guards that only look down is NP-hard.
We will show how to use the terrain guarding hardness
result for guards that only see down to show that vertex
guarding a WV-polygon with half-guards that see tothe right is NP-hard. One can take the modified terrain
reduction, rotate it counterclockwise 90° and connect
vertex l to vertex r to create a WV-polygon that isvisible from the edge e = (l, r), see Figure 7(left). The
reduction holds the same way that it does for vertex
guarding a terrain with half-guards that only see down.
One will notice that when the WV-edge is rotatedslightly counterclockwise, the reduction still holds, see
Figure 7(right). The key visibilities from the guards
remain and the polygon is still weakly-visible. The reduction begins to fail whenever a guard visibility fromthe original reduction starts to have a negative slope. If
this happens, the guard no longer sees the distinguishedpoint(s) to its right. To account for this, the originalterrain is “stretched” such that none of the guard visibilities have a negative slope. Details of this stretchingare in the appendix.
4

Conclusion and Future WorkIn this paper, we present a PTAS for vertex guarding
WV-polygons with half-guards that see to the right.
This algorithm works regardless of the orientation of the
WV-edge. We also present an NP-hardness proof forvertex guarding a WV-polygon with half-guards that[2] S. Ashur, O. Filtser, M. J. Katz, and R. Saban.
Terrain-like graphs: Ptass for guarding weaklyvisible polygons and terrains. Computational Geometry, 101:101832, 2022.
[3] P. Bhattacharya, S. Ghosh, and B. Roy. Approximability of guarding weak visibility polygons. Discrete
Applied Mathematics, 228, 02 2017.
[4] M. C. Couto, P. J. de Rezende, and C. C. de Souza.
An exact algorithm for minimizing vertex guards on
art galleries. Int. Trans. Oper. Res., 18(4):425–448,
2011.
[5] S. Eidenbenz. Inapproximability results for guarding
polygons without holes. In ISAAC, pages 427–436,
1998.
[6] S. K. Ghosh. On recognizing and characterizing
visibility graphs of simple polygons. Discrete &Computational Geometry, 17(2):143–162, 1997.
[7] J. King and E. Krohn. Terrain guarding is np-hard.
SIAM J. Comput., 40(5):1316–1339, 2011.
[8] E. Krohn and B. J. Nilsson. Approximate guardingof monotone and rectilinear polygons. Algorithmica,
66(3):564–594, 2013.
[9] A. Kröller, T. Baumgartner, S. P. Fekete, and
C. Schmidt. Exact solutions and bounds for generalart gallery problems. ACM J. Exp. Algorithmics,
17, may 2012.
[10] D. T. Lee and A. K. Lin. Computational complexity of art gallery problems. IEEE Trans. Inform.
Theory, 32(2):276–282, March 1986.
[11] D. Lichtenstein. Planar formulae and their uses.
SIAM J. Comput., 11:329–343, 1982.

ICCG 2022, Sharif UT, February 24, 2022

Appendix
Theorem 1 from [2]Theorem There exists a PTAS for (general) minimum
dominating set in terrain-like graphs. That is, for any
ϵ > 0, there is a polynomial-time algorithm which, givena terrain-like graph G = (V, E) and two sets C, W ⊆ V ,returns Q ⊆ C such that Q dominates W and |Q| ≤(1 + ϵ) · OP T ; here OP T is the size of a minimum subset
of C that dominates W .

Figure 8: The left shows an overview of the NP-hardness
reduction for terrain guarding. The middle is a variablegadget. The right is a starting gadget.

Proof of Lemma 6
Proof. We break up this proof into several cases.

NP-hardness for Vertex Guarding a Terrain with HalfGuards

1. If a and d are both above the WV-edge, then theorder claim cannot be broken as shown in [2].
2. If a is below the WV-edge and d is above the WVedge, then by Lemma 3, a and d see l. It also
must be the case that a and d are to the left of l(otherwise l would see one of them). Since a seesl, d sees l, a sees (or is seen by) c and b sees (or isseen by) d, the entire ad line segment is surroundedby visibility lines that cannot be pierced. Therefore,a must see (or be seen by) d, a contradiction thatthe order claim was broken. Since a and d cannot
both be to the left of l, it must be that l sees oneof them.
3. If a is above the WV-edge and d is below the WVedge, then by Corollary 4, r sees (or is seen by) aand d. In order for r to not see a or d (and rather
be seen by both a and d), both must be to the leftof r. If b or c are below the WV-edge, then r will
see them. Therefore, b and c must be above theWV-edge. Since d sees b, it must be the case thatb is to the right of r. Since b is above and to theright of r, there must be a vertex that blocks r fromseeing b. By Corollary 2, the blocker for r to b must
be in the (b, r) range. If the blocker is in the (b, d)range, then d would not see b. If the blocker is in the(d, r) range, then d would not see r, a contradictionthat the polygon is weakly-visible. It must be thecase that r sees b.
4. If a and d are both below the WV-edge, a is to theleft of l and d is to the left of r, then in order for dto see b, it must be the case that the db line segment
goes below r forcing b to be to the right of r. Similar
to case 3, r sees b. Although not necessary for the
proof, using similar arguments, one can show that lsees c.
□Abusing notation, only in this section, we will assume
that half-guards can only see “down.” If we restrict
guards to be half-guards that see “down” in the terrain,
then the terrain guarding problem is still NP-hard. In
regular terrain guarding, a point p sees another point q
if the line segment connecting p and q does not go below
the terrain. In this half-guard variant, the point p sees q
only if the y-coordinate of p is greater than or equal to
the y-coordinate of q and the line segment connecting p
and q does not go below the terrain.
Sketch of Reduction
The terrain guarding reduction is from PLANAR 3SAT
[11] where an instance has n variables and m clauses.
The reduction works by assigning vertices on the terrain
to truth values of variables from the PLANAR 3SAT
instance. For each variable in the PLANAR 3SAT instance, variable gadgets are created such that the gadget
contains a vertex representing xi and vertex representing xi , see Figure 8(middle). These variable gadgets
are grouped together in chunks on the terrain. Figure8(left) shows an example of one such chunk that contains
one variable gadget for each variable in {x1 , x2 , . . . , xn }.
These chunks are replicated on the terrain such that a
guard placed at the xi vertex in the variable gadget ofxi in chunk Cj would require a guard to be placed at thexi vertex in another variable gadget in a different chunk
Ck , see Figure 10 for an example of such mirroring ofdata. There are points on the terrain that correspondto clauses of the PLANAR 3SAT instance. For example,
if clause ci = (xi+1 ∨ xi+3 ∨ xi+4 ) were in the original
PLANAR 3SAT instance, then a point on the terrain
would exist that is seen by three vertices corresponding
to xi , xi+3 and xi+4 . If one of those vertices has a guard
placed on it, then the clause would be satisfied. If noneof those vertices has a guard placed on it, then an extra
guard would be required to guard the terrain. If someminimum number of guards were placed and the entire

5th Iranian Conference on Computational Geometry

Figure 9: To ensure the entire terrain is seen, a guard
is placed at e to see vertices f and g along with the uregion.

Figure 10: The variable gadget remains unchanged from
[7].

terrain was seen, then the original instance was satisfied.
If not, then the original instance was unsatisfiable.
The interested reader is encouraged to read [7] to see
the full details of the original reduction. We modify thegadgets from [7] and show how these modified gadgets
work for guards that can only see down.
Terrain Hardness Modifications
We describe the changes to the gadgets of [7] that must
be made in order for the reduction to hold. Each partwill explain why the original gadget doesn’t work forthis half-guard variant and what changes must be madein order to have the reduction hold.
Between Chunks: Let us order the chunks from top
to bottom (C1 , C2 , . . . , Cm ). We will assume that all
variables gadgets in chunk Ci are below all variablegadgets in chunk Ci−1 . In the original reduction, theterrain between Ci the Ci+2 is seen by any guard placedin the Ci+1 chunk. Since guards can only see down inthis variant, a portion of the terrain, which we will callu, below the lowest variable gadget in Ci and above
the highest variable gadget in Ci+1 will be unseen, see
Figure 9. To fix this, we place a new gadget on theother side of the terrain from Ci . This gadget is at thesame y-coordinate of the lowest variable gadget in chunk
Ci . This ensures that the new guard will not affect themirroring. The vertices f and g can only be seen fromvertex e. Placing a guard at e will see f and g and also
see the unseen region u below chunk Ci .
Variable Gadget: The variable gadgets, shown in Figure
10, do not need to be tweaked much to work. Assume
the xi vertex in the variable gadget in chunk Cj has aguard placed on it and it sees b. In this case, a guard isplaced at xi in the variable gadget in chunk Cj+1 to seea and c. The entire xi variable gadget in chunk Cj+1
is seen. Likewise, if a guard placed at xi in chunk Cjsees a, then a guard is placed at xi in chunk Cj+1 sees b
and c. A small portion of the terrain below xi in chunk

Figure 11: The overview of the terrain reduction whereguards see down.

Cj+1 may have been missed, see Figure 10. However, if
the xi vertex in chunk Cj is lowered just slightly, thenthe guard placed at xi in Cj will see this region andan additional guard is not required. One must ensure
the previously placed xi does not see b but it can see
anything in this gadget above b. Therefore, we ensurethat xi in the previous variable gadget is placed in sucha way that it blocks xi from seeing just above b in thesubsequent variable gadget.
Removing a Variable: We will assume we are removing
a variable from chunk Ci . When a variable gadget isremoved going upwards, the gadget is modified slightly
to remove the a and b vertices. Such a gadget is also
called a starting gadget. When a guard is placed atthe “lower” vertex in this gadget, a small portion of theterrain below the “higher” vertex remains unseen. In
Figure 8(right), a starting gadget is shown. A guard
placed at xi would not see the small portion of theterrain below the xi guard. To ensure this region is seen,
we look at the variable patterns placed in the chunkabove it, chunk Ci−1 . The guard placed in the lowest
variable pattern will see all of these potentially unseen
portions. For example, in Figure 11, the guard placed in
the variable gadget, xk , directly above the rl point will
see all of these unseen regions in the variable patterns
between lr and the variable gadget for xk in chunk C2 .
Therefore, no modification is needed and no additional

ICCG 2022, Sharif UT, February 24, 2022

Figure 12: The inversion gadget for variable xi in chunk
Cj+1 . This gadget is not tweaked but the variable gadget
xi in chunk Cj is modified slightly.

guard is needed.
When removing a variable going down, the variablegadget is simply removed. The guard placed in theprevious chunk’s lowest variable gadget will see thisregion. If the lowest variable was being removed, thenthe e guard in the gadget that sees between chunks will
see this region (see Figure 9).
Above chunk C1 and C2 : Since guards cannot see “up,”a guard must be placed that guards the terrain above
the first set of variable gadgets in chunk C1 and above
the variable gadgets in C2 . Assume WLOG that C1 ison the left side of the terrain. Two guards are placedat points l and r as shown in Figure 11. These guards
are required to see their own set of distinguished points,
namely ll , lr , rr and rl . They see the “top” of the terrain
above chunks C1 and C2 . Since all gadgets in chunk
C1 are starting gadgets, rl is placed below chunk C1 toensure the relevant part of the terrain in the starting
gadgets and the terrain above the chunk are seen.
Clause Gadgets: No change is needed for the clausegadgets. All points in the clause gadgets are seen by theappropriate vertices above it.
Inversion Gadgets: A small update is needed for the
inversion gadgets. See Figure 12 for a sample inversion
gadget placed in chunk Cj+1 . If a guard from the variablegadget xi in chunk Cj sees point p, then when guards
are placed at xi1 and xi2 , the entire gadget is seen. If
the guard from chunk Cj guard sees point q, then guards
are placed at xi1 and xi2 . This leaves a small portionof the terrain unseen, the line segment e in Figure 12.
To fix this, similar to the tweak of the variable gadget,the previously placed guard in chunk Cj is tweaked suchthat it sees just over the xi1 guard. In this example,
the previously placed guard must see q and not see p.
As long as it is blocked from p, this is all that matters.
Therefore, it can be tweaked to see the e line segment.
Putting it all together: As seen above, certain tweaks
and updates are made to ensure that the entire terrain
is seen. Making these changes will cause the minimum

Figure 13: A stretched WV-polygon such that the NPhardness result holds.
number of guards that must be placed, k, to increase by
m + 1. An additional m − 1 guards are needed to see theunseen regions between chunks. Two additional guards
are added at l and r to see the “top” of the terrain. This
gives us a total of m − 1 + 2 = m + 1 additional required
guards. None of these additional required guards see anyof the original distinguished points of the terrain. They
see their own set of distinguished points and also see theportion of the terrain that would have been unseen. As
shown in [7], if k guards can guard the entire terrain,
the instance is satisfiable. If more than k are needed,
then the instance is not satisfiable.
Theorem 8 Finding the smallest vertex guard coverfor guarding a terrain using half-guards that see down is
NP-hard.
Stretching WV-Polygon Hardness
An example of this stretching is seen in Figure 13(left).
As seen in the example, the original bottom of the terrain
is pulled up and to the right to ensure the polygon
remains weakly-visible and all important lines of sight
look to the right. The l and r vertices are tweaked slightly
to ensure they also see their respective distinguishedvertices to the right.
This stretching of the polygon works even if the WVedge has a positive slope, see Figure 13(right). The
polygon can continue to be stretched as far up and rightas necessary. However, the tweak fails when the WVedge is a vertical edge and the inside of the polygon is tothe left of the edge. We leave this as an open problem.