A Linear Time Algorithm for Constructing Visibility Diagram Shou-Yan Chou Tony C. Woo Department of Industrial & Operations Engineering University of Michigan Ann Arbor, MI 48109-2117 Technical Report 91-28 October 1991 To appear in ASME Transactions, J. of Mechanical Design

A Linear Time Algorithm for Constructing a Circular Visibility Diagram Shuo-Yan Chou Tony C. Woo Department of Industrial and Operations Engineering University of Michigan Ann Arbor, MI 48109-2117 Technical Report 91-28 October 1991

A Linear Time Algorithm for Constructing a Circular Visibility Diagram Shuo-Yan Chou Tony C. Woo Department of Industrial and Operations Engineering University of Michigan October 28, 1991 Abstract Unlike linear visibility for which there exists only one line segment connecting two points, there are an infinite number of circular arcs connecting two points. To compute circular visibility: a collection of circular arcs which emanate from a given point and reach an edge without intersecting another edge in a polygon, the arcs are classified with respect to the edges of the polygon resulting in a planar partition. It is shown in this paper that such a partition can be constructed in O(n) time, where n is the number of vertices in the polygon. Given such a diagram, the point visibility hull inside a simple polygon can be found easily.

1 Introduction Among the visibility problems, a fundamental one is the computation of a point visibility polygon: the portion of a polygon which is visible to a point internal to it. ElGindy and Avis [9] and Lee [12] developed linear time algorithms for constructing a point visibility polygon inside a simple polygon. Another fundamental visibility problem is the computation of an edge-visibility polygon. Introduced by Avis and Toussaint [2], edge visibility is divided into three categories: complete, strong, and weak. Whether a polygon is completely or strongly visible to a given edge can be answered by the kernel algorithm developed by Lee and Preparata [11], whereas the problem of detecting if a polygon is weakly visible from an edge can be solved in linear time [2]. Chazelle et. al [4,5] show that an edge-visibility polygon inside a triangulated simple polygon can be constructed in linear time. Suri and O'Rourke [17] show that an edge visibility polygon inside a non-simple polygon can be constructed in Q(n4) time. These linear visibility algorithms support many applications. The art gallery problem [14] seeks the minimum number of points inside a polygon such that the point-visibility polygons of these points cover the entire polygon. The minimum link path between two points inside a-simple polygon is solved optimally by constructing a sequence of visibility polygons [16]. The shortest path can also be solved in linear time by utilizing visibility [10]. Circular visibility is established by arcs. Since straight lines can be considered as degenerate arcs, the realm of visibility is extended by considering circularity, the notion of of which is illustrated in Figure 1, where a point q is circularly visible to a point p if a circular arc can be drawn from p to q without hitting an obstacle. Such a directed circular arc - clockwise or counterclockwise - is called a visibility arc and can be uniquely defined by its radius, center, endpoints, and direction. For 1

Figure 1: Circularly visible points the simplicity of discussion, we adopt the counterclockwise direction. An O(n log n) algorithm has been reported by Agarwal and Sharir [1] for computing the portion of a simple polygon which is circularly visible to a fixed interior point. Circular visibility can be used to characterize the motions of a mobile robot. The number of links in a minimum link path is smaller with circular arcs than with line segments as links. Circular visibility can also be used to characterize the workspace of a stationary robot with rotary joints - locating joints for assembly or disassembly. Clearly, there can be more than one circular arc between the point in question and points on an edge of a polygon. Since an arc can be represented by its center, the visibility arcs to a particular edge of the polygon can be represented by a region for their corresponding centers. We utilize this representation to solve the following problem. Problem CVD(p,Q): Circular Visibility Diagram of a Simple Polygon Q Given: a simple polygon Q with edges eo, el,..., en, and a point p contained in Q. Find: for each ei, the circular arcs which emanate from p and intersect ei before intersecting any other edge of Q. 2

Figure 2: Some counterclockwise visibility arcs of edge ei. Let F denote the set of centers corresponding to the counterclockwise visibility arcs from p to ej, as shown in Figure 2. (The notation FA is used, throughout this paper, to represent the set of centers of the visibility arcs from a given point to A in the presence of B.) Since visibility arcs are represented by their centers, a solution to Problem CVD(p,Q) indicates a partition of the plane. The partition is represented as {FQ, FQ, FQ,..., FQ}, where FQ represents the set of centers for counterclockwise arcs which emanate from p that do not hit the boundary of Q. Such a partition is called the circular visibility diagram (CVD) of Q with respect to p. The data structure of the CVD is similar to the dual space data structure used by Chazelle and Guibas [5] for solving a variety of linear visibility problems. In that paper, a transform is employed in which a line ax + by + 1 = 0 is represented by a point' (a,b) [4,13]. Points in the dual space are grouped into regions according to 3

Figure 3: The possible hitting order between two edges. the edge whose corresponding visibility rays hit, resulting in a planar partition in the dual space. In linear visibility, a partial order in which visibility rays hit the edges of a polygon is crucial for the construction. In circular visibility, however, arcs emanating from a point can hit two edges in either order, as shown in Figure 3. To overcome the apparent lack of a partial order, a polygon is decomposed into a star-shaped polygon and a set of pockets, each of which exhibit a partial order. By constructing the CVDs for the star-shaped polygon and then for every pocket, the CVD of a simple polygon is constructed. The sections follow the development of such an idea. The CVD of a single edge is first examined. Based on the CVD for an edge, algorithms for constructing the CVDs of two types of open polygonal curves - obtuse star-shaped chains and pockets - are developed. Finally, the circular visibility diagram of the simple polygon is constructed and linearity in time for the construction is shown. 2 Circular Visibility Diagram of An Edge In this section, the CVD for a single edge is constructed. The objective is to classify the visibility arcs into three groups - those which hit one side of an edge; those which hit the other side of the edge; and those which do not hit an edge at all - by their 4

U v (a) (b) Figure 4: A partition of counterclockwise visibility arcs with respect to edge uv. corresponding centers. The distinction among various visibility arcs is first examined. Let p be the point from which visibility arcs emanate. Let q be a point on a directed edge uv. A visibility arc can reach q from the left or from the right of uv. Such a distinction among visibility arcs can be made by classifying the loci of the centers to p and to uV, as the partition shown in Figure 4 (a). First, the bisector P,u of p and u and the bisector f, of p and v, are constructed respectively. Then, a parabola p- with focus p and directrix coincident with uv, is constructed. By construction, p- is tangent to O3u and 3v at u' and v', and both uu1 and vv' are perpendicular to uv [3]. Let 3 denote the portion of #- between u' and v'. Let #/ denote the half-line of #3u which has C1 continuity with /3 at u' and P/3 the half-line of /,, which has C1 continuity with 13, at v'l. While /,u, Pv, and p,- contain all the equidistant points between p and u, p and v, and p and u5, respectively, the continuous curve /3rv consisting of /3,, and /3, contains all the equidistant points between p and uv. This curve is also known [15] as the Voronoi diagram of p and uv. /,, /A, and /' partition the plane into five regions, RI, R2,..., and R5, as shown 'The other halves of flu and /,v are denoted as P3; and p;. 5

op *p V l -:::::::: 2:::::::::::: 5::...............:.:::\:..:::...: r x (a) (b) (c) Figure 5: The centers of visibility arcs which: (a) miss uv, (b) hit uv from the left, and (c) hit uv from the right. in Figure 4 (b). It is shown in the following theorem that, arcs drawn from p about points in a region will miss uv, or hit uv from the left, or hit uv from the right. These five regions are thus combined into three sets, as shown in Figure 5. We note that hitting the right side of uv is essentially the same as hitting the left side of vu. Theorem 2.1 Let Fr, FU, and Fvt represent, respectively, the regions containing all the points about which counterclockwise arcs drawn from p miss uv, hit uv from the left, and hit uT from the right. Then, (i) Fv = R1 U R2 (ii) F, = R4 U Rs (iii) Fv R3 Proof: As R1 lies on the side of the Voronoi diagram which contains p, the distances d(x, p) < d(x, uv), for all x E R1, which means that visibility arcs from p centered at a point in R1 will not intersect uv. Similarly, since R2 is the intersection of the half-planes (not containing p) of the bisectors fl and P,5 i.e. d(x, u) < d(x, p) and 6

d(x, v) < d(x,p), for all x E R2, visibility arcs centered at a point in R2 will not intersect uv either. Thus, (i) is true. To show (ii) and (iii), first consider the points in R4. As R4 lies on the side of the Voronoi diagram that does not contain p, d(x, uv) < d(x, p), for all x E R4; R4 also lies in the half-planes, containing p, of the bisectors,u and P,, in which d(x,p) < d(x,u) and d(x,p) < d(x,v), for all x E R4. In other words, any circle centered at a point in R4 will not contain the end points of uv; yet, the distance between the center and uv is shorter than the radius of the circle, which means that such circles will intersect uv at two points. Since R4 lies to the left of uv, all such arcs will intersect uv from the left. A similar reasoning shows that every arc drawn from point p about a point in R3 or R5 will intersect uv at one point. Suppose an arbitrary arc drawn from p intersects uv at q. The center of the arc pq, if in R5, always lies to the right of qp. This indicates that a counterclockwise pq drawn from p and centered at a point in R5 always hits uv from the left. On the other hand, if arc pq is drawn from p and centered at a point in R3, it always hits uv from the right. This completes the proof for (ii) and (iii). [I2 Suppose that the edges of a polygon are given in the counterclockwise order. Since p is inside the polygon, all the first crossings of the visibility arcs will be from the left of the edges. Thus only the intersections from the left of an edge are of interest. Figure 6 gives the four possible cases of the counterclockwise CVDs of an edge uv. Figure 6 (a) depicts a Type L CVD, where p is to the left of uv and a Type R CVD, where p is to the right of uv. In both cases, counterclockwise arcs drawn from p about a point in Fu hit the left side of uv. Figure 6 (b) shows the limiting cases Type T and Type A, in which p is collinear with uv and uv is directed either toward 7

Type L u \\ ov TypeR U ~ ~^iii ^~~~~~~~~~~~~~;~~ii p (a) Type T P Type A v U u * p (b) Figure 6: Counterclockwise CVDs for p and uv. 8

or away from p. We note that if u'v is directed away from p, no counterclockwise arc emanating from p will hit uv from the left side. 3 Circular Visibility Diagram of an Obtuse Starshaped Chain The classification of the visibility arcs which hit a special class of open polygonal chain on the left in next examined. As noted earlier, edges of a polygonal chain may obstruct visibility arcs. The resolution of the obstruction and subsequently the construction of the CVD can be costly. However, if a partial order in which an arc hits the edges of such a chain can be established, the CVD can be then constructed efficiently. An open polygonal chain is star-shaped if the polar angle 9, which is the angle rotated counterclockwise from the polar axis, of a point traversing the chain is either monotonically decreasing or increasing, with respect to some point p. A star-shaped chain is obtuse if the span of 0 of the points on the chain is less than 180~. Given an obtuse star-shaped chain with monotonically increasing 0 with respect to p (with all the edges directed counterclockwise), the visibility arcs to the individual edges of the chain can be identified. To determine efficiently the first edge that an arc hits, a partial order in which circular arcs emanating from p hit the edges of the chain is identified. That such a partial order exists is established by the following lemma. Lemma 3.1 Let C = eo, el,e2,...,em} be an obtuse star-shaped chain which is monotonically increasing in 9. A counterclockwise arc emanating from p hits ej before ej only if i < j. Similarly, if is monotonically decreasing, then an arc can hits ei before Aitting ej only if j < i. 9

Proof: For a chain that is monotonically increasing, a counterclockwise arc drawn from p which hits e, at a point q will always lie to the left of qp, whereas ej, for all j > i, always lies to the right of qp because the chain C is star-shaped about p and spans less than 1800. Since such an arc does not intersect any succeeding edges of e, in C, it hits another edge before hitting ei only if the edge precedes ei. O Since constructing the CVD for an obtuse star-shaped chain with decreasing 0 is closely analogous to that with increasing 0, we will illustrate the latter case. Based on Lemma 3.1, a recursive relationship between the CVD of an obtuse star-shaped chain and the CVDs of its constituent edges is established. Theorem 3.2 The regions in a counterclockwise CVD of the monotonically increasing chain C can be computed by: Fc_ Feo if i = e 1 F,nFCI- ifi>0, and Fc FI if i =o Fy - F' ne Fi'-' if i >0 where Ci = {eo, el,..., ei} denotes a sub-chain of C. Proof: Based on Lemma 3.1, circular arcs about points in Fe. may hit ej, only if j < i. Therefore, for points to be in FC, their corresponding circular arcs can not hit ej, for all j < i. As F' represents the intersection of Fe, for all j < i, F is equal to the intersection of Fe, and FC'-'. 10

Intersecting Fe,i and Fi'-1 for all i > 0, takes O(n2) time, which seems to indicate that an algorithm for constructing a CVD for an obtuse star-shaped chain exceeds linear time. However, by utilizing certain properties of the consecutive Fes, we can show that constructing a circular visibility diagram of an obtuse star-shaped chain is analogous to cutting a pie, piece by piece. Also, since the time complexity for the identification of the cutting points is amortized, such a pie cutting procedure can therefore be achieved in linear time. A similar linear time cutting procedure is described by Edelsbrunner and Guibas [7] for computing a "bay" formed by lines sorted in slope order. Before investigating the properties of the consecutive Fs, the portion of F', which has no effect on the construction of the CVD, is identified and is omitted from the subsequent analysis. Recall that F"', which equals the union of regions R1 and R2 as shown in Figure 5 (a), contains all the points about which arcs emanating from p miss ei. Let region R2 computed with respect to ei be denoted as R"'. As to be established in Lemma 3.3, the intersection of R"' and Fe,i+ is always empty. Also, since the star-shaped chain is obtuse, the region Fe,, for j > i, will not go around p and come back to intersect R"'. Therefore, each individual F~' denotes only points in R1, which is also the region of the Voronoi diagram of p and ei containing p. Lemma 3.3 Let C be an obtuse star-shaped chain, and ei and ei+1 be two consecutive edges in C. Then, Fei+ n R'=. Proof: Let,iv, represent the perpendicular bisectors of pv, as shown in Figure 7. Since C is star-shaped, p is to the left of ei and ei+l, which means that Fe, and Fe,+1 are both Type L regions. F,6, which is the perpendicular bisector of p and the vertex vi joining edges ei and ei+1, creates two half-planes, one of which contains p. By definition, Fei+. is on the side of half-plane containing p while R2 of ei is on the other 11

p 0 vi I ON,+ Figure 7: The superimposition of Fe,+i and R2,e,. half-plane. Therefore, Fe,+i n R2' =. Ei Also, properties on the unbounded regions in the CVD are needed before establishing the properties on the consecutive FCs. In a given CVD, it is possible to distinguish bounded regions from the unbounded ones. The existence of unbounded regions in a CVD is closely related to the linear visibility of the edges, as established in the following lemma. Lemma 3.4 For some edge ei of a polygon Q, the region FQ is unbounded if and only if some point on ei is linearly visible from p. Proof: A point q on ei is linearly visible from p if and only if the line segment pq does not intersect any other edges of Q. A line segment is in fact a degenerate circular arc whose center lies on the perpendicular bisector of this line segment at infinity. A region corresponding to a linearly visible edge contains points to infinity and therefore is unbounded. The validity of the converse is easy to see. 12

O It can also be shown that these unbounded regions of a CVD are ordered about p. Lemma 3.5 The counterclockwise order of the unbounded regions around p in the counterclockwise CVD is the same as that of the edges linearly visible from p. Proof: The order of the linearly visible edges around p follows the order of the rays from p to the edges. Also, the order of the unbounded regions around p follows the order of the centers at infinity which in turn follows the order of the rays from p to the edge because the radii of the centers at infinity are perpendicular to the right of the rays from p. L1 With the order on the unbounded regions of the CVD in hand, a property between the consecutive FCs can now be extablished. Without loss of generality, all the CVDs of individual edges of a chain C are assumed to be of Type L. (Refer to Figure 6.) Being Type L, Fe, of edge e, in C is bounded by three curves: P/3v_, 'ei which is the portion of P/e, between v1 and v, and +, as shown in Figure 8 (a). To simplify the following discussion, 'i. and &+ are denoted by a single curve fe,, as indicated in Figure 8 (a). The portion of fe, remaining in the CVD of an obtuse star-shaped chain C is denoted as f', as shown in Figure 8 (b). Since C is star-shaped about p, i.e. every vertex on ej is linearly visible to p, FC is unbounded and the order of FC about p is the same as that of e,. Such an order of Fe indicates an order for constructing the CVD of C. In the following, F+ is shown to be bounded by fe,+i and the boundaries of Fr'. 13

\ -i '"'I '"' \ FCi+1 -_ 1+1"""''"' \ l..,,.,,,,,.,,,,. \ "!:::F iil'""""""""::., *- eF /~,,,......... pvi (a) (b) Figure 8: (a) Overlapping the CVDs of two edges. (b) The circular visibility diagram of two consecutive edges. Lemma 3.6 Let C be an obtuse star-shaped chain, and let e1 and ei+1 be two consecutive edges in C. Then, Fc1 is bounded by fe,+, and the boundaries of F '. Proof: As shown in Theorem 3.2, FC is equal to the intersection of Fe,,i and F,'. As Fe,+ is a Type L region, by definition, it is bounded by fe,+i and /3.i See Figure 8 (a). Also, F, is bounded by f,i, as F' is bounded by /,;, and F'i is a subset of F~'. Moreover, since both Fei+, and F,' lie in the half-plane of /,i which contains p, Fe+l is therefore bounded by fe,+ and the boundary of F i'. It is also essential for the algorithm that fe,+i intersects the boundaries of FR at only one point, which is equivalent to showing that fec is continuous. Lemma 3.7 fC is continuous, for all i. 14

Proof: Given two consecutive edges, we show that fi+1 will intersect f,i only once. This is because that the tangents of the points on fe are non-decreasing as f, goes to infinity and are bounded by the two perpendicular bisectors between p and the two end points of ei. Thus, the tangents of the points on fe,+i are greater than those on fei. Also, since C is obtuse, /,i+ can not go around p and hit fei. Therefore, fe,+i will only intersect fe, once. By using the same argument, we can show that fe,+i can intersect the boundaries of Fo ' only once, which means that the portion of fe,+i becoming fec is continuous. D Lemma 3.6 indicates that FC can be constructed by intersecting fe+i with the boundaries of FC, and Lemma 3.7 that they intersect at only one point. Subsequently, in each iteration of the algorithm, f,.+ partitions Fo' into two regions: FeC and FC'+1, as depicted in Figure 8 (b). In the algorithm for constructing a CVD, Fe and FC~ are constructed first. This can be done in constant time. Then, in each iteration, fe, is employed to intersect the boundaries of FC~-' which subsequently results in FC' and FC. After fC is computed, it replaces those boundaries2 of F *-' which lie in FC and becomes a boundary of Fr'. A stack is used to record fC that comprise the boundaries of Fi'; every time an fe, is introduced to partition F;1-', those feC that do not intersect fe, are popped out until one does. Then fJ is computed and pushed to the top of the stack. Those fC that were popped, along with fC comprise the boundaries of Fe. At the end of the algorithm, the fes remaining in the stack are identified as the boundaries of F. 2It is noted that the particular fC bounding F'-1 that fe, intersects may still contribute to the boundaries of FC. 15

The time complexity of this algorithm is of the same order as the number of fC popped out of the stack, which is of the same order as the number of edges in the chain. Therefore, this algorithm takes O(n) time, where n is the total number of vertices in C. The counterclockwise CVD of an obtuse star-shaped chain is depicted in Figure 9. 4 Circular Visibility Diagram of a Pocket In this section, the CVDs of another class of open polygonal chain is discussed. This open polygonal chain is called a pocket. It has its two end points collinear with p, and p does not lie on the lid, the line segment connecting the two end points. As adopted earlier, the edges of a pocket are oriented counterclockwise; only visibility arcs hitting the left side (the inside) of the pocket are of interest. In the example depicted in Figure 10 (a), only counterclockwise arcs emanating from p can hit the inside of the pocket without first hitting the pocket from the outside. Such pockets are called counterclockwise pockets. Pockets on the opposite side of a lid, on the other hand, can only have clockwise visibility arcs hitting the inside of them and are thus called clockwise pockets, as illustrated by the shaded area in Figure 10 (b). The collinearity of p with the lid exhibits an essential property, which will be explained shortly and employed in the construction of the CVD for a pocket. Lemma 4.1 Let utv be a line segment collinear with point p, where u E pv. Then every arc emanating from p will intersect uv at most once. Proof: Suppose an arc emanating from p passes through uv at q. Since there can be at most two intersections between an arc and a line segment, and since the arc has 16

FC 0 p C Figure 9: The CVD of an obtuse star-shaped chain. 17

p p (a) (b) Figure 10: (a) A counterclockwise pocket. (b) The trapezoidization of a pocket. already passed through pv at q and p, it can not have another intersection with pv. As p ~ uvy, uv contains exactly one intersection with the arc, namely q. To efficiently construct the CVD for a pocket, a partial order in which arcs emanating from p hit the edges of the pocket is required. However, the edges of a pocket do not inherently possess such an order. In the following, the edges of a pocket are decomposed into edges exhibiting partial ordering: a CVD is first computed with respect to the decomposed edges; and regions in such a CVD are then merged into the CVD of the pocket with respect to the original (undecomposed) edges. The decomposition of the edges of the pocket is done by utilizing vertex-edge visible pairs joined by dotted line segments, as shown in the pocket of Figure 10 (b). A vertex-edge visible pair is a vertex and an edge which can be connected by a line segment lying entirely inside the pocket. By employing line segments whose extensions pass through p to connect all the vertex-edge pairs of the pocket, the 18

interior of the pocket is decomposed into trapezoids3, as shown in Figure 10 (b). Such a decomposition is also known as a trapezoidization[6,15,18]. Tarjan and van Wyk [18] show that a trapezoidization of a simple polygon can be done in O(n loglogn) time, where n is the total number of vertices in the simple polygon. As a recent development, the time complexity of the trapezoidization algorithm is advanced by Chazelle [6] to O(n). Each trapezoid in the pocket consists of four sides. The in-edge and the out-edge are connecting line segments of the vertex-edge visible pair, where the in-edge is the side with the smaller 0. Both of the in-edge and the out-edge are considered to be transparent. The top-edge and the bottom-edge are portions of the edges of the pocket, where the top-edge is closer to p than the bottom-edge is. Both of the top-edge and the bottom-edge are considered to be opaque. The circular arcs are now classified with respect to the side of a trapezoid they hit. Let ej, eo, eT, and eB denote the in-edge, out-edge, top-edge, and bottom-edge, respectively, of a trapezoid Ti. Let FT' denote the region containing all the centers eI about which arcs emanating from p hit ej from the outside (right side)4. Since eT and eB are opaque and since only counterclockwise visibility arcs are employed, any arc which hits eT, eB, or eo from the inside must first pass through ej. After crossing el, an arc will then first hit eT, eB, or eo. Those arcs that hit eT or eB are blocked. Those arcs that hit eo, on the other hand, may pass through eo (as eo is transparent), come back through it, and hit either eT or eB. However, since p is collinear with eo, by Lemma 4.1, those arcs that pass through eo can not come back into Ti through 3lines originating from the same point can be viewed as in parallel. 4As adopted earlier, ej is a directed edge such that the inside of the trapezoid is to the left of it. e7 is e, directed in the opposite direction. In other word, visibility arcs about points in FT' will ehit om the let, which is consistent with the notation o F hit ej from the left, which is consistent with the notation of FAB. 19

Figure 11: FT' is divided into FT, FT;, and FT. ~I~I eO. Therefore, F^T can be partitioned into three mutually exclusive regions, FT, FeT' and F^', corresponding to arcs that pass through e1 and hit eT, eB, and eo, respectively. Such a partition is illustrated in Figure 11. A partial order in which arcs about points in FT' intersect eT, eo, and eB is e' utilized to compute Fe, Fi, and Fi. Theorem 4.2 Let FT, FB and Fo be the regions containing all the points about which circular arcs hit eT, eB and eo, respectively. Then, Fi = FI,n FB I F Ts F FT n (F F l eo e-~ e FBeo e/) Proof: Since eT is facing away from the emanating point p, arcs which hit eT immediately after crossing el will not intersect eo or eB afterwards. Also, by Lemma 4.1, an arc which hits eo immediately after crossing el will not intersect eB or eT afterwards. However, since eB is facing toward p, an arc which hits eB immediately 20

after crossing ej may intersect eo or eT afterwards. These three relations indicate that only eB may obstruct arcs in hitting eo or eT. Since eo and eT do not obstruct circular arcs passing through ej in hitting eB, FT; = F T n Fa. On the other hand, since eB may obstruct arcs in hitting eT or eo, FT = (FT n FT) - Ff and FT, = (F n Fo) - Fe. By substituting FTi with (F' i nFeB), FT = (FT nFCT)-(Fe nFeB) I I FTi n(FT -Fe,). e7 Similarly, FT, = FT- n (Feo - F), which completes the proof. eI eB D With the visibility arcs classified according to the side of a trapezoid they hit, the transition of the visibility arcs from one trapezoid to the next is now examined. Since no counterclockwise visibility arc can reach the inside of a clockwise pocket, the trapezoids in CW pockets as depicted in Figure 10 (b) are discarded from further consideration. Also, since counterclockwise visibility arcs can not reach portions of the pocket on the other side of the line coincident with the lid, such portions are discarded as well. Consequently, the in-edgs of the trapezoids to be considered span less than 180~. Without the CW pockets and portions of the pocket requiring visibility arcs to travel more than 360~ to reach them, it can be safely assumed that the trapezoid containing the lid of a pocket has the smallest 0 with respect to p. The Os of in-edges exhibit a partial order in which the visibility arcs pass through these trapezoids. The same order also gives rise to the order in which arcs hit the top-edges and the bottom-edges of the trapezoids in a pocket. Such a partial order can be uniquely represented by the dual graph of the trapezoidized pocket, in which each 21

node is associated with a trapezoid and each link with any two trapezoids sharing a side. This dual graph is clearly a partial-order tree with the root node representing the trapezoid containing the lid of the pocket5, as shown in Figure 10 (b). The construction of the CVD of a pocket starts from TR, the trapezoid at the root of the partial-order tree. FTR is subsequently partitioned into three regions: el FTT FT^, and TTo by utilizing Theorem 4.2. FTR then becomes FT- of T1, the immediate descendant trapezoid of TR. The CVD of a pocket is constructed by orderly partitioning FT' (or FTi-1) into FTT FTi and FTi throughout the partialorder tree. It is noted that arcs which hit eT and eB of Th hit the same two edges in the pocket P where Ti resides, which means FP - FeT and FP - FJT. Such a partition seems to require O(nlogn) time to complete[8], where n is the number of vertices of the pocket. However, by showing that FT is convex and utilizing the counterclockwise order of the in-edges about p, the partition can be completed in linear time. Before verifying the two properties indicated above, the detailed construction of FT is first examined. Let the trapezoid of interest, Ti, be depicted as in Figure 12 (a). By Theorem 4.2, FeT equals the intersection of FT- and (Feo - F,). Since Fo is a type T region bounded by /3, and P,+, and FeB is a type L region bounded by feB and /3p, subtracting FeB from Feo always results in two separate regions, denoted as A+ and AT as shown in Figure 12 (a). It is noted that At C ReB, i.e., all the arcs centered at points in Af will hit eB from the outside. Since an arc can not hit both el and eB from the outside, the intersection of Af and FT' is therefore always empty. On the other hand, At may contribute to FTi since (R1f n RIT) C At, where 51t is noted that there are trapezoids with three opaque sides and only one transparent side. However, since such trapezoids only appear at the leaves of the partial order tree, they will not affect the algorithm, and therefore will not be discussed. 22

P /I /I \ j+l >I, eB e,l T1, e0 RB oRT I I V1 eB V... (a) (b) Figure 12: (a) (Feo - FeB) is divided into At+ and AT. (b) (Rid f R T) (RoB n R2T), as illustrated in Figure 12 (b), contains all the centers about which arcs emanating from p do not hit either eT or eB from the inside. Therefore, the intersection of F73 and (Feo - Fee) can be subsituted with the intersection of F23 and At. That FeT is convex can be shown by examining the intersection of F2 and At.i Theorem 4.3 FeT, for all T, X P, is convex. Proof: The initial F~ is a stripe bounded by two parallel lines and is therefore convex. Subsequent Fe2a, which is equal to the intersection of A and F(b) (R is convex eo/ since both A fo and F o are convex. Therefore, by induction, all the Fe s are convex. The. That FT is convex cmputingan be shown by exaining the intersection of FT' and IO~ eo A~t_ Theorem 4.3 FT/, for all Ti E P, is convex. Proby th Te inico tialg of intersectio pointsd bewteen the boundary of F and the boundary of. It is shown the wic is equallowi t h the intersection of F ad is convex eI The computing of the intersection of FT' and At, for all Ti E P, is dominated eI boundary of At. It is shown in the following that, by dividing the boundary of FT eI 23

into two pieces and maintaining them with two stacks, completing all the intersections can be achieved in linear time. Since FT results from the intersection of F'-' and A+, the boundary of FTi consists of portions of the /o,.s and the fes contributing to the boundary of FT, where vj is a vertex of the top-edge of a trapezoid and ei is the bottom-edge of a trapezoid. Since the in-edges of the pockets are ordered about p, the perpendicular bisectors of line segments between p and the vertices of the top-edges and the bottom-edges are also ordered, respectively, by their normals (pointing toward p); consequently, the /,s and the fes6 of the A+s are in slope order, respectively, following the partial ordering of the pockets. The construction of the CVD for a pocket by intersecting FT' with A+ is thus analoguous to constructing an upper bay and a lower bay, as Ie described in Section 3, simultaneously. The upper bay, maintained by a stack Su, consists of only the /v,s whereas the lower bay, maintained by stack SL, consists of only the fes. Let p and v denote the intersections between the upper bay and the lower bay, as shown in Figure 13 (a). As the construction of the CVD proceeds, the intersection of FT' and At with boundary /,, and fe, is computed, as shown in Figure 13 (b). The intersection points between /,, and the boundary of FT' are sought by checking through Su and SL, I~ respectively, starting from the end of the stacks containing p. The f/j s in Su which do not intersect /,, are popped out sequentially until one does. Similarly, SL is updated by popping out fes which do not intersect /,, until one does. The portion of p,, lying inside FT' contributes a boundary curve to FT'+', and is pushed into Su. The region encompassed by this portions of /,, and the boundary curves of FT' between p and the two intersections with #, yields Fi. (The boundary curves of FT between eI 6By construction, the slope on fa, changes monotonically and is bounded by the slopes of Pu and,. 24

g____ g SL (a) (b) Figure 13: The partition of FI. IL and the two intersections with,3,, are the fjs and fis being popped out of Su and SL when computing the intersections with #,,.) Likewise, the intersection points between feB and the boundary of FT can be identified by checking through Su and eI SL from v, the other end of the stacks. The portion of fe, lying inside FT' contributes a boundary curve to FT'+1, and is pushed into SL. The region encompassed by this eC portions of fe, and the boundary curves of FT- between v and the two intersections eI with feB yields FT,. (The boundary curves of FT between v and the two intersections with feB are the,/vs and feis being popped out of Su and SL when computing the intersections with feB.) The curves remain in Su and SL yeild FT. If neither,3, or feB intersects FT+', Su and SL remain the same. The partition continues until all eI of the trapezoids are examined or when FT' n A+ is empty, which means that all the visibility arcs are blocked. 25

The time required for finishing all the partitioning is shown to be linear to the number of vertices in the pocket. Let nu and nL be the number of /3,s and feis in Su and SL, respectively, and let C(nu, nL) denote the total time required for partitioning the FTiwith Su and SL of size nu and nL, respectively. Suppose iu, iL, jU, and jL eI curved are checked, respectively, for identifying the intersections between 3,, and Su, /,, and SL, fee and Su, and feB and SL. Then, C(nU, fnL) = O(iU) + O(iL) + O(jU) + O(jL) + C(nU - iu - ju, nL - ZL - jL)By replacing C(nu, nL) with C(nu + nL), C(nu + nL) = O(iu + iL + jU + jL) + C(nu + nL - iu - jU - iL - jL)Let (nu + nL) equal n and (iU + jU + iL + jL) equal k. By substituting n and k into the formula, a recurrence formula C(n) = O(k) + C(n- k) is obtained. The solution to this recurrence formula is clearly O(n). In other words, the plane partition, which yields the CVD of a pocket, can be constructed in O(n) time, where n is the number of vertices in the trapezoidized pocket. It is clear that the number of vertices in the original pocket and the number of vertices in the trapezoidized pocket are of the same order. Therefore, given a pocket with n vertices, the CVD of the pocket with decomposed edges can be constructed in O(n) time. The CVD of the pocket with the original edges can be then obtained by merging the regions corresponding to the decomposed edges of original edges, which can be computed easily in O(n) time. Therefore, the total time complexity of the algorithm is still bounded by O(n). The CVD of the pocket P in Figure 10 is depicted in Figure 14. Figure 14 (a) 26

(a) (b) Figure 14: (a) CVD of a pocket with decomposed edges. (b) CVD of a pocket with the original edges. 27

shows the CVD of P with the decomposed edges, and Figure 14 (b) shows the CVD of P with the original edges. 5 Circular Visibility Diagram of a Star-shaped Polygon The notion of a star-shaped polygon is defined as a closed polygonal curve whose boundary is monotonic in 0 about p. The CVD for such a polygon can be constructed by using the algorithm for obtuse star-shaped chains discussed in Section 3. Given a polygon Q, star-shaped about p, it is observed that cutting Q by a horizontal line passing through p yields two obtuse star-shaped chains - the upper chain Cu and the lower chain CL - each of which spans 1800 about p. The CVDs for Cu and CL can be constructed individually, and then merged. Clearly, if an arc does not intersect either Cu or CL, it will not intersect Q. If an arc intersects only one of the chains, it intersects the corresponing edge in Q. If an ar intersects both chains, the center of such an arc appears in both of the CVDs of the two chains. Yet, the arc can only hit one edge in Q. This means that the overlapping of the two CVDs needs to be resolved so as to merge the two CVDs properly. To resolve the overlapping, the order in which the arc intersects the two chains needs to be determined. Let Lv be the perpendicular line passing through p. Let Fc, and FcL denote the regions containing the centers about which arcs emanate from p and hit Cu and CL, respectively. Let FQu and FcL be the regions containing the centers about which arcs emanate from p and intersect Cu and CL, respectively, in the presence of Q. The following lemma resolves the overlappings between the CVDs of the two chains. Lemma 5.1 Let q be a point in FCu n FCL. Then, if q lies to the left of Lv, q E FCu' 28

If q lies to the right of Lv, q E FcQ. Proof: Arcs centered at a point to the right of Lv always go downward first from p. Therefore, if such arcs intersect both Cu and CL, they must hit CL first. Likewise, arcs centered at a point to the left of Lv must hit Cu first if they intersect both Cu and CL. Lemma 5.1 indicates that, in the presence of Q, arcs emanating from p and centered at points to the right of Lv can hit Cu without being blocked by CL only if these points also lie in F L. Similarly, arcs emanating from p and centered at points to the left of Lv can hit CL without being blocked by Cu only if these points also lie in Fv. Let F, for all ej E CL, be constructed first. The feasible area where FCL can lie is the union of FcU and the half-plane to the right of Lv. FUu can be obtain by computing the CVD of Cv, as shown in Figure 15 (a). The result of the union of FU and the half-plane to the right of Lv is shown in Figure 15 (b). FQ can therefore be constructed along the boundary of F. u with the procedure used for obtuse starshaped chains. After completing constructing the FQ s, FCL is obtained. FQ for all ei E Cu, can then be constructed similarly along the boundary of F L. Figure 16 shows the final result of the CVD of the star-shaped polygon Q. It is noted that the construction of the CVD for Q is equivalent to constructing the CVDs for three obtuse star-shaped chains (one and a half rounds of the star-shaped polygon). Since the construction of FQ for all ei E Cu, and FQ for all ej E CL, takes O(n) time each, where n is the number of vertics of Q, the time required for constructing the CVD for a star-shaped polygon is bounded by O(n). 29

i s \CU Ii...... a.>>....E i~. t............ (a) (b) Figure 15: Construction of the CVD for the upper chain of a star-shaped polygon. 6 Circular Visibility Diagram of a Simple Polygon Now that the linear time algorithms that compute the CVDs for a star-shaped polygon and for a pocket have been established, the utilization of these algorithms for constructing the CVD of a simple polygon is to be shown. The outline of the CVD construction procedure is illustrated as follows. Algorithm CVD(p,Q) Decompose Q: Q = Q* + P1 +... + Pm Construct CVD(p,Q*) for i = 1 to m do Construct CVD(p,P.) Merge the CVDs end. ~~~~ ~:~:~' ''~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~:~:~:~: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~...... ~ ~ bjiiiiiiiiiiiiiiiii~ii~i~iiii~i~~i I ~ i..........................tilir::::~~~~~:~~-::~~~~.~~:~:~~~~:::;5:::~:~:;:~:~:~:~:~:~:~:~:~:~:~:~:~:~:::~:...........................:::::::::::::::::::::::.........................................~:~:~: ~ ~S ~~i ~:~:~:~:..~........................................::::::::~~~~:~~:~~;:~~;~':'`;?s~~~~-~2~~~f: ~:~:~:~:~:~: ~:~:~:~:~:~:~:~:~:........~.:.........:........................:tff~~~~~ff~~~~:::~~~~:::::::::: ~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~~ ~ ~ ~~~~~~~~~........:~;::fif:::::t::::::~:.::::::::::::::::....::::::.....................................~::~~::~ ~~::~~: ~ ~:: ~~:: ~~:: ~~:: ~~:: ~~::~ ~ ~~f ~ iiiiiiiiiiiii~iiiiiii~i~iiiii..................................: ~:~:~:~~:~:~~:~:~~:~ C~~t~t~~:~::~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:::::~~~~~~~~~~~::::::::::........................ ~ ~~~ ~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~....... ~~:::~~i~~i~i~~i~ ~ ~ iiiiiijijiiiijiiiiiijijiijiiiiiiiiiij~~~~~~~~~~~~~~~j:~:~:~:~:~:~:~:~:~:~:~:~:.............................:~-:~:~~:li~~~r~~)" ~..............................................::::::::::::::::::::::::::::::::::::::: X~:~: ~~:~:~:~:~:~:~~i~:~: ~ L::~:~:~:~:~:~:~......... ~ ~''~~~':ff:;f,~~~~~~~:~~:::~~~~:::~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~: ~:~:~:~:~:~:~:~~~~~~~~~~~~~~~~~~~~.............. ~ ~ ~~i~i~~:~jl~~f::...................................................................................:~::~::~::~::~::~::~:..................:~:: ~~~:: ~~::: ~~::: ~~:: ~~~:~::................................................................. ~ t t i:::::i i:::::::::::::i i~ ~i~:: ~~.............: ~ ~:: ~:~:: ~ ~..........~ ~:: ~ ~:: ~................. F ig u r e 1 5: C on................................................................. 6 C ircular V isibili............................ end. 30

Figure 16: The CVDs of the star-shaped polygon. 31

Figure 17: The decomposition of a simple polygon Q. It is observed that any simple polygon can be decomposed into a star-shaped polygon and a number of pockets, with respect to a point inside the polygon, as shown Figure 17. Let Q* be the star-shaped polygon obtained by computing the linear visibility polygon with respect to p. It can be constructed optimally by the algorithm developed by Lee [12] in 0(n) time, where n is the number of vertices of Q. Then, taking the boolean difference between Q* and Q results in (if exists) a set of pockets P1, P2,..., Pm. Since Q* C Q, the computing of the boolean difference between them can be achieved in O(n) time. That this algorithm constructs a correct CVD of a simple polygon is easy to see. By Lemma 4.1, arcs crossing the lid of a pocket can not come back into Q* (p is be definition in Q*) through the lid and hit other edges of Q*. Thus, the collection of visibility arcs that hit the edges of Q which are also the edges of Q* are the same as those computed with respect to Q*. On the other hand, visibility arcs that hit the 32

edge of Q* which is the lid of a pocket contribute to all the visibility arcs going into this pocket. The CVD for edges of Q which are in the pockets can thus be computed by further decomposing the region containing all the points about which arcs hit the lid, as described in Section 4. It is shown in the following that the construction of the CVDs of Q* and the pockets is bounded by O(n), where n is the total number of vertices in Q. Where the CVD of Q* can be constructed in O(n) time using the algorithm described in Section 5, the computing of the CVDs of the pockets in Q requires extra effort. It is because as some of the visibility arcs to the lids may be obstructed by other edges of Q*, the CVD region of the lid of a pocket will not be a simple Type T region. By construction, such a region is the intersection of a stripe, a region bounded by two parallel lines, and a FC', as described in Section 3. Since both the stripe and FC' are convex, the region containing all the points about which visibility arcs crossing the lid is convex. The algorithm for computing the CVDs for pockets is therefore applicable with starting regions being convex. The time required for constructing the CVD for a pocket becomes 0(mi + ni), where mi is the number of vertices in pocket Pi and ni is the number of edges of the starting region FQ, where ei is the lid of Pi. Note that the sum of ni is bounded by the total number of vertices in Q*. Therefore, the total time required for constructing the CVDs for all the pockets is still bounded by the total number of vertices in Q. The total time complexity for constructing the CVD of a simple polygon is the sum of the time complexity for the individual processes. Since the time complexity of all of the processes are bounded by O(n), this algorithm computes the CVD of a simple polygon in linear time. The CVD of the polygon in Figure 17 is shown in Figure 18. 33

Figure 18: The CVD of a simple polygon Q. 34

7 Conclusion This paper utilized the notion of circular visibility and developed an algorithm for the classification of circular visibility arcs. Such a classification is achieved by computing a plane partition of the centers about which arcs emanating from a fixed point hit a particular edge of a simple polygon. A linear time algorithm is developed to compute such a plane partition. Acknowledgment The authors would like to thank Jan Wolter who initiated the work. 35

References [1] Agarwal P.K. and M. Sharir, "Circular Visibility in a Simple Polygon from a Point", Technical Report No. 527, Department of Computer Science, New York University, August 1990. [2] Avis D. and G.T. Toussaint, "An Optimal Algorithm for Determining the Visibility of a Polygon from an Edge", IEEE Trans. Comput., C-30, 910-914, 1981. [3] Baker, W.M., Algebric Geometry: A New Treatise on Analytical Conic Sections, George Bell and Sons, London, 1906. [4] Chazelle, B.M., L.T. Guibas, and D.T. Lee, "The Power of Geometric Duality', BIT, 25(1), 76-90, 1985. [5] Chazelle, B.M. and L.T. Guibas, "Visibility and Intersection Problems in Plane Geometry", Discrete & Computational Geometry, 4, 551-581, 1989. [6] Chazelle, B.M., "Triangulating a Simple Polygon in Linear Time", Discrete & Computational Geometry, 6, 485-524, 1991. [7] Edelsbrunner, H. and L.J. Guibas, "Topologically Sweeping an Arrangement", Proc. 18th Ann. ACM Sympos. Theory Comput., 389-403, 1986. [8] Edelsbrunner, H., Algorithms in Combinatorial Geometry, Springer-Verlag, 1987. [9] ElGindy, H. and D. Avis, "A Linear Time Algorithm for Computing the Visibility Polygon from a Point", J. Algorithms, 2, 186-197, 1981. 36

UNIVERSITY OF MICHIGAN I I1 1 11 1 IIr I Ilrrr1111111111111111111 3 9015 04733 8556 [10] Guibas, L., J. Hershberger, D. Leven, M. Sharir, and R. Tarjan, "Linear-Time Visibility and Shortest Path Problems Inside Triangulated Simple Polygons", Algorithmica, 2, 209-233, 1987. [11] Lee, D.T. and F.P. Preparata, "An Optimal Algorithm for Finding the Kernel of a Polygon", J. ACM, 26, 415-421, 1979. [12] Lee, D.T., "Visibility of a Simple Polygon", Computer Vision, Graphics, and Image Processing, 22, 207-221, 1983. [13] Lee, D.T. and Y.T. Ching, "The Power of Geometric Duality Revisited", Information Processing Letters, 21, 117-122, 1985. [14] O'Rourke, J., Art Gallery Theorems and Algorithms, Oxford University Press, 1987. [15] Preparata, F. and M.I. Shamos, Computational Geometry: An Introduction, Springer-Verlag, 1985. [16] Suri, S., "A Linear Time Algorithm for Minimum Link Paths inside a Simple Polygon", Computer Vision, Graphics, and Image Processing, 35, 99-110, 1986. [17] Suri, S. and J. O'Rourke, "Worst-Case Optimal Algorithms for Constructing Visibility Polygons with Holes", Proc. 2nd ACM Symp. Comp. Geom., Yorktown Heights, 14-23, 1986. [18] Tarjan, R.E. and C. van Wyk, "An O(n log logn)-time Algorithm for Triangulating a Simple Polygon", SIAM J. Computing, 17(5), 143-178, October 1985. 37