AN OPTIMAL ALGORITHM FOR FINDING ALL VISIBLE EDGES IN A SIMPLE POLYGON S.Y. Shin T.C. Woot Technical Report 87-28 School of School of Electrical Engineering and Computer Science Korea Institute of Technology Taejeon, Korea tDepartment of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan

abbreviated title: All Visible Edges in a Simple Polygon mailing address: T.C. Woo Department of Industrial & Operations Engineering University of Michigan Ann Arbor, MI 48109-2117

Abstract Whether the interior of a simple polygon is visible to a given edge can be determined in O(n) time [1], where n is the total number of edges in the polygon. In this paper, we find all such visible edges in O(n) time. It is made possible by showing that there can be at most three visible edges in a simple polygon with an empty kernel.

-1 1. Introduction The visibility of a polygon from an edge is considered by Avis and Toussaint[l]. In it,they developed an O(n) algorithm for determining if a simple polygon is visible from a given edge. They also introduce three kinds of edge visibility-weak, strong and complete, that are illustrated in Figure 1.1. In this paper, we pose the question: Given a simple polygon, can we find all the visible edges, if there are any, in O(n) time? If the kernel of the given polygon exists, then finding all the completely visible edges is trivial since they must be contained in the kernel. Likewise, finding all the strongly visible edges in a polygon with a kernel is also straightforward. (It may be noted that if the kernel of a polygon does not share any point with the boundary of the polygon, then these two kinds of visible edges do not exist.) The only interesting variation is to find all the weakly visible edges. Shin and Woo[7,8] described a linear time algorithm for finding all weakly visible edges in a polygon for which a kernel exists. In this paper, we examine the problem of finding all weakly visible edges in a simple polygon in which a kernel does not exist. A straightforward approach would be to apply the Avis and Toussaint's linear time test[l] for edge visibility to each of n edges hence yeielding an O(n2) algorithm. We give an O(n) algorithm for finding all weakly visible edges, if any, in a simple polygon with an empty kernel. This algorithm together with the Shin and Woo's algorithm[8] make it possible to find all weakly visible edges of a simple polygon in linear time. < Insert Figure 1.1 >

- iL/S~~~~ssss~~ In in P vI Vi vi E(vi,vi+i) (a) P is completely visible fromi E-v,, vi+1) +1 Vi i+ 1 E(Vi,vi+1) (b) P is strongly visible from E(vi,vi+l) Vi E (Vi, vi+ l ) Vi+ I (c) P is weakly visible from E(vi,vi+l) Figure 1.1: P is visible from E(vi,vi,l)

-2 2. Preliminaries Let P be a simple polygon with n vertices in the plane. Every vertex vi, where i is taken modulo n, is represented by its Cartesian coordinates (xi,yi). These vertices in sequence are maintained as a circular doubly linked list so that the interior of P lies to the left as the boundary B(P) of P is traversed in the counter-clockwise order. We assume that no three consecutive vertices of P are colinear. Definition 2.1: L (u,w) denotes a directed line segment joining two points, u and w with the direction from u to w. An open line segment L(u,w) is the line segment L(u,w) excluding its two endpoints, u and w. Definition 2.2: An edge E(vi,vi+l) is the segment L(v1,vi+l) joining two adjacent vertices vi and vi+l on the boundary B(P) of P. An open edge E(v,,vi+1) is the edge E(vi,vi+) excluding its two endpoints, vi and vi+i. Definition 2.3: Let u and w be two distinct points on the boundary B(P) of P. A chain Ch(u,w) is the portion of B(P) from u to w as B(P) is traversed in the counter-clockwise sense. An open chain C^(u,w) is the chain Ck(u,w) excluding its two endpoints u and w. Definition 2.4: A ray RAY(u,w) is a halfline starting from u with the direction from u to w. Definition 2.5: Two points u and w in P is said to be visible if the line segment joining them is completely contained in P. Definition 2.6: 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).

-3 Definition 2.7: P is said to be weakly visible from L (u,w) in P if, for every point s in P, there exists a point t in L(u,w) ( depending on s ) such that s and t are visible. P is line-visible if there exists a line segment L(u,w) in P from which P is weakly visible. If such a line segment L(u,w) is contained in an edge of P, then P is said to be edge-visible. Definition 2.8: An edge E(vi,v1i+) is said to be a visible edge if P is weakly visible from E(vi,vi+l). Definition 2.9: Given a polygon P and a point z in P, the visibility polygon V(z,P) from z is defined to be the set of all points in P, which is visible from z. Avis and Toussaint gave an elegant characterization of a visible edge. We state a part of their results[l] without proof. Lemma 2.1: A polygon P is weakly visible from an edge E(vi,vi+l) if and only if its boundary B (P) is weakly visible from E(vi,vi+1)[l]. Shin and Woo [7,8] exhibited an O(n) algorithm for finding all visible edges for a polygon with a non-empty kernel. Their basic idea was to discard all edges not satisfying Lemma 2.1. Linear time was made possible by exploiting pointvisibility of a star-shaped polygon. In this paper, we find all visible edges in a polygon with an empty kernel. We employ Helly's theorem [6] to discard edges not satisfying Lemma 2.1. Lemma 2.2(Helly's theorem): Let {Sil i I, where I is an index set} be a finite collection of convex sets in R d. If every subcollection consisting of d+ 1 or fewer sets in the collection has a nonempty intersection, then the entire collection has a nonempty intersection[6]. Let HP(u,w) denoted the half plane which lies to the left of L (u,w). It is well

-4 known that n-1 (2.1) K(P)= r HP(vi,vi+l) (2.1) i=O Suppose that K(P)=0. Since HP(vj,vi+l), 0~ i< n, is a convex set in R2, the following result is immediate from Lemma 2.2. Lemma 2.3: If the kernel K(P) of a simple polygon P is empty, then there exist three distinct edges, E(vi,vi+l), E(vvj,,vj), and E(vk,vk+l) such that HP(vi,vj+))n HP(vj,vj+ )n HP(vk,vk+l)=. Assuming that K(P)=0, consider three distinct edges, E(viv+1i), E(v,,vi+I) and E(vk,vk+i) such that HP (vi,vi+ l) H HP (vj, vj+l) HP (vi, vk + 1)= 0 (2.2) Suppose that E(v,,Va,+) is a visible edge. Then, every point z in E(vr,vr+l), r=i,j,k is visible from some point ( depending on z ) in E(vva+l). In particular, each midpoint of E(v,,vr+l), r=i,j,k, is visible from E(va,va+l). Since visibility is a symmetric relation, the converse is also true, i.e., there exists a point in E(va,Va+l), which is visible from the midpoint of E(v,,vr+i) for each r=i,j,k. In section 3, we show that there exist at most three edges in P such that each of them contains a point ( depending on r ) which is visible from the midpoint of E(vr,vr+l) for all r=i,j,k. In section 4, we present a linear time algorithm for finding all such edges. Although each of these edges contains a point which is visible from the midpoint of E(v,,v,+l), r=i,j,k, it may not be a visible edge since they do not necessarily satisfy Lemma2.1. We submit each of these edges to Avis and Toussaint's test [1] for determining its edge visibility. Finally, in section 5, we present a linear time algorithm for finding all visible edges in a simple polygon.

-5 3. Characterization of a Candidate Visible Edge Let mr be a point in an open edge E(vr,vr+i), i.e., mreE (vr,v+ 1),r= i,j,k (3.1) Suppose that K(P)=0. From Lemma 2.3, there exist three edges E(vi,vi+i), E(vj,vi+l) and E(vk,vk+l) such that HP(vivi+l)n HP(vi,vj+l)n HP(vkvk+l)=0 (3.2) Since V(mr,P) C HP(vr,vr+l),r=i,j,k, V(mi,P)n V(mj,P)' V(mt,P)=0. (3.3) It is obvious that a visible edge shares at least a point with each of three visibility polygons, V(mr,P),r=i,j,k. Conversely, if an edge shares at least a point with each of them, it can possibly be a visible edge. Definition 3.1: Let HP(vj,vi+i)) HP(v,vj,+i) ) HP(vk,vk+l)= 0. An edge of P is said to be a candidate if it shares at least one point with each of V(mi,P), V(mj,P), and V(mk,P). We show that there are at most three candidates if K(P)=0. From Equation (3.3), there are two possibilities: Case 1: Among three visibility polygons, V(m,,P),r=i,j,k, there exist a pair of them which do not have a common intersection. Case 2: The three visibility polygons are pairwise intersecting. For Case 1, let V(mi,P)n V(mj,P)=0 without loss of generality. By taking out from P all points in V(mi,P), the remaining part of P is partitioned into disjoint regions as shown in Figure 3.1. < Insert Figure 3.1 >

\ V' (mi,P) i * * ~ a.1 % p d Figure 3.1: V(mi,P) Partitions P

-6 Each region Rf,f=0,1,2, is a simple polygon bounded by a portion of B(P) and a line segment S on the boundary of V(mi,P). Let mj be contained in Rf for some f. We show that V(mj,P) does not share any point with another remaining region. Lemma 3.1: Suppose that V(mi,P)h V(mj,P)=0. Let Rf,f=0,1,2, be the remaining region after subtracting V(mi,P) from P. If mjERf for some f, then V(mj,P)C Rf. [Proof] Suppose that V(mjP) shares a point z with another remaining region Rg,g: f. Then L(mj,z)c V(m,P)cP (3.4) Rg is bounded by a portion of B(P) and a line segment S on the boundary of V(mi,P). Since V(mi,P)( V(mj,P)= 0, SqL(my,z)=0. Since the remaining regions are disjoint, mjdRg. Therefore, L(mj,z) crosses an edge of P which bounds Rg. This contradicts Equation (3.4), which asserts that L(mj,z)CP. Hence, V(mj,P) does not intersect any remaining region except Rf. 0 An implication of Lemma 3.1 is that mj is not visible from any edge which does not intersect Rf. Thus, only the edges sharing one or more points with Rf can possibly be a visible edge. However, a visible edge is required to intersect V(mi,P). By the way in which Rf is constructed, there are only two such edges, i.e., the edges which are contained (or partly contained) in Rf and intersect V(mi,P). Therefore, there are at most two candidates in Case 1. Lemma 3.2! Let HP(vi,vi+1)^ HP(vj,vj+1) HP(vL,vk+l)=0. If V(mf,P),r=i,j,k does not pairwise intersect, then there exist at most two candidates. Now, consider Case 2, where V(m,,P),r=i,j,k are pairwise intersecting. Let Lr = the line containing E(vr,v,+1),r=i,j,k

-7 ip, = the intersection point of lines Lp and Lq. By assumption, HP(vi,vi+l)n HP(vj,vj+l)n HP(vk,vk+l)= 0. Since V(m,,P) C HP(Vr,Vr+), HP(Vr,Vr+), r=i,j,k are pairwise intersecting. Therefore, the following is true: (1) iij, ijk, and iki are well-defined and distinct (2) iij, ijk, and iki are not colinear As illustrated in Figure 3.2, no interior point of the triangle (ij,,ik,iki) is contained in HP(vT,vr+i) for any r=i,j,k. In the following lemma, we show that the triangle (iij,,k,iki) is entirely contained in P. < Insert Figure 3.2 > Lemma 3.3: Suppose that the following is true: (1) HP (vi,vi+l) HP (vj,j+ ) n HP (vktv+ )== 0. (2) V(mr,P),r=i,j,k are pairwise intersecting. Then, every point in the triangle, (ii,ijk,iki) is contained in P. [Proof] Take three points, uij,uij, and uki such that Uij, V(mi,P)(r V(mj,P) ujkE V(mj,P)r V(mk,p) (3.5) ukiE V(mk,P)( V(mi,P) Since HP(vi,vi+l)F HP(vj,vj+l)' HP(vk,vk+l)= 0, V(mi,P)n V(mj,P)" V(mk,P)=0 (3.6) From Equations (3.5) and (3.6), three points, uijujk, and uki are necessarily distinct. Futhermore, Uki E V(mi,P) and uiji V(mi,P) uije V(mj,P) and uj, V(mj,P) (3.7) ujkE V(mk,P) and uki V(mk,P) Let P(w,z) be a simple path between two points, w and z. From Equation

Lk Hp(vi,vi+l) HP(Vk,Vkl) HP,vk+l) 1-[P(vjvj+i) n lIP(v,,vjl) n HP(vi,vi+) Figure 3.2: iii,ijk, and iki are well-defined.

-8 (3.7), it is possible to construct three simple paths, P(Uki,ui), P(Uij,Ujk), and P(ujk,Uki) such that P(Uki,Uij)C V (mi,P) P(uij,ujk)c V(mj,P) (3.8) P(jk,uki)c V (mk,P) Moreover, these three paths can be constructed so that they pairwise intersect only at uij,uik, and uki. Since V(m,,P)cP,r=i,j,k, P(uki,uij)cP, P(uij,ujk)cP, and P(ujk,uki) P (3.9) In words, each of these simple paths is completely contained in P. Since V(mr,P)CHP(vr,vr+l),r=i,j,k, the following is immediate from (3.8): P(Uki,Uij)c HP (vi, vi+l) P(uij,uj)c HP(v,vj,+l) (3.10) P(ujk, uki)c HP(vk,vk+l) Equations (3.10) implies that each of these three paths does not share any point with the interior of the triangle (iij,ijk,ik). This is true since HP(vr,vr+),r=i,j,k does not share any point with the interior of the triangle. Thus the triangle (iiO,ijk,ik) is completely contained in R bounded by the three paths (See Figure 3.3). From Equations (3.9), these three paths lie completely in P. Hence, the triangle (ii,ijk,ik) is completely contained in P. 0 < Insert Figure 3.3 > From Lemma 3.3, every interior point of the triangle (ii,ijk,ik,) is an interior point of P. Let u be an interior point of the triangle (ij,ij,,iki). Since u is also interior point of P, there exists a line segment L(w,,z,) for each r=i,j,k satisfying the following properties (See Figure 3.4): (P1) u L (wr,zr)cP (P2) L(wr,Zr),n B(P )={Wr,zr}and L(w,,z,) q B(P)= 0

HP(vi,vi.+) n HP(vk,vk+l) IP (vj,vj. ) r HP( vk,v,+ HP(vi,vil) n HP(vj,vijt) Figure 3.3: The triangle (iii,ijk,ik) is contained in P.

-9 (P3) L(Wr,Zr) is parallel with E(Vr,vr+i) (P4) the direction of L (wr,zr) is opposite to that of E(V,vr+i). < Insert Figure 3.4 > HP(vr,vr+l),r=i,j,k is determined by the line Lr containing E(vr,vr+i) which is parallel with L(wr,zr). Therefore, L(wr,zr) either is contained in HP(vr,vr+I) or does not share any point with HP(vr,vr+l). However, no interior point of the triangle (iij,ijk,iki) is contained in HP(vr,Vr+l). In particular, u4 HP(vr,Vr+l) for any r=i,j,k. Therefore, L (w,r,r) HP(vr,v,r+l)= 0,r=i,j,k. (3.11) From Equation (3.11), the following two lemmas are immediate. Lemma 3.4: Let HP(vi,vi+)n HP(v,vY+1i)n HP(vk,v^t+)=0. If V(mr,P),r=i,j,k, are pairwise intersecting, then HP (Vr,V+ )c HP (z, r),r= i, j,k. [Proof] Let V(mr,P),r=i,j,k be pairwise intersecting. By property (P4), L (Wr,Zr) has the opposite direction to E(vr,vr+l). Thus, L(zrwr) and E(Vr,v^r+) have the same direction. From property (P3), L(zr,w,) and E(v,,vr+l) are parallel. Therefore, either HP(v,,vr+l)cHP(zr,wr) or HP(zr,wr)cHP(vrvr+). If HP(vr,Vr+i)C HP(zr,wr), then L(z,,wr)C HP(v,,vr+l) (or equivalently L(wr,zr)C HP(vr,Vr+l)), which contradicts Equation (3.11). Hence, HP(vr,vr+l) HP(Zr,Wr). 0 Lemma 3.5: Let HP(vi,vi+l)' HP(vj,vj+l)( HP(vk,vk+l)=0. If V(m,,P),r=i,j,k are pairwise intersecting, then no point in L (wr,zr) is visible from mr, i.e., L (Wr,Zr) ( V(mr,P)=0,r=i,j,k. [Proof] From Equation (3.11), L(wr,zr) n HP(vrVr+l)=0. Since V(m,,P) C HP(vr,,vr+), L(Wr,Z,) n V(mr,P)=0. 0

HP (vi,vi+ l) Z. / Vi Vi+ I Wi HP (v;, vj+ 1) HP(vk,vk+l) V. /+I Figure 3.4: HP(Yvr,r+) n L (wrr) = 4,r = i, j k.

- 10 A pair of points, w, and z, for each r=i,j,k partition B(P) into two chains, Ch(Wr,Zr) and Ch(ZrWr). From properties (P1) and (P2) of L(w,,zr), L(w,,zr) partitions P into two simple polygons, and PI and,2 as follows: P,r = the simple polygon bounded by C,(w,,z,) and L (z,,w,) p2 = the simple polygon bounded by C (Zr^,w) and L (Wr,Zr). Accordingly, Pr, Pr = P and prl pr2=L ( rz),r=ijk. (3.12) By properties (P1) abd (P3) of L(wi,zi), L(wi,zi) containing u is parallel with E(vi,vi+l), where u is an interior point of the triangle (iij,ik,iki). Thus, L(wi,zi) and E(vi,vi+) are not colinear. Since L (iki,iij) is contained in the line Li containing E(vi,vi+,), L(wi,z,) and L(iki,iij) are parallel but not colinear. Futhermore, L(wi,zi) bisects both L(iij,ij,) and L(ij,,iki). Therefore, Lu(iki,ij) and ijk cannot be simultaneously contained in Pi1 (or Pi2). Since L (iki,ii)cLicHP(vi,vi+l), L(iki,ijj)cHP(zi,w,). This implies that L(iki,iij) lies to the right of L(wi,zi). Since the interior of Pi, lies to the right of L(wi,zi), L (ik,iij)cPi' and i E Pi2 (3.13) Similarly, as illustrated in Figure 3.4, L (iij,iji)cPil and iiePj2 (3.14) L (ik,iki)c P and iijeP2 Thus, the following lemma can be obtained. Lemma 3.6: Let HP(vi,vi+l)" HP(vj,vj+l)n HP(vk,vk+l)=0. If V(m7,P),r=i,j,k are pairwise intersecting, then the following is true L ( ii,iij) c Pi 1 and ik E Pi2 L (ijjijk)c P1l and ikiEP L(ijk,iki)c P1 and iijeP2 ^~ ~~ (^kc1ad^^

- 11 - < Insert Figure 3.5 > Since mEE(vr,vr+i), every point in E(vr,vr+l) is visible from m,. From Lemma 3.5, neither w, nor w, is visible from m,. Therefore, w4E(vr,Vr+l) and zE(v,,r+l). (3.15) This implies that either E(Vr,v)+l)cCh(wr,Zr) or E(vr,Vr+l)CCh(zr,Wr). We show that E(v,,vr+l)C Ch(wr,Zr). Lemma 3.7: Let HP(vi,vi+i)Th HP(vj,vj+l)r HP(vk,vk+l)=0. If V(mr,P),r=i,j,k are pairwise intersecting, then E(Vr,Vr+l) C:h(wr,Zr),r=i,j,k. [Proof] Suppose that E(vi,vi+l)cC,(zi,wi). Then, mi E ( vi,vi+ )c Pi2. (3.16) We first show that, given E(vi,vi+l)c Ch(zi,wi), mrE Ch (Zi,wi),r=i,j,k. (3.17) Assume that mjECh(wi,zi). Then mjePil. Since miePi2 and L (wi,zi)n V(mi,P)=0, V (mi,P)c Pi2. (3.18) Thus, V(m,,P) n V(mj,P)cPi2 (3.19) Let a set G be defined as follows: G={gl gV(mj,P) and gEPi2}. Then, from Equation (3.18), V(mi,P)f V(mj,P)=V(mi,P)( G. (3.20) By Lemma 3.4,

Wi Zk Zi ( a ii) u Lki vi v ik~ Vi i L k L LK a) (wi, zk, wj, zi, wt, Zi) zj Lk (b) (wi, Zj, wk, zi, Wj, Zk) Zi Figure 3.5: wj and z,, r = i, j, k are alternating.

- 12 V(mi,P)c HP (vi,vi+l)c HP(zi,wi). (3.21) Therefore, every point in V(mi,P) lies strictly to the left of L(zi,wi) or equivalently lies to the right of L (wi,zL). Now, consider G. The interior of pi2 lies to the left of L(wi,z,). Since myjeC(wi,zi)cPiI, every point g is visible from mi only through L (wi,z), i.e., L (mj,g)n" L (wi,zi) 0 for all g G. (3.22) Moreover, mjEE(vj,vj+1) so that mj is not an endpoint of E(vy,vy+l). Thus, Equation (3.22) implies that every point g in G lies on or to the left of L(wi,zi). Therefore, V(mi,P) G = 0, (3.23) From Equations (3.20) and (3.23), V(mi,P)( V(mj,P)=0, which is a contraction. Thus, mjiC^(wi,zi) or mjECh(zi,wi). Similarly, mkECh(Zi,wi). Hence, given E(vi,vi+l)cC^(zi,wi), Equation (3.17) holds true. Now, we show that E(vi,vi+,) cannot be contained in C^(zi,wi) using Lemma 3.3 and thus arrive at a contradiction. Consider the simple polygon i2. Since mrECh(zi,Wi)cPi2, there exists an edge E(ar,br) of Pi2 for each r=i,j,k such that (1) E(ar,br)gE(v,,vr+l) and mrE(ar,,br) (2) E(ar,br) has the same direction as E(v,,vr+l) By property (1), E(ar,br)c Lr,r=i,j,k (3.24) From Equation (3.24) and property (2), HP (ar,br)=HP (v,,vr+),r=i,j,k (3.25)

- 13 - Therefore, the triangle determined by Lr containing E(a,,b,),r=i,j,k is the triangle (iij,ijk,iki). By Lemma 3.6, L (iki,iij) Pi2= 0, (3.26) which means that the triangle (iij,ij^,iki) is not completely contained in Pi2. This contradicts Lemma 3.3 if pi2 satisfies the assumptions for this lemma. From Equation (3.25), HP(ai,bi)( HP(aj,bj)(- HP(ak,bk)=0. Thus, P2 satisfies assumption (1) for Lemma 3.3. We will be done if we show that Pi2 also satisfies assumption (2), i.e., V(m,,Pi2),r=i,j,k are pairwise intersecting. Since V(m,P )c Pi2, V(mi,Pi2)" V(mj,Pi2)=V(mi,P)() V(mj,P)~ 0 (3.27) V ( mi,Pi2) h V (mk,Pi2)= V (mi,P) (" V(mk,P ) 0 We need to show that V (mj,Pi2)( V(mk,Pi2) 0. (3.28) From Lemmma 3.6, ijePi2 and L (ik,ii)cPi'. Since L (wi,zi) bisects L(ijk,ik), ijk lies strictly to the left of L (wi,zi). Therefore, every point in HP(vj,vj+1)n HP(vk,vk+1) lies strictly to the left of L (wi,zi). Thus, every point in V(m,,P)n V(mk,P) also lies strictly to the left of L(wi,zi). Suppose that a point h in V(mj,P) V(mk,P) is contained in Pi,. Since both m1 and mk are contained in CA,(zi,wi), h lies to the right of L (wi,z,), which is not possible. Therefore, V(mj,P)(n V(mk,P)c Pi2 (3.29) From Equation (3.29), inequality (3.28) follows. Hence, Pi2 also satisfies assumption (2) for Lemma 3.3. However, the triangle (iij,ijk,ijk), which is determined by L,,r=i,j,k, containing E(a,,br), is not contained in Pi2. This contradicts Lemma 3.3. Thus, E(vi,vi+l)cC1(wi,zi). By a similar reasoning, E(vj,vj+l)cCh(Wj,Zj) and E(vk,Vk+l)cCh(wk,zk)-. O

- 14 - Based on Lemma 3.7, we develop a fundamental relationship among w, and Zr r=i,j,k. Lemma 3.8: Let HP(vi,vi+ 1) HP(vj,vj+1) ( HP(v,,vk+l)=0. Suppose that V(mM,P),r=i,j,k are pairwise intersecting. Then, wr and z,,r=i,j,k, appear in one of the following order as B(P) is scanned from wi in the counter-clockwise sense: (1) (wi,zk,Wj,zi,Wk,zj ) (2) (wi,zj,Wk,Zi,wj,z ) [Proof] L(w,,zr),r=i,j,k are pairwise not parallel and share a common point u from properties (P1) and (P4) of L(w,,z,) so that L (wi,zi)n L (wj,z)=L (wj,zj) n L (wk,zk)=L (wk,zkn L (wi,zi)=u (3.30) Therefore, either wi or zj(but not both) is to the right of L(wi,zi). We consider the following two cases separately: Case (a): wj lies to the right of L (wi,zi) Case (b): zj lies to the right of L (wi,zi) Case (a): Let CN(s,t) be a cone obtained by rotating the ray RAY(u,s) about u in the counter-clockwise sense until RAY(u,t) is encountered. Since wj lies to the right of L(wi,zi), RAY(u,wj) partitions HP(zi,wi) into two cones, CN(wi,wj) and CN(wj,z1). Accordingly, by Equation (3,30) and properties (p2) and (P4), Ch(wi,zi) is also partitioned into Ch(wj,wj) and Ch(wj,zi). From Lemma 3.4, HP (,Vr+1)c:HP(zr,wr),r=i,j,k. Therefore, HP (vi,vi+l)(hn HP (vj,vj+l)c z HP (zi,wi)n HP (zj,wj). (3.31) HP(vr,Vr+l) lies strictly to the right of L(wr,zr),r=i,j,k. Since ueL(wrZr), HP(vr,vr+l) lies strictly to the left of L(u,wr) and strictly to the right of L(u,zr). By definition, every point in CN (wj,zj) lies to the left of L (u,wj) and to the right

- 15 - of L(u,zi). Since every point in HP(z,,wi)n HP(zj,wj) lies to the left of L(u,w1) and to the right of L(u,zi), CN (wj,zi)=HP(zi,wi)^ HP(zj,wj) (3.32) From Equations (3.31) and (3.32), HP(vi,vi+l) h HP(vj,vj+l)c CN (wj,zi). (3.33) Since L(wi,zi) LH(wk,zk)=u, either wk or zk (but not both) lies to the right of L (wi,zi). Suppose that wk lies to the right of L (wi,zi). Then, RAY(u,wk)cHP(zi,wi) (3.34) Since RAY(u,wj) partions HP(zi,wi), either RAY(u,w)c CN (wi,wj) or RAY(u,wk)c CN(wj,zi). If RAY (u,w)c CN (wi,wj), then CN (wj,zi)c HP( zk,wk ), (3.35) since L(w,,z,),w=i,j,k are pairwise not parallel and share a point u. From Equations (3.33) and (3.35), HP (vi, vi+ 1)n HP(vj,vj+l)c HP(zk,wk) (3.36) This together with the fact that HP(vk,vk+) cHP(zk,wk) implies that HP (ivi+,vi+l) HP(vj,vj+1) ( HP(vk,vk+l) 0, which is a contradiction. Thus, RAY (u,wk)ct CN (w,wj). Now, suppose that RAY(u,wk)c CN (wj,z ). L,,r=i,j,k determining HP(v,,vr,+) is parallel with L (w,z,). Since HP(vi,vi+l)M HP(vj,vj+1)c:CN(wj,zi), RAY(u,wk) intersects HP(vi,vi+l) HP(vY,vj+i). However, RAY(u,wk)cLk HP(vk,vk+ 1) (3.37) Therefore, HP(vi,vi+l)( HP(vj,vjy+i) HP(vk,vk+l)* 0, which is also a contradiction. Thus, RAY(u,wk) CN(wj,zi), either. Consequently, wk does not lie to the right of L (wi,zi), and zk lies to the right of L (wi,zi), i.e.,

- 16 - RAY(u,zk)c HP(zi,Wi) (3.38) Thus, either RAY (u,zk)c CH(wi,wj) or RAY (u,zk)c CN(wj,zi). Suppose that RAY(u,zk)cCN(wj,zi). Using a similar argument as that employed for deriving Equations (3.33) and (3.35), HP ( v vj+ ) n HP( vk, v+ ) c CN (wj,zk) CN (wj,zk)c HP ( i,wi) (3.39) Equations (3.39) implies that HP(vi,vi+l)n HP(Vk,Vj+l) n HP(vk,vk+l)~ 0, which is a contradiction. Therefore, RAY(u,zk)c CN(wi,zj) (3.40) Thus, ZkECh(wi,wj). Since WjECh(Wi,Z;), Ch(wi,Zk)c CA(wi,wj)c Ch(wi,zi) (3.41) Accordingly, as illustrated in Figure 3.5, Ch(zi,wk)c Ca(zi,zj)c Ch(zi,Wi) (3.42) From Equations (3.41) and (3.42), the result follows. Case (b): By a similar argument, CA (Wi,j)c C (wi,wk )c Ch(Wi,Zi) Ch(zi,Wj)c Ca(zi,zk)c Ca(zi,Wi) (3.43) Hence, the result holds. 0 Now, we are ready to present the comparison lemma of Lemma 3.2 for Case 2. Lemma 3.9: Let HP(vi,vi+1)r HP(vj,vj+1) - HP(vk,vk+i)~ 0. If V(mr,P),r=i,j,k are pairwise intersecting, then there exist at most three candidates. [Proof] From Lemma 3.5, V(m,,P)(qn L (wr,Zr)=,r=i,j,k. By Lemma 3.7,

- 17 - mrEE(vr,vr+l)c Ch(Wr,z,)c P1. (3.44) Therefore, no point in Pr is visible from mr,r=i,j,k. In particular, no point in Ch(zr,Wr) is visible from mr. Thus, if an edge of P is completely contained in Ch(Zr,Wr) for some r=i,j,k, it can not be a candidate by Definition 3.1. Points wi and zi partition B(P) into two chains, Ch(wi,zi) and Ch(zi,wi). None of the edges, which are completely contained in Ch(Zi,wi), can be a candidate. However, an edge, which is partly contained in Ch(z;,wi), can possibly be a candidate. There are at most two edges which are partly contained in Ch(zi,wi), i.e., (1) the edge containing w, if wi is not a vertex. (2) the edge containing zi if z, is not a vertex. These edges, if they exist, are also partly contained in Ch(Wi,Zi). In order to identify other possible candidates, consider Ch(wi,zi). From Lemma 3.8, there are two possibilities: (a) Ch(wi,zk)c Ch(wi,wj)c Ch(wi,Zi) (b) CA(wi,zi) chC(Wi,Wk)C CCh(wwizi) Without loss of generality, let CA(wi,zk)c Ch(wi,wj)c Ch(wi,zi). (3.45) (Notice that (a) can be obtained from (b) by swapping (wj,Zk) and (Wk,zj). ) Then, Ch((Wi,Zi)=Ch (Wi,zk)n CA(ZkZ). (3.46) Consider Ch(zk,Zi). Since Ch(zk,zi) c CA(zk,wk), no point in CA(zk,zi) is visible from mk. Therefore, if an edge is completely contained in Ch(zk,zi), it cannot be a candidate. There are at most two edges which are partly contained in Ch(zt,zi), i.e., (3) the edge containing zk if zk is not a vertex.

- 18 - (4) the edge containing z, if z, is not a vertex. However, the edges (2) and (4) are the same. Finally, consider Ch(wi,zk). Since Ch(Wi,zk) C CA(zj,Wj), no point in Ch(wi,zk) is visible from mi. There are at most two edges which are partly contained in Ch(wi,zk), i.e., (5) the edge containing wi if wi is not a vertex (6) the edge containing zk if zk is not a vertex. However, the edges (5) and (6), if any, are the same as the edges (1) and (3), respectively. Hence, there are at most three candidates in Case 2. 0 From Lemma 3.2 and 3.9, the following result is immediate. Theorem 3.1: If K(P)=0, then there are at most three candidates, and thus at most three visible edges in P. 4. Choosing all Candidates In this section, assuming that K(P)=0, we show algorithmically that all candidates can be found in 0(n) time. Suppose that K(P)=0. From Lemma 2.3, there exist three edges, E(v,,v,+l),r=ij,k, such that HP (vi,vi+l)( HP(vi,vj+l)q HP(vk,vk+l)=0 (4.1) We first show that E(Vr,vr+i), r=i,j,k can be found in O(n) time. Let Kt(P)= HP(vm,v,m+),t=0,1,2,,n-1. (4.2) m=O Since K(P) is the intersection of n half planes HP(vm,vm+l), O< m< n, K,_-(P)=K(P). Lee and Preparata[4] presented a linear time algorithm for finding K(P). Their basic idea is to iteratively construct Kt(P), i.e., HP(vo,vl), if t=o Kt(P) = K,.1(P)n HP(vt,vt+1), otherwise (4.3) The algorithm is terminated if it encounters one of the following conditions:

- 19 - (1) Kt_1(P)~ 0 and K,(P)=0 for some 0< t< n-1 (2) K^.-(P) is constructed, i.e., t=n-1. Since K(P)=0, the algorithm is always terminated with condition (1), i.e., Kt-,(P): 0 and Kt(P)~0 for some 0< t n-l. Moreover, 2<t<n-l since two adjacent edges share a common vertex. Thus, the following result is immediate from reference[4]. Lemma 4.1: Suppose that K(P)=0. Then, there exist K-_(P) and E(vt,vt+) for some 2< t< n-l such that K,_1(P)~ 0 and K,(P)= 0. Such an edge E(v,,v,+l) can be obtained in 0(n) time[4]. Assuming that K,-1(P)~ 0 and K,(P)=0,0< t< n- 1, let Ht = {HP(v,,v,,,+) 0< m< t}. (4.4) Since Kt,_(P)~ 0, every subset of t or fewer halfplanes in H,_1 has a non-empty intersection. Consider Ht=H,_l..U {HP(vt,vt+i)}. (4.5) By assumption, Kt(P)=Kt_i(P))n HP(vt,vt+l)=0 From Lemma 2.2(Helly's theorem), there exist two halfplanes, HP(vi,vi+l) and HP(v, vj+1) in H,_ such that HP(vi,vi+l)qn HP(vi,vji+)nh HP(v,,vt+1)=0. (4.6) There are two possibilities: Case, I: HP (vm,v,m+)( HP(vt,vt+1)= 0 for some 0< m< t Case II: HP(v,,vm+l)(" HP(v,,vt+l)~ 0 for any 0< m< t In case I, take any halfplane HP(vj,vYj+) in Ht.1, which is not HP(vmv+in). Since HP(vm,vm+i) n HP(vt,vt+l) = 0, HP(v,,v,,+l)f HP(vi,vY+l) HP(vt,vt+l) = 0. By

- 20 setting i=m, HP (vi,vi+ l) n HP (vj, vj+ l) ) HP ( vt, v+ 1)= 0. Now, consider Case II. In this case, K,-_(P)=0, KA(P) = 0, and there does not exist any halfplane HP(vm,vm+i) in Ht,1 such that HP(vm,v+ l)n HP(v,,vt+,) = 0. Therefore, the halfplanes in H, are pairwise intersecting. In particular, HP(vr,vr+), r=i,j,t are pairwise intersecting (notice that indices i,j, and t are the same as used in Equation (4.6) ). Recalling that Lr is the line containing E(vr,vr+),L,,r=i,j,t are pairwise intersecting, and lines Lr,r=i,j,t do not have a common intersection. Thus, three intersection points iij,ij, and ii, of these lines are distinct and well-defined. Futhermore, they are not colinear. Obviously, iijtHP(vtvt+l), ijttHP(vi,vi+l), and ii,0HP(vj,vj+l). Otherwise, HP(vr,vr+),r=i,j,t would have a non-empty intersection. Since ii, is the intersection point of Lt and Li, iiteLt. Similarly, ijteL,. By definition, E(vt,vt+l)cL,. Therefore, ii,ij,, and E(v,,v,+i) are contained in the same line L,. Let Dt be a unit vector such that = vt+ t (4.7) Since iiteL,,iit partitions L, into two halflines, i.e., {x I x=i+e.D,,~> 0} and (4.8) {x I x=ii-e.Dt,e, 0} L, and Li share only one point ii,. Therefore, one of two halflines in Equations (4.8) are completely contained in HP(v,,vi+) and the other shares only one point ii, with HP(vi,vi+,). Assuming that ipt is well-defined, ip, is said to be marked white if ip+ ep.Dt is in HP(vp,vp+l) for all ep 0. Otherwise, ipt is said to be marked black. Let three index sets U,S, and Q be defined as follows: U= {u IHP(u,v,+l)eH,_,} S= {s HP(v.,vs+l)eH _ and igt is well-defined}

- 21 - Q= {q IHP(vq,vq+l)eH,_1 and ig is not well-defined}. Clearly, U= {0,1,2,...,t-1} = Sj Q and Sn Q = 0. Since every point i, for seS is marked white or black, S can be partitioned into two subsets, W and B as follows: w= {w IweS and i, is marked white } B= {b beS and ib, is marked black } S=Wu B and W nB=0. Consider two points, i, and ij,. Since i, and iti are well-defined, both i and j are in S. Suppose that both i and i are in the same subset, say w. Then fiie+ ~ij Dt,,ei> Oc: HP (vi, vi+l) (4.9) {ij,+ ej Z Dt,,ej2 O0c HP (vj,vj+ 1). Therefore, either iiteHP(vj,vj+l) or ijteHP(vi,vi+), whichever implies that HP(vi,vi+,) " HP(vj,vj+l) n HP(vv,vt+l) ~ 0. This contradicts Equation (4.6). Hence, i and j cannot be contained in the same subset, w or B. Take any point t. in L,. Then, every point in L, can be expressed as t+~E.Dt for some eeR'. Let iad=t*+ed.Dt and ift=t+*+efD, for some Ed and Ef in R 1. idt is said to be to the right of if if Ed> Ef. If Ed< Ef, then id is said to be the left of ift. Otherwise, id, is said to be on ift. This makes sense if the direction given by Dt is pointing to the right along L,. Let eg= max w I (4.10) WeW E,= maXI Eb beB Then, igt is a rightmost point among all i,, for we W, and ik, is a leftmost point among all ib, for weB. (The article "a" is used rather than "the" since ig as well as iht may be on another point in the same subset ). The following lemma shows that HP(vg,vg+1)("n HP(vh,h+l)(' HP(v,,v,+ )=0. Lemma 4.1: In Case II, HP(vg,vg+l) "n HP(v,,vh+) n HP(v,,v,+l)=0.

- 22 [Proof] Since the halfplanes in Ht are pairwise intersecting, HP(vg,vg+ l) HP(vh,vh+l): 0. (4.11) By definition of igt, ig, is on or to the right if i, for all we W. Since i, for weW is marked white, igE HP (vw,vw+l) for all WW. (4.12) Similarly, iht HP(vb,vb+l) for all beW. (4.13) Suppose that ig, is not to the right of iht. Then, ig, is also contained in HP(Vb,Vb+1) for all bEB, i.e., igE n HP(vs,vs+l). (4.14) seS If Q = 0, then U = S U Q =S. Therefore, igtE n HP(vs,vs+ )=" HP(v,vu+l ). seS SuEU This implies that K,(P)~ 0, which is a contradiction. Thus, Q cannot be empty. Let Io=. HP(v,,vs+1) (4.15) seS Il= HP(vq,Vq+l) qEQ Clearly, K,_i(P)=Ion I1* 0. (4.16) From Equations (4.14) and (4.15), ig Io. (4.17) Since ig Lc HP (vt,v,+l) igtI oon HP (v,,v,+l). (4.18) Now, consider I,. Since iq, is not well-defined for all qeQ, Lq and Lt are either

- 23 parallel or colinear. Suppose that I n HP (v,,v,+ 1)= 0. Since Lq and L, are either parallel or colinear for all qeQ, HP(Vq,vq+)fl HP (vt,vt+l)=0 for some qe Q. This contradicts that HP(vm,vm+i)HP(vt,vt+i) ~ 0 for all 0< m< t. Thus, IlnP HP(v,,vt+l)* 0, (4.19) which implies that either I1 QHP(v,,vt,+) or Lt I. (4.20) Suppose that IQHP(v,,vt+l). Since K,_I(P) = Ion( I1, Kt_ i(P )Q I 1 HP (v,,v,+ 1). Therefore, K,(P)=K,_.(P)n HP(v,,v,+i)~ 0, which is a contradiction. Now, suppose that LcI1. Since igeLt, ittEI1. (4.21) From Equations (4.18) and (4.21), it,,Ion I n HP(vt,,v,+ )=Kt(P). This means that K,(P)* 0, which is also a contradiction. Hence, ig, is to the right of i,,. By definition, ig, and iA are marked white and black, respectively. This together with the fact that i,, is to the right of i,, guarantee that HP (v,vg+ l)(n HP (v,v^+ 1) n L) = 0. (4.22) Therefore, either [HP(vg,vs+l) n HP(vA,vh+l)] cHP(vt,vt+l), or [HP(vg,vg+l) HP(vh,vh+l)] n HP(v,,vt+l) = 0. Clearly,

- 24 - K,-_(P)c [HP (Vg,vg+,)) HP (vh,vhA+)]. If [HP(vg,vg+i)n HP(vh,v^+l)]cHP(v,,vt+l), then K,_-(P) c HP(vt,vt+l), which would mean that K,(P)~ 0. Hence, HP(vg,v+i)n HP(vh,vh+l)n HP(vt,vt+l)=0. O Given t with K,_1(P)~ 0 and K,(P)= 0, Lemma 4.2 suggests an algorithm for finding two edges, E(v,,vi+l) and E(vi,va+1) such that HP(vi,vi+) n HP(vj,vj+1) n HP (v vt+)= 0. Algorithm 4.1: (Finding E(vi,vi+1) and E(vj,vj+,)) Procedure FIND-J(t,ij) begin Step 0 GO v- true i <-0 while (GO and i< t) do begin if HP (vi,vl+ l)n HP(vt,vt+l)=0 then GO <- false else i <- i+ 1 end Step 1 if GO = false then begin j <- any positive integer x such that 0< x< t and x i. end Step 2 else begin m <- 0, W <- 0, B <- 0 Step 2a while ( m < t) do begin if the line Lm containing E(v,,v,+l) is neither parallel nor colinear with Lt containing E(v,,v,+l) then begin compute and mark i,, if imt is white then W - W U {m} else B - B {m} end m +- m+ 1 end Step 2b ig<- the rightmost point among all i, for w E W. iht<- the leftmost point among all ibt for b e B. i —g, i-h end end

- 25 - Lemma 4.3: Given t with K,_-(P)~ 0 and K,(P)=0, Algorithm 4.1 can find, in O(n) time, two edges, E(vi,vi+l) and E(vj,vji+) such that HP(v+,v5i+) n HP(vj,vj+l) ( HP(v,,v,+l) = 0. [Proofl In Step 0, the algorithm checks if there exists any halfplane HP(vi,vi+i) such that HP(vi,vi+)P) HP(vt,vt+i)=0. If there exists such a halfplane HP(vi,vji+), the algorithm sets the logical variable GO false. Otherwise, it sets GO true. Obviously, if GO = false, then Case I must occur. Therefore, an edge E(vj,vjy+)O< jj i< t is chosen by Step 1. Since HP(vi,vi+l)n HP(v,,vt+) = 0, HP(vj,vi+)n HP(vj,vj+l) n HP(v,,v,+1)=0 for any j such that 0< j~ i< t. If GO = true, Case II must occur. Therefore, Step 2 chooses E(vi,vi+,) and E(vj,vj+) such that HP(vi,vi+l)' HP(vj,vji+) n HP(v,,v,+l)=0, which is guaranteed by Lemma 4.2. Hence, the correstness of the algorithm is immediate. The algorithm traverses CA(vO,v,) at most twice; once in Step 0 and once in Step 2a. Therefore, each edge in C,(vo,v,) is visited at most twice. At each edge, a constant number of operations is needed. Thus, Step 0 and Step 2a can be done in 0(t) time. Clearly, Step 1 and Step 2b can be done in 0(1) and 0(t), respectively. Since t< n, the time complexity of Algorithm 4.1 is O(n). 0 If K(P)=0, Algorithm 4.1 together with the kernel finding algorithm[4] can choose, in 0(n) time, three edges, E(v,,v;+i), E(vj,vj+i) and E(vk,vk+l) such that HP(vi,vi+l)n HP(vj,vj+l)pnHP(vk,vk+l)=0. This is true since HP(vt,vt+1) can be equated to HP(vk,vk+l). From Theorem 3.1, there are at most three candidates in a simple polygon with an empty kernel. By Definition 3.1, each of them intersects V(mi,P), V(mj,P), and V(mk,P) such that HP(vi,vi+l)n HP(vi,vi+i)( HP(vk,vk+l)=0, where m,=i,j,k is a point in E(vr,vr+). A point is said to be marked red if z e V(mi,P). If z E V(mj,P) then z is said to be marked green. Z is said to be marked yellow if

- 26 z E V(mk,P). Since HP(vi,vi+l) " HP(vj,vj+l) n HP(vk,vk+l)=0, V(mi,P) r V(mk,P) i V(mk,P)=0. Therefore, if K(P)=0, a point z in P can not be marked with these three colors, simutaneously. An edge of P is said to be marked "C", if a point in the edge is marked "C", where "C" is red, green, or yellow. An edge is said to be full-colored if it is marked with three colors simultaneously. It is clear that a candidate must be full-colored. Therefore, finding all candidates is equivalent to finding all full-colored edges. Without loss of generality, let m, be the mid-point of E(v,,v,.l), i.e., mr= 2* (Vr+I+ v,),r=i,j,k. (4.23) Our strategy for determining all candidates is first marking the edges of P using the three colors assigned to V(m,,P),r=i,j,k and then choosing all fullcolored edges. Therefore, an efficient algorithm for constructing the visibility polygon V(m,,P) from m, is needed. V(m,,P),r=i,j,k can be constructed in 0(n) time[2,3,5]. Lemma 4.4: V(mr,P),r=i,j,k can be constructed in 0(n) time[2,3,5]. In order to efficiently mark the edges of P with three colors, the structure V(mr,P),r=i,j,k is exploited. Let B(V(m,,P)) = (L(s0,s1), L(s1,s2),', L(Sc-2,sc-l), L(s,_l,So)), where B(V(m,,P)) is the boundary of V(m,,P),r=i,j,k. (So,S1,...,Sc-) is the sequence of all corner points on B(V(m,,P)) such that Sa appears before Sb for all b> a as B(P) is scanned from s0 in the counterclockwise order. Therefore, (s0,,.,sC-) partitions B (P), i.e., c-1 B(P)=U C (Sa,Sa+i). (4.24) a=O As illustrated in Figure 4.1, either Ch(sa,sa+,)=L(Sa,Sa+ ) or Ch(SaSa+1) n L(SaSa+i)=0, where Ch(Sa,sa+i) is the chain Ch(sa,sa+i) excluding its two end

- 27 - points, Sa and Sa+1. If Ch(Sa,Sa+1)=L (sa,sa+i), then L (Sa,Sa+i) c E(vb,vb+1) for some 0<b<n. Otherwise, C^(sa,sa+l) n V(m,,P)=0 [2,3,5]. Since L(Sa,,sa+) C V(mr,P), an edge of P can be marked with the color assigned to V(m,,P) if and only if it contains Sa for some 0< a< c. Without loss of generality, let s0=+,,1. The following algorithm is for marking the edges of P with the color assigned to V(mP,P),r=i,j,k. < Insert Figure 4.1> Algorithm 4.2: (Coloring the edges of P ) procedure EDGE-CLR(r,C) begin StepO m, = 2 (vr+v,+l) compute V(mr,P) b <- r, q <- 0 Step 1 while (q< c) do begin Step la while (SqtE(Vb,vb+l)) do begin b - b+ 1 end Step lb mark E(vb,vb+ ) with C if Sq EE(vb+1,Vb+2), then mark E(vb+,vb+2) with C q - q+ 1 end end Lemma 4.5: Let Er={E(Vb,vb+) 10< b< n and E(vb,vb+l)' V(m,,P)~ 0 for some r=i,j,k }. Algorithm 4.2 marks, in O(n) time, all the edges in E, with the color assigned to V(m,,P). [Proof] Let B(V(m,,P))=(L (so,sl),L(sl,s2), *,L (S,-2,Sc-1),L (Sc-1,SO)). (So,S1,,SC1) is in the order appearing on B(P) as B(P) is scanned from so in the counter-clockwise sense. Therefore, (sosl, s,,s -) partitions B(P) into c chains, CC(so,sl), CA (S1,S2), *, C (sc- 2, sc- 1), and C (sc-,so). Algorithm 4.2 traverses B(P) from so(or equivalently vr+i) in the counter-clockwise order. Step 0 is mainly for computing V(mr,P). We inductively show that Step 1 correctly

Vr+ 3 p ~~~~~~~~~~~~~S 3=vr Sc- 1= Vr MrS 0 — Vr+1 rr ~~~~~~m Figure 4.1: A shape of V,(m,,P)

- 28 - marks the edges in Er with the given color. g=0: Initially, Step 0 sets q=0 and b=r since so=vr+. Therefore, both E(vr,Vr+i) and E(vr+l,Vr+2) are marked C by Step 1. Since so is chosen to be a vertex vr+l, there does not exist any other edge E(a,,va+i) such that so E (va,va+i). Thus, Step 1 works correctly when a=0. Assuming that Step 1 marks the edges correctly for sf,0< f< c, consider q=f+l. From the previous excution of Step 1, Sf EE(vb,b+l). There are two possibilities: (1) sf +lE(Vb,Vb+l). (2) Sf+1i(E(Vb,Vb+ ). If Sf+iEE(Vb,Vb+l), then Step la is skipped and Step lb marks E(vb,Yb+l) with the given color. Futhermore, E(Vb+1,vb+2) is also marked if Sf+lEE(vb+l,vb+2). If Sf+l i E(Vb,b+ 1), then Step la scans Ch(sf,Sf+l) from sf until an edge containing sf+l is encountered. After Step la, the new E(vb,vb+1) contains sf+ so that Step lb can be applied. In either case, Step 1 marks every edge E(va,va+l) such that S +l E E(va,va+i). This together with the induction hypothesis give the correctness of Step 1. Hence, the correctness of the algorithm follows. V(mr,P) can be computed in 0(n) time by Lemma 4.4. Therefore, Step 0 can be done in O(n) time. Step 1 also requires O(n) time since sq,< q< c is contained at most two edges. Hence, the time complexity of the algorithm is O(n). Now, we are ready to present a linear time algorithm for finding all candidates of a simple polygon P with an empty K(P). Algorithm 4.3: ( Finding all candidates in P with an Empty K(P) ) procedure FIND-CD (t, CAND) begin Step 0 call FIND-IJ(t,i,j),k<-t Step 1 call EDGE-CLR(i,"red") call EDGE-CLR(j,"green")

- 29 - call EDGE-CLR(k,"yellow") Step 2 f<-O, CAND<-0 while ( f< n ) do begin if E(vf,vf+ ) is full-closed, then CAND<-CAND u {E(vf,vf+l)} f<-f+ 1 end end Theorem 4.1: Suppose that the kernel K(P) of a simple polygon P is empty. Given t with K,_1(P)~ 0 and K,(P)=0, Algorithm 4.3 finds all candidates, if any, in O(n) time. [Proof] In Step 0, the algorithm chooses three edges, E(vi,vi+l), E(vj,vj+l), and E(vk,vk+1) such that HP(vi,vi+l) n HP(vj,vY+l) ) HP(vk,vk+l) = 0. This can be done in O(n) time by Lemma 4.3. Step 1 marks the edges of P with the three colors assigned to V(mr,P),r=i,j,k, which can also be done in O(n) time by Lemma 4.5. Now, Step 2 scans B(P) once and picks up all full-colored edges. Clearly, Step 2 takes O(n) time. Since an edge is a candidate if and only if it is full-colored, the result follows. O 5. Determining All Visible Edge A simple polygon P may or may not have a non-empty kernel K(P). If K(P) is not empty, we employ Shin and Woo's algorithm [8] to find all visible edges. Lemma 5.1: Suppose that a simple polygon P has a non-empty kernel K(P). Then, all visible edges of P can be determined in O(n) time [8]. Suppose that K(P)=0. From Theorem 3.1, there exist at most three candidates in P. By Theorem 4.1, all candidates, if any, can be determined in O(n) time. A visible edge is always a candidate. However, a candidate is not necessarily a visible edge. This is true since Definition 3.1 does not guarantee that

- 30 every point in P is visible from a candidate. In order to check if a candidate is indeed a visible edge, we use Avis and Toussaint's result[l]. Lemma 5.2: Given an edge E(va,Va+,) of a simple polygon P, it takes 0(n) time for determining whether or not E(va,va+) is a visible edge. Since there are at most three candidates if K(P)=0, given all candidates, all visible edges can be found in O(n) time using Lemma 5.2. Now, a linear time algorithm for finding all visible edges in a simple polygon P is in order. Algorithm 5.1: (Finding all Visible Edges in P) Procedure V-EDGE begin Step 0 find K(P) Step 1 if K (P) ~ 0, then determine all visible edges using Shin and Woo's algorithm[8] Step 2 else begin compute t such that Kt,_(P)* 0 and K,(P)=0 call FIND-CD(t, CAND) choose all visible edges in CAND using Avis and Toussaint's algorithm [1] end end Theorem 5.1: Algorithm 5.1 can determine all visible edges in a simple polygon in O(n) time. [Proof] Step 0 is for finding K(P) which can be done in 0(n) time [4]. Step 1 determies all visible edges if K(P)* 0. Otherwise, Step 2 finds all visible edges. Step 1 needs 0(n) time by Lemma 5.1. From Theorem 3.1, 4.1, and Lemma 5.2, Step 2 can also be done in O(n) time. Hence, the result follows: 0 6. Concluding Remark A trivial lower bound for determining all visible edges is n (n. Therefore, Algorithm 5.1 is optimal within a mutiplicative constant factor. As a direct

- 31 - consequent of Theorem 3.1, there are at most three visible edges in a simple polygon P if K(P)=0. Theorem 3.1 may be extended for a simple polygon with disjoint holes. Acknowledgement - The authors wish to thank Mr. N. H. Baek for his excellent typing of the manuscript and his constructive suggestions.

- 32 - references 1. Avis, D. and Toussaint, G., An optimal algorithm for determining the visibility of a polygon from an edge, IEEE Trans. Comput., C-35, 12, 905 - 914, (1981). 2. El Gindy, H. and Avis, D., A linear algorithm for computing the visibility polygon from a point, J. Algorithm, 2, 186 - 197, (1981). 3. Lee, D., Visibility of a simple polygon, CGVIP, 22, 207 - 221, (1983). 4. Lee, D. and Preparata, F., An optimal algorithm for finding the kernel of a polygon, J. ACM, 26, 3, 415 - 421, (1979). 5. Melkman, N., On computing the visibility polygon from a point, Tech. Report, CS - 85 - 265, Ben Gurion University, Israel, (1985). 6. Penny, D., Perspective in Mathematics, W. A. Benjamin Inc., Menlo Park, Califonia, (1972). 7. Shin, S., Visibility and its related problems, Ph.D. Thesis, Industrial and Operations Engineering, University of Michigan, (1986). 8. Shin, S. and Woo, T., An optimal algorithm for determining edge visibility in a point-visible polygon, IEEE J. Robotics and Automation, (to appear).