Informatica 39 (2015)221-227 221
Barrier Resilience of Visibility Polygons
Alexander Gilbers
Institute of Computer Science, University of Bonn 53113 Bonn, Germany E-mail: agilbers@gmx.de
Keywords: computational geometry, barrier resilience, visibility Received: June 21, 2014
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.
Povzetek: Prispevek analizira problematičnost 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?
Figure 1: Path n from s to t is seen by two witnesses (black points).
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
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
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.
222 Informatica 39 (2015) 221-227
A. Gilbers
x S
Figure 2: An instance of the Barrier Resilience problem for disks
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 n from a given starting point through a polygon P such that every point of P can be seen from some point of n. 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(n4 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(k4 n4). 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 O(2log1 iac|) |C|), where | C| is the number of colors and S(| C|) = log loga |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 C 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 G P and a set of so-called witness points W = {wi,..., wn} C 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 pi G P sees p2 G P iff the line segment plp2 is a subset of P. We say that a witness point w G P sees the path n iff there is a point p on n that is seen by w.
Barrier Resilience of Visibility Polygons
Informatica 39 (2015)221-227 223
Figure 3: Path n is seen by witness v but not by witness 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 G P and a witness point w G P. If there is a path n 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 G P and a set of witness points W c P, the shortest path between s and t is an optimal solution to the minimum witness path problem.
Proof. Let n' denote the shortest path from s to t. By Lemma 1, for every path n between s and t the set W' =
{w G W | w sees n'} is a subset of W(n) = {w G W | w sees n} and consequently |W'| < |W(n)|.	□
Corollary 1. Given a simple polygon P with n edges, two points s, t G P and a set of witness points W c 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 n' be the shortest path between s and t and w g P a point that sees the point p on n'. 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) n P. Now P \ C splits into at least two connected components. As n' is the shortest path, s and t lie in different components (otherwise n' 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.	□
Figure 4: The connected component C of L(w,p) n P that contains w and p splits P into two connected components, one containing s, the other containing t.
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 Hi,..., Hm, called the holes, where every hole lies in the interior of P' and H n Hj = 0 for all 1 < i < j < m. The polygon with holes P then is defined to be P = P' \ |Jm=i H, where H denotes the topological interior of Hj. Let |P| denote the total number of edges of P. Two points pi, p2 G P see each other if and only if the line segment pip2 is completely contained in P.
Again we are given two points s, t G P and witnesses wi,..., wn G P in general position, and we want to find a path n inside P from s to t minimizing the number of witnesses who can see n.
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 ofvis-ibility 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 ei, e2,..., em an enumeration of the edges, vi, v2,... vn 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
224 Informatica 39 (2015) 221-227
A. Gilbers
W 3
W 2
Wi
Figure 5: On the left side of the polygon there are only narrow slits between the holes through which the witnesses (which correspond to the vertices) can peek.
points wi,... wn 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 — 1, 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 ej in E, we add a thin rectangular hole
Rj = jj +0.5] x [—j,j].
Then we place the witness points at wj = (—2(m + n),i — [n 1). If and vi (with k < l) are the vertices incident to edge ej we define L(j) = wk, H(j) = wi to be the witnesses corresponding to the vertices with lower and with higher index, respectively. We also define f: {w1,..., wn} —>• {v1,..., vn} to be the bijection that maps every wj to vj.
To construct the holes that model the vertex-edge incidences we proceed as follows: We start with one rectangle
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 ej we define the two triangles
and
THj = A(H(j), (j, j - 0.25), (j, j - 0.5))
TLj = A(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
m
Z' = Z \ J (THj U LH, ) j=i
We add the connected components of Z' as holes to our scene.
By this construction every witness w sees a rectangle Rj iff the vertex v is incident to e,.
Figure 6: Far away on the right side portions of visibility regions hit the rectangles corresponding to edges.
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 ej the quadrilateral with corners (j, 0.5 — j), (j, j — 0.5), H(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 n is a path from s to t that is seen by the set of witnesses W(n) then the image of W(n) under f is a vertex cover of G. As f is a bijection, the set of witnesses has the same cardinality as the resulting vertex cover.
On the other hand, if C c 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 R1 that corresponds to edge e1. By definition, f (H(1)) or f (L(1)) 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)) € C and crossing the visibility region of L(j) otherwise, until we reach t. The resulting set W(n) of witnesses has at most as many elements as C. It follows that an a-approximation for the BARRIER RESILIENCE problem yields an a-approximation for Minimum Vertex Cover.	□
t
Barrier Resilience of Visibility Polygons
Informatica 39 (2015)221-227 227
h	
	H
x t
Figure 7: The removal of the segments Si and S2 splits P into two connected components. s and t lie in the same connected component.
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' \ H for some simple polygon P' and a convex polygon H c P). Assume that for every point h G H and for every two line segments Si, S2 C P U H that both have as one endpoint h and the other endpoint on d (P U H), s and t lie in the same connected component of (P U H) \ (Si U S2). Then there is a unique shortest path from s to t in P and it is a minimum witness path.
Proof. Take the shortest path n between s and t in P' = P U H. As this is a simple polygon, n is unique. By assumption, there is no point h G H and line segments Si,S2 c P' that connect h to the boundary of P' such that s, t lie in different components of P' \ (Si U S2), see Figure 7. Then n does not intersect H.
Otherwise we could take a point h G n n H and draw a line segment S c P' that crosses n in h and ends in the two points bi, b2 on the boundary of P'. Then setting Si = bih and S2 = b2h yields a contradiction to the assumption as s and t lie in different connected components of P' \ (Si U S2) (because the shortest path crosses the segment S exactly once).
Therefore, n 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 n'. Then there was in particular one witness w that sees n but not n'. Let p be a point on the path n that is seen by w. Let further S be the connected component of the intersection L(w,p) n P' of the line through w and p with P' that contains p and Si be the connected component of L(w,p) n P that contains p. If both endpoints of Si lay on the boundary of P' then s and t were in distinct components of P \ Si. Then every path from s to t would have to cross Si 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 S2 to be the topological closure of S \ Si, then h, Si, S2 are as above
Figure 8: The removal of either Si or S2 leaves polygons with unique shortest paths n1, n2 one of which is a minimum witness path
and s, t are in different connected components of P' \ (Si U S2 ) , a contradiction.
It follows, that there can be no path n from s to t and witness w such that w sees n but not n'. Thus the shortest path n is optimal.	□
Theorem 3. Let P = P' \ H a polygon with one convex hole, s,t be start and target point, respectively. Let there be line segments Si, S2, 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 U H, so that s and t lie in different connected components of P \ (Si U S2). Either the shortest path ni from s to t in P \ Si or the shortest path n2 from s to t in P \ S2 is a minimum witness path in P.
Proof. Suppose none of them were optimal. Then there exist witnesses wi, w2 (possibly wi = w2) and a path n', such that wi, w2 do not see n', but wi sees point pi on ni and w2 sees p2 on n2. Let Ti and T2 denote the line segments from boundary to boundary of P U H through wi and pi and through w2 and p2, respectively. The segments Si and Ti together with H as well as S2, T2, H separate the points s and t. By the existence of n', Ti, T2 and H together do not separate s and t. The connected component of s in P \ (Ti U T2 ) is simply connected and contains t. As n' does not cross Ti, T2 it crosses both Si and S2. s and t lie in different components of P \ (Si U S2), so (Si U S2 ) is crossed an odd number of times. Now we can repeatedly replace subpaths between two crossings of the same segment Sj by the direct paths along the segment (this does not add witnesses) until only one crossing is left, contradicting the fact, that n' crosses Si and S2.	□
It follows that in this case the barrier resilience can be computed in polynomial time by computing Si and S2 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' \ U?
holes, s,t G P, W = {wi,..
= 1 Hi a polygon with convex , wn} c P a set of witness
points. Let for every i = j there be a line segment Sj c P
23 Informatica 39 (2015) 221-227
A. Gilbers
s.t. Hi and Hj lie in distinct connected components of P' \ Sij and Sij is not seen by any witness w G W. Then one can find a minimum witness path from s to t in polynomial time.
Proof. Let Cij denote the connected component of P' \ Sij that contains Hi. Then for every 1 < i < m, Ci = j Cij is a simple polygon, that contains Hi but no Hj for any other index j = i. For j = i Ci n Cj = 0. We now compute in O(|P'|) time the shortest path n' from s to t in P'. The parts of n' outside |Jrri=1 Ci are already optimal by Theorem 3. To get the witness-minimal path n through P, we replace the parts of n' inside the Ci 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 n' enters Ci si and the point where it leaves Ci ti. We then draw a segment B1 from an arbitrary point on the boundary of Hi to the boundary of Ci. Then we compute in time O(|P'| + m) = O(|P|) the shortest path n1 from si to ti in Ci \ (H U B1). We then choose a second segment B2 from Hi to the boundary of Ci, that intersects (if such a segment exists; otherwise is optimal in Ci by Lemma 2) and compute in time O( |P' | + m) = O( |P|) the shortest path n? from si to ti in Ci \ (H U B2). We choose the path less seen by witnesses in P to replace the part of n' inside Ci. (Testing all possible path or n? with all possible witnesses can be done in total time O(n|P|2) after the construction of the witnesses' visibility polygons.)
By sewing together the thus computed parts we get a witness-minimal path n from s to t in P. The running time is dominated by the visibility tests that can be carried out in O(n|P|2) The computation of the polygons Ci can be computed in time O(m2|P'|). (Shoot a ray from Hi to find the boundary of Ci in O(|P '|+m). Then follow the boundary, turning at every intersection. Testing for the intersections of the m many Sij is in total time O(m2), following the boundary of |P' | and testing if it meets a segment is in O(m|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 seper-atedness 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.
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 ACM-SIAM 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/to 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, Universität 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:209233, 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.
Barrier Resilience of Visibility Polygons
Informatica 39 (2015)221-227 24
[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 ALGO-SENSORS, pages 130-144, 2011.
[16]	Shengli Yuan, S. Varma, and J.P. Jue. Minimum-color path problems for reliability in mesh networks. In IN-FOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE, volume 4, pages 2658-2669 vol. 4, 2005.