"i.' —'; -'"-"-...i. i "-i AUTOMATIC DISASSEMBLY AND TOTAL ORDERING IN THREE DIMENSIONS Tony C. Woo Department of Industrial and Operations Engineering Debasish Dutta Design Laboratory, Department of Mechanical Engineering The University of Michigan Ann Arbor, Michigan 48109 UM-MEAM-90-01.

N (tl.. I al'1 I~

AUTOMATIC DISASSEMBLY AND TOTAL ORDERING IN THREE DIMENSIONS Tony C. Woo Department of Industrial and Operations Engineering Debasish Dutta Design Laboratory, Department of Mechanical Engineering The University of Michigan Ann Arbor, Michigan 48109 Abstract Generating a sequence of motions for removing components in a three-dimensional assembly, one at a time, is considered -- the robot motion being strictly translational. We map the boundary representation of a given assembly to a tree structure called Disassembly Tree (DT). Traversing the DT in pre- and post-order yields a minimal sequence of operations for disassembly and assembly, respectively. In this paper, an assembly is classified by the logical complexity of its DT (an ordered graph whose nodes are components of the given assembly) and by the geometric complexity of the nodes in DT (in terms of the number of motions needed to remove a single component). Next, whether a component can be removed in one motion is described as a predicate. This predicate is then used in an algorithm for constructing the DT. For a class of assemblies that exhibit total ordering, the algorithm decides whether each component can be removed in a single motion, by constructing a DT in O(N log N) time, on the average, where N is the total number of mating faces in the assembly.

1. INTRODUCTION Automatic assembly may be studied from the point of view of disassembly. If we visualize the process of assembly as having a finite number of "states", each being captured by a single frame on film, then rolling the film backward corresponds to disassembly. If the components are rigid and there is no internal energy stored, the process of assembly/disassembly is reversible. (Such would not be the case with components of variable geometry such as a spring or a clip fastener.) Given a collection of components, a goal in automatic assembly is to arrive at a logical sequence of composition operations (for the components), with preferably the shortest total travel between the component bins. Reversing the process for disassembly, we require a minimal sequence operations for decomposing a given assembly. Conceptually, a possible approach may be the "Onion Peeling" procedure -- one starts from the outside and works inward, by exploiting the given structure of the assembly. While we are appealing to the intuition that automatic disassembly may be more feasible than automatic assembly, it is useful to examine the inherent structure of assemblies that is independent of the approach. We introduce three measures of complexity -- geometrical, logical, and dimensional -- for the assembly/disassembly problem. The "SQfa Moving Problem" [51 is an instance of a geometrically complex assembly/disassembly problem, in which an object (possibly non-convex) is to be navigated through corridors and obstacles without collision. If we associate a sofa to a single component being removed, then motion planning is concerned with the generation of a geometric solution (the shortest path, for instance) under constraints (that the obstacles are immobile and that collision is to be avoided, for example). Assembly planning, on the other hand, is concerned with the generation of a logical sequence of steps, each of which may be be a geometrically simple motion plan. The "Tower of Hanoi" is an instance -- its solution is well-known [1]. For less structured instances, such as stacking blocks given a non-unique initial configuration, more powerful reasoning mechanisms employing artificial intelligence may be needed [8]. Indeed, when the problem is logically and geometrically complex, it can be very difficult. The "Warehouseman's Problem", in which sofas are to be unstacked and removed, is known to be PSPACE-complete [2]. The degrees of freedom permitted, in the planning of motion, is another measure of complexity -- that of dimensionality. When the motion is restricted to translation only, and

the domain is in the plane, the solution for the Sofa Moving Problem is reduced from a doubly exponential time algorithm to one that is of polynomial time [6]. If N is the number of walls, the motion for a circular disk can be planned in O(NlogN) time [3], and for two disks in O(N3) time [7]. While there are other parameters influencing the complexity of the assembly/disassembly problem, such as the number of jigs and fixtures, and the number of robots simultaneously performing the task, they will be incorporated into these three measures -- geometrical, logical and dimensional, in the following characterization. First, we identify the notion of "clearing" a component from a subassembly. The criterion may be either of the following: C1. The convex hull of the component in question does not intersect the convex hull of the subassembly. C2. The component can be translated and rotated to the perimeter of a sphere of sufficiently large radius. C3. The component can be translated to infinity. For simplicity, we adopt C3 as the criterion in this paper. By allowing three degrees of freedom for translation in three dimensions, we have specified the domain of our problem, as illustrated in Figure 1.1, along the axis of "Dimensionality". < Insert Figure 1.1> Next, we specify the "Logical" complexity of our problem. Let the solution to a disassembly problem be represented by a tree, the nodes of which represent the components. In Figure 1.2(a), the assembly A has four interlocking components. It can be disassembled not individually, but only by removing the subassembly (ala2) first. Thus, as shown in the disassembly tree, nodes corresponding to parents of individual components, are complex and in general, correspond to subassemblies. Definition 1. I An assembly is k-parallel if the disassembly of a component requires the immediate prior clearing of k components, in parallel. A k-parallel assembly is one that requires k robots working simultaneously. Alternatively, it may be viewed as one requiring a special jig that "joins" the k components under consideration, while using one robot. (The trade-off between an active processor,

Geometry (Disassemblability) >2 otal Partial Logic (Ordering) 2 Dimensionality (Degree of Freedom) Figure 1.1 Complexity of Assemblies

such as a robot, and a passive one, such as a fixture, while interesting, is not within the scope of this paper.) <Insert Figure 1.2> Now consider the component bn in Figure 1.2(b). The tree in Figure 1.2(b) shows that disassembly of bn is possible after k of its neighbors have been cleared, not necessarily in parallel. As such, the parent nodes of leaves in this tree are simpler than in Figure 1.2(a) in that, they are components and not subassemblies. Note however, each leaf can have one or more parent. Definition 1.2 An assembly is k-sequential if the disassembly of a component requires the prior disassembly of k other adjacent components. It may be noted that while parallelism imposes necessary conditions, sequentialism' imposes only sufficiency conditions. In other words, a k-sequential assembly, though requiring only one robot k times, can be disassembled by using k robots operating in parallel, once. However, a k-parallel assembly cannot be disassembled using one robot k times. The complexity of the parent nodes in a disassembly tree provides insights on the parallelism associated with the problem. When it is a sequential problem, by observing the number of "parents" of a node in the disassembly tree, we arrive at a characterization of assemblies by "logical" ordering. Definition 1.3 An assembly is partially ordered if the disassembly of a component requires an immediately prior disassembly of k components. If k < 2, the assembly is totally ordered. In this paper, we restrict our study to sequential assemblies that are totally ordered. Thus, corresponding to each component, a node in the disassembly tree will have exactly one parent. Finally, we examine the "Geometric" complexity of assemblies as prescribed by Figure 1.1. Consider the assembly shown in Figure 1.3(a). The clearing of component al requires two translations. Recalling the general "Sofa Moving Problem", in which multiple motions are required, we have a characterization for the complexity of nodes in a disassembly tree (whose structure is characterized by partial or total ordering).

(al a2) ( 7 iI a1 a2 (a) Parallel Assembly 23J 0 000 b bi A _h oo I j (b) Sequential Assembly Figure 1.2 Partially Ordered Assemblies

<Insert Figure 1.3> Definition 1.4 A component is n-disassemblable if m motions are needed to clear it While a k-parallel assembly differs from a k-sequential one in the number of processors required, an m-disassemble component differs from an n-disassemblable one, by the amount of storage required. By Definition 1.4, an m-disassemblable component requires (m-l) temporary locations before it reaches its destination. Viewed as a program, a motion plan for an m-disassemblably component requires (m-1) assignments or temporary variables. (While the trade off between the number of processors and the amount of storage is an issue, we shall return our focus to characterization.) In this paper, we consider assemblies that are totally ordered, for which each component is 1-disassemblable with three degrees of freedom (as shown in Figure 1.1). The construction of a disassembly tree for an object (assembly) composed of three dimensional, totally ordered, 1-disassemblable components, is not trivial. One of the difficulties comes from the observation that improper ordering of the components affects the m-disassemblability of each component. Consider Figure 1.3(b) in which there are L components on the left and R components on the right. If removed first, each of the L components are 2-disassemblable. However, after all R components are removed first, the L components become 1-disassemblable. To determine which one of the k = (L + R) components is 1-disassemblable suggests a decision procedure that could take [k + (k-l) + (k-2) +...] steps leading to an O(k2) time algorithm. In this paper we provide an algorithm that requires O(N log N) time, where N is the number of mating faces of a component. The remaining sections are organized as follows. Section 2 discusses the determination of 1-disassemblability of a component. We use a motonicity check for the mating faces of the component. In Section 3 we present an algorithm for constructing the disassembly tree (DT) for an assembly. The algorithm is then illustrated by an example. Section 4 concludes the paper. 2. COMPONENT DISASSE.MBLABILITY In this paper, we assume that components in an assembly "touch" each other, i.e. they are not disjoint nor do they intersect (occupying the same space). For simplicity, we shall first consider assemblies with only two components -- one being the component under consideration for removal and the other representing the subassembly (the rest of the

a I2 (a) 2-Disassemblable Jl l I IL R ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~II A (b) 1-Disassemblable Figure 1.3 Totally Ordered Assemblies

assembly). Compare the two examples in Figure 2.1(a) and (b), whose exploded views are given by Figure 2.1(c) and (d), respectively. It is clear that component cl is disassemblable with respect to subassembly SI1 while component c2 is not disassemblable with respect to S2. We can distinguish these two types by computing a range of directions along which a component can be translated such that it does not interfere with the subassembly. <Insert Figure 2.1> Definition 2.1 A component c is I -disassemblable (or just disassemblable, for short) from a subassembly S in the direction d if, for all points p in c, a RAY (p,d), which is a semiinfinite line from p in the direction d, does not intersect S. Intuitively, it is clear that if a robot can "see" all points p of component c from infinity, along the direction of RAY (p,d), then an interference-free disassembly is ensured. In Figure 2.2, we illustrate the notion of disassemblability by RAY (p,d). For ease of illustration, a two-dimensional cross-section is considered. However, in subsequent analysis, we generalize the concepts to 3D. <Insert Figure 2.2> In Figure 2.2(a), directions dl and d2 satisfy Definition 2.1, for all points p in component cl, Thus, RAY(p, dj) and RAY(p, d2) are both valid directions for the disassembling component cl from S. By contrast, directions d3 and d4 do not satisfy Definition 2.1, for all p in cl. In Figure 2.2(b), however, there does not exist a direction d such that RAY (p,d), for all p in c2, satisfies Definition 2.1. While Ray (pl,di) seems satisfactory for point pl, the same direction dl applied to point P2 causes interference. Similarly, RAY (p3,d2) does not satisfy disassemblability for point pil though d2 is satisfactory for P2. The crucial test for disassemblability, according to Definition 2.1, is that the direction d must yield a non-intersection RAY (p,d) for all points p in the component under consideration. As there are uncountably many points in each component, we need to identify a finite set based on which we can compute disassemblability for the entire component.

(a) (b) S2 (c) (d) Figure 2.1 Disassemblability

XlqtuIssgsT. Jo uoi;c3lO. Z' Z OmI (q) dd *d I p P P I (t) zd I P n

In the following sections, we compute the directions for disassembly from the normals of the mating faces, a subset of the boundary shared by a component and the subassembly. (Readers with intuition may choose to go directly to Section 2.2 in which the procedure is given.) For completeness, we need to show that consideration of mating face normals is not only necessary but also sufficient. 2.1 Mating Faces Disassembly, according to Definition 2.1, involves two entities: a point and a direction. For a given direction, we need to verify that it satisfies all the points in the component under consideration. The following lemma shows the sufficiency of considering only the boundary. Lemma 2. 1 For a given direction d, component c is disassemblable if RAY (p,d) does not intersect subassembly S, for all points p on the boundary of c. [Proof] Let a point p be in the interior of component c. The RAY (p,d) makes an odd number of intersections with the boundary of c. Consider the intersections by PI, P2, P3.-.Pn+l, where n is an even integer starting at o. Since p is in c, it is necessarily outside S. The RAY (p,d) makes an even number of intersection with the boundary of S, possibly none. Let these intersections be ql, q2,...qm-l, where m is an odd integer starting at 1. Referring to Figure 2.3, we see that it is not possible to have qi between p and l, and in general between Peven and Podd, in the direction of RAY (p,d). Thus, there is no loss of generality by treating p as pi and as being on the boundary of c, since p lies between Peven and Podd and intersection with S cannot occur in that interval. <Insert Figure 2.3> While Lemma 2.1 provides the basis for computing disassemblability (replacing the interior by the boundary), we still need to show that only the portion of boundary in common between the component and the subassembly is necessary for computation. Lemma 2.2 Disassembly in the sense of Definition 2.1 can be determined if and only if there is a common boundary between component c and subassembly S.

C p i;)% 1 qp 3q3 q4 Sure Figure 2.3 Proof of Lemma 2.1

[Proof] Divide the boundary of c into two disjoint subsets, one of which may be empty. In Figure 2.4, we denote the subset in common with that of the subassembly s by Bcs and the other B'cs, We show that Bcs dominates B'cs by the following case analyses. Case 1 [Ray from a point in B'cs does not intersect S.] Let Pl be in B'cs.Suppose RAY (pl,dl) does not intersect S. But a ray in the same direction from a point in Bcs, p3 for example, will intersect S. Case 2. [Ray from a point in B'cs intersects S.] Let P2 be a point in B cs. Suppose RAY (Pl, P1) does intersect S. A ray in the same direction from any point in Bcs, P4 for example, must also intersect S. Case 3 [Ray from a point in Bcs does not intersect S.] Suppose RAY (p3,d3) does not intersect S, where p3 is in Bcs. By the same reasoning in the Proof for Lemma 2.1, a ray in the same direction from another point in B'cs, P1 for example, cannot intersect S. Case 4 [Ray from a point in Bcs intersects S.] Suppose RAY (p4,d4) intersects S, where p4 is in Bcs. A ray in the same direction from a point in B'cs does not have to intersect S -- RAY (pl,dl), for example. <Insert Figure 2.4> 2.2 Monotoniticity Having identified the mating faces as being necessary and sufficient for computing a direction for disassembly, we can now describe the procedure for checking disassemblability of a component with respect to its mating component (or subassembly). Let us impose directions on the unit normals of all faces such that they point inwards (i.e. towards the material side of the component). Each face can be mapped via its directed normal to a point on the unit sphere. Thus, corresponding to the set of mating faces we obtain a set of points on the sphere. (Loosely speaking, this point set can be thought of as the spherical representation of the mating faces). The convex hull of a set of points on a sphere can be defined similar to its cousin on the plane, and when computed, has portions of great circles of the sphere as its edges [11]. Thus, each set of mating faces

Cs d, dl/ P;4.Bcs' \ 44 gf Fig 2.4 Proof of Lemma 2.2

of a component has an associated convex hull (of normals) on the unit sphere. Clearly, the lower dimensional analogue of the spherical convex hull is an arc segment of the unit circle (resulting, for example, from the normals of the mating face set of a 2.5 D object). Figures 2.5 (a), (c), and (e) illustrate the planar case for an assembly that is disassemblable (the arc segment lies within a semicircle), while Figures 2.5 (b), (d) and (f) depict one that is not disassemblable (arc segment spans more than a semicircle). The notion of montonicity of faces [4], provides a precise characterization of disassemblability of a component. <Insert Figure 2.5> Definition 2.2 A set of faces (fl) with directed normals (dl) in 3-space is monotone if the set of points corresponding to the spherical representation of (di) lies on a hemisphere. It is easy to visualize the 3D analogues of the cases shown by Figures 2.5(e) and (f). The convex hull associated with the normals of component cl in Figure 2.5(e) lies on a hemisphere which has the XY plane as its base, while the convex hull of normals of c2 in Figure 2.5(f) spans more than a hemisphere. Thus, c cannot be disassembled. On the other hand, component cI can be disassembled from its subassembly S1. A valid direction for the disassembly is given by the RAY (o,h), where o is the center of the sphere and h is the pole of the hemisphere. Procedures based on central projections have been reported for computing convex hulls on the sphere and for checking hemisphericity [ 1 ]. They require O(N log N) time where N is the number of points being considered on the sphere. However, a check for hemisphericity is required prior to the convex hull computation. Thus, although the convex hull allows for easier visualization of the boundary of the set of points on the sphere, it is not required for performing the hemisphricity check. The following procedure determines monotonicity and a direction of removal D, for a given component c with a set of mating faces (fi). Function Disassemblable (.c l 1. (fi) < — mating faces of c 2. (di) < — unit normals of (fi) 3. (ri) < — points on sphere SPH corresponding to (di) 4 If (ri) contained in a hemisphere of SPH

SI S2 (a) (b) (c) (d) * Y y y (e) (f) Figure 2.5 Hemisphericity of Face Normals

then return'RAY(o,h)' else return'false' Lemma 2.3 The disassemblability of a component c with respect to a subassembly S can be determined in O(n log n) time, where n is the number of mating faces in c. [Proof] Let the cardinality of (fi) be n. Clearly, the steps 1, 2 and 3 in Function Disassemblable take O(n) time. Step 4 is the hemisphericity check and requires O(n log n) time. It is to be noted that the inclusion of the convex hull computation in the above algorithm does not increase its time complexity. We are now ready to consider the generation of DT with more than two components. 3. DISASSEMBLY TREE The input to the algorithm consists of two data structures. A face adjacency graph FAG contains nodes that are faces of each component and arcs that denote adjacency. Each face belongs to exactly two mates. If one of the two mates is the background, then the face is a boundary face. Otherwise, it is a mating face. FAG is used as input to Function Disassemblable. In Figure 3.1(a), faces of two mating components are shown. The L-shaped face is split into two faces -- fi is a mating face and fj is a boundary face. As shown in Figure 3.1(b), a mating face is denoted by a circle and a boundary face by a square in FAG. A second data structure, component mating graph CMG, is a weak dual of FMG. Its nodes are components and its arcs denote mating. CMG is used in determining the ordering. Figure 3. 1(c) shows two components a and b mating at face fi. Mating with boundary B is denoted likewise. Both FAG and CMG can be constructed from a boundary representation of a solid model in linear time [9]. <Insert Figure 3.1> Our strategy is to begin from the outside. We take a component with a boundary face and test it for disassemblability. If it is disassemblable, we delete its boundary faces from FAG, change its mating faces to boundary faces, delete the component from CMIG and insert it in DT. Next, we exploit the adjacency relation in the CMG. If a component is found to be disassemblable, its mating components are the next candidates. If each

~k " I component a f k component b (a) Faces of Two Components faces of other faces component b of component a 0: mating face (b) Face Adjacency Graph: boundary face other components Jf (c) Component Mating Graph Figure 3.1 Data Structure

component has m mates then the algorithm would run in O(mk) time. The following lemma asserts that m, on the average, is a constant. Lemma 3.1 In a component mating graph CMG with k nodes, each node on the average has (3 - 6/k) nodes that are adjacent to it. [Proof] The CMG with k nodes is a three-dimensional polyhedron P with k vertices. If the faces of P are triangulated there are a maximum of (3k - 6) edges in P [10]. Averaged over k vertices, each vertex has (3 - 6/k) edges in CMIG. Hence, each component, on the average, has (3 - 6/k) mating components. Thus, the first "layer" of components disassembled are the ones with boundary faces. The second and subsequent layers are the mates of the ones that have been disassembled. 3.1 DT Construction We first state the algorithm and then illustrate its use by an example. Algorithm Disassembly Tree Input: FAG and CMG Output: Disassembly Tree (DT) [Initialize] 1. Root (DT) < — Assembly A 2. NODES = 0, LEVEL = 0, COMP = Number of components in A 4. Active_Leaf= =Boundary node in CMG [Grow Tree] While (NODES < COMP ) do Retrieve all mates of Active_Leaf from CMG LEVEL = LEVEL + 1 At HEIGHT=LEVEL, for each mate M of Active_Leaf do If M not at HEIGHT < LEVEL, call FunctionDisassemblable (M) If M is disassemblable then

insert M as Active_Leaf in DT and NODES = NODES + 1 else return'false' End For the ease of illustration, we shall take the cross-section of a three-dimensional assembly and combine it with FAG. In Figure 3.2(a), we see five components: a, b, c, d and e. For example, face (f17 ) is a mating face between a and b and face (fl4 ) is a mating face between a and the background B (i.e. a boundary face belonging to the component a). The CMG in Figure 3.2(b) shows the mating of the components with each other as well as with the background B. <Insert Figure 3.2> The generation of a disassembly tree for this example is illustrated in Figure 3.3. The empty disassembly tree DT is initialized with a root node A (denoting the entire assembly). From CMG, we find four candidate components a, b, c, and d that mate with the boundary and are retrieved, as shown in Figure 3.3(a). Each candidate is tested for disassemblability with respect to an appropriate subassembly, i.e [assembly A - component]. Thus, for example, the subassembly for component d is [A - d]. Testing d for disassemblability using Function_Disasemblable returns "false".Therefore, d is not a new node in the tree (and is marked by a shaded circle in Figure 3.3(a)). All other components are added to the tree. An integer variable NODES is used to record the total number of attached nodes, excluding the root node A. Currently, NODES has a value 3. <Insert Figure 3.3> Next, we expand the tree by retrieving from CMG the mates of each of the leaf nodes and by testing their disassemblability. If a retrieved mate occurs elsewhere in the tree, (i.e. at a HEIGHT less than the current LEVEL) it is discarded from further consideration. In Figure 3.3(b), the component a has two mates, b and d. Since b occurs previously (at LEVEL = 1), it is marked by a circle and not considered for further testing. The mate d has not occurred previously and is now tested for disassemblability. Following the example, it is found that d is disasssemblable. Hence, it is inserted in the tree and NODES is incremented by 1 (to equal 4). Next, the mates for component b are retrieved. They are shown as a, c, d, and e in Figure 3.3(c). Since components a, c and d have occurred previously (at LEVEL = 1), they are excluded from further consideration. The

V15 V14 17 Background a f 14 b d Z V13 C (a) Face Adjacency Graph b a Ge. C d (b) Component Mating Graph 9~ igr I. xml

a b c a b c. Nodes =3 Nodes 4 (a) (b) A A a b c a b d W)c(d e d e Nodes =5 Nodes =5 (c) (d): not disassemblable O: occurs previously Figllre 3.3 Generation of a Disassembly Tree

remaining component e is tested and found to be disassemblable, and is added to the tree. At this point, NODES is incremented by 1, to equal 5. Since NODES equals the total number of components in the assembly the algorithm terminates. The resulting tree is shown in Figure 3.3(d). It is important to note that the choice of a 2D example to demonstrate the working of our algorithm was primarily with a view towards keeping the explanations/illustrations simple. The correctness of the algorithm when applied to 3D assemblies, is a direct consequence of the disassemblability check for 3D assemblies, as performed by Function Disassemblable. A pre-order traversal on the DT shown in Figure 3.3(d) yields the disassembly sequence (a — > d — > b — > e — > c). Similarly, a post-order traversal on DT yields the assembly sequence (d — > a — > e — > b — > c). It is easy to verify that both sequences are valid. Now, it is useful to show that the DT thus constructed yields a minimum number of removals (motions) in order to have access to a certain component. For example, suppose component e in Figure 3.2(a) is to be removed. According to the DT generated in Figure 3.3(d), only component b has to be removed (rather than components a and d, for example). The following lemma, which asserts the minimality of the number of removals, is proved by an induction on the height of DT. Lemma 3.2 The disassembly tree DT is optimal in that, the path from the root of DT to any node is the shortest possible when traversed top-down (in pre-order). [Proof] At initialization, DT has a root node and its height is 0. The first layer of components with boundary faces gives DT a height of 1. Now, suppose the height of DT is (h - 1). We examine the cases in which a new node (corresponding to a component c) is to be inserted in DT. Case 1. [Component c appears elsewhere in DT] If the component appears elsewhere in DT, it will not be considered again, by construction. Hence the number of removals to disassemble component c is no greater than (h - i).

Case 2. [Component c is not yet in DT] If the component has not appeared before, its position in the tree can be at most height h. Since a node appears exactly once in DT and since its position is as near the root as possible, the number of removals is minimum. Hence DT is optimal. 4. CONCLUSION We have characterized the complexity of automatically generating assembly sequences based upon geometrical, logical and dimensional considerations. Within this framework, we addressed assemblies composed of planar faceted components, that were totally ordered and 1 -disassemblable. We presented an algorithm for computing disassembly sequences for a given assembly, by generating a disassembly tree DT. Traversing the DT in pre-order yields a minimal disassembly sequence. Traversing it in post-order yields an assembly sequence. If there are k-components each with m mates, it is possible that in the worst case the algorithm takes O(mk) time to construct a DT. Since the expected value of m is bounded by "a constant, it runs in O(k) time on the average. To compute disassemblability, we involve N, the number of mating faces for each component. Summed over k components, the time complexity for constructing a DT is O(N log N), where N is the total number of mating faces in the assembly. 5. REFERENCES 1. Aho, A. V., Hopcroft, E., and Ullman, J. D., Data Structures and Algorthms, Addison-Wesley, 1983, pp. 306-306. 2. Hopcroft, J.E., Schwartz, J. T. and M. Sharir, "On the Complexity of Motion Planning for Multiple Independent Objects: PSPACE Hardness of the Warehouseman's Problem". Int. J. of Robotics Research. Vol. 3, No. 4, 1984, pp. 76-88. 3. O"Dunlaing, C. and Yap, C., "A Retraction Method for Planning the Motion of a Disc", J. of Algorithms, Vol. 6, 1985, pp. 104-111. 4. Preparata, F. P. and Supowit, K., "Testing a Simple Polygon for Montonicity" Information Processing Letters, Vol. 12, No. 4, 1981, pp. 161-163.

5. Reif, J., "Complexity of the Mover's Problems and Generalizations", Proc. 20 IEEE Symp. on Foundations of Computer Science. 1979, pp. 421-427. 6. Schwartz, J. T. and Sherir, M., "On the Piano Mover's Problem: II. General Techniques for Computing Topological Properties of Real Algebraic Manifolds", Advances in Appl. Math, Vol. 4, 1983, pp. 298-351. 7. Schwartz, J. T. and Sharir, M., "On the Piano Movers' Problem: III. Coordinating the Motion of Several Independent Bodies: The Special Case of Circular Bodes Moving Amidst Polygonal Barriers", Int. J. of Robotics Research, Vol. 2, No. 3, 1983, pp. 46-75. 8. Winston, P. H., Artificial Intelligence, Addison-Wesley, 1977, pp. 157-164. 9. Woo, T. C., "A Combinatorial Analysis of Boundary Data Structure Schemata", IEEE Computer Graphics & Applications. Vol. 5, No. 3, 1985, pp. 19-27. 10. Woo, T. C. and Wolter, J. D. "A Constant Average Time and Linear Storage Data Structure for Three-Dimensional Objects", IEEE Trans. Systems. Man and Cybernetics. Vol. SMC-14, No. 3, 1984, pp. 510-515. 1 1. Chen, L. L and Woo, T. C., "Computational Geometry On The Sphere With Applications To Automated Machining", Tech. Report TR-89-30, Dept. of Industrial & Operations Engineering, The University of Michigan, Ann Arbor, MI 48109-2117, August 1989.

UNIVERSITY OF MICHIGAN 3901511111111111! Ie9~ 02229 noo 15;72