# Barrier resilience of visibility polygons.

We consider the problem of computing the Barrier Resilience of a set of Visibility Polygons inside a Polygon. We show that in simple polygons the problem is solvable in time linear in the number of edges. In polygons with holes the problem is APX-hard, so only for special cases can we provide polynomial time algorithms.

Keywords: computational geometry, barrier resilience, visibility

Povzetek: Prispevek analizira problematicnost prehoda poligona.

1 Introduction

Put yourself in a smuggler's shoes. You want to deliver some goods to a fixed destination but you do not want to be seen by many witnesses. Unfortunately, there is no way to your destination that is completely unobserved, nor can you conceal your goods. Perhaps you just want to minimize the number of witnesses or perhaps there is some number k of witnesses that still is acceptable.

It is not important to you, how often or how long the witnesses see you on your way. You only care for their number.

You are given a map of your city, in which your starting and your target point are marked as well as the positions of all the possible witnesses, see Figure 1. Can you compute the path that is seen by the minimum number of witnesses?

This turns out to be a special case of the BARRIER RESILIENCE problem. Given a start point s and a target point t as well as the positions and ranges of n sensors that are designed to detect intruders, we want to find a path from s to t that minimizes the number of its witnesses (i.e. the sensors that detect the agent traveling on this path, see Figure 2 for an instance of the BARRIER RESILIENCE problem for disk sensors). We call an optimal path in this respect a minimum witness path.

This problem can be seen from two sides: On the one hand, it is a path planning problem. On the other hand, the minimum possible number of sensors that detect a path of the agent is an important parameter of the sensor network. It is called the barrier resilience of the network, sensor networks with a low barrier resilience are more error-prone than those with high barrier resilience. In the analysis of a sensor network that is designed to detect an intruder, the minimum witness path points to the network's weak spot. Therefore, to optimize sensor networks it would be very helpful to have an efficient method at hand to compute the barrier resilience of the network or, even better, a minimum witness path.

There are many different types of sensor networks conceivable. We here restrict our attention to the very natural case where the sensor regions are visibility domains.

In the following sections, we will show that we can find minimum witness paths in polynomial time in simple polygons and in polygons with one hole. On the other hand we prove that the Barrier Resilience problem for visibility polygons in polygons with holes is APX-hard. In particular, we get a stronger inapproximability factor than the hardness results known for line segments.

The results in this paper have also been presented in my thesis [9].

2 Related work

Finding minimum witness paths is related to several other tasks. Algorithms that are concerned with the search for shortest paths in polygons (see for example [10]) or minimum cost paths in graphs, where weights are assigned to the edges of the graph [6] are among the best-researched topics in the field of algorithms.

While this paper is about getting somewhere without being seen by too many people, there are many works concerning itself with deploying guards or cameras so that everything of interest is seen at least once or at least a certain number of times. In this category fall the many variations of the art gallery problem, see for example [14],

Also problems that combine path planning questions with guarding problems have been examined. In the WATCHMAN ROUTE problem, introduced by Chin and Ntafos [5] the task is to find a shortest closed path [pi] from a given starting point through a polygon P such that every point of P can be seen from some point of [pi]. Since then, various versions of the WATCHMAN ROUTE problem have been defined. The one most strongly related to our problem is the ROBBER problem that was defined by Ntafos in 1990 [13]. Given a set of edges S and a set of threats T, a robber in a simple polygon P wants to find a shortest cycle from which he can see all of S, while not being seen by any of the threats. In this setting, the problem has got a solution only if there exists such a path outside the visibility polygons of the threats. Ntafos gives an algorithm that solves the problem in time O([n.sup.4] log log n).

In [7] Gewali et al. define a special case of the WEIGHTED REGIONS problem [12] and apply it to the following problem. Given a polygon with holes, a starting point s, a target point t and a set of k threats. Find the least risk path from s to t. The authors give an algorithm that computes a least risk path in time O([k.sup.4][n.sup.4]]). The risk is measured by the total length of the subpaths that are inside the visibility polygon of some threat. Here lies the main difference to our model in which the cost of using a witnesses visibility region is fixed, no matter how often or how long the path traverses this region.

In 2005, in the environment of sensor networks Kumar et al. [11] introduce the notion of a k-barrier coverage. In their setting, somebody wants to cross a belt region over which a sensor network is deployed. The belt region is called k-barrier covered if every path that crosses the belt is detected by at least k sensors.

Bereg and Kirkpatrick [2] introduce the notion of barrier resilience: Given a collection of geometric objects that model the ranges of sensors and two points s, t in the plane, find the minimum number of objects one has to remove such that s and t are in the same component of the complement of the remaining objects. I.e. the barrier resilience is the maximum k such that the region is k-covered. They give an approximation algorithm for this problem when the sensor ranges are unit disks. Until today it is unknown if this original problem is NP-hard. In [1] Alt et al. show that the Barrier Resilience problem for line segments is APX-hard and they also define related problems. In [15] Tseng and Kirkpatrick strengthen the result to unit line segments. Gibson et al. [8] give an approximation algorithm for a path that visits multiple points and tries to avoid as many unit disks as possible. Chan and Kirkpatrick [4] give a 2-approximation algorithm for the case of Non-identical Disk Sensors.

One can also view the barrier resilience problem in a very abstract graph-theoretic setting where an agent wants to travel from some start vertex of a graph G to some target vertex. In this setting the barriers are arbitrary subsets of the edge set of G. The barriers can also be interpreted as colors that are assigned to the edges. This problem is then called the MINIMUM COLOR PATH problem. Carr et al. [3] show that unless P = NP, the optimal solution cannot be approximated to within a factor [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [absolute value of C] is the number of colors and [delta]([absolute value of C]) = 1/log [log.sup.a] [absolute value of C] for any constant a < 1/2. In [16], Yuan et al. use the Minimum Color Path model to analyze reliability in mesh networks.

3 Minimum witness paths in simple polygons

In our first setting the starting point s and the target point t lie inside a simple polygon P, and we are given a finite set of witness points W [subset] P. We want to find a path from s to t that is seen by as few as possible witnesses. Let us restate this formally.

Definition 1. Let a polygon P, two points s, t [member of] P and a set of so-called witness points W = {[w.sub.1], ..., [w.sub.n]} [subset] P be given. The barrier resilience of W is the minimum cardinality of a subset V of W such that there is an s--t-path in P that does not touch any visibility polygon of a point in W \ V. A path that attains this minimum is called a minimum witness path.

We use the usual notion of visibility inside simple polygons that is also illustrated in Figure 3.

Definition 2. Let P be a simple polygon. We say that [p.sub.1] [member of] P sees [p.sub.2] [member of] P iff the line segment [bar.[p.sub.1][p.sub.2]] is a subset of P. We say that a witness point w [member of] P sees the path [pi] iff there is a point p on [pi] that is seen by w.

It turns out that in this setting one can find an optimal path very efficiently. The key insight is the following structural lemma.

Lemma 1. Let P a simple polygon, points s, t [member of] P and a witness point w [member of] P. If there is a path [pi] in P from s to t that is not seen by w, then the shortest path from s to t in P is not seen by w.

Before we prove the lemma, we draw the following conclusions that settle the problem for simple polygons.

Theorem 1. Given a simple polygon P with n edges, two points s, t [member of] P and a set of witness points W [subset] P, the shortest path between s and t is an optimal solution to the minimum witness path problem.

Proof. Let [pi]' denote the shortest path from s to t. By Lemma 1, for every path [pi] between s and t the set W' = {w [member of] W | w sees [pi]'} is a subset of W([pi]) = {w [member of] W | w sees [pi]} and consequently [absolute value of W'] [less than or equal to] [absolute value of W ([pi])].

Corollary 1. Given a simple polygon P with n edges, two points s, t [member of] P and a set of witness points W [subset] P, we can determine a minimum-witness path in time O(n).

Proof. The shortest path between two points inside a simple polygon with n edges can be computed in time O(n) [10].

The proof of the lemma uses the simple topological structure of the polygon.

Proof of Lemma 1. Let [pi]' be the shortest path between s and t and w [member of] P a point that sees the point p on [pi]'. If w sees s or t it obviously sees every path from s to t. Otherwise consider the line L(w,p) through w and p.

The points w and p lie in the same connected component C of L(w,p) [intersection] P. Now P\C splits into at least two connected components. As [pi]' is the shortest path, s and t lie in different components (otherwise [pi]' could be shortened to a path that is completely contained in the common component of s and t).

It follows that every path from s to t must pass C and is therefore seen by w.

4 Polygons with holes

The next step is looking at polygons with holes. So now we have a simple polygon P' and a collection of simple polygons [H.sub.1], ..., [H.sub.m], called the holes, where every hole lies in the interior of P' and [H.sub.i] [intersection] [H.sub.j] = [empty set] for all 1 [less than or equal to] i < j [less than or equal to] m. The polygon with holes P then is defined to be P = P' [[union].sup.m.sub.i=1] [H.sub.i], where [[??].sub.i] denotes the topological interior of [H.sub.i]. Let [absolute value of P] denote the total number of edges of P. Two points [p.sub.1], [p.sub.2] [member of] P see each other if and only if the line segment [[bar.p].sub.1][[bar.p].sub.2] is completely contained in P.

Again we are given two points s,t [member of] P and witnesses [w.sub.1], ..., [w.sub.n] [member of] P in general position, and we want to find a path [pi] inside P from s to t minimizing the number of witnesses who can see [pi].

First we show that the problem is APX-hard by a reduction from Vertex Cover that provides a stronger factor than other hardness proofs in the context of barrier resilience.

Theorem 2. Estimating the barrier resilience of a set of visibility polygons inside polygons with holes is APX-hard. In particular, unless P = NP, the barrier resilience of visibility polygons with holes cannot be approximated within a factor of 1.3606. If the Unique Games Conjecture

is true, then the barrier resilience cannot be approximated within any constant factor better than 2.

Proof. We show this by an approximation factor preserving reduction from MINIMUM VERTEX COVER.

Let G = (V, E) be an instance of vertex cover. Let [e.sub.1], [e.sub.2], ..., [e.sub.m] an enumeration of the edges, [[upsilon].sub.1], [[upsilon].sub.2], ... [[upsilon].sub.n] an enumeration of the vertices.

We now construct a polygon with holes P in the plane that contains a start point s, a target point t and n witness points [w.sub.1], ... [w.sub.n] such that every path from s to t in P corresponds to a vertex cover of G.

To this end we build a big surrounding rectangle P' = [- 2(m + n + 1), m + 2] x [-m - n - l, m + n + 1]. We place the start point at the origin, s = (0,0) and the target point at t = (m + 1,0). For every edge [e.sub.j] in E, we add a thin rectangular hole [R.sub.j] = [j, j + 0.5] x [-j, j]. Then we place the witness points at [w.sub.i] = (-2(m + n), i - [??]n/2[??]). If [[upsilon].sub.k] and [[upsilon].sub.l] (with k [less than or equal to] l) are the vertices incident to edge [e.sub.j] we define L(j) = [w.sub.k], H(j) = [w.sub.l] to be the witnesses corresponding to the vertices with lower and with higher index, respectively. We also define f : {[w.sub.1], ..., [w.sub.n]} [right arrow] {[[upsilon].sub.i], ..., [[upsilon].sub.n]} to be the bijection that maps every [w.sub.i], [[upsilon].sub.i].

To construct the holes that model the vertex-edge incidences we proceed as follows:

Z = [-2(m + n) + 0.5, - 2(m + n) +1] x [-m - n, m + n] and split it into 2m + 1 pieces.

For every edge [e.sub.j] we define the two triangles

[TH.sub.j] = [DELTA](H(j), (j,j - 0.25), (j,j - 0.5))

and

[TL.sub.j] = [DELTA](L(j), (j, 0.25 - j), (j, 0.5 - j)).

Now we construct the 2m + 1 holes by simultaneously cutting the interiors of all these triangles out of Z. We set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We add the connected components of Z' as holes to our scene.

By this construction every witness [w.sub.i] sees a rectangle [R.sub.j] iff the vertex [[upsilon].sub.i] is incident to [e.sub.j].

We first notice that this reduction is clearly polynomial-time. The total number of edges of P is 12m + 8 and the number of points (witnesses and start/target) is n+2, each of which can easily be computed in polynomial time.

To see that every path from s to t that is seen by k witnesses corresponds to a vertex cover of G, observe the following: For every edge [e.sub.j] the quadrilateral with corners 0,0.5 - j), (j, j - 0.5), if (j), L(j) contains s and does not contain t. Thus every path from s to t must cross one of its four sides. One of the sides is the edge of a hole that cannot be crossed. The other three sides are visibility segments of L(j) and H(j), respectively, and thus crossing them means to be seen by L(j) or H(j). Therefore, if [pi] is a path from s to f that is seen by the set of witnesses W([pi]) then the image of W([pi]) under / is a vertex cover of G. As / is a bijection, the set of witnesses has the same cardinality as the resulting vertex cover.

On the other hand, if C [subset] V is a vertex cover of G we can construct a path from s to t with at most the same number of witnesses. From s we first go to the point (1,0). Now we are on the boundary of [R.sub.1] that corresponds to edge [e.sub.1]. By definition, f(H(1)) or /(L(l)) are in C. If f(H(1)) is in C, our path proceeds to (1,1), crossing the visibility region of H(1) (but no other visibility region), and then to (1.5,1). Otherwise, the path proceeds to (1, -1) (crossing the visibility region of L(1)) and then to (1.5, -1). In both cases, the next way point is (2,0). We continue in this manner, getting, for every j, from (j. 0) to (j + 1,0) by crossing the visibility region of H(j) if f(H(j)) [member of] C and crossing the visibility region of L(j) otherwise, until we reach t. The resulting set W([pi]) of witnesses has at most as many elements as C. It follows that an [alpha]-approximation for the Barrier Resilience problem yields an [alpha]-approximation for MINIMUM VERTEX COVER.

Next we show that in the case of one convex hole either one can ignore the hole (Lemma 2) or one can compute two paths, one of which is a minimum witness path (Theorem 3).

Lemma 2. Let P be a polygon with one convex hole H, (i.e. P = P'\[??] for some simple polygon P' and a convex polygon H [subset] P). Assume that for every point h [member of] H and for every two line segments [S.sub.1], [S.sub.2] [subset] P [union] H that both have as one endpoint h and the other endpoint on [partial derivative](P [union] H), s and t lie in the same connected component of (P [union] H) \ ([S.sub.1] [union] [S.sub.2]). Then there is a unique shortest path from stot in P and it is a minimum witness path.

Proof. Take the shortest path [pi] between s and t in P' = P [union] H. As this is a simple polygon, [pi] is unique. By assumption, there is no point h [member of] H and line segments [S.sub.1], [S.sub.2] [subset] P' that connect h to the boundary of P' such that s, t lie in different components of P' \ ([S.sub.1] [union] [S.sub.2]), see Figure 7. Then [pi] does not intersect H.

Otherwise we could take a point h [member of] [pi] [intersection] H and draw a line segment S [subset] P' that crosses [pi] in h and ends in the two points [b.sub.1], [b.sub.2] on the boundary of P'. Then setting [S.sub.1] = [bar.[b.sub.1]h] and [S.sub.2] = [bar.[b.sub.2]h] yields a contradiction to the assumption as s and t lie in different connected components of P'\([S.sub.1] [union] [S.sub.2]) (because the shortest path crosses the segment S exactly once).

Therefore, [pi] is completely contained in P and is the unique shortest path between s and t. Now suppose, there was a path that was seen by less witnesses [pi]'. Then there was in particular one witness w that sees [pi] but not [pi]'. Let p be a point on the path [pi] that is seen by w. Let further 5 be the connected component of the intersection L(w, p) [intersection] P' of the line through w and p with P' that contains p and [S.sub.1] be the connected component of L(w, p) [intersection] P that contains p. If both endpoints of [S.sub.1] lay on the boundary of P' then s and t were in distinct components of P \ [S.sub.1]. Then every path from s to t would have to cross [S.sub.1] and therefore be seen by w, a contradiction.

Thus, one of the endpoints must lie on the boundary of H, let us call this endpoint h. If we now set [S.sub.2] to be the topological closure of S \ [S.sub.1], then h. [S.sub.1], [S.sub.2] are as above and s, t are in different connected components of P'\([S.sub.1] [union] [S.sub.2]), a contradiction.

It follows, that there can be no path [pi] from s to t and witness w such that w sees [pi] but not [pi]'. Thus the shortest path [pi] is optimal.

Theorem 3. Let P = P'\[??] a polygon with one convex hole, s, t be start and target point, respectively. Let there be line segments [S.sub.1], [S.sub.2], each of them connecting a point on an edge (not a vertex) of H to a point on an edge (not a vertex) of the boundary of P [union] H, so that s and t lie in different connected components of P ([S.sub.1] [union] [S.sub.2]). Either the shortest path [[pi].sub.1] from s to t in P \ [S.sub.1] or the shortest path [[pi].sub.2] from s to t in P\[S.sub.2] is a minimum witness path in P.

Proof. Suppose none of them were optimal. Then there exist witnesses [w.sub.1], [w.sub.2] (possibly [w.sub.1] = [w.sub.2]) and a path [pi]', such that [w.sub.1], [w.sub.2] do not see [pi]', but [w.sub.1] sees point [p.sub.1] on [[pi].sub.1] and [w.sub.2] sees [p.sub.2] on [[pi].sub.2]. Let [T.sub.1] and [T.sub.2] denote the line segments from boundary to boundary of P [union] H through [w.sub.1] and [p.sub.1] and through [w.sub.2] and [p.sub.2], respectively. The segments [S.sub.1] and [T.sub.1] together with H as well as [S.sub.2], [T.sub.2], H separate the points s and t. By the existence of [pi]', [T.sub.1], [T.sub.2] and H together do not separate s and t. The connected component of s in P \ ([T.sub.1] [union] [T.sub.2]) is simply connected and contains t. As [pi]' does not cross [T.sub.1], [T.sub.2] it crosses both [S.sub.1] and [S.sub.2]. s and t lie in different components of P \ ([S.sub.1] [union] [S.sub.2]), so ([S.sub.1] [union] [S.sub.2]) is crossed an odd number of times. Now we can repeatedly replace subpaths between two crossings of the same segment [S.sub.i] by the direct paths along the segment (this does not add witnesses) until only one crossing is left, contradicting the fact, that [pi]' crosses [S.sub.1] and [S.sub.2].

It follows that in this case the barrier resilience can be computed in polynomial time by computing [S.sub.1] and [S.sub.2] and then the respective shortest paths. One can show that this also holds if P contains many convex holes that are strictly separated in a sense made precise below.

Theorem 4. Let P = P'\[[union].sup.m.sub.i=1] [[??].sub.i], a polygon with convex holes, s, t [member of] P, W = {[w.sub.1], ..., [w.sub.n]} [subset] P a set of witness points. Let for every i [not equal to] j there be a line segment [S.sub.ij] [subset] P s.t. [H.sub.i] and [H.sub.j] lie in distinct connected components of P'[S.sub.ij] and [S.sub.ij] is not seen by any witness w [member of] W. Then one can find a minimum witness path from s tot in polynomial time.

Proof Let [C.sub.ij] denote the connected component of P'[S.sub.ij] that contains [H.sub.i]. Then for every 1 [less than or equal to] 1 [less than or equal to] m, [C.sub.i] = [[intersection].sub.j[not equal to]i] [C.sub.ij] is a simple polygon, that contains [H.sub.i] but no [H.sub.j] for any other index j [not equal to] i. For j [not equal to] i [C.sub.i] [intersection] [C.sub.j] = [empty set]. We now compute in O([absolute value of P']) time the shortest path [pi]' from s to t in P'. The parts of [pi]' outside [[union].sup.m.sub.i=1] [C.sub.i] are already optimal by Theorem 3. To get the witness-minimal path [pi] through P, we replace the parts of [pi]' inside the [C.sub.i] by witness-optimal paths, according to Lemma 2 or Theorem 3. The different parts do not affect each other. To this end let us call the point where [pi]' enters [C.sub.i] [s.sub.i] and the point where it leaves [C.sub.i] [t.sub.i]. We then draw a segment [B.sub.1] from an arbitrary point on the boundary of [H.sub.i] to the boundary of [C.sub.i]. Then we compute in time O([absolute value of P] + m) = O([absolute value of P]) the shortest path [[pi].sup.1.sub.i] from [s.sub.i] to [t.sub.i], in [C.sub.i]\([[??].sub.i] [union][B.sub.1]. We then choose a second segment [B.sub.2] from [H.sub.i] to the boundary of [C.sub.i], that intersects [[pi].sup.1.sub.i] (if such a segment exists; otherwise [[pi].sup.1.sub.i] is optimal in [C.sub.i] by Lemma 2) and compute in time O([absolute value of P'] + m) = O([absolute value of P]) the shortest path [[pi].sup.2.sub.i] [s.sub.i] to [t.sub.i] in [C.sub.i] {[[??].sub.i] [union] [B.sub.2]). We choose the path less seen by witnesses in P to replace the part of [pi]' inside [C.sub.i]. (Testing all possible path [[pi].sup.1.sub.i] or [[pi].sup.2.sub.i] with all possible witnesses can be done in total time O(n[[absolute value of P].sup.2]) after the construction of the witnesses' visibility polygons.)

By sewing together the thus computed parts we get a witness-minimal path [pi] from s to t in P. The running time is dominated by the visibility tests that can be carried out in O(n[[absolute value of P].sup.2]) The computation of the polygons [C.sub.i] can be computed in time O([m.sup.2] [absolute value of P']). (Shoot a ray from [H.sub.i] to find the boundary of [C.sub.i] in O([absolute value of P'] + m). Then follow the boundary, turning at every intersection. Testing for the intersections of the m many [S.sub.ij] is in total time O([m.sup.2]), following the boundary of [absolute value of P'] and testing if it meets a segment is in O(m [absolute value of P']).)

We note that as usual for fixed k the question if the barrier resilience is at most k is polynomially solvable by checking all k-element subsets of the set of visibility polygons of witnesses.

5 Future work

Finding more classes of polygons where the problem is polynomially solvable is one direction of future research. Introducing more sophisticated assumptions on the seperatedness of the sensors is another direction. There are also variations like weighted or mobile sensors waiting to be examined further. It would be interesting to know if the inapproximability result is tight, so probably the most important task is to design an approximation algorithm for the general case of polygons with arbitrarily many holes.

Alexander Gilbers

Institute of Computer Science, University of Bonn 53113 Bonn, Germany

E-mail: agilbers@gmx.de

References

[1] Helmut Alt, Sergio Cabello, Panos Giannopoulos, and Christian Knauer. Minimum cell connection and separation in line segment arrangements. CoRR, abs/1104.4618, 2011.

[2] Sergey Bereg and David G. Kirkpatrick. Approximating barrier resilience in wireless sensor networks. In ALGOSENSORS. pages 29-40, 2009.

[3] Robert D. Carr, Srinivas Doddi, Goran Konjevod, and Madhav Marathe. On the red-blue set cover problem. In Proceedings of the eleventh annual ACMSIAM symposium on Discrete algorithms, SODA '00, pages 345-353, Philadelphia, PA, USA, 2000. Society for Industrial and Applied Mathematics.

[4] David Yu Cheng Chan and David G. Kirkpatrick. Approximating barrier resilience for arrangements of non-identical disk sensors. In ALGOSENSORS, pages 42-53, 2012.

[5] Wei-Pang Chin and Simeon Ntafos. Optimum watchman routes. Information Processing Letters, 28:3944, 1988.

[6] E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269-271, 1959.

[7] Laxmi Gewali, Alex Meng, Joseph S. B. Mitchell, and Simeon Ntafos. Path planning in 0/1/[infinity] weighted regions with applications. In Symposium on Computational Geometry, pages 266-278, 1988.

[8] Matt Gibson, Gaurav Kanade, and Kasturi R. Varadarajan. On isolating points using disks. In ESA, pages 61-69, 2011.

[9] Alexander Gilbers. Visibility Domains and Complexity. PhD thesis, Universitat Bonn, 2014.

[10] Leonidas Guibas, John Hershberger, Daniel Leven, Micha Sharir, and Robert Tarjan. Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica, 2:209-233, 1987.

[11] Santosh Kumar, Ten H Lai, and Anish Arora. Barrier coverage with wireless sensors. In Proceedings of the 11th annual international conference on Mobile computing and networking, pages 284-298. ACM, 2005.

[12] Joseph S.B. Mitchell and Christos H. Papadimitriou. The weighted region problem: finding shortest paths through a weighted planar subdivision. Journal of the ACM, 38(1): 18-73, 1991.

[13] Simeon Ntafos. The robber problem. Information Processing Letters, 34:59-63, 1990.

[14] Joseph O'Rourke. Art gallery theorems and algorithms. Oxford University Press, New York, 1987.

[15] Kuan-Chieh Robert Tseng and David G. Kirkpatrick. On barrier resilience of sensor networks. In ALGOSENSORS, pages 130-144, 2011.

[16] Shengli Yuan, S. Varma, and J.P. Jue. Minimum-color path problems for reliability in mesh networks. In INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE, volume 4, pages 2658-2669 vol. 4, 2005.