THE SPANNING LINE SEGMENTS OF A POLYHEDRON Tony C. Woo Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109-2117 and Jia Ye Wang and Ding Yuan Liu GINTIC Institute of Manufacturing Technology Nanyang Technological University Singapore 2263 Technical Report 93-42 December 1993

The Spanning Line Segments of a Polyhedron Jia Ye Wang Ding Yuan Liu GINTIC Institute of Manufacturing Technology Nanyang Technological University Singapore 2263 Tony C. Woo Department of Industrial and Operations Engineering University of Michigan Ann Arbor, MI 48109-2117 Xiaoming Chen School of Medicine Johns Hopkins University Baltimore, MD Abstract In a polyhedron, it is observed that line segments arranged in a certain fashion preserves the intersection property. That is, if intersection occurs with a given polyhedron, the same must take place with the line segments; and vice versa. These line segments are said to be spanning the (non-convex, and non-simply connected) polyhedron. In this paper, the properties for the spanning line segments are introduced and algorithms are presented for their construction.

1 Introduction Computing for the intersection between two polyhedra is found in many applications, such as computer graphics, solid modeling, computer-aided design, computer-aided manufacturing, robotics, inspection and assembly. While there is an abundance of literature in the application areas, there is little to be found in the way of improving one of the fundamental algorithms: testing for possible intersection between a plane and a polyhedron - with the notable exception of a recent article [R93] on testing for the intersection between a plane and a box, using interval arithmetic. To be sure, if a polyhedron is convex, the box test often suffices. One finds the minima and the maxima in each of the three coordinates of the vertices of the given polyhedron, giving rise to six rectilinear planes - forming a "box". To detect if two boxes intersect, for example, their intervals are compared. Intersection occurs if two intervals overlap. Such an algorithm would take O(N) time, where N is the number of vertices, in finding the minimum or maximum. If the polyhedron is non-convex and is non-simply connected, an approximation closer than that of a box is desirable, with a correspondingly higher processing time. One can, for example, find the convex hull of a polyhedron with N vertices in O(N log N) time [P85] and the intersection of two convex hulls take O(N2) in time. Whether a polyhedron is convex or otherwise, the basic idea in testing for intersection has been the same: substitute the given polyhedron with one which is topologically simpler and test for possible geometric intersections. A box or a convex hull has fewer vertices, in general, than does a non-convex polyhedron. As there 2

are fewer topological entities in number, the surrogate serves its purpose. It may be noted, however, that the dimensionality of the surrogate and that of the polyhedron are the same: both are 3D. Symbolically, the intersection between a 2D plane and a 3D entity (a box, a convex hull or a general polyhedron) may be denoted as a 2 x 3 problem. In this paper, the 2 x 3 problem in reduced to a number of 2 x 1 problems, in which the surrogate is a collection of ID line segments. The surrogates are called the spanning line segments (or SLS for short). Likewise, the 3 x 3 problem of intersection between two polyhedra is reduced to that of a number of 3 x 1 problem between a polyhedron and a set of line segments. When a problem is simplified in its dimensionality, one expects a corresponding decrease in the computation time. Let s denote the number SLS in a polyhedron with N vertices. The employment of the SLS reduces the computation time from O(N) to O(s), as given in Table 1. without SLS with SLS intersection dim time intersection dim time polyhedron x polyhedron 3 x 3 O(N2) polyhedron x SLS 3 x 1 O(N * s) plane x polyhedron 2 x 3 O(N) plane x SLS 2 x 1 O(s) Table 1 Contribution of SLS In this paper, s is shown to be lower-bounded by n/2, where n is the number of extreme vertices which lie on the convex hull of an arbitrary polyhedron with N vertices. There is no general relationship between n and N; in the best case (of a convex hul being a tetrahedron) n = 4, and in the worst case (of a convex polyhedron) n = N. Thus, SLS guarantees a savings of 50% or more in computation time. 3

The immediate possibility of a faster test for polyhedral intersection aside, there is the implication of a more compact representation for general polyhedra. Indeed, this idea of finding the "skeleton" of a planar or spatial region is not new. The celebrated medial-axis transformation [B67, B78] is an example, which finds applications in biology, image processing, and manufacturing automation. The structure for a set of line segments as a surrogate is different from that of a skeleton. A set of line segments is said to be spanning a given polyhedron if and only if a plane intersecting the polyhedron also intersects one or more of the line segments. Figure l(a) shows an "hour glass" shaped polyhedron; its corresponding set of SLS is illustrated in Figure 1(b). It may be noted that any plane that intersects the hourglass must necessarily intersect its SLS, and vice versa. It may also be noted that the SLS of a polyhedron is not unique. The set, though different in appearance, in Figure l(c) has the same spanning characteristics. The observation that the extreme vertices play a role in the construction of the SLS suggests a trivial algorithm: 1. Choose an extreme vertex (which lies on co the convex hull) of the given polyhedron. 2. Create line segments between it and all other extreme vertices. Such an algorithm clearly generates (n - 1) spanning line segments, where n is the number of extreme vertices. For comparison, the hour-glass has N = 12 vertices, of which n = 8 are extreme. The trivial algorithm would yield n - 1 = 7 line segments for the SLS, while the examples in Figure 1 suggested s = 4. The challenge for computing the SLS is becoming clear. It would be desirable to 4

find a minimal SLS, given a polyhedron of N vertices from which n extreme vertices are derived. In the following sections, the characterizations of the SLS are given, with bounds established. Algorithms approaching the optimum are then presented. 2 Properties To characterize intersection, the notion of the convex hull of a set of points is employed at several places in this section. First, a basic observation on the intersection between a plane and a polyhedron is made. Lemma 1. A plane intersects a polyhedron if and only if the plane intersects the convex hull of the polyhedron. The proof is rather straight forward and is omitted for brevity. The observation made by Lemma 1, though simple, is useful. It reduces the number N of vertices in a given polyhedron to that of the extreme vertices n. Algorithmically, Lemma 1 suggests taking the convex hull of the given polyhedron if it is non-convex and non-simply connected. Consequently, all polyhedra will be treated as convex in the following discussion. To replace a polyhedron by a set of line segments so that their intersections with a plane are equivalent, the line segments must have certain properties. Definition. A set of line segments is said to be spanning a polyhedron, if the following conditions are satisfied: 1. Convexity Every line segment of the set is totally in or on the (convex hull of the) polyhedron. 5

2. Covering: For every (extreme) vertex of the polyhedron, there must be a line segment passing through it. 3. Inseparability There can not be a plane that separates the set into two, without intersecting with one or more line segments in the set. The first condition of convexity echoes Lemma 1. The other two conditions, covering and inseparability, are examined in turn. 2.1 Covering Let s be the cardinality of the SLS. In this section, the upper and the lower bounds of s are examined. Lemma 2. In a polyhedron with n vertices, there need be at most s = (n - 1) number of SLS. Proof. A polygon in the plane with n vertices needs (n - 1) edges to form a set of SLS. A polyhedron is a planar graph (recall condition 1 of the Definition) having at most n vertices on the boundary of the graph; hence the (n - 1) upperbound. a A corollary to Lemma 2 is that the upper bound in s is reached by taking the edges as the SLS. Diagonals which join vertices not connected by existing edges are also admissable as SLS. Let d be the number of diagonals. Figure 2 gives three exarmples: (a) n = 4, d = 0 s = 3; (b) n = 5, d = 1 s = 3; and (c) n = 6, d = 3 s = 3. For n = 4, all the SLS are edges. For n = 5, there involves one diagonal and two edges. For n = 6, s = d = 3. The last example in Figure 2(c) motivates a lower bound in s. INSERT FIGURE 4 Lemma 3. In a polyhedron with n vertices, n > 4, there are at least s = fn/21 number of SLS. 6

Proof. A tetrahedron admits no diagonal. Therefore, consider polyhedra for which n > 4 and d > O. Suppose a vertex in a polyhedron is connected by edges to k of the n vertices. There are (n - k) candidates for a diagonal, at each vertex. Choose any one and identify a pair of vertices. In a polyhedron with n vertices, there are n/2 such pairs when n is even, and + 1 when n is odd. Covering of the n vertices with [n/2] SLS is assured. * The proof for Lemma 3 suggests that the lower bound in the number of SLS may be reached if the construction takes the diagonals. It is useful to re-examine the case in which n = 4. The s = Fn/21 = 2 lower bound on a tetrahedron is shown in Figure 3(a). The two bold line segments of the tetrahedron are covering, satisfying condition 2 of the Definition, but not inseparable, violating condition 3. The inseparability of the SLS is next examined, with Figure 3(b) revisited for illustration of inseparability. 2.2 Inseparability The spatial relation between a polyhedron and an arbitrary plane can be such that there are zero, one, two or more vertices in the given plane. The configurations are illustrated in Figure 4, in which only two vertices of the polyhedron are shown, joined by an edge. All configurations involve intersection, except the one in Figure 4(b). Of particular interest is the configuration in Figure 3(a): the plane is said to separate the two vertices. Theorem 1. A plane intersects a polyhedron if and only if the plane intersects one or more of the SLS of the polyhedron. Proof. If a plane intersects a polyhedron, it must necessarily separate the vertices of the polyhedron. Since all vertices are connected by the SLS, by condition 2 of the Definition, the plane must intersect one or more of the SLS. Conversely, if a plane intersects an SLS, it must also intersect the polyhedron since, by condition 1 of the Definition, the SLS lies in the polyhedron.. While Figure 4 suggests a way for testing for the inseparability of the constructed 7

SLS, such tests are not practical. To wit, given a set of three-dimensional line segments (as candidate SLS), one needs to identify a plane such that it separates the set into two - without intersection. A two-dimensional version of separating a set of line segments by a line takes O(n log n) time. Separating three-dimensional line segments by a plane is expected to take longer. Instead, an implicit test for inseparability of a set of line segments is considered. Theorem 2. A set of line segments S is inseparable if and only if the convex hull of any subset S1 E S intersects the convex hull of the complement S - Si. Proof. If the convex hulls of the subset and the complement intersect then clearly the line segments do not admit a plane that separates them. On the other hand, if such a plane exists then the two cannot intersect. * The tetrahedron in Figure 3(b) illustrates Theorem 2, in which the set S consists of the two bold line segments. S1 is one of them, and S - S1 is the other. (Their convex hulls are themselves.) Since their convex hulls do not intersect, the set S must be separable. So that Theorem 2 is not interpreted an explicit test (of computing the convex hulls and the intersection of the convex hulls), vertices for the candidate SLS must be chosen such that there is an implicit intersection. 3 Algorithm The basic idea is to begin with a simple building block, with k vertices, for which its SLS is well-understood. Procedurally, k vertices are chosen from the given n; the SLS for the k vertices are constructed in constant time. A subsequent building block (also of k vertices) is then identified such that it shares one vertex with the previous building block - to ensure inseparability as prescribed by Theorem 2. This process 8

continues until all the n vertices are exhausted. Two kinds of building blocks will be examined leading to two algorithms: Penta for a precedure with five-vertex building blocks, and Hexa with six-vertex building blocks. The latter yields a smaller number of SLS then does the former. 3.1 Building Blocks First, consider k = 5 vertices to be in general positions, such that no four are coplanar. From the five vertices, a triangle and a line segment can be formed. As in Figure 5(a) or Figure 5(b), the line segment either does or does not intersect the triangle. Joining the two vertices (of the line segment) to the three vertices (of the triangle) gives a pentahedron, as in Figures 5(c) or (d). Three spanning line segments are then constructed as follows: first construct a diagonal to connect two vertices, shown dotted; then construct two additional line segments which are edges, shown in bold in Figures 5(e) and (f), to cover the three remaining vertices. Lemma 4. In a pentahedron with five vertices in general positions, a diagonal and two other edges constitute the SLS. Proof. The proof is by construction, as given in the previous paragraph.. Now, consider six vertices to be in general positions. They form two triangles. As illustrated in Figures 6(a), (b) and (c), the two triangles can be either disjoint or intersecting. Joining the three vertices of one triangle to the three vertices of the other triangle results in a triangulated hexahedron, as illustrated in Figures 6(d), (e) and (f). In the triangulated hexahedron, three diagonals may be constructed. They are shown, as dotted lines, in Figures 6(g), (h) and (i). It is to be noted that the 9

three diagonals, though inseparable, are not covering in all cases. The two vertices not covered by the diagonals are circled in Figure 6(i). (The three diagonals in Figures 6(g) and (h), on the other hand, are covering and inseparable.) Because the vertices are in general positions, the hexahedra are difficult to visualize. To aid the intuition, three "regular" hexahedra are given as examples in Figure 7: (a) "prism", (b) "wedge", and (c) "pyramid". These three hexahedra are further triangulated, as shown in Figures 7(d), (e) and (f), to reflect the general positions of the vertices. The three diagonals, in each of the cases, are shown dotted in Figures 8(g), (h) and (i). Revisiting Figure 6, one may correspond the three cases. For example, the "top" and the "bottom" of the prism in Figure 7(a) are the two disjoint triangles in Figure 6(a). The two vertices not covered in Figure 6(i) are correspondingly circled in Figure 7(i). Figure 8(j) summarizes the transformation of three diagonals (that are inseparable but not covering) to two diagonals and two edges, to be discussed next. To ensure that the constructed line segments are always spanning the six-vertex configuration leading to the non-convering case illustrated by Figure 6(c) is further examined. Figure 8(a) repeats Figure 6(i). The vertices that were not covered are first joined by a line segment. This results in an edge, as shown in Figure 8(b). The four line segments, three in Figure 8(a) and one in Figure 8(b), are still separable. Joining a newly covered vertex, by an edge, to another already convered vertex is illustrated in Figure 8(c). (Thus far, there are three diagonals and two edges.) Clearly, the vertices of the hexahedron are over-covered, as shown in Figure 8(d). Removing a diagonal eminating from an over-covered vertex results in the configuration of two diagonals and two edges, as shown in Figure 8(e). 10

INSERT FIGURE 7 The situations with the SLS in a hexahedron may now be summarized. Lemma 5. In a hexahedron with the six vertices in general positions, either three diagonals or two diagonals and two edges constitute the spanning line segments. The proof is again by construction as given in the previous two paragraphs. 3.2 Procedures and Analyses The development of the algorithm for constructing the SLS is now in order. Lemma 4 suggests the construction of taking five vertices and finding three SLS in the resulting pentahedron. To ensure that the subsequent sets of three SLS are inseparable from the rest, recalling Theorem 2, only four new vertices are chosen - to be combined with any one vertex that has been previously spanned. Procedure Penta 0. Given n vertices, choose any k = 5 and form a pentahedron from a triangle (three vertices) and a line segment (two vertices). 1. Construct three SLS, according to Lemma 4. 2. Of the remaining (n - k) vertices, 2.1 If (n - k) < 4, construct 3, 2, or 1 line segments and return. 2.2 Otherwise, choose any k = 4. 3. Combine the newly chosen four with any one vertex previously spanned and form a pentahedron. 4. Go to step 1. The number of SLS thus constructed is rather amenable to analysis. Lemma 6. Procedure Penta yields in the order of |n number of SLS in a polyhedron with n vertices. 11

Proof. In step 1 of Procedure Penta, five vertices yield three SLS, or 3. In step 2 and in the subsequent iterations, only four new vertices are fetched (to be combined with an old one) to yield three SLS, or 3. In the last iteration, when there are fewer than four vertices left, each vertex yields one SLS, or. Suppose the Procedure Penta terminates in p steps. The rates at which the vertices are transformed into SLS form a series: 3 3 3 3 - ++ + + + r +1 5 4 4 4 with (p - 2) terms of 3 in the middle. For n large, the (p - 2) terms dominate the first and the last terms; hence yielding |n in the number of SLS. * The development of Procedure Hexa is seen to be analogous, except for one difference. The case for which a hexahedral building block yields two diagonals and two edges, or s = 4, is to be avoided. The configuration of the two triangles, forrning a tetrahedron, as illustrated in Figure 6(c), is said to be mutually piercing. A hexahedron formed by two mutually piercing triangles yields 4 the first time and 4 in the subsequent iterations, while any other hexahedron yields 3 the first time and 3 subsequently, as shown in Figures 6(a) and (b). Procedure MutuallyPiercing 0. Given two triangles T1 and T2. 1. If an edge of T1 intersects T2 and an edge of T2 intersects T1 then return'IXue. Otherwise return False. Procedure Mutually-Piercing is clearly constant in time. And Procedure Hexa follows. Procedure Hexa 0. Given n vertices, choose any k = 6 and form two triangles. 1. If the two triangles are not mutuallypiercing then construct three SLS, according to Lemma 5. Otherwise, form two other triangles and repeat the step. 2. Of the remaining (n - k) vertices, 2.1 If (n - k) < 5, construct 4, 3, 2, or 1 line segments and return. 12

2.2 Otherwise, choose any k = 5. 3. Combine the newly chosen five, with any one vertex previously spanned, and form two triangles in a hexahedron. 4. Go to step 1. In a fashion similar to the proof of Lemma 6, it can be seen that Procedure Hexa produces SLS with the following rates: 3 3 33 - + -+. + - +16 5 5 5 Lemma 7. Procedure Hexa yields in the order of 5 in the number of SLS in a polyhedron with n vertices. 4 Generalization and Summary Recall that the goal is to construct fn/21 SLS in a polyhedron with n vertices. Procedure Penta yields 3n/4 or 75% of the number of vertices and Procedure Hexa yields 3n/5 or 60% of the number of vertices. It may be tempting to take seven vertices and hope that the result gives 3n/6 = n/2 number of SLS. Such, unfortunately, is not the case. A seven-vertex polyhedron and an eight-vertex polyhedron will yield, not three, but four SLS. (Imagine, for example, a cube with four diagonals.) Hence, a sevenvertex procedure - taking six additional ones at intermediate iterations - will yield in the order of 4n/6. Likewise, an eight-vertex procedure will yield in the order of 4n/7. The general picture is clear. Lemma 3 had predicted a lower bound of fn/21 in the number of SLS. While taking additionally more vertices will produce SLS at a rate 13

approaching the theoretical [n/21 bound, the procedure for doing so also becomes increasingly complex. Procedure Penta involves no testing of MutuallyPiercing as does Procedure Hexa. As k the number of vertices in a building block increases, there are combinatorially many more cases - to verify that the fk/21 line segments are indeed covering and inseparable. In view of this trend of "diminishing return", Procedures Penta and Hexa are offered. At the same time, the development of an algorithm for obtaining the minimal number of SLS is left as an open problem. 14

References [B65] Blum, H., "A Transormation for Extracting New Descriptors of Shape", Models for the Perceptions of Speech and Visual Form (Ed. Whaten-Dunn), MIT Press, Cambridge, MA, p. 362-380, 1967. [B78] Blum, H. and Nagel, R., "Shape Description using Weighted Symmetric Axis Features", Pattern Recognition, Vol. 10, pp. 167-180, 1978. [P85] Preparata, F. and Shamos, M., Computational Geometry, Springer Verlag, New York, 1985. [R93] Ratschek, H. and Rokne, J., "Test for Intersection Between Plane and Box", Computer Aided Design, Vol. 25, No. 4, April 1993, pp. 249-250. 15