AN OPTIMAL ALGORITHM FOR DETERMINING EDGE VISIBILITY IN A POINT-VISIBLE POLYGON S. Y. Shin T. C. Woo Department of Industrial & Operations Engineering The University of Michigan Ann Arbor, Michigan 48109-2117 Technical Report 87-8 March 1987

An Optimal Algorithm for Determining Edge Visibility in a Point-Visible Polygon S. Y. Shin T. C. Woo* Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109-2117 March, 1987 *Correspondence should be sent to T.C. Woo at the above address.

Abstract By testing the floor plan of a building as a polygon, we study the problem of locating a camera for surveillance. If the polygon is point-visible then only one camera is needed. A visible edge corresponds to the wall on which the camera is to be mounted. While a given edge can be tested for visibility in time linear in the number of edges n [1], there can be O(n) such edges. In this paper, we give an O(n) time algorithm for finding all visible edges in a point-visible polygon.

1. Introduction Two points u and w in a polygon P are said to be visible if the line segment L(u,w) joining u and w is completely contained in P. Suppose that P represents the floor plan of a building. The celebrated "Art Gallery Problem" [3,4] seeks a bound on the number of guards such that the entire interior of P is visible at all times. The kernel of P, denoted by K(P), is the set of all points in P such that every point u in P is visible from any point w in K(P). Lee and Preparata [6] showed an algorithm for finding K(P) in time linear in the number of edges n of a given polygon P. A polygon with a non-empty kernel is a point-visible polygon [5]. Figure 1 shows the relation of K(P) to a point-visible polygon P. <Insert Figure 1 > For surveillance applications, a television camera can be located in K(P). To be less obstructive, a camera may be better placed on a wall. However, K(P) may not be on the boundary of P. This leads to the notion of edge-visibility. According to Avis and Toussaint [1], there are three types of edge-visibility. Let an edge E(vi,v + 1) be a directed line segment L(vj,vj + 1) joining two adjacent vertices vj and v- + 1 on the boundary B(P) of P. Then, (i) P is completely visible from an edge E(vi,vj + 1) if, for every point u in P and every point w in E(vi,vj + 1), u and w are visible. (ii) P is strongly visible from E(vi,vi + 1) if there exists a point w such that every point u in P is visible from w. (iii) P is weakly visible from E(vi,vj + 1) if, for every point u in P, there exists some point w in E(vi-vi + 1) (depending on u) such that u and w are visible. We now relate edge visibility to point visibility. Let a visibility polygon V(u,P) be the set of all points in P, which are visible from a point u [2]. If P is completely visible from an edge E(v-,vi + 1), then E(v,,vJ + 1) is completely contained in K(P). In other words, the visibility polygon V(w,P) from w is the entire polygon P, where w is any 1

Figure 1: A point-visible polygon P has a non-empty kernel K(P).

point in the edge E(vj,vi + 1). Figure 2(c) illustrates such a polygon. If P is strongly visible from E(vj,vi + 1), then E(v|,vi + 1) n K(P) t 0. In other words, there exists some point w in E(vi,v1 + 1) such that P = V(w,P). Figure 2 (b) illustrates such an edge. On the other hand, if P is weakly visible from E(vi,vj + 1), E(vi,vj + 1) may not share a point with K(P) as illustrated in Figure 2 (a). However, the union of the visibility polygons V(w,P), where wE E (vi,vi + 1), covers P. <Insert Figure 2> In the context of locating surveillance equipment on a wall, a camera can be fixed at any point in a completely visible edge since P is visible from every point in the edge. For a strongly visible polygon, a camera should be mounted at a point u in an edge E(v1,vi + 1) such that uE K(P). These two cases, complete and strong edgevisibility, entail a stationary camera. If the field of view of the camera is sufficiently wide, no panning is required. Otherwise, the camera, while fixed at a point, must rotate about that point for complete coverage. The case of weak edge-visibility entails a movinq camera. To ensure that union of visibility polygons at all points in a weakly visible edge E(vi,vi + i), the camera must be translated from vi and v + 1 and back. The characterization of edge visibility suggest three problems: that of finding completely, strongly, and weakly visible edges in a point-visible polygon. The first two problems can trivially be solved in O(n) time by checking intersection of K(P) and the boundary B(P) of P. The last problem of fiding a weakly visible edge in a point-visible polygon P is the focus of this paper. Avis and Toussaint [1] gave an O(n) algorithm for determing whether or not a polygon is visible from a given edge. Since there are n edges, finding all the weakly visible edge would take O(n2) time, if we use their algorithm. Here, we give an O(n) algorithm for soliving this problem. 2

Vi E(vi, Vi+l) (a) P is weakly visible from E(vi,vi+l). P A/N) P Vi+l E(v Vi+l ) (b) P is strongly visible from E(vi, vil). vi vi L vi+l P cvi Vi+l ) (c) P is completely visible from E(vi,vi+l). Figure 2: P is visible from E(vi, vi+l).

2. Characterization of Edge Visibility In this section we develop properties that enable us to find all weakly visible edges. For brevity, we refer to a weakly visible edge as a visible edge. First, some definitions and terms are in order. Let P be a simple polygon with n vertices. Each vertex vj, i = 0,1,2..., (n-1), is represented by its Catesian coordinates, (xj,yj). Starting from a vertex vo and traversing the boundary B(P) of P in the counter-clockwise order, we label the jth vertex from vo as vi, where i is taken j modulo n. These vertices in sequence are maintained as a circular doubly linked list. A vertex vi is said to be concave if the internal angle at v, is less than 180 degrees. vi is said to be reflexive, otherwise. (L(u,w) denotes a directed line segment joining two points u and w with a direction from u to w. An open edge E(v|,v, +1) is a directed line segment L(vj,vj + 1) without its two endpoints, vi and v- + 1. Let u and w be two distinct points on B(P). A chain Ch(u,w) is said to be the portion of B(P) from u to w in the counter-clockwise order. An open chain Ch(u,w) is a chain Ch(u,w) excluding its two endpoints u and w. A ray RAY (u,w) is a half line starting at u with the direction from u to w. Consider an edge E(vi,vi + 1) of P. Suppose that E(vi,vi + 1) lies completely to the right of E(vr,vr+ i) for some r<n. Since the interior of P lies to the left of E(vi,vj + l), every point on an open edge E(vr,vr + l) is not visible from any point on E(vi,vj + i). This gives a characterization of a visible edge. 3

Lemma 2.1: Suppose that a simple polygon P is visible from an edge E(vj,vi + 1) of P. Then, for every edge E(vr,vr + l), there exists at least a point on E(vi,vj + i), which is on or to the left of E(vr,vr+ 1). Lemma 2.1 provides a necessary condition for a visible edge. Avis and Toussaint supplied a necessary and sufficient condition [1]. Lemma 2.2: A simple polygon P is weakly visible from E(vi,vi + l) if and only if the boundary B(P) of P is weakly visible from E(vi,vi + 1). A trivial lower bound in time complexity for checking this condition for a given edge is Q(n) [1]. Since there are n edges in P, it is hard to accomplish a linear time complexity with Lemma 2.2. We will develop another characterization of a visible edge by exploiting pointvisibility of P. A point x in RAY (vi,vj) nB(P) is said to be a visible intersection point if x is visible from vi. Let VXii + 1 = vi + 1, if vi + 1 is concave. Otherwise, it is the first visible intersection point in RAY (vivi + 1)nCh(vi + i,vi)as Ch(vi + 1,vi) is scanned counter-clockwise from vi + 1. VXii = vi if vji is concave. Otherwise, it is the first visible interesection point in RAY (vi + 1,vi)nCh(vi + 1, vi) as Ch(vi +, vi) is scanned clockwise from vj. 4

Suppose that vi + 1 is not concave. Then, there does not exist any point in E(vj,vi + i), which is visible from Ch(vi + 1, VX j i + 1). As illustrated in Figure 3, the same is true for E(vj,vi + 1) and Ch (VX1 + 1,, v,). This motivates the notion of a feasible chain which is defined as follows: FC(VXij, + 1,VXi + 1,i) = {xlx E E(vi,vi + 1) or x E Ch(VXi,i + 1,VX + 1,i)}. This definition gives rise to a new characterization of a visible edge. < Insert Figure 3 > Lemma 2.3: A simple polygon P is visible from E(vj,vi + 1) if and only if E(v,,v1 + i) n FC (vk,vk+1) 0 forall o k<n. [Proof] Let P be visible from E(vi,vi + 1). Suppose that there exists a feasible chain FC(vr,vr + 1) such that FC(vr,vr + 1)nfE(v(,vi + 1) = 0 for some r - i. Then, there does not exist any point in E(vr,vr + 1), which is visible from E(vi,vi + 1). This is a contradiction. Hence, E(vi,vi + 1)nFC(vk,vk + 1)); 0 for all k. Now, assume that E(vj,vi + 1) nFC(vk,vk + 1)e 0 for all k. Suppose that E(vi,vj + 1) is not a visible edge. By Lemma 2.1, there exist a point x in B(P), which is not visible from E(v,vi + i). If the visibility polygon V(x,P) from x is taken out from P, then the remaining portion of P is partitioned into one or more disjoint regions as shown in Figure 3. Clearly, only one of these regions contains E(vj,vi + 1) on its boundary. Let R denote this region. R is bounded by a chain Ch(u,w) and a line segment L(w,u) on the boundary of V(x,P). Without loss of generality, let u be closer to x than w is. Then, u must be a vertex of P, say vj. As illustrated in Figure 4, the internal angle (vj-l,vj,w) is greater than or equal to 180 degrees. Therefore, either RnFC(vj-i,vj) = u or RnFC(vj-i,vj) = {u,w}. Since L(w,u) CV(x,P), E(vi,vi + i)nFC(vj-i,vi) = 0, which is a contradiction. Hence, E(vj,vj + 1) must be a visible edge.' <Insert Figure 4> 5

Ch (VXii+l,VXi+l,i) 1411 VXi+l,i VXi,i+l RAY(Vi+, Vi ) RAY(vi, vi+l ) Ch(VXi+l,i,Vi ) Ch (Vi+l,VXi,i+l ) Figure 3: E(vi,vi+l)is visible from neither Ch(Vi+l,VXji+l )nor Ch(VXi+l,i,Vi).

P w Vr+i Vi I i+1 Figure 4: E( vi'Vi+l) n FC(vj, vj+) = 0.

3. Determining All Visible Edges,~~~~~~~~~~~~~~~qAlV The basic idea for finding all visible edges is to discard, from B(P), every edge which does not share any point with FC(vi,vi + 1), o i <n. In other words, an edge which lies completely in Ch (v; + 1, VXj, + 1) or Ch (VXj + 1,i,vj) cannot be a visible edge. Hence, if all the edges lying completely in Ch (vi + i, VXJ + i) or Ch (VX1 + 1,i, vi) for any i are discarded from B(P), what remains must be all visible edges by Lemma 2.3. In order to find Ch(vi + 1, VXi, + 1) and Ch(VXj + 1,i,vi), it is required to compute VXij + 1, and VXj +,i, respectively, By definition, VXi,i + 1 is v + 1 if vi + 1 is concave. However, it is not obvious how to compute VXij + 1 when vj + 1 is reflexive. The following lemma suggests a way for computing VXji + 1. Lemma 3.1: Let P be point-visible. Suppose that vi + 1 is reflexive. Then, VXij + 1 is the first interesection point of Ch (vi + 1,vi) and RAY(vj,vi + 1) as Ch(vi + 1,vj) is scanned counter-clockwise from vi + 1. [Proof] Let x be the first intersection point of Ch (vi + i,vi) and RAY(vi,vi + 1) as Ch (vi + 1,v) is scanned counter-clockwise from vj + 1. If x is internally visible from vj, then x = VXi, + 1 by definition. Suppose that x is not internally visible from vi. Then, xEV(vj,P). Let w be the first intersection point of Ch (vi + 1,vi) and RAY(vi,vi + i), which is visible from vj, as Ch(vi +,vi) is scanned counter-clockwise from v, + 1. Clearly, the region R bounded by Ch(vj + 1,w) and L(w,v| + 1) is a simple polygon. Since w is colinear with E(vj,vi + 1), RnV(vj,P) = L(vi + 1,w). Suppose that w is visible from x. Then, L(w,x)cP. Since L(vi,w)cP and since x is colinear with E(vi,vi + i), L(vi,x)cP, which is a contradiction. Therefore wEV(x,P), and thus L(vi + l,w)nV(x,P) = 0 as shown in Figure 5. Now consider V(x,P). By the way in which w is chosen, xER. Since L(vj + 1,w) nV(x,P) = 0, V(x,P)c (R \ L(vi + 1,w)). Therefore, V(x,P)nV(vj,P) = 0, i.e., there does 6

w Vi ' Vi+i Figure 5' L( Vi~~l, w ) r'l V~~xP) = ~............

not exist any point y in P such that vi and x can be internally visible from y. This is contradiction-since P is point-visible. Thus, x is visible from vj. Hence, x = VXjj + 1. < Insert Figure 5 > The companion lemma of Lemma 3.1 can be stated for VXj +,i from the symmetry of VXi, + 1 and VX 1,ij. Lemma 3.2: Let P be point-visible. Suppose that vi is reflexive. Then, VX + 1,, is the first intersection point of Ch (vi + 1,vi) and RAY(vi +,vi) as Ch(vi + 1,vi) is scanned clockwise from vi. In order to refer to the open chains Ch (vi + 1,VXi,i + 1) and Ch (VXi + 1 ivi) conveniently, FC(vi,vi + 1) is further decomposed as shown in Figure 5. A chain Ch(VXIj, + 1, v + 1) is said to be a right-feasible chain RFC (vi,v- + 1) with respect to E(vj,v1 + 1). Ch(vi,VXj + 1i) is said to be a left-reasible chain LFC (vivi + 1) with respect to E(vj,vi + 1). It is clear that Ch (v + 1,VX, + 1) and Ch (VXi + 1,j,v) are the complements of RFC(vi,vj + 1) and LFC (vivi + 1), respectively. Furthermore, FC(vi,vi + 1) = RFC(vi,vi + 1) n LFC (vi,vi + 1). Therefore, the following lemma is immediate from Lemma 2.3. Lemma 3.3: A simple polygon P is internally visible from E(vi,vj + 1) if and only if E(vj,v, + 1)nRFC(vk,vk + 1)= 0 and E(vi,vi + 1)nLFC(vk,vk + 1)' 0 for all 0 - k<n. Based on Lemma 3.3, two operations, the right scan and the left scan will be developed. These operations are for discarding, from B(P), all edges which do not share any point with either RFC(vi,vj + 1) or LFC (vi,v + 1) for some O0 i < n. For the right scan, B(P) is traversed from vo in the clockwise order to visit all vertices of P. At each vertex vj, the edges of P are scanned in the counter-clockwise order from E(v2,v3) until the edge E(vr, vr + i) containing VXi, + 1 is encountered. Since VXij, + 1 E E(vr,vr + 1), all the scanned edges except E(vr,vr + 1) are completely contained in Ch(vi + 1, VXj, + 1) and do not share any point with RFC(vi,vi + 1). These 7

edges can be discarded by Lemma 3.3. This process is called the right scan at vi. Performing the right scan at each vertex in turn, it is possible to discard all edges which do not share any point with RFC(vk,vk + 1) for some k. The left scan is symmetric to the right scan. The following data structures will be used for scanning operations: (1) VERTEX: An array containing all vertices of P in the order appearing on B(P) (2) EDGE: A doubly linked list containing all edges of P in the order appearing on B(P) Algorithm 3.1 is for performing the right scan. In the algorithm, CW(x) and CCW(x) denote the next clockwise and counter-clockwise edges of edge x, respectively. Mod (i,n) is a function computing i modulo n. SCAN and RIGHT are Boolean variables which control the outer and inner while-loops, respectively. IAgorithm 3.1: (Performing the right scan) procedure RSCAN (VERTEX,EDG begin Step 0 NEXT -CCW(E(vl,v2)) in EDGE i< —0 SCA N-true Step 1 while (EDGE: 0 and SCAN) do begin Step la RIGHT<-true if vi + 1 is concave, then RIGHT —false Step lb while (EDGE = 0 and RIGHT) do begin if NEXT is to the right of RAY(vi,vi + 1), then begin SAVE<-NEXT NEXT,-CCW(NEXT) in EDGE discard SAVE from EDGE end else RIGHT —false end Step 1c if CW(NEXT) = E(vi + 1,vi + 2) then NEXTE-CW(NEXT) i —mod(i-1,n) if i = 0, then SCAN-false end end 8

Lemma 3.4: Algorithm 3.1 does not discard any visible edge but discards, in O(n) time, all edges which are completely contained in Ch (v; + 1,VXj,i + 1) for some 0-' i<n. [Proof] First, we inductively show that the algorithm does not discard any visible edge but discard all edges which are completely contained in Ch (vi + 1,VXi,j + 1) for some 0- i < n. The induction will be on the number of times Step 1 is reached. Initially, step 0 sets NEXT = E(v2,v3),i = 0, and SCAN = true. Therefore, vi = vo = vn. Since neither EDGE = 0 nor SCAN = false, the body of the outer while-loop is executed. Clearly, vi + 1 = vi. If vi is concave, the inner while-loop is skipped by setting RIGHT = false. Otherwise, the inner while-loop (Step 1 b) scans EDGE from E(v2,v3) in the counter-clockwise order until an edge E(vt,vt + 1) not completely lying to the right of RAY(vo,vl) is encountered. E(vt,vt + 1) must contain VXo,1. Therefore, all edges which are completely in Ch (vi,VXo,1) are discarded, but no visible edge is discarded from EDGE. Notice that this is what the right scan at Vn (or equivalently vo) is required to do. Furthermore, NEXT points to E(vl,v2) by Step 1c so that the right scan at Vn-1 can be performed. Suppose that the following is true until Step 1 is executed k times, 0<k<n: (1) No visible edge is discarded. (2) All edges, which are contained in Ch (vi+ 1,VXi + 1), k<i — n, are discarded. (3) NEXT points to the first edge to be traversed for the right scan at vk. Notice that NEXT does not necessarily point to E(vk + 2, vk + 3) since E(vk + 2,vk + 3) may be discarded from EDGE during the previous scans. Therefore, assumption (3) can be restated as follows: (3) NEXT points to E(vs,vs + 1) in EDGE, where E(us,us + 1) = E(vk + 2,vk + 3), if E(vk + 2, vk + 3)is in EDGE. 9

Otherwise, it is the edge in EDGE such that no edge in Ch(vk + 2,vs), k + 2: s, exists in EDGE. We show that these three assumptions are satisifed after the kth execution of Step 1 (the outer while-loop). There are two possibilities depending on EDGE. Case 1: EDGE =0 Case 2: EDGE 0 If EDGE = 0, then the algortihm is terminated. By assumptions (1) and (2) in the induction hypothesis, the result holds trivially. In this case, there does not exist any visible edge. Suppose that EDGE = 0. There are two subcases: Case 2a: NEXT points to E(vk + 2, vk + 3) Case 2b: NEXT does not point to E(vk + 2,vk + 3). Case 2a: If vk is concave, then the inner while-loop is skipped. Therefore, no edge is discarded from EDGE. By the induction hypothesis, assumptions (1) and (2) are satisfied. By Step 1c, assumption (3) is also satisfied. Thus, the result is obvious. Suppose that vk is reflexive. Since NEXT points to E(vk + 2,vk + 3), Step 1 b (the inner while loop) scans EDGE from E(vk + 2,vk +3) in the counter-clockwise order until the edge E(vt,vt + 1) not completely lying to the right of RAY(vk,vk + 1) is found. If such an edge E(vt,vt + 1) does not exist, then EDGE = 0. In this case, all the discarded edges in the kth execution of Step 1 are lies to the right of E(vk,vk + 1). By Lemma 2.1, none of them can be a visible edge. This together with the induction hypothesis guarantee the result. Now, assume that E(vt,vt + 1) exists. By Lemma 3.1, Ch (vk + 1, VX k,k + 1) CCh (vk + 1,vt + 1). Therefore, no edge in Ch (vk + l, VXk,k + 1) remains in EDGE. However, some edges not contained in Ch (vk + 1,VXk,k + 1) may be discarded. These edges, if any, must lie 10

to the right of E(vk,vk + 1), and none of them can be a visible edge. Thus, assumptions(1) and (2) follow. After executing Step 1b, no edge completely contained in Ch(vk + 2,vt) is available in EDGE, and NEXT points to E(vt,vt + 1). Therefore, if E(vk + 1, vk + 2) is in EDGE, then it must be CW (NEXT), i.e., the clockwise edge of NEXT. Accordingly, by Step 1c, assumption (3) also satisfied. Case 2b: In this case, NEXT points to the edge E(vs, vs + 1) in EDGE such that no edge in Ch(vk + 2,vs) exists in EDGE. By a similar argument as in Case 2a, the result follows. Since the three assumptions are true for all O< k- n, the correctness of the algorithm is immediate. Now, let us analyze the time complexity. At each vertex vi, 0' i < n ( or equivalently O<i n), Algorithm 3.1 scans undiscarded edges in EDGE from E(vs,vs + 1) in the counter-clockwise order until either EDGE = 0 or an edge E(vt,vt + 1), which does not completely lie to the right of RAY (vi,vi + 1), is encountered, where E(vs,s + i) = E(vi + 2,vi + 3) if E(v + 2,vi + 3) is in EDGE the edge in EDGE such that no edge in Ch(vj + 2,vs), i + 2 s exists in EDGE, otherwise, Therefore, Total number of edges scanned by Algorithm 3.1 = \~ the number of edges scanned at v, i=0 11

1<s1 the number of edges scanned and undiscarded at vi i=0 I- 1 + - the number of edges scanned and discarded at vi z=0 Since there at most one scanned and undiscarded edge at each vj, i.e., the last scanned edge if EDGE= 0, the total number of edges scanned and undiscarded is at most n. The total number of edges scanned and discarded is also at most n since a discarded edge is never scanned again. Thus, the total number of edges scanned by Algorithm 3.1 is at most 2n. Since a constant number of operations are needed for each scanned edge, Algorithm 3.1 requires O(n) time in the worst case.I From the symmetry of right and left scans, a similar algorithm can be given for the left scan. Algorithm 3.2: (Performing the left scan) Procedure LSCAN (VERTEX, EDGE) begin Step 0 NEXT —CW (E(vn-,vo)) in EDGE ie-0 SCAN — true Step 1 while (EDGE= 0 and SCAN) do begin Step 1a LEFT-true if vj is concave, then LEFT<-false Step 1b while (EDGE = 0 and LEFT) do begin if NEXT is to the left of RAY (vi + 1,vi) then begin SAVE<~-NEXT NEXT<-CW(NEXT) in EDGE discard SAVE from EDGE end else LEFT<-false end if CCW (NEXT) = E(vil,vi), then NEXT —CCW (NEXT) i-mod (i + 1,n) if i= 0, then SCAN<-false end end 12

Lemma 3.5: Algorithm 3.2 does not discard any visible edge but discards, in O(n) time, all edges which are contained in Ch (VXj + 1,,vi) for some 0- i< n. From Algorithms 3.1 and 3.2, a linear time algorithm for determining all visible edges in a point-visible polygon is immediate. Algorithm 3.3: (Determining all visible edges in a point-visible polygon) procedure VEDGE-P begin Step 1 REDGE <-EDGE Call RSCAN (VERTEX, REDGE) Step 2 LEDGE<-EDGE Call LSCAN (VERTEX, LEDGE) Step 3 VEDGE<-REDGEnLEDGE end Theorem 3.1: Algorithm 3.3 finds all visible edge of a point-visible polygon in O(n) time. [Proof] From Lemma 3.4, Step 1 discards all edges from an edge list REDGE, which are completely in Ch (vI + 1,VXj, + 1) for some 0O i <n. After executing Step 1, every edge in REDGE shares at least a point with RFC (vk,vk + 1) for all O — k<n. Similarily, after executing Step 2, every edge in LEDGE shares at least a point with LFC (vk,vk + l) for all 0 k<n (see Lemma 3.5). By Lemma 3.3, VEDGE which is REDGE nLEDGE (see Step 3) contains all visible edges. By Lemmas 3.4 and 3.5, Steps 1 and 2 can be done in O(n) time. Since both REDGE and LEDGE are sorted, Step 3 can also be done in O(n) time. Hence the time complexity of Algorithm 3.3 is O(n). I A trivial lower bound in time complexity for computing all visible edge in a point-visible polygon with n edges is Q(n). Thus, Algorithm 3.3. is optimal within some constant multiplictive factor. 13

4. Conclusion It has been an-open problem to determine a visible edge, if any, of a simple polygon in O(n) time ever since Avis and Toussaint [1] presented a linear time algorithm for determining if a simple polygon is visible from a given edge. In this paper, we show that if the kernel of a simple polygon is non-empty, then all visible edges, whether they are completely, strongly, or weakly visible, can be found in O(n) time. 14

References 1. Avis D. and Toussaint, G., An Optimal Algorithm for Determining the Visibility of a Polygon from an EDGE, IEEE Tran. Comput., C-30, 12, (1981), 910-914. 2. El Gindy, H. and Avis, D., A Linear Algorithm for Computing the Visibility Polygon from a Point, J. Algorithm, 2, (1981), 186-187. 3. Fisk, S., Short Proff of Chvatal's Wachman Theorem, J. of Combinatorial Theory B, Vol. 24, (1978), 374. 4. Kahn, J., Klawe, M., Kleitman, D., Traditional Galleries Require Fewer Watchman, IBM Research Report RJ3021, (Dec. 1980). 5. Lee, D. and Preparata, F., An Optimal Algorithm for Finding the Kernel of a Polygon, J. ACM, 26, 3 (July 1976), 415-421. 6. Woo, T. and Shin, S., A Linear Time Algorithm for Triangulating a Point-Visible Polygon, ACM Trans. Graphics, Vol. 4,1, (1985), 60-70. 15