ALGORITHMIC APSECTS OF ALTERNATING SUM OF VOLUMES, PART II. NON-CONVERGENCE AND ITS REMEDY Kai Tang Tony Woo Department of Industrial & Operations Engineering University of Michigan Ann Arbor, MI 48109-2117 Technical Report 90-30 October 1990

ALGORITHMIC ASPECTS OF ALTERNATING SUM OF VOLUMES Part II. Non-Convergence and its Remedy Kai Tang Tony Woo University of Michigan * Send correspondence to: Tony Woo Dept of Industrial & Operations Engineering University of Michigan Ann Arbor, MI 48109-2117 U.S.A. Accepted by Journal of Computer Aided Design, to appeari March 1991.

1 Abstract This is the second of a two-part paper. As the first part focused on the issues of data structure and fast difference operation, this part studies the non-convergence of the Alternating Sum of Volumes (ASV) process. An ASV is a series of convex components joined by alternating union and difference operations. It is desirable that an ASV series be finite. However, such is not always the case - that the ASV algorithm can be non-convergent. In this paper, the causes of this non-convergence are investigated and the conditions responsible for it is found and proven. Linear time algorithms are then developed for the detection.

2 1. INTRODUCTION An Alternating Sum of Volumes (ASV) series is convergent if a deficiency Q1 is the null set; otherwise, it is said to be non-convergent. (For computation of efficiency, the detection of a null deficiency Q. can be replaced by the determination of the convexity of Qn1.) Figure 1 illustrates a non-convergent ASV series. The series of deficiencies 2l, Q2,..., as derived from the convex hull (CH) and difference (-) operations never converges to the null set, resulting in an infinite alternating series: {CH(2) - CH(f1) + CH(2) -... - CH(f2i-1) + CH(Q2i) - *... Qf Qfl CH / CH 7 C 7 CH(Q) CH(fb) __ Q2S S_ 57 f> fls CH CH CH CH(Q2) repeats CH: Convex hull operation -: Difference operation Figure 1. Illustration of ASV non-convergence

3 As implied in Figure 1, the non-convergence of an ASV series is determined by the non-convergence of a deficiency in its expansion. It is known [12] that an ASV series is non-convergent when the convex hull of a deficiency Ri identifies with the convex hull of the deficiency of Ri. For the example in Figure 1, the convex hull CH(Q1) is equal to the convex hull CH(Q2). As the result of the identification: CH(Qi)=CH(Qi+l), the following relation between the deficiencies holds: Qj=Qj+2 (igj). Formally, a deficiency Ri is said to be non-convergent if the convex hull of its deficiency CH(Qi)-2i is equal to CH(fi), and convergent otherwise. It is desirable to be able to characterize the non-convergence of a deficiency Sfi directly, rather than invoking the comparision between CH(Qi) and CH(Ri)-Qi. This persuit is justified in two regards. First, four convex hull operations and two set difference operations must be performed to obtain the datum CH(Qi), CH(2i)-fli, and CH(CH(Ci)-Qi) for the comparision. Set difference operation on a polyhedron with m vertices is known to take at least O(m2) time prior to the O(mlogm) result in Part I of this paper. Secondly, even if the fast O(mlogm) difference operation is involved, detecting the presence of a null set, as the result of the difference, can be numerically unstable. A fast non-convergence detection algorithm for a pseudo polyhedron without carrying on the set difference and comparision operations is offered as a new result for this part of the paper. Suppose a fast non-convergence detection algorithm for a deficiency is available. One way to detect the non-convergence of an ASV series is to test for the non-convergence of every deficiency as it is being computed. The time required by such a detection scheme is heavily dependent on the depth n of the first non-convergent deficiency fln -- the larger the number n is, the more time it will take. Alternatively, it may be inquired if the detection of the non-convergence of a series can be achieved without invoking the ASV process itself. Not only because the deficiencies thus produced are non-productive if that ASV series does not converge, but also because a separate scheme may speed up the detection time. From the theorectic point of view, such a study induces some interesting problems, such as that of finding the minimum number of faces in a non-convergent deficiency. These two closely related issues, fast detection of the non-convergence of a deficiency and that of an ASV series, are investigated in this paper. In the next section, the concepts of strong hull and weak hull vertices are introduced. The characterization of these two types of vertices

4 leads to an O(nlogn) algorithm for detecting the non-convergence of a deficiency, where n is the number of vertices in the deficiency. In Section 3, a sufficient condition for the non-convergence of an ASV series is given, which requires only linear time to detect.

5 2. CHARACTERIZATION OF NON-CONVERGENT DEFICIENCIES In this section, the following problem is to be solved: Given a pseudo polyhedron Qi, under what condition will the equation CH(QR) = CH(CH(Q2) - Qi) hold and how fast can such a condition be detected? The symbols "CH" and "-" represent the convex hull and regularized difference operations, respectively. (Note that every deficiency in an ASV series must be a pseudo polyhedron, as shown in Part I of this paper. Hereafter, the two terms "pseudo polyhedron" and "deficiency" will be used interchangeably.) Before the condition for non-convergence is characterized, it is useful to summarize the relations between the boundary and interior points of a pseudo polyhedron Q2, its convex hull CH(Qi), and its deficiency CH(Qi) - SQ. The first relation, which has been shown in Part I of this paper, is re-cited below. Lemma 1. The deficiency of a pseudo polyhedron fi is also a pseudo polyhedron, whose interior I(CH(Q) - Qi) is the set difference (I(CH(Qi)) - I(Qi)), and the boundary B(CH(Ri) - Qi) is a subset of (B(CH(Qi)) - B(Qi)} that forms the closure of {I(CH(Qi)) -I(Q) }. A pseudo polyhedron is completely described by its faces and a face is determined by its edges which themselves are defined by their end points called vertices. Since the vertices of the convex hull of a set of points must be a subset of that point set, by Lemma 1, the vertices of the deficiency of 4i is a subset of the vertices of 4i. In other words, the difference operation in the ASV expansion can be viewed as a vertex elimination process: After each difference operation, the deficiency RQ possesses fewer vertices than does the deficiency Qi 1; this process continues until a convex pseudo polyhedron n is reached so that its deficiency Qn+ is the null set. If the vertices in the deficiencies can not be eliminated through the difference operation, then the ASV series does not converge. A vertex of a pseudo polyhedron Ri is eliminatable if it does not exist in its deficiency CH(Qi)-Q, otherwise it is non-eliminatable. A formal definition of the non-convergence of pseudo polyhedron is then in order. Definition 1. A pseudo polyhedron Qi is non-convergent if all of its vertices are

6 non-eliminatable; otherwise, it is convergent. To characterize the eliminatability of vertices in ri, the vertices are categorized into two groups, hull vertices and internal vertices. The hull vertices are those that are on the boundary of CH(Qi), whereas those vertices of Qi that are not on the boundary of CH(RQ) are internal. Each of the internal vertices has a three-dimensional neighborhood which is strictly inside CH(Qi). Furthermore, this neighborhood contains a subset of (I(CH(Qi)) - I(Qi)} since an internal vertex is also a boundary point of ui. Therefore, by Lemma 1 all the internal vertices are non-eliminatable. To study the eliminatability of the hull vertices, they are further separated into weak and strong hull vertices. Definition 2. In E3, the three-dimensional Euclidean space, a hull vertex of Qi is weak if it has a three-dimensional neighborhood that contains points in (fi u {E3 -CH(Q)})) only; otherwise it is called a strong hull vertex. Difference operation 0: Weak hull vertices *: Strong hull vertices *: Internal vertices Figure 2. Weak, strong hull and internal vertices As shown in Figure 2, after a difference operation, strong hull and internal vertices remain whereas all the weak hull vertices are eliminated. Let those faces (edges) of a pseudo polyhedron Si be called hullfaces (hull edges) if they are completely on the boundary surface of CH(Qi), and internal faces (internal edges) otherwise. Referring to Figure 2, it can be inferred that a hull vertex is weak if and only if all of its incident faces are hull faces of Qi.

7 (Note however that this condition does not hold for incident edges. That is, a hull vertex with incident hull edges only is not necessarily weak, as shown by Figure 3, where the strong hull vertex v has no incident internal edges.) The contribution of strong hull vertices to the non-convergence is manifested by the following lemma. v Figure 3. A strong hull vertex with no incident internal edges Lemma 2. A pseudo polyhedron Qi is non-convergent if and only if all of its hull vertices are strong. Proof. First it is noted that the hull and internal vertices partition the entire vertex set of Qi, due to their mutual exclusivity. By Definition 2, a weak hull vertex has an open three-dimensional neighborhood within which Qi is equal to CH(Qi) and thus there is no any subset of (I(CH(Ri)) - I(i)}) in that neighborhood. Hence, by Lemma 1, all the weak hull vertices are eliminatable. Conversely, since every three-dimensional neighborhood of a strong hull vertex contains a subset of (I(CH(Qi)) - I(Ri)), they are preserved on the deficiency of fi, i.e., they are non-eliminatable. By Definition 1 and the fact that all the internal vertices are non-eliminatable, the proof is complete. Q.E.D. Lemma 2 implies that the detection of the non-convergence of a pseudo polyhedron R is equivalent to distinguishing its strong hull vertices from the weak ones. Such a process takes two steps: classify the hull and internal faces of Qi, and then check if Ri has a vertex which has incident hull faces only. Whether a face is internal can be identified by way of checking that of one of its interior points. (Such a point must not be on an edge of the face since an internal face may have hull edges only, e.g. face f in Figure 3.) Si is then non-convergent if and only if no

8 weak hull vertex exists. The algorithm given below follows the two steps just described. It is assumed that a procedure HULL(N,V,Vtg) is in hand, which takes a list V of N points as input and outputs a property array V g such that if Vtg(i) is "true" then point i in V is a hull vertex of CH(V); and "false" if it is an internal vertex. Algorithm DETECT ((q) /* Detect the non-convergence of a pseudo polyhedron Qi. The vertex list V and face list F of (i have n, vertices and nf faces, respectively */ begin step 1. for k=lto nf do V(nv+k) < — an interior point of face k in F end do step 2. call HULL(nv+nf,V,Vg) step 3. set array VP(1: n,) to "true" step 4. for k=1 to nf do for every vertex v of face k in F do VP(v) < — VP(v)nV(nv+k) end do end do step 5. for k=l to nv do if VP(k)="true" then return ('convergence') end if end do

9 step 6. return ('non-convergence') end DETECT In the algorithm DETECT, the nf interior points of the faces of Qi are first appended to the vertex array V of Qi. Since each interior point of a face can be obtained in constant time by considering any two adjacent edges of that face, step 1 takes O(nf) time. The convex hull procedure HULL is called at step 2 which requires only O((nv+nf)log(nv+nf)) time [6]. At step 3, a property array VP(1:nv) is preset to "true". At step 4, the following is carried out: if a face k is internal, i.e., its interior point tag V,(n,+k) is "false", the corresponding entries in VP for all the vertices of face k are reset to "false". Such a process obviously takes 0(D) time, where D=~di (i=1,2,...,nv), and di is the degree of vertex i. It is shown in the Appendix of Part I of this paper that D is O(nf). Finally, at step 5, the array VP is scanned and i is identified as convergent if some entry in VP is "true", and non-convergent otherwise. The time complexity of the algorithm DETECT is summarized by the following theorem. Theorem 1. The detection of the non-convergence of a pseudo polyhedron fi with n vertices can be done in O(nlogn) time. Compared to the simple comparision method: CH(Qi) = CH(CH(fi)-fi) [12], the new detection algorithm DETECT avoids both the time consuming difference operation and the identification of a null set which could be numerically unstable. Two convex hull operations are also saved. It may be noted that the detection algorithm DETECT disregards the disconnectedness of a set. The pseudo polyhedron li in Figure 4(a) is non-convergent by Lemma 2. The deficiency Qi+1, however, consists of two separate pseudo polyhedra P1 and P2. Though 1i+l is non-convergent as a single set, it is convergent if represented as ASV(RQ+1) = ASV(P1+P2) = ASV(P1) + ASV(P2) because P1 and P2 are both convergent. It results in a convergent ASV tree ASV(Qn) = H - Qi+, = H - ASV(-+,1) = H - (ASV(Pi) + ASV(P2)), which branches at the

10 deficiency Qi+l. In some other cases, a pseudo polyhedron, though connected, might be separated uniquely at some edges such that the separated subsets are all convergent. For example, the pseudo polyhedron fi in Figure 4(b) is non-convergent by Lemma 2, it is however convergent if expressed as Qi = H - Qi+l = H - (P + P2 + P3 + P4) since all Pl, P2, P3 and P4 are convergent. 0; A _-^^,CHH H SQi> pz = 000- + m (a) Li CH iiiii ~zj~ H p P (b) Figure 4. Convergence by set separation Both examples of set separation on 4i.l shown in Figure 4 bear a crucial property: the boundary of the separated pseudo polyhedron remains unchanged. Unlike polyhedral decomposition [4], such a property guarantees that the boundary after the separation will have the same sets of vertices, edges, and faces, with only the adjacency and incidence relations among them altered. Furthermore, it will be shown next that such a separation is unique, thus

11 justifying the existence of a deterministic algorithm. To define set separation rigrously, the concept of well-connectedness is needed. Definition 3. Two points p and q of a pseudo polyhedron Qi are said to be well connected in Qi if there exists a curve c between p and q such that all the points in c, except for possibly p and q, are in I(,2). fi is a well-connected set if all of its points are well connected in it, otherwise it is a ill-connected set. (Refer to Figure 5.) (a) Well-Connected set (b) Ill-Connected set Figure 5. Well-connected set vs. Ill-connected set The Qi+l in Figure 4(a) and both Di and Qi+l in Figure 4(b) are ill-connected pseudo polyhedra. A well connected pseudo polyhedron is also called a robust set, meaning its interior is all connected. A subset r of a pseudo polyhedron Di is a maximally well-connected set (MWCS) of Qi if r is a well-connected set and any addition of non-4 points of Li to 5 will constitute an ill-connected set. As an example, only Pi, P2, P3 and P4 are the MWCSs of the pseudo polyhedron Qi+1 in Figure 4(b). It is desirable that an ASV series be expanded as much as possible so that more features can be extracted. Once a non-convergent and ill-connected deficiency is encountered, it should be separated into the MWCSs and the ASV process can then be performed on each of them. This leads to the notion of strong and weak non-convergence. Definition4. A non-convergent pseudo polyhedron Ri is strongly non-convergent if both itself and its deficiency are robust. Otherwise, Qfi is weakly non-convergent. As examples, the deficiency Sl in Figure 1 is strongly non-convergent since both itself

12 and its deficiency 22 are robust, whereas each Qi in Figure 4 is weakly non-convergent because either itself or its deficiency Q,+ is ill-connected The detection of the strength of non-convergence of a pseudo polyhedron Qi of n faces requires three steps: the identification of its non-convergence, the computation for the deficiency of Di, and the classification of the well-connectedness of Qi and/or its deficiency. The first step can be done, by Theorem 1, in O(nlogn) time. The difference operation also requires O(nlogn) time as shown in Part I of this paper. Thus, if the classification of the robustness of Qi can be done in O(nlogn) time, so can the detection of the strong non-convergence. Since Ski is robust if and only if its MWCS separation contains only one MWCS, i.e., itself, the goal becomes the finding of an O(nlogn) time MWCS separation algorithm In implementing such an algorithm, it is noted that, by definition of a pseudo polyhedron, the well-connectedness of its boundary point set will ensure it to be a well-connected set. This fact ensures that the MWCSs of a pseudo polyhedron can be detected by checking only the well-connectedness of its faces. Let two faces of a pseudo polyhedron be well-adjacent to each other if they share a common edge and are well-connected to each other. It can be easily shown that two faces A and B of a pseudo polyhedron are well-connected if and only if either they are well-adjacent or there exist a number of faces f1, f2,... fl such that A is well-adjacent to fl, f1 is well-adjacent to f2,..., and fk is well-adjacent to B. For example, in Figure 6, faces A and B are not well-connected because the curve c connecting points p and q passes through edge "e" which does not belong to the interior of that pseudo polyhedron. poi.nt. A _pofite B face A point p.... point q ut;Lt VI Figure 6. Ill-connectedness of faces of a pseudo polyhedron

13 To characterize face well-adjacency, let fl, f2,... fm be the faces incident to a common edge, ordered by their spatial angles. (In Figure 7, flI,f2...fm are the intersections between the faces sharing a common edge and a plane orthogonal to that edge.) Apparently, the well-adjacent face of face fi (i=1,2,...,m) is either fi-l or fil (mod m), depending on the direction of the outward normal of fi. Such a pairing process can be done in O(m) time. The following recursive procedure MWCSFACES finds the faces of a maximally well-connected set of a pseudo polyhedron Qi. The input is the pseudo polyhedron representation (V,E,F,NORM,Ef) of 2i and the index of a face of Qi. The output are the indices of those faces of (i that form the boundary of a MWCS of fi. fin-l beg Figure 7. Well-adjacency of faces. Procedure MWCS_FACES (f,i Qi) /* Find those faces of a maximum well-connected set of pseudo polyhedron n; f is the index of a face that is required to be on the MWCS. */ begin step 1. output f step 2. el, e2,..., ek < — edges of face f step 3. forj=l, k do step 3.1. f < — the index of the face well-adjacent to f at edge ej step 3.2. if (f has not been output) then call MWCSFACES(f,Qi)

14 end do {step 3) end MWCS FACES Suppose a total of m edges el,e2,...,em of Qi are found in a MWCS, denoted by P, through MWCS FACES. Let ki and ki' be the face adjacency indices of ~i and P at edge ei respectively (i=1,2,...,m). Step 1 takes constant time and thus the overall time spent at step 1 when MWCSFACES terminates is O(n), where n is the number of faces on P. Since each face of P is processed only once, the overall time required by step 2 is 0(1(ki') (i=1,2,...,m)). As for the loop at step 3, note that the indices of the faces of fi adjacent to edge ej are stored in the order of their spatial angles in an entry of the Ef list of Di. So, only O(logkj) time is needed to locate the position of f in that entry, hence, the index f of the face well-adjacent to face f at an edge ej. As a result, the overall time taken by step 3.1 is O(1(ki'logki) (i=1,2,...,m)). The total time cost of MWCS FACES is therefore O(n + (z(ki'logki) (i=l,2,...,m))). Before presenting the complete algorithm to carry out the MWCS separation, it is necessary to clarify that, given the indices of n faces that form the boundary of a MWCS of Qi, only O(n) time is needed to construct the pseudo polyhedron representation <V,E,F,NORM,Ef> of that MWCS, say Pi. To see this, note that all the VE,F,NORM and Ef lists of Pi are readily available in the <VE,F,NORM, Ef> of Pi. The only work needed besides the retrieval is to re-index the vertices, edges and faces of Pi once they are retrieved from Qi. For example, if only vertices (v3,V4,V7,V9,Vi5) are on Pi, and there is an edge on Pi whose entry in the E list of Q is <9,4>, then this edge will become <4,2> in the E list of Pi because vertices v9 and V4 now sit at the forth and second positions of the V list of Pi. Analogously, if edges (e2,e7,el0,e13) are on Pi and Pi has a face stored in the F list of Qi as <10,7,13>, then this face will become <3,2,4> due to the re-indexing of (e2,e7,e10,e13). Clearly, this re-indexing process can be done in 0(n) time through simple index mapping. Let MWCS OUTPUT be such a process, which takes as input a pseudo polyhedron Qi and a list L of indices of the faces of fi and outputs the pseudo polyhedron representation of a MWCS of Qi whose faces are those of Qi with indices in L. Utilizing both procedures

15 MWCS FACES and MWCS OUTPUT, the algorithm given next performs the MWCS separation. Algorithm MWCSSEPARATION (i) /* Compute the MWCS's of a pseudo polyhedron fi and output them */ begin step 1. unmark all the faces in the F list of fi step 2. while (there is a face f in F which is not marked) do step 2.1. L < — MWCS_FACES (f, i) step 2.2. call MWCSOUTPUT(L,Qi) step 2.3. mark all the faces with indices in L end do (step 2) end MWCS SEPARATION Lemma 3. The MWCS separation of a pseudo polyhedron 4j with nf faces can be done in O(nflognf) time and O(nf) space. Proof. In the algorithm MWCS SEPARATION, step 1 takes O(nf) time. For the while loop at step 2, since each face can only be in one MWCS, the overall time cost of step 2.2 and step 2.3 is clearly O(nf). The time taken by each execution of the procedure MWCS FACES is in the form of O(n + (I(ki'logki) (i=1,2,...,m))), where n and m are the numbers of the faces and edges on that particular MWCS, ki and ki' are numbers of the faces of Qi and that MWCS adjacent to an edge of the MWCS respectively. By the same reason that a face of fi can only be in one of its MWCS's, the sum of Ywki'(i=1,2,...m) over all the edges of fi is O(Zki (i=1,2,...,ne)), where ne is the total number of edges of i. Therefore, after the termination of MWCS SEPARATION the overall time taken by step 2.1 is O(nf + (lkq) lognf ), that is, O(nf lognf ), since Ski (i= 1, 2,...,ne) is O(nf). Q.E.D.

16 With Theorem 1 and Lemma 3, the following is in order. Theorem 2. Whether a pseudo polyhedron 4i is strongly non-convergent or not can be detected in O(nlogn) time, where n is the number of the faces of (i. It is worth noting that in the ASV process, the algorithm MWCSSEPARATION not only detectes the strong non-convergence of a deficiency ~i, but also constructs the MWCS's of the deficiency 1-l. The pseudo polyhedron representation of the MWCS's can then be used for the subsequent convex hull and difference operations, along the corresponding branches after 2i+l.

17 3. FAST DETECTION FOR ASV NON-CONVERGENCE An ASV series is non-convergent if it has a non-convergent deficiency Qn. A way to detect the non-convergence of an ASV series is to check the non-convergence of every deficiency in the series. The time required by such a detection sets an upper bound. Theorem 3. It needs at most O(n2logn) time to decide whether the ASV series of a pseudo polyhedron Q is convergent or not, where n is the number of vertices of Q. Proof. Recall that the difference operation is a vertex elimination process. That is, a non-convergent deficiency ak in ASV(Q) always has fewer vertices than that of Qk- l In the worst case, suppose only one vertex is eliminated after each difference operation. To obtain the deficiency Qk through ASV process, k convex hull and difference operations are needed, resulting in an overall time requirement of XO(ilogi)(i=n,n-1,...,n-k). Therefore, at most;O(ilogi)(i=n,n-l,...,l)~O(n21ogn) time is needed to detect whether ASV(Q) converges or not. Q.E.D. In an attempt to improve this upper bound, the local cause of the ASV non-convergence of a pseudo polyhedron Q is sought. Such a study results in a sufficient condition for the ASV non-convergence, which eventually leads to a linear detection algorithm. In search for this local cause, it is useful to invoke the mechanics of regularized intersection [9]. Definition 5. The regularized intersection of two pseudo manifolds A and B, denoted by A*B, is a pseudo manifold whose interior is I(A)rnI(B). Figure 8 gives two examples of regularized intersection. As shown in Figure 8(a), the regularized intersection A*B is the null set < even though the ordinary set intersection AnB yields two faces. The result of the regularized intersection in Figure 8(b) is a non-convergent pseudo polyhedron. A tantalizing finding is revealed by the example of Figure 8(b): if there exists a (non-empty) subset (prior to the reqularized intersection) which is non-convergent, then the ASV series to be expanded is non-convergent. Such an observation is not an coincidence, the basis of which is shown by the following lemma.

18 (a) (b) Figure 8. Regularized set intersection Lemma 4. Let r be a subset of the vertices of a pseudo polyhedron Q. If the regularized intersection between Q and CH(r) is a non-convergent pseudo polyhedron, the ASV series of 2 is non-convergent. Proof. Assume that Q*CH(r) is a non-convergent pseudo polyhedron. It is claimed that all the vertices in r are non-eliminatable. Suppose there is a deficiency Qi in ASV(Q), whose vertex set is a superset of (, such that some vertex v in ( is lost on the deficiency fi+l. By Lemma 2, this means that all the incident faces of v are the hull faces of Qi. Since CH() is a subset of CH(Qi), it follows that v is also a weak hull vertex of Q*CH(~), which is contractory to the assumption that Q*CH(r) is non-convergent. Q.E.D. Lemma 4 provides a sufficient condition for the non-convergence of an ASV series, without invoking the ASV process itself. A direct implement of such an algorithm is, however, infeasible since there are O(n!) number of subsets. To reduce this high complexity, the characterization of local subsets of vertices, i.e., those that are adjacent to a common vertex, is investigated.

19 Let two vertices of a pseudo polyhedron be said to be adjacent to each other if they are the two end points of an edge. Definition 6. A vertex v of a pseudo polyhedron Q is supportable if there exists a plane containing v such that the point set, lie on its one side, (where,, consists of those vertices that are adjacent to v); otherwise v is a non-supportable vertex. As an example, all the vertices except for v of the pseudo polyhedron in Figure 9(a) are supportable. Also shown in Figure 9(b), a vertex v is non-supportable if and only if it is strictly inside the convex hull of the vertices adjacent to it. v (a) (b) Figure 9. Supportable and non-supportable vertices Lemma 5. If a pseudo polyhedron Q has a non-supportable vertex, then the ASV series of Q is non-convergent. Proof. Let v be a non-supportable vertex of L and, be the point set consisting of those vertices that are adjacent to v. The lemma is proven by showing that Q*CH(^,) is a non-convergent pseudo polyhedron. Since v is internal to CH(^,), all its incident faces have portions that are internal to CH(V). Then, in each of these faces, there is a point which has an open threedimensional neighborhood that contains a subset of I(Q) that is strictly inside CH(4,). By definition of the regularized intersection, this neighborhood is preserved on Q2*CH(4,). In other words, Q*CH(,) must be a pseudo polyhedron since its interior is

20 not empty. Now, consider a hull vertex p of Q*CH(k), as illustrated in Figure 10(a). If p belongs to,, as none of the incident faces of v can be a hull face of CH(4,), p can only be a strong hull vertex of Q*CH(4v). If p does not belong to 4, it must be an intersection point between some face f of Q and a hull face of CH(4,). (Refer to Figures 10(b) and (c).) Since face f has a portion internal to CH(4,), which becomes an internal face of Q*CH(tv), p must be a strong hull vertex of Q*CH(,v). Therefore, all the vertices of Q*CH(4v) are either internal or strong. By Lemma 2, K*CH(&,) is non-convergent. Q.E.D.;I~~~~ /\/ CH( I:4v.cV) (a) (b) (c) Figure 10. Proof of Lemma 6 As an illustration of Lemma 5, vertex v of the pseudo polyhedron in Figure 9(a) is non-supportable. The regularized intersection between the pseudo polyhedron and CH(4V), where, are those six vertices adjacent to v, is another pseudo polyhedron as in Figure 9(b) which is non-convergent. By Lemma 5, the ASV series of the pseudo polyhedron in Figure 9(a) does not converge, which can be easily verified. An extension to the supportability of vertices is the supportability of edges. Consider the

21 pseudo polyhedron L in Figure 11(a). Its ASV series can be easily shown to be non-convergent, though all its vertices are supportable. n f' vl (a) (b) Figure 11. Non-supportable vertex introduced by a non-supportable edge Definition 7. An edge e of a pseudo polyhedron is supportable if there exists a plane containing e such that all the faces incident to e are on one side of that plane; otherwise edge e is non-supportable. Lemma 6. If pseudo polyhedron Q has a non-supportable edge e, then ASV(Q) is non-convergent. Proof. Assume that the non-supportable edge e has k incident faces fl, f29...fk, and v1 and v2 are its two vertices. Let p be an arbitrary point on e, but not v1 or v2. Also let pi, which is not vl or v2, be a vertex on face fi (i=1,2,...,k). Since the line segment [p,pi] is on a face fi of a, the addition of p to the vertex set of Q as well as the addition of edges [p,vl],[p,v2],..., and [p,pi] (i=1,2,...,k) to the edge set of Q introduce a new pseudo polyhedron representation of Q, as in Figure 1 l(b). Since e is non-supportable, all the points in it, except for possibly vl or v2, are strictly inside CH((vl,V2,p,p29...Pk) ) This implies that the vertex p is non-supportable. By Lemma 5, ASV(f2) is nonconvergent. Q.E.D. It should be mentioned that Lemma 5 and Lemma 6 supply a sufficient but not necessary condition for non-convergence. As an example, all the vertices and edges of the polyhedron in Figure 12 are supportable. Yet, its ASV series is non-convergent

22 Figure 12. Non-convergent polyhedron with no non-supportable vertices or edges Nevertheless, a linear time algorithm for detecting the sufficiency of non-convergence offers an attractive alternative to the O(n2logn) time for both necessity and sufficiency. Let o be the origin and (xl,yl,zl),(x2,y2,z2),...,(xk,yk,zk) be k points in the threedimensional space. If the point o is supportable against (x1,ylzl), (x2,Y2,Z2),., (Xk,Yk,Zk), the angle between the normal vector No of a supporting plane PO and the vector (xi,yi,zi) must not be greater than 900 for all the i=1,2,..., k. (See Figure 13.) Conversely, if there exists a vector No such that the angle between it and a vector (xi,yi,zi) (i=1,2,...,k) is less than or equal to 900, then the plane passing through o and orthogonal to No is clearly a supporting plane. Therefore, the detection of the supportability becomes the following: Given k vectors (x1,Y1,z1), (x2,y2,z2),., (xk,Ykz,), find another non-zero vector (A,B,C) such that Axi+Byi+Czi2O (i=1,2,...,k). It is known [6] that the solution to this three-variable problem, if it exists, can be obtained in O(k) time. No (, Yi zi) Figure 13. Angular relation between the normal of a supporting plane and the adjacent vertices Let SUPPORT(kL) be such a supportability detection procedure, which takes a list L of k points as input and outputs either "true" if the origin is supportable against L or "false" otherwise. With the procedure SUPPORT, the following algorithm is in order.

23 Algorithm NSVDETECT (Q) /* Detect the existence of non-supportable vertices in a pseudo polyhedron Q with nv vertices. */ begin step 1. for i=l,nv do step 1.1 v < — the ith vertex in the vertex list V of Q step 1.2. {Pl, P2,-*.,Pk} < — those vertices in V that are adjecent to vertex v step 1.3. translate {Pi, P2,..-,Pk) by a displacement of -v step 1.4. if SUPPORT(k,(pl, p2,...,pk))='false' then return with "non-supportable vertex found" end if end do step 2. return with "no non-supportable vertex found" end NSV DETECT To device an algorithm for detecting the supportability of an edge e of a pseudo polyhedron Q, let v and v' be the two end points of e, p be its center point, and f, f2,..., fk be the faces of Q incident to e. Also let pi be a point on face fi such that the line segment [p,pi] completely belongs to fi (i=1,2,...,k). (See Figure 14.) Such a point pi can be obtained in the constant time from the (clockwise or counter-clockwise) order of the edges. Let FS(p, fi) denote the function which returns the point pi. Referring to the proof of Lemma 6, e is supportable if and only if p is supportable against the point set {v,v',pl, P2, —.,Pk}. This equivalence relation gives rise the following algorithm.

24 Figure 14. Finding the point Pi on face fi Algorithm NSE_DETECT (Q) /* Detect the existence of non-supportable edges in a pseudo polyhedron n with ne vertices. */ begin step 1. for i=l,nedo step 1.1 v, v' < — the two vertices of the ith edge in the edge list E of Q step 1.2. p < — the center point of [v,v'] step 1.3. fl, f2,...,fk <- those faces in Q that are adjecent to the edge [v,v'] step 1.4. pi, P2,..-,Pk < — FS(p, fl), FS(p, f2),..., FS(p, fk) step 1.5. translate {v,v', Pi, P2,.-,Pk) by a displacement of -p step 1.6. if SUPPORT(k+2,{v,v',pl, p2,...,pk))='false' then return with "non-supportable edge found" end if end do step 2. return with "no non-supportable edge found" end NSE DETECT Lemma 7. The existence of non-supportable vertices and non-supportable edges of a pseudo polyhedron Q with n, vertices, n. edges, and nf faces can be detected in at most O(nf) time. Proof. The theorem is proven by showing that both the algorithms NSV_DETECT

25 and NSE_DETECT are O(nf) in time. For the algorithm NSV DETECT, because the procedure SUPPORT runs in linear time, the time complexity required by the loop at step 1 is linear in Idi(i=1,2,..., n,), where d, is the degree of the ith vertex in Q, which has been proven to be O(nf) in the Appendix of Part I of this paper. Therefore, NSVDETECT runs in O(nf) time. For the algorithm NSEDETECT, by a similar reasoning, the time required by the loop at step 1 is linear in ki(=,2,..., where ki is the face adjacency index of the ith edge in Q. In the Appendix of Part I of this paper, it is shown that Iki(i=l,2,..., ne) is O(nf). Therefore, NSEDETECT runs in O(nf) time. Q.E.D.

26 4. SUMMARY It has been established that it takes O(n2logn) time to determine if the ASV seris of a given Q converges. In particular, it takes O(nlogn) time to detect if a deficiency iQ is non-convergent. To remedy the non-convergence, an O(nlogn) time algorithm is offered to separate the culprit deficiency Qi into maximally well-connected sets. As an expedient alternative to the O(n2logn) time detection for non-convergence, the sufficiency condition for non-convergence can be detected in O(n) time.

27 References [1] A. Baer, C. Eastman, and M. Henrion, "Geometric Modeling: A Survey" Computer -Aided Design, Vol. 11, No. 5, Sept. 1979, pp. 253-272. [2] C. Bollobas, Graph Theorev. Springer-Verlag, 1979 [3] A. Cary, "BUILD USERS' GUIDE", University of Cambridge, C.A.D. Group Document,No. 102, Nov. 1979. [4] B.M. Chazelle, "Convex Decomposition of Polyhedra", ACM Symposium on Theory of Computing, Milwaukee 1981, pp. 70-79. [5] H. Chiyokura, F. Kimura, "A Method of Representing the Solid Design Process", IEEE Computer Graphics and Application, April 1985, Vol. 5, No.4, pp. 32-41. [6] F.P. Preparata and M. L. Shamos, Computaional Geometry, Springer-Verlag, 1985 [7] F.P. Preparata and S.J. Hong, "Convex Hull of Finite Sets of Points in Two and Three Dimensions", Comm. ACM 2(20), Feb. 1977, pp. 87-93. [8] A.A.G. Requicha, "Representation for Rigid Solids: Theory, Methods and Systems", ACM Computing Surveys, Vol. 12, No 4, Dec. 1980, pp. 437-464. [9] A.A.G. Requicha, H.B. Voelcker, "Solid Modeling: Current Status and Research Directions", IEEE Computer Graphics and Application, Oct. 1983, Vol. 3, No.7, pp. 25-37. [10] A.A.G. Requicha, H.B. Voelcher, "Constructive Solid Geometry", University of Rochester, Production Automation Project, TM-25, Nov. 1977. [11] K. Weiler, "Topologocal Structures for Geometric Modeling", Ph.D dissertation, Rensselaer Polytechnic Institute, Aug. 1986.

UNIVERSITY OF MICHIGAN 3 I V 28 [12] T.C. Woo, "Feature Extraction by Volume Decomposition", Proc. Conf. On CAD/CAM Technology in Mechanical Engineering, Cambridge, Mass. 1982 [13] T.C. Woo, "A Combinatorial Analysis of Boundary Data Structure Schemata", IEEE CG&A, Vol. 5, No. 3, March 1985, pp. 19-27.