CIRCULAR VISIBILITY OF A SIMPLE POLYGON SHOU-YAN CHOU Iowa Center for Emerging Manufacturing Technology Iowa State University Ames, IA 50010 LIN-LIN CHEN Dept of Industrial and Manufacturing Systems Eng Iowa State University Ames, IA 50010 TONY C. WOO Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109-2117 Technical Report 92-2 January 1992

CIRCULAR VISIBILITY OF A SIMPLE POLYGON SHUO-YAN CHOU Iowa Center for Emerging Manufacturing Technology, Iowa State University Ames, Iowa 50010, U. S. A. LIN-LIN CHEN Department of Industrial and Manufacturing Systems Engineering, Iowa State University Ames, Iowa 50010, U. S. A. and TONY C. WOO Department of Industrial and Operations Engineering, University of Michigan Ann Arbor, Michigan 48105, U. S. A. ABSTRACT The point visibility and the edge visibility of a simple polygon are computed. The portion of a simple polygon circularly visible from a given point is obtained in O(n) time, where n is the number of vertices. This requires the construction of a circular visibility diagram (CVD) - a classification of arcs emanating from a given point to the edges they hit. This is done in linear time. The portion of a simple polygon circularly visible from a given edge is obtained in O(kn) time, where k is the number of CVDs computed. In the worst case, k equals n. 1. Introduction As visibility can be characterized by lines of sight, a point is (linearly) visible from another point if there exists a line segment connecting them without crossing any obstacle. Using lines to represent the trajectories of visibility facilitates the computation of linear visibility, which subsequently enables the computation of notions such reachability, assemblability, and separability. One of the fundamental linear visibility problems is the computation of a point visibility polygon, the portion of a polygon that is visible from an internal point. ElGindy and Avis7 and Lee12 develop linear time algorithms for constructing a linear visibility polygon inside a simple polygon. O'Rourke14 shows that O(n log n) time is required to compute a visibility polygon for a non-simple polygon. Another fundamental linear visibility problem is the computation of an edge visibility polygon, the portion of a polygon that is visible from an edge, internally. Avis and Toussaint3 define three levels - complete, strong, and weak - of edge visibility. Lee and Preparatall give an algorithm that determines whether a simple polygon is completely or strongly visible from a given edge. Avis and Toussaint3 present a linear time algorithm for determining whether a polygon is weakly visible. Chazelle and Guibas5 show that an edge visibility polygon inside a triangulated simple polygon can be constructed in linear time. Suri and O'Rourke'7 develop an algorithm for constructing a weak edge visibility polygon inside a non-simple polygon in Q(n4) time. 1

Figure 1: The linear visibility polygon and the circular visibility region of s. These fundamental algorithms have many extensions. In the art gallery problem14, a minimum number of points inside a polygon is to be positioned such that the union of the point-visibility polygons equals the simple polygon. In the minimum link path problem, a path which connects two points inside a polygon and which consist a minimum number of line segments is sought; Suri16 gives a linear time algorithm which compute such a path by constructing a sequence of visibility polygons. Guibas et al.8 show that the shortest path inside a simple polygon can also be solved in linear time by utilizing the notion of visibility. Not all paths have to be linear. In engineering applications, devices such as machine tools and robots are equipped with circular interpolators, giving rise to the notion of circular visibility. A point q is said to be circularly visible from a distinct point p if a circular arc can be drawn from p to q without hitting an obstacle. The set of directed circular arc - clockwise or counterclockwise - drawn from p are called visibility arcs emanating from p and can be uniquely defined by their centers, endpoints, and directions. The difference between linear and circular visibility is illustrated in Figure 1. The shaded portions are not visible. Since arcs are involved in circular visibility, the term "region" is used (instead of "polygon"). And since straight lines can be considered as degenerate arcs, the linear visibility polygon is a subset of the circular visibility region. Research on circular visibility is relatively sparse. Agarwal and Sharir1 present an O(n log n) algorithm for computing the circular visibility region of a given point inside a simple polygon. Agarwal and Sharir2 also show that by preprocessing a simple polygon, with O(n log3 n) time, the query to the first intersection point between a circular arc emanating from a given point and the simple polygon can be answered in O(log4 n) time. A linear time algorithm is developed by Chou and Woo6 for classifying the visibility arcs emanating from a given point with respect to the edges of a simple polygon that they hit; such a classification is called the circular visibility diagram (or CVD) of a fixed point. In this paper, two types of circular visibility regions are computed by utilizing the CVD: that of a given point and that of a given edge. The rest of the paper is organized as follows. The structure of the CVD is first 2

. v... ^iii.iij. v.......^^^......ii^ 1iiiii~ u ~P (a) (b) (c) (d) Figure 2: Centers of the CCW visibility arcs that hit the left of utv. reviewed; the correspondence between a particular class of circular visibility arcs and their counterparts in the CVD is then established. In Section 3, a linear time algorithm for computing a circular visibility region of a point is described. Finally, in Section 4, an O(kn) time algorithm for computing a circular visibility region of an edge is developed, where n is the total number of vertices in the simple polygon and k is the number of different pairs of supports of the circular arcs that contribute to the boundary of the visibility region. 2. Preliminaries The representation for a collection of visibility arcs is first established. Whereas there is only one line segment connecting two given points, there are an infinite number of circular arcs connecting them. Additionally, due to the non-linearity, the collection of visibility arcs from a point to an edge can no longer be represented by a one-dimensional direction wedge7. The pattern of these visibility arcs is very difficult to visualize as they cross each other along their paths. It is noted that circles passing through a given point can be uniquely represented by their corresponding centers. Each point in the plane corresponds to the center of exactly two circular arcs - CW or CCW along the same circle - emanating from the given point. By considering CW and CCW arcs separately, there is a one-to-one correspondence between a point in the plane and either a CW or a CCW visibility arc. The visibility arcs from the given point to an edge can therefore be uniquely represented by the collection of the centers of the visibility arcs. Let the edges of a simple polygon be ordered in the CCW direction. Since p is inside the polygon, all the the visibility arcs that hit an edge uv of the polygon will hit the left side of the edge. Thus, only the intersections from the left of the edges are of interest. Figure 2 illustrates the four possible configurations of p and u-v. The loci of the centers of the CCW visibility arcs emanating from p and hitting the left side of uv are shaded. Figure 2 (a) depicts the case where p is to the left of uv, whereas Figure 2 (b) depicts the case where p is to the right of uv. Figure 2 (c) and (d) shows the limiting cases, where p is collinear with uv and uv is directed towards and away from p, respectively. It is noted that if uv is directed away from p, no CCW arc emanating from p will hit the left side of uv. The classification of visibility arcs with respect to the edges of the polygon that they hit can now be obtained. Such a classification results in two partitions of the 3

Figure 3: The CCW CVD of a simple polygon Q. plane, for the centers of CW and CCW arcs, and are called the CW CVD and the CCW CVD, respectively. An example of a CCW CVD is shown in Figure 3, where p is the emanating point, Q in dotted lines the simple polygon of interest, and the CCW CVD of p in solid lines. A CVD can have up to n + 1 regions. Points in the same region correspond to the centers of all the CCW visibility arcs which emanate from p and hit a particular edge of Q. (The region FQ contains all the points about which CCW visibility arcs emanating from p and missing all the edges of Q.) The boundaries of the regions of the CVD consist of: line segments or half-lines, each of which is a portion of the perpendicular bisector between p and a vertex of Q, and parabolic curves, each of which is a portion of the parabolaa defined by p and an edge of Q. The data structure of the CVD is similar to the dual space data structure used by Chazelle and Guibas5 for solving a variety of linear visibility problems, in which a line ax -- by + 1 = 0 in the primal space is represented by a point (a,b) in the dual space4'13. Points in the dual space are then grouped into regions according to the edges that their corresponding visibility rays hit in the primal, which results in a planar partition in the dual space. Prior to the development of the algorithms, some terminologies are introduced to aid the presentation of the ideas. Given an arc pq, as shown in Figure 4, let the region bounded by arc pq and line segment pq be called the segment of pq. The convex side of a circular arc can subsequently be defined as the side of the arc that aA parabola can be defined as the locus of all the equi-distant points between a point and a line. Every portion of the line corresponds to a portion of such a parabola. 4

convex side vj concave side Figure 4: Sides and supports with respect to an arc pq. is the inside of the segment, whereas the concave side of a circular arc is the side that is to the outside. Let a point in contact with an arc be called a support of the arc. A vertex of a polygon is therefore said to be a convez support of a circular arc, if it is in contact with the arc on the convex side. Likewise, a vertex or a non-vertex pointb on an edge of a polygon in contact with an arc on its concave side is called a concave support of this arc. In Figure 4, vertex vj is a convex support of pq, whereas vertex vi and point vk are concave supports of pq. The closure of the circular visibility region is first computed. This means that a visibility arc which passes through a vertex of the polygon and stays inside the polygon is not blocked by the vertex. Likewise, a visibility arc tangent to an edge of the polygon is not blocked by the edge. The circular visibility region computed accordingly is a closed region. By taking the open set of this closed region, the desired circular visibility region is obtained. Since the open set of a dangling curve in the plane is empty, the dangling arcs identified are ignored. 3. Circular Visibility Region of a Given Point In this section, an efficient algorithm that computes the solution to the following visibility problem is developed. Problem CVR(p,Q): Circular visibility region of a given point Given: a simple polygon Q = el, e2,..., en}, and a point p contained in Q. Find: the portion of Q that is circularly visible from p. To construct such a visibility region, the constituents of its boundary are first examined. By establishing the properties for the visibility arcs that contribute to the boundary of the visibility region, and subsequently establishing the correspondence between these visibility arcs and their counterparts in the CVD, the circular visibility region of a point can then be constructed. Since lines are degenerate circular arcs, and consequently the linear visibility polygon of p is a subset of the circular visibility region of p, only regions not in the linear visibility polygon of p need to be examined. These disjoint regions are called pockets, and can be obtained by taking the boolean difference between Q and the blt is noted that if an edge is in contact with an arc on its convex side, the contact must be with the endpoint(s) of the edge. 5

convex convex v./\ \ concave deficiency \ Vk deficiency Vi r Figure 5: Convex and concave caps of p. linear visibility polygon of p. Since visibility arcs which do not hit any edge of Q can only travel within the linear visibility polygon of p, visibility arcs entering a pocket always hit the boundary of the pocket. The identification of the boundary of the circular visibility region from p can therefore be reduced to the examination of the visibility arcs hitting the boundary of the pockets. The boundary of the circular visibility region in a pocket consists of portions of the boundary of Q and portions of visibility arcs. The latter can be classified into two groups. Let vj q be a portion of a visibility arc emanating from p such that there does not exist any visibility arc that can reach the region to the convex side of viq, as shown in Figure 5. Arc vjq is a portion of the boundary of the circular visibility region of p, and is called a convex cap of p; the region to the convex side of vjq is called a convex deficiency of p. Similarly, concave caps and concave deficiencies of p can be defined. Visibility arcs which are supersets of a cap are said to contain the cap. To construct the circular visibility regions inside the pockets, all the visibility arcs that contain a convex or a concave cap of p need to be identified. Whether or not a visibility arc contains a cap can be determined by the configuration of the support(s) on the arc. Suppose that a visibility arc pq hits the boundary of Q at q and does not have any support. Since circular arcs passing through p and q and lying entirely on either side of pq can be obtained, arc pq can not be on the boundary of the circular visibility region of p, and thus does not contain a cap. By a similar argument, visibility arcs that have only one support cannot contain a cap either. The following lemma establishes the properties for a CCW visibility arc having two supports and containing a cap. Lemma 1 (I) Let q be a point on the boundary of Q, and let pq be a CCW visibility arc with a concave support, vi, and a convex support, vj, ordered as p, vi, vj, and q. Then, arc vjq is a convex cap of p. (2) Let r be a point on the boundary of Q, and let pr be a CCW visibility arc with a convex support, vi, and a concave support, vk, ordered as p, vi, Vk, and r. Then, arc vkr is a concave cap of p. Proof. (1) Suppose, to the contrary, that there exists a visibility arc which em 6

anates from p and crosses vjq at q' (q' $ q), as shown in Figure 5. Because both of the supports vi and vj are on Q, which is a simple polygon, this visibility arc has to cross vVj. This means that this arc and pq intersect at three points, p, q", and q'. As two distinct circles have at most two intersections, an arc emanating from p and crossing vjq at a point other than vj cannot exist. As the region that is not circularly visible from p is to the convex side of vjq, arc vjq is a convex cap of p. (2) An illustration of such an arc is also given in Figure 5. As the proof for (2) is similar to that of (1), it is omitted. o It is easy to verify that without the confinement of a concave support on pvj (as shown in Figure 5), no matter how many more convex and concave supports there are, arc vrq can not be a convex cap. On the other hand, when pq has support(s) besides v, and vj, as established in Lemma 1, the region to the convex side of vj q is still not circularly visible from p. Arc vjq therefore remains to be a convex cap and a portion of the boundary of the circular visibility region of p. Likewise, without a convex support on pvk, arc vkr would not be a concave cap, whereas even if visibility arc vkr is in contact with supports besides vl and vk, arc Vkr will still be a concave cap of p. Additionally, a CW visibility arc contains a convex or a concave cap if its supports satisfy the same configurations as described in Lemma 1 for the supports of a CCW visibility arc. By identifying all the caps of p, and subsequently discarding its corresponding deficiencies, the circular visibility region of p is obtained. In the following, points in the CVD corresponding to visibility arcs that contain caps are identified. The correspondence between points on the partitioning curves of the CVD and their corresponding visibility arcs is now established. Recall that each partitioning curve in the CVD may be composed of a line segment (or a half-line), a piece of a parabolic curve, or both of them6. A partitioning line segment (or a partitioning half-line) is a portion of the perpendicular bisector between p and a vertex of Q, which means that the visibility arc centered at a point on this line segment will hit this vertex of Q. On the other hand, a partitioning parabolic curve, which is a portion of the parabola defined by p and an edge of Q, represents the locus of the centers of the visibility arcs that are tangent to this edge of Q. Let the points joining two or more partitioning curves be called the nodes of the CVD. A node that is joined by exactly two partitioning curves corresponds to the center of a visibility arc in one of the following three configurations: passing through two vertices of Q, passing through a vertex and tangent to an edge of Q, or tangent to two edges of Q. These vertices and/or edges of Q are the supports of this visibility arc. An illustration of the correspondence between a node of the CVD and its corresponding visibility arc is shown in Figure 6. Since this node vc is at the point where fi, a portion of the perpendicular bisector of p and vi, is joined by?j, a portion of the perpendicular bisector of p and vj, it corresponds to a visibility arc which has two supports vi and vj. Since the visibility arcs containing the convex and concave caps of p are visibility arcs with supports satisfying Lemma 1, they can be identified by examining the nodes of the CVD. In the degenerate case, a visibility arc may have more than two supports, which 7

Figure 6: Correspondence between a cap of p and a node in the CVD. corresponds to a node joined by more than two partitioning curves. In this case, there is still only one cap that needs to be identified. Suppose the sequence of the supports on a visibility arc pq begins with a concave support vi, as shown in Figure 7 (a), the region to the convex side of the arc between the first convex support vj and the end of this visibility arc is not circularly visible from p. Arc vjq is therefore a convex cap of p. On the other hand, suppose the sequence of the supports on a visibility arc pr begins with a convex support vl, as shown in Figure 7 (b), the region to the concave side of the arc between the first concave support Vk and the end of this visibility arc is not circularly visible from p. Arc vkr is therefore a concave cap of p. Furthermore, if there exists a concave support v, on vjq, as shown in Figure p p (a) (b) p (c) p (d) Figure 7: Visibility arcs that have more than two supports. 8

7 (c). Then, arc vq is a dangling arc. As indicated earlier, the open set of the dangling arc qv, is empty, arc v,q can therefore be ignored, and arc vjv, (rather than arc vjq) becomes the convex cap contained by pq. Similarly, if there exists a convex support vt on vkr, as shown in Figure 7 (d). Then, arc vtr is a dangling arc, and is therefore ignored. Arc vkvt (rather than arc vkr) becomes the concave cap contained by pr. By construction, the number of nodes and the number of partitioning curves of the CVD are of the same order as the vertices of Q, which is O(n). The identification of the caps, which requires the examination of all the nodes of the CVD and the partitioning curves passing through each of the nodes, can therefore be completed in O(n) time. With all the caps of p identified, the boundary of Q is then traversed to sew the caps to the boundary of Q contributing to the boundary of the circular visibility region, which can be achieved trivially in linear time. The total time required for this algorithm to construct the circular visibility region of a given point inside a simple polygon is thus O(n). Figure 6 illustrates the correspondence between a concave cap of p and its corresponding node in the CVD. The shaded region is the concave deficiency of p associating with the concave cap. Since this cap is the only cap of p, the unshaded portion of Q is thus the circular visibility region of p. 4. Circular Visibility Region of a Given Edge It is established in this section that the boundary of such a circular visibility region consists of portions of the boundary of the simple polygon and the convex and concave caps computed with respect to the emanating edge. These caps are obtained by sweeping the region of the polygon with various sets of visibility arcs from the emanating edge. The CVDs of some of the vertices of the simple polygon are computed to determine the transition between two sets of sweeping arcs. Due to the lack of amortized behavior in searching of the transitions for the sweeping arcs, the time complexity for constructing the circular visibility region of an edge is substantially higher than that for computing for a point. Let the emanating edge be denoted by uv, directed from u to v, and let the rays emanating from u and v and coincident with uv hit Q at points u' and v', as shown in Figure 8. It is noted that CCW visibility arcs emanating from the left side of u- (except at v) do not cross vv'. By duplicating uv and vv', a new polygon which consists of not only all the edges of Q but also edges v'v, vu, uv, and vv' is obtained. The emanating edge uv becomes an edge on the boundary of this new polygon. Similarly, a new polygon consisting of all the edges of Q and edge u'u, uv, vu, and uu' can be constructed, in which CCW arcs emanating from the left of -vu will not hit uu' and u'u. The circular visibility region of u-v with CCW visibility arcs can be obtained by merging the circular visibility regions computed individually for the two polygons above. The CW circular visibility region can be established similarly. For simplicity of discussion, it is assumed that the emanating edge is an edge on the boundary of the simple polygon, as defined in the following. 9

Figure 8: Decomposition of Q into two sub-polygons. Problem CVR(uv,Q): circular visibility region of an edge Given: a simple polygon Q with edges ~u, el, e2,..., and e,. Find: the portion of Q that is circularly visible from uv. Let a cap computed with respect to ~u be called a cap of uv. No other visibility arc emanating from u will cross a cap of u. The region separated from the circular visibility region of uv by a cap of ~uv is thus called a deficiency of uv. As adopted in Section 3, the deficiency that is to the convex (concave) side of a cap is called a convex (concave) deficiency, and the cap separating it from the circular visibility region is called a convex (concave) cap. In the following lemma, sufficient conditions for a point on uv to contribute a CCW visibility arc that contains a cap of uv are established. Lemma:2 Let p (p $ u and p $ v) be a point on uv and pq be a CCW visibility arc which emanates from p and hits Q at q. (1) Let vjq be a convex cap of p, where vj is a convex support of pq. Then, vjq is also a convex cap of uv if p is the point on uv which is circularly visible from vj and the closest to u, or if pq is tangent to uv at p. (2) Let viq be a concave cap of to p, where vi is a concave support of pq. Then, viq is also a concave cap of u-v if p is the point on Tu which is circularly visible from vi and the closest to v. Proof. As visibility arcs only emanate from the left of u- and pq is a CCW visibility arc, pv must lie on the concave side of pq. The two cases in the first part of the lemma are first discussed. (1) Suppose p is the point on uv which is circularly visible from vj and the closest to u, as shown in Figure 9 (a); points on uv which are circularly visible from vj must lie on pv. Since Q is a simple polygon, for an arc emanating from pv to reach vjq, the arc must first cross viVj from its convex side, where vi denotes the concave support that confines pq and makes vjq a convex cap of p. Since pv lies on the concave side of pq, for an arc emanating from pv to reach vivj, the arc must first cross pvi from its concave side. However, as two distinct arcs can have at most two intersections, an arc which emanates from pv and crosses pvi and vivj cannot cross vjq at a point other than vj. Therefore, vjq is a convex cap of uv. 10

(a) Lv (b) Figure 9: Convex and concave caps of uv. On the other hand, suppose p is the tangent point between pq and ui, which means that except for p, the rest of uv lies to the concave side of pq. For the same reason as established in the previous case, no other visibility arcs emanating from uv will cross vjq at a point other than vj. Consequently, in this case, vjq is also a convex cap of u. (2) The concave cap viq of p is shown in Figure 9 (b). Since the proof for showing that this cap is also the concave cap of uv is analogous to that for showing the convex cap of uv in (1), further analysis is omitted. o By the above lemma, it follows directly that some caps of an endpoint of uv are also the caps of uv. Corollary 1 (1) A CCW convex cap of u is also a convex cap of uv. (2) A CCW concave cap of v is also a concave cap of uv. Note that since uv is on the boundary of Q, a visibility arc of u computed in the presence of Q is always a visibility arc of uv. Edge uv may be considered as a concave support of a visibility arc emanating from u if this arc is tangent to uv. While Lemma 2 establishes sufficient conditions for a point on uv- to emanate visibility arcs that contribute to caps of uv, the following lemma establishes necessary conditions on the supports for such visibility arcs. Lemma 3 Let p (p $ u and p $ v) be a point on 'uT and pq be a CCW visibility arc which emanates from p and hits Q at q. (1) Let vjq be a convex cap of p, where vi is a convex support of pq and vi is the only concave support on pvj. Suppose p is the point on ui which is circularly visible from vj and the closest to u. Then, there exists a convex support, vj+i, on pvi, such that pvj+1 is a convex cap of vj. (2) Let viq be a concave cap of p, where vi is a concave support of pq and vj is the only convex support on pvi. Suppose p is the point on uv which is circularly visible from vi and the closest to v. Then, there exists a concave support, vi+i, on pvj, such that pvi+l is a concave cap of vi. Proof. The proofs are straightforward. In (1), if there does not exist such a convex support vj+l, there must exist a visibility arc from vj to up with a radius smaller than that of pq as up lies to the convex side of p. This contradicts the fact 11

that p is the point on uv which is circularly visible from vj and the closest to u. Since the order of supports on pvj, emanating from vj, follows the order described in Lemma 1 (1), pvj+l is a convex cap of vj. Similarly, in (2), if there does not exist such a concave support vi+l, p can not be the point on Wiv which is circularly visible from vi and the closest to v. The order of supports on Vip follows the order given in Lemma 1 (2), arc pvi+1 is therefore a concave cap of vi. o With the properties of the caps of uv identified, the details of the algorithm that computes the circular visibility region of -u are now described. First, terminologies and the hierarchy of the algorithm are given. It is clear that the portion of the polygon which is linearly visible from ~uv is also circularly visible from uv. By subtracting this linear visibility polygon from Q, a set of pockets with respect to uv, are obtained. Only circular visibility region inside the pockets need to be computed. A pocket is said to be a CW pocket if only CW arcs emanating from uv can reach the interior of the pocket, and a CCW pocket if only CCW arcs can enter it. (Since only CCW arcs are used for the illustration of the algorithm, CW pockets are ignored for the further consideration.) A line segment that separates a pocket from the linear visibility polygon is called the lid of the pocket. Every visibility arc which emanates from u-v and enters a pocket must cross the lid of the pocket. Let the extension of the lid of a CCW pocket intersect uv at a point p, where p - v. It is noted that only the arcs emanating from points on up may reach the inside of this CCW pocket. This means that up can replace 1u5 as the emanating edge, and therefore only the case where the extension of the lid intersects an endpoint of the emanating edge is analyzed. The domain in which caps of ~u need to be identified can be further reduced. In each CCW pocket, the convex and concave caps of v are first computed. This can be achieved by utilizing the CCW CVD of v, as discussed in Section 3. The region in a pocket that is circularly visible from v is also circularly visible from uv. Furthermore, by Corollary 1, the concave caps of v are also the concave caps of u-. Consequently, only the convex deficiencies of v may contain regions which are not circular visible from v but are circularly visible from uv, and requires further examination. The process for constructing caps of ~u in the convex deficiencies of v is now described by using the example shown in Figure 10, in which vjsl is a convex cap of v, the region to the convex side of vjs1 is a convex deficiency of v and is denoted as DV(vjsi), and vj is a convex support of vsl. To start, three possible emanating points on ilv which contribute visibility arcs that pass through vj and contain convex caps of 1uv are identified. The distinction among these three emanating points and the approach to construct them are given in the following. Case 1. Suppose that arc p2vj+l, a CW convex cap of Vj as shown in Figure 11 (a), is identified, where P2 (p2 7 u) is a point on uv and vj+1 is a convex support on p2vj. Since arc p2vj+l is a convex cap of vj, there must exist a concave support vi, on vj vj+l, that makes pzvj+l a convex cap of vj. Suppose that the CCW extension of Vjp2 intersects the boundary of Dv(vjs1) at a point s2. This concave support vi also makes Vjs2 a convex cap of P2. Again, since arc p2vj+1 is a convex cap of vj, 12

Figure 10: A convex cap vjs2 of uv. 8 82 82 vi v Viv ua v u P2 U V (a) (b) (c) Figure 11: Three emanating points that contribute convex caps of uv. p2 must be the point on uv which is circularly visible from vj and the closest to u. By Lemma 2, arc vjs2 is a convex cap of uv. Case 2. Suppose a CW visibility arc of Vj having a concave support vi and tangent to -uv at p2 is identified, as shown in Figure 11 (b). Due to the configuration of supports vi and vj on p2s2, arc v2j2 is a convex cap of P2, and by Lemma 2, a convex cap of Uv. Case 3. Suppose that u is circularly visible from vj, as shown in Figure 11 (c). By Corollary 1, the convex cap vjs2 of u is also a convex cap of uv. As visibility arcs of a point having supports in a certain configuration can be identified in the CVD of that point, which one of these three cases that is encountered can be determined by utilizing the CW CVD of vj. First, assume that Case 1 is encountered. Let vj+l denote the convex support on p2vi. Then, only the region bounded between vjsl and vjs2 (the region in Q that is to the convex side of vjsi and to the concave side of Vjs2), as shown in Figure 10, remains to be decomposed by additional caps. Since whether or not a visibility arc contains a cap can be determined by the configuration of the supports that confine the arc, the pairs of supports that may create a cap of uv are identified. By propagating such supports and sweeping with visibility arcs passing through these supports, the caps of uv in the region bounded between vjsl and vj2 can be constructed efficiently. 13

Figure 12: The transition of hinges of the sweeping arc. The process of sweeping for the identification of the convex caps of uv is now described. Imagine that P2S2, as shown in Figure 12, is a physical entity with elasticity which retains circularity when bent. Suppose that this physical arc is bent against its two supports at vj+l and vi by gradually pulling the center of the arc at c2 away from P2s2, along the perpendicular bisector between vi and vj+1. This process can also be viewed as sweeping with visibility arcs which emanate from ~uv and pass through two fixed points (provided that these arcs can reach uv). Vertices vj+l and vi are called the hinges of this sweep, and the arc that is bent is referred to as a sweeping arc. When the concave support is an edge rather than a vertex, the hinge point moves along the edge as the arc is swept. It is therefore the edge, rather than a fixed point on the edge, that is the hinge. Also, as the sweep proceeds, the center of the sweeping arc will move along a parabolic curve, rather than a straight line, defined by the edge and the other hinge which is a vertex of Q. Suppose instead of Case 1 it is Case 2 that is encountered, the emanating point P2 and vi will be used as the hinges, whereas if Case 3 is encountered, u and and vi will be used as the hinges. The sweep from p2s2 with hinges at vj+l and vi continues until the sweeping arc intersects the boundary of Du(vj s) (not including vj s) at s1, or comes in contact with either a convex support between vi and vj+l or a concave support between vi and the intersection of the sweeping arc with the boundary of Dv(vjsi). The part of the sweeping arc between vj+l and its intersection with uv cannot come in contact with any concave support during the sweep because it always lies in the region to the convex side of vvj and to the concave side of p2vj. This region does not contain any portion of the boundary of Q because vvj is confined by a concave support and p2vj by a convex support. Therefore, this part of the sweeping arc cannot encounter any support. When the sweeping arc reaches s1, the sweep is discontinued as the entire region bounded by vjsl and vjs2 is swept. On the other hand, if the sweeping arc comes in contact with one of the two types of supports before reaching sl, the sweep is stopped for changing the hinge(s). 14

P2 P3 I TV v1 L-~~~~~~~~~~~~~~~~~~~~~~~~~~~ Figure 13: A convex deficiency in the region bounded between Vis2 and vis3. The case that the sweeping arc comes in contact with a concave support vi+l between vi and the intersection of the sweeping arc with the boundary of Dv(vjsl) is presented. Let the sweeping arc at this moment intersect p-v at p3 and intersect the boundary of D (vj s) at 53. All the convex caps in the region bounded between v2s2 and ViS3 can be identified during the sweep from p2s2 to P3S3 with hinges at Vj+l and vi. Suppose that a convex support, such as vk shown in Figure 13, lying in D,(vjsl) and between vi and s4, the intersection of the sweeping arc with the boundary of Dv(vjsl), is encountered during the sweep. Since the sweeping arc is hinged at vi and vj+l, arc p4vj+l, where p4 is the intersection of the sweeping arc at this instance with uT, is a convex cap of vk. By Lemma 2, arc vkS4 is a convex cap of uv. While conceptually the immediate successive hinge vi+l and the convex caps of uv in the region swept before changing the hinge(s) are identified via the sweeping of visibility arcs, all of them can be identified directly from the CCW CVD of vj+l. Since the sweeping arc is hinged at vi and vj+l, the centers of the visibility arcs emanating from uv which are generated during the sweep must lie on the perpendicular bisector between vj+l and vi. Recall that a portion of this perpendicular bisector is a partitioning curve to the CVD of vj+l, and the nodes on this partitioning curve correspond to the centers of all the visibility arcs having vj+l, vi and other vertices or edges as supports. It is therefore sufficient to examine these nodes only. Since the sweeping arc is bent outwards, the radius of the sweeping arc must be getting larger accordingly. The search of the centers of the convex caps of uv starts from the node (on this partitioning curve) that defines P2s2, and moves away from vj+i for visibility arcs with larger radii. After the engagement of a new concave support at vi+1, as shown in Figure 12, the sweeping arc hinged at supports vi and vj+l can no longer reach the region bounded by vjs^ and vjs2. To avoid the obstruction, the hinge vi is replaced by the new concave support vi+i. With the hinges vj+l and vi+l, the process of sweeping the region for identifying convex caps of uv and updating the pair of hinges is repeated, until the sweeping arc intersects the boundary of Dv(vjsl) at sl. In the degenerate case the sweeping arc may come in contact with more than 15

Pf Figure 14: A concave deficiency in the region bounded between vj^s and v7s2. one support at the same time. Since the sweeping arc is bent outwards, it can be verified easily that when the sweeping arc comes in contact with multiple convex supports between vi and vj+1, the support that is the closest to vi should be selected. On the other hand, if the sweeping arc comes in contact with multiple concave supports between vi and the intersection of the arc with the boundary of Dv (vjs), the support that is the farthest from vi should selected. When there are multiple supports come in contact with the sweeping arc simultaneously between vi and vj+l and between vi and the intersection of the sweeping arc with the boundary of Dv(vjSi), individual rules are applied and both of the hinges are changed. After the above sweeping procedure, all the convex caps of uv' in Dv (vsl) are identified. Similarly, concave caps in the same region can be identified by bending vsl inwards against supports vj and vi, as shown in Figure 14. The main difference between the identification of convex caps and that of concave caps is in the transition of hinges. When vsl is bent inwards, it is the portion of the sweeping arc between vi and vj that may come in contact with another concave support and the portion of the sweeping arc between vj and its intersection with the boundary of D, (vsl) that may become in contact with another convex support. Alternating with the changing of the hinges of the sweeping arc, the concave caps of uv can be identified by utilizing the CVDs of one of the two current hinges. By this procedure, all the concave caps of uv and in Dv(vjs1) can be identified. The convex and concave caps of uV in all the convex deficiencies of v can be identified by using the above procedure. With the caps of ui identified, the boundary of the circular visibility region of uv is then completed by connecting these caps with the boundary of Q contributing to the boundary of the circular visibility region. The time required for constructing the circular visibility region from -uv is now analyzed. The (linear) edge visibility polygon from uv can be computed in linear time with an algorithm developed by Guibas, et al.8. The convex and concave caps of v which are computed in the beginning of the algorithm can be achieved in linear time, as illustrated in Section 3. Since the concave deficiencies of v are also the concave deficiencies of uv and the region in Q circularly visible from v is also circularly visible from uv, only the convex deficiencies of v are further examined. 16

For each convex deficiency of v, the caps of u' inside is are computed, which invokes two processes: computing the successive hinges and computing caps of 'uv while sweeping arcs against the two hinges. Since both processes can be achieved in linear time with the aid of the CCW CVD of a hinge, the total time required for the identification of all the caps of uv in the convex deficiencies of v is proportional to the number of CVDs computed. A new CVD needs to be constructed only when the hinge with respect to which the CVD is computed is replaced by another support. Let the total number of CVDs computed be denoted as k. As each of the CVDs can be computed in linear time, the total time required for the identification of all the caps inside convex deficiencies of v is O(kn), where n is the total number of vertices in Q. The connection of the caps of uv with the boundary of Q contributing to the boundary of the circular visibility region from uv can be achieved in linear time. The total time complexity for constructing the circular visibility region of uv is dominated by the identification of the caps of uv inside convex deficiencies of v, which is O(kn). It is noted that in the worst case, the number of the hinges with respect to which the CVDs are computed is O(n); the worst-case total time complexity of this algorithm is therefore O(n2). 5. Conclusion This paper utilized the structure of circular visibility diagrams in developing algorithms for computing circular visibility regions inside a simple polygon. It is shown that the circular visibility region of a point inside a simple polygon can be constructed in linear time. It is also shown that the circular visibility region of an edge inside a simple polygon can be constructed in O(nk) time, where n is the total number of vertices in Q and k is the total number of different sets of hinges for the caps. The increase in the time required for computing a circular visibility region from a given edge versus that for computing a linear visibility polygon of a given edge is also observed in the computing of the width of a polygon. It has been shown that the minimum distance of a pair of parallel lines which contain a simple polygon can be computed in linear time9, whereas the minimum distance of a pair of concentric circles which contain the same simple polygon can be computed in O(n log n + m) time10, where m is the number of intersections of the farthest point Voronoi diagram and the medial axis. In the worst case, m is equal to O(n2). References 1. P.K. Agarwal and M. Sharir, "Circular visibility in a simple polygon from a point", Technical Report No. 527, Department of Computer Science, New York University, 1993. 2. P.K. Agarwal and M. Sharir, "Circle shooting in a simple polygon", Technical Report No. 186/90, Institute of Computer Sciences, Tel Aviv University, 1990. 3. D. Avis and G. T. Toussaint, "An optimal algorithm for determining the visibility of a polygon from an edge", IEEE Trans. Comput., C-30, 1981, pp. 910-914. 17

4. B. M. Chazelle, L. T. Guibas, and D. T. Lee, "The power of geometric duality", BIT, 25(1), 1985, 76-90. 5. B. M. Chazelle and L. T. Guibas, " Visibility and intersection problems in plane Geometry", Discrete & Computational Geometry, 4, 1989, pp. 551-581. 6. S. Y. Chou and T. C. Woo, "A linear time algorithm for constructing a circular visibility diagram", Technical Report 91-28, Department of Industrial and Operations Engineering, University of Michigan, October 1991. 7. H. ElGindy and D. Avis, "A linear time algorithm for computing the visibility polygon from a point", J. Algorithms, 2, 1981, pp. 186-197. 8. L. Guibas, J. Hershberger, D. Leven, M. Sharir, and R. Tarjan, "Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons", Algorithmica, 2, 1987, pp. 209-233. 9. M. E. Houle and G. T. Toussaint, "Computing the width of a set", IEEE Trans. on Pattern Analysis and Machine Intelligence, 10(5), 1988, pp. 761-765. 10. V. B. Le and D. T. Lee, "Out-of-roundness problem revisited", IEEE Trans. Pattern Analysis and Machine Intelligence, 13(3), 1991, pp. 217-223. 11. D. T. Lee and F. P. Preparata, "An optimal algorithm for finding the kernel of a polygon", J. ACM, 26, 1979, pp. 415-421. 12. D. T. Lee, "Visibility of a simple polygon", Computer Vision, Graphics, and Image Processing, 22, 1983, pp. 207-221. 13. D. T. Lee and Y. T. Ching, "The power of geometric duality revisited", Information Processing Letters, 21, 1985, pp. 117-122. 14. J. O'Rourke, Art Gallery Theorems and Algorithms, Oxford University Press, 1987. 15. F. Preparata and M. I. Shamos, Computational Geometry: An Introduction, Springer-Verlag, 1985. 16. S. Suri, "A Linear Time Algorithm for Minimum Link Paths inside a Simple Polygon", Computer Vision, Graphics, and Image Processing, 35, 99-110, 1986. 17. S. Suri and J. O'Rourke, "Worst-Case Optimal Algorithms for Constructing Visibility Polygons with Holes", Proc. 2nd ACM Symposium on Computational Geometry, Yorktown Heights, 1986, pp. 14-23. 18