A SIMPLE PRIMAL ALGORITHM FOR INTERSECTING 3-POLYHEDRA IN LINEAR TIME By Andrew K. Martin B.Sc.(Hons.) A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF T H E REQUIREMENTS FOR T H E D E G R E E OF M A S T E R OF SCIENCE in T H E FACULTY OF G R A D U A T E STUDIES COMPUTER SCIENCE We accept this thesis as conforming to the required standard T H E UNIVERSITY OF BRITISH COLUMBIA 1991 © Andrew K. Martin, 1991 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department The University of British Columbia Vancouver, Canada Date DE-6 (2/88) Abstract This thesis presents, in full, a simple linear time algorithm for intersecting two convex 3-polyhedra P and Q. This differs from the first such algorithm — due to Chazelle — in that it operates entirely in primal space, whereas Chazelle's algo-rithm relies heavily on duality transforms. We use the hierarchical representations of polyhedra due to Dobkin and Kirkpatrick to induce a cell complexes between coarse approximations, Pk and Pk of P satisfying Pk C P C Pk, and similar ap-proximations Qk and Qk of Q satisfying Qk Q Q Q Qk • We show that the structure of such complexes allows intersection queries to be answered efficiently. In particu-lar, the sequence of cells intersected by a ray can be identified in time proportional to the length of the sequence. The algorithm operates by recursively computing the intersections: Pk D Qk and Pk fl Qk. Then edges of the union of approximations P D Qk and Q D Pk are traversed by tracing their intersection with the two cell complexes. We show that each such edge can be traversed in constant time. In the process, most of the edges of P n Q which lie simultaneously on the boundary of P and Q will be traced. We show that the total time needed to construct those which remain is linear in the size of P and Q. Though based on the same general principles, the algorithm presented here is somewhat simpler than that described by Chazelle, which uses only the cell complexes induced by the inner hierarchical representations of P and Q. By ex-tending Chazelle's search structure to the space exterior to the given polyhedra, we avoid having to operate simultaneously in primal and dual spaces. This per-mits us to conceptualise the algorithm as traversing the edges of the boundary of (PDQk)ll(QnPk). As a side effect, we avoid one half of Chazelle's recursive calls, which leads to a modest improvement in the asymptotic constants. n Table of Contents List of Figures v 1 Introduction 1 2 Terms and Definitions ' 4 3 Polytope Sequences Viewed as Cell Complexes 6 3.1 Representation 8 3.2 Point Location and Ray Tracing 9 3.3 Steepest Descent 15 4 Hierarchical Representations 17 4.1 Inner Hierarchical Descriptions 19 4.2 Outer Hierarchical Descriptions 24 4.3 The Size of Pk and Pk 28 5 Computing PnQ 36 5.1 Facets of E 40 5.2 Tracing Edges of E . 41 5.3 Crossing Perforated Facets 45 5.4 An Edge Traversal Algorithm for E 46 5.5 Filling in the Gaps 47 5.6 Time Analysis 49 iii 6 Conclusions Bibliography List of Figures 3.1 A polytopal Cell Complex 7 3.2 Locating a point i in a cell complex 11 3.3 Tracing a ray outwards 13 4.4 An inner hierarchical description of a polytope P 18 4.5 An outer hierarchical description of a polytope P 18 5.6 A perforated facet of P U Q 37 5.7 Coplanar facets of P n Qk and Q fl Pk 38 v Acknowledgement 1 would like to acknowledge the tremendous amount help and support given to me by my supervisor, David K., without which this thesis surely would not have been written. David spent many, many hours discussing various details of this algorithm, and even more reading draft after draft as the thesis took shape. My thanks is extended also to the many graduate students and faculty of the UBC Computer Science Department, who have helped and encouraged me throughout this last year, and who put up with and even tried to listen to my endless ramblings about convex poly topes and cell complexes. Finally, I would like to thank my Fiance, Dawn, for her continued support and her faith that this thesis would someday be completed. vi Chapter 1 Introduction The main contribution of this thesis, is the development in full of a simple linear-time algorithm for computing the intersection of two three dimensional convex polytopes. In the process, cell complexes are described which abstract some of the properties of Dobkin and Kirkpatrick's hierarchical representations. The properties of such cell complexes are described for arbitrary dimensions, although their use is restricted to three dimensions in this thesis. As shown by Muller and Preparata[7], the problem of computing the intersection of two convex polytopes can be linearly reduced to that of computing a description of the intersection of their boundaries. Intuitively, such a description provides a pattern for 'sewing' together facets of the two polyhedra to form their intersection. Brute force ap-proaches to computing the boundary intersection which simply compute the intersection of each facet of one, with all facets of the other are, of course, doomed to take 0(n2) time, where n is any reasonable measure of the combined complexity of the two poly-topes. Muller and Preparata describe the first non-trivial algorithm for computing the intersection of two convex polyhedra. Their algorithm, which runs in 0(n log n) time, relies on the dual relationship between polytope intersection and convex union. Given two polytopes P and Q, the algorithm first identifies a point p in their intersection (or returns the empty set if none exists). Then, by applying an inversion transform[9] about p, P and Q are transformed into their duals, Ps and Qs respectively. The convex hull Z of Ps U Qs is then computed, and finally the dual of Z is computed to yield a description 1 Chapter 1. Introduction 2 of POQ. Since both inversion and intersection detection are accomplished in linear time the algorithm is dominated by the 0{n log n) cost of computing the convex union. Sub-sequently Hertel et al. [5] give a fundamentally different algorithm based on planar sweep to achieve the same upper bound. Yet another 0(n log n) algorithm follows by direct application of the hierarchical representations of 3-polyhedra introduced in Dobkin and Kirkpatrick[3] (and revisited in Chapter 3 of this thesis). While linear time solutions to the two-dimensional version of this problem (ie. in-tersecting convex polygons) have been known for some time[9], until Chazelle's re-cent result[2], linear time algorithms for intersecting 3-polyhedra have remained elu-sive. Chazelle's linear time algorithm uses both a truncated version of the hierarchical representations of Dobkin and Kirkpatrick, and the dual transforms used by Muller and Preparata. Even though the induced search structure which underlies Chazelle's algorithm has logarithmic depth, making a running time of ©(nlogn) seem unavoid-able, Chazelle uses an ingenious dove-tailed recursion to avoid using the entire structure thereby reducing the time taken to 0(n). The algorithm presented here was inspired by and bears considerable resemblance to Chazelle's algorithm. In particular Chazelle's observations that an inner hierarchical representation induces a cell complex suitable for ray tracing, and that a truncated version of this can be exploited in a recursive algorithm are fundamental to our algorithm as well. However, the two algorithms differ in several important respects. By extending Chazelle's search structure to the space exterior to the given polyhedra, we manage with only one half of Chazelle's recursive calls which leads to a simplification in the analysis of the algorithm and to a modest improvement in the asymptotic constants. We consider both the inner and the outer hierarchical representations simultaneously and view their union as a cell complex partitioning both the interior and the exterior of the given polytopes. Truncating the approximation sequences at a fixed depth (k) gives a Chapter 1. Introduction 3 cell-complex which is bounded by two coarse approximations to the original and in which ray-tracing can be performed in constant O(k) time. More specifically suppose P and Q are two convex polytopes with n and m edges respectively. To construct P fl Q we begin by building a search structure Cp on the space between two coarse approximations P/. and Pk satisfying P/. C P C PkA similar structure CQ is built between approximations Qk and Qk of Q. Recursively, Qk D Pk and Pk fl Qk are computed. The result of these recursive calls is then used to trace the edges of a carefully constructed approximation to P U Q through Cp and CQ taking 0(m + n) time in total. Chapter 2 provides definitions for the terms and symbols used throughout the paper. Chapters 3 and 4 develop a cell decomposition of the space within and outside of each polytope. This structure will allow us to trace the surface of one polytope through the structure induced by the other, thereby exploiting the structure of both to reduce the number of boundary intersections which need to be considered. Chapter 5 shows how to use these structures to achieve an 0(n) algorithm. Finally Chapter 6 compares our algorithm with that described by Chazelle. C h a p t e r 2 T e r m s a n d D e f i n i t i o n s We begin by defining some terms and symbols which will be used throughout this paper. Many of the definitions, and in particular the definitions of (oriented) hyperplanes, convex polyhedra, convex polytopes, faces, vertices, edges and facets are exactly as described in[3]. If a e $d - {0} and c <= ft then the set H(a,c) = {x <E ^d\(x,a) = c} (where (x,a) denotes the inner product of vectors x and a) is called a hyperplane in A hyperplane H(a,c) defines two closed half spaces, H+(a,c) = {x G $ld\(x,a) > c} and H~(a,c) = {x € $ld\(x,a) < c}. A (convex) polyhedron is defined as the intersection of a finite number of such closed half-spaces. Bounded polyhedra are known as polytopes. A polytope can be defined equivalently as the convex hull of a finite point set. If S is such a point-set set, we denote the convex hull of S by CH(S). If ri is a finite set of hyperplanes, we define the associated polyhedra V(J-C) = C\HenH+. We say that a hyperplane H supports a polytope P if P C H+ and H fl P ^ 0. We say a hyperplane H supports P at x when P C H+ and x £ P 0 H. If H supports P, then H fl P is called a face of P. Zero dimensional faces of are called vertices, one dimensional faces are called edges and d — 1-dimensional faces are called facets. The set of all vertices (resp. edges and facets) of a polytope P is denoted by V(P) (resp. E(P) and F(P)). The union of all the facets of P is called the boundary of P and is denoted by dP. P - dP is called the interior of P and denoted Int(P). Observe that the set V(P) is the smallest set of points S such that P — CH(S). Similarly, we use the notation 4 Chapter 2. Terms and Definitions 5 T>(P) to denote the smallest set of hyperplanes, ri satisfying P — V{^H). We call such a hyperplane a defining hyperplane, and observe that its intersection with P is a facet. We say two vertices, Vi and V2 are neighbours in P iff there is an edge, e £ E(P) such that e = C7i({vi,V2}). We say that they are independent if they are not neighbours. The neighbourhood Af(P; v) of a vertex, v is the set of all such neighbours. We say two defining hyperplanes hi and h2 are neighbours in P iff their common intersection with P is a d — 2 dimensional face. Defining hyperplanes are independent iff they are not neighbours. The neighbourhood AT(P; h) of a defining hyperplane h, is the set of all such neighbours. As polytopes are closed objects, the compliment of P , denoted P, specifically excludes the boundary of P . On occasion, it will be convenient to have a way to refer to the set of points on or beyond the boundary of P. Thus we denote P U dP by P. Since P U Q = (P D Q) U (P fl Q) U (P fl Q), the notions of faces, vertices, edges and facets can be extended in a natural way to the union of convex polytopes. In particular, d{P UQ) = (DP f)Q)U (dQ n P). Chapter 3 Polytope Sequences Viewed as Cel l Complexes Let S = Pi,..., Pa be an arbitrary sequence of polyhedra in such that, for 1 < i < a, P t + i C Pi. The connected components of P, — P,+i for each i, together with Pi and Pa, will be referred to as cells. 1 A cell complex C(S) arising in this way will be referred to as a polytopal cell complex. Such a complex is illustrated in Figure 3.1. We associate with each cell c a level C(C(S); c), such that C(C(S); c) = i iff c C P, - Pi+U £(£($); P\) = 0 and C(C(S); Pa) = ct. In cases where the polytope sequence S is clear from the context, we will omit the first argument, abbreviating the notation to C(c). Cells c such that £(c) > 0 and C(c) < a will be called proper cells to distinguish them from Pi and Pa. The concept of levels can be extended naturally to arbitrary points x £ $ld by defining £.(C(S); X) = C(C(S); c) where c is the unique cell which contains the point x. Lemma 3.1 If an arbitrary line penetrates a sequence of cells c\,... ,cn of a polytopal cell complex then the sequence of levels, C(ci),... C(cn) is unimodal. Proof: The polytopes which form the complex are convex, and hence each can be intersected by a line at most once. • We define |c|, the complexity of a level i cell c as the total number of faces of P, and P;+i which intersect its boundary. We say that c is simple iff its complexity is bounded by a predetermined constant p. We say that a polytopal cell complex is simple if all of ^his is somewhat of an abuse of the term used in various branches of topology, since the boundaries of our cells are partially open. 6 Chapter 3. Polytope Sequences Viewed as Cell Complexes 7 Figure 3.1: A polytopal Cell Complex its proper cells are simple. If the innermost (resp. outermost) polytope Pa of a simple polytopal cell complex is also simple, then we say that the complex is {-simple (resp. o-simple). A cell complex which is both i-simple and o-simple will be said to be t-simple. Throughout the remainder of this chapter, we assume that C(S) is an arbitrary simple polytopal cell complex. Moreover, throughout the rest of this thesis, we restrict the generality of the term "cell complex" to simple polytopal cell complexes just defined. Lemma 3.2 Suppose that H is a defining hyperplane of some Pj G <S* and i is the smallest integer such that H € T>(Pi). Then there is a unique cell C(H) such that P i . i n F cC(H). Proof: Let Xi and x2 be two points in Pi-\C\H+. We show that they are in the same cell. Clearly, x\X2 H P,- = 0 since both Xi and x2 lie in H+. On the other hand, X\X2 C jP,-_x since both x\ and x2 are in Since the line connecting them neither enters P, nor leaves P,_! we must conclude that they are in the same cell. • Chapter 3. Polytope Sequences Viewed as Cell Complexes 8 Lemma 3.3 If C(P\,..., Pa) is an arbitrary simple (resp. \-simple,o-simple,t-simple) cell complex, and H an arbitrary hyperplane, then the cell complex C(P\ fl H,..., Pa Pi H) is a simple (resp. i-simple, o-simple, t-simple) cell complex. Lemma 3.4 If C(P\,..., Pa) is an arbitrary simple cell complex and H is a defining hyperplane of some P, where i > 1, but is not a defining hyperplane of Pi, then the cell complex C(Pi fl H,..., Pa fl H) is a o-simple cell complex. Proof: The facet P, fl H must be simple since it bounds a simple cell. • 3.1 Representation Before proceeding to make claims about the cost of computing certain things with a polytopal cell complex, we must make explicit some assumptions about representation. We assume that the full facial graph is available for each polytope in the sequence, with each face being represented explicitly. For polytopes of three or less dimensions, this graph will be planar and hence can be represented in linear space using the doubly connected edge list representation of Muller and Preparata[7]. In this representation, edges are oriented and represented explicitly by data structures containing the names of the two vertices which terminate them, the two facets which they separate, and pointers to the next edges encountered when proceeding clockwise around their terminating vertices. We assume that cells are explicitly represented, or at least that a list of the faces of P, and P,+i which bound each level i cell can be constructed in constant (depending on p) time. We also assume that for each defining hyperplane H of each p , we have at hand, the unique cell C(H) whose existence was proved in Lemma 3.2. Moreover for each face Chapter 3. Polytope Sequences Viewed as Cell Complexes 9 / of each P t , we have a pointer to the highest dimensional face of P,+i which it contains (if one exists). If no such face of P , + i exists, then /'s representation includes a pointer to the representation of the level i cell which it bounds. Lemmas 3.3 discussed the cell complex which results from intersecting a cell complex C with a hyperplane H. While a representation of this complex is implicit in the repre-sentation of C, some cost may be incurred in extracting descriptions of its features. On the other hand a description of the cell complex arising in the more restricted situation discussed in Lemma 3.4 is explicitly present in the description of the original: Let / be a facet of some Pk G { P i , . . . , P a }, let /; = Pi Of for all k < i < a, and let j be the largest i such that f}; ^ 0. Let C* = C(fk,..., fj). Observe that each /,• for k < i < j is actually a face of P,, and thus a description of it is directly available from the description of P t. Each cell in C* is merely a cell of C which has been intersected by a hyperplane. Thus, a description of each cell of C* can be obtained in O(p) time from the description of the corresponding cell in C. In fact, all the information which we claimed to have at hand for C, is available for C* in O(p) time from the description of C. 3.2 Point Location and Ray Tracing Our primary interest in cell complexes, concerns the ease with which point-location and ray-tracing operations can be performed. We first define these operations. The problem of ray-tracing can be described as follows: Given a point x inside a known proper cell c and a direction vector v, compute the next cell c' entered by a ray r which emanates from p in the direction v. Since c has a constant sized description, it is a simple matter to compute the coordinates of the point x' at which the ray leaves c in 0{p) time. Thus, we lose no generality in assuming the the point x' on the boundary of c is also given. We say that r is emanating outwards if C(c') < C{c). Of course, if r is emanating outwards, x' will Chapter 3. Polytope Sequences Viewed as Cell Complexes 10 actually be a point in the cell c. We say that r is emanating inwards if C(c') > C(c). If r is emanating inwards, x' will be a point in the cell c' whose identity we are to determine. Unfortunately, in both cases knowing the face by which r leaves c does not immediately identify the new cell d which it enters. The problem of point-location is to identify the cell in a cell complex containing a point whose physical co-ordinates are known. For our purposes, it will suffice to consider this problem in the restricted case where cell complex is osimple. Lemma 3.5 If an algorithm exists to solve the point-location problem for any query point x in an arbitrary d — 1 dimensional o-simple cell complex C* in 0(C(C*; x)) time, then the identity of the next cell c' of an arbitrary d dimensional cell complex C(S) entered by an arbitrary ray r which emanates inwards from a point p in a known proper cell c of C(S)) can be computed in 0(C(C(S); c') — C(C(S); c)) time. Proof: Let i = C(C(S); c). Let / be the facet of P, bounding c by which r leaves. Since c has an O(p) sized description, we can identify / in O(p) time. Let x' be the point at which r touches / , let c' be the cell which contains x', and let j — C(C(S);c'). Let fk represent Pk fl / for all i < k < j, and observe that each fk is a face of Pk. The sequence ..., fj forms a d — 1 dimensional o-simple cell complex, the structure of which — including cell names—is explicitly described by the description of the original. Thus, we can appeal to the point-location algorithm to locate w in the d — 1 dimensional cell complex, C(/,+i,. . . , fj) in 0(j — i) time. • Lemma 3.6 If point location for all points x in an arbitrary d—1 dimensional o-simple cell complex C* can be accomplished in 0(C(C*;x)) time, then it can be accomplished for all points y in an arbitrary d dimensional o-simple cell complex C in 0(C(C;y)) time. Chapter 3. Polytope Sequences Viewed as Cell Complexes 11 Figure 3.2: Locating a point x in a cell complex Proof: Suppose that x is the point we wish to locate in a d-dimensional cell complex C — C(S). Let o be any point in Pa. Let r be a ray from o through x. Since Pi has a simple description, we can identify the co-ordinates of the point w at which r intersects the boundary of Pi, and the facet / of Pi which contains w in 0(p) time. This construction is illustrated in Figure 3.2. We now appeal to algorithm for computing point location in d — 1 dimensions to compute the cell in the o-simple C(Pi fl / , . . . , Pa H /) which contains w. Having identified the cell which contains w, we appeal to Lemmas 3.1 and 3.5 to trace the ray from w to x in the required time. • Theorem 3.7 It is possible to locate any point x in an arbitrary d dimensional o-simple cell complex, C, in 0(C(C; x)) time. Proof: We prove the theorem by induction on the dimension of the problem. In one Chapter 3. Polytope Sequences Viewed as Cell Complexes 12 dimension, a simple cell complex is just a set of intervals, and point-location in the required time is trivial. Suppose that the theorem is true for all problems of dimension less than d. Then Lemma 3.6 says that it is true for problems of dimension equal to d. • Theorem 3.8 The identity of the next cell c' of a cell complex C entered by a ray r which emanates inwards from a point p in a known proper cell c can be computed in 0(C(C;c')-C(C;c)) time. Proof: Follows directly from Theorem 3.7 and Lemma 3.5. • Having given upper bounds for the costs of doing point location in a o-simple cell complex, and tracing rays inwards in a simple cell complex, we now attend to tracing rays outwards. Algorithm 3.1 finds the next cell c' entered by a ray r which emanates Algorithm 3.1 Repeat c := C{H) Let D be the set of all hyperplanes G satisfying G 6 T>{Pc(c)), G fl c ^ 0, r C G~, and r fl G = x. If D ^ 0 then let H be any element of D. Endif Until D = 0 outwards from a cell c. Its operation is illustrated in Figure 3.3. Lemma 3.9 shows it to be efficient, and Lemma 3.10 shows it to be correct. Initially, we let x be the point on dc Chapter 3. Polytope Sequences Viewed as Cell Complexes Figure 3.3: Tracing a ray outwards Chapter 3. Polytope Sequences Viewed as Cell Complexes 14 by which r leaves. We initialise H to be any defining hyperplane of Pc(C) which bounds c and which r crosses by leaving c. More formally, we require: H G V(Pc(c)),r Q H~ and r n H = x. Such a hyperplane is guaranteed to exist, since r must cross some bounding hyperplane. After the algorithm terminates, c will identify the next cell entered by r. L e m m a 3.9 Suppose c, is the initial value of c. Then the algorithm terminates in 0(C(ci) — C(cr)) time, where cr is the final value of c. Proof: The algorithm terminates since £(c) is monotonically decreasing, and T)(P\) = 0. It terminates in the required time, since each step in the iteration requires only constant time. • L e m m a 3.10 When Algorithm 3.1 terminates, c will be the next cell entered by r. Proof: We first show that the algorithm does not 'miss' the appropriate cell. Suppose that D is not empty, and hence the algorithm continues for at least one more iteration. Let G be any element of D and observe that j — {x} C G+, but c C G+. Thus, c cannot be the next cell entered by r, and the algorithm correctly continues to iterate. Suppose on the other hand that D is empty. We must show that that c is the next cell entered by r. Let x = r fl H. Let v be a unit vector in the direction of r, so that points along r can be expressed as x +1v for non-negative scalars t. We say that a point x violates a defining hyperplane H of some polytope P C H+ if x e H+. We say that a ray r immediately violates such a hyperplane H if for all positive (non-zero) scalars s we have i + w G H+. We know that r C H~ for some H G V(Pc(c)+\), and that c is the unique cell C(H) such that Pc(c) H H+ Q c. Now, if a point is not in c, then it clearly must violate a defining hyperplane of Pc(c) which bounds c, or it must be inside Pc(c)+i- Since D is Chapter 3. Polytope Sequences Viewed as Cell Complexes 15 empty, we know that the ray does not immediately violate a defining hyperplane of Pc(c) which bounds c. Since r immediately crosses H entering H~, we must conclude that r immediately enters c. • Theorem 3.11 Suppose that C — C(Pi,..., Pa) is an arbitrary simple cell complex, and suppose that x is a point in Px f l Pa, or in an edge of Pa. Given the proper cell c of C or the edges of Pa containing x, the next cell c' of C entered by a ray r emanating from x can be computed in 0(|£(C;c') — £(C;x)\) time. Proof: The result is a direct consequence of Theorem 3.8 and Lemmas 3.9 and 3.10. • This result is the fundamental result of this section, providing a primitive operation used throughout the algorithm for computing P f l Q. If C = C(P\,..., Pa), we say that the region CN = Pi-K IJ e e<=E(Pa) is the navigable region of C. Observe that if / is a line segment, and x is a point in a connected component /' of / f l CN then the sequence of cells ci , . . . , ck intersected by /' can be computed in 0(max{£(C; Cj)} — min{£(C; Cj)}) time by repeated application of Theorem 3.11. 3.3 Steepest Descent We conclude this chapter by describing a procedure that we call "steepest descent," which enables us to find out whether a particular polytope in the sequence intersects a given hyperplane. Chapter 3. Polytope Sequences Viewed as Cell Complexes 16 Theorem 3.12 Suppose that C = C(S) is a simple cell complex and that H is a hyper-plane intersecting Pj. If the cell c containing a point x € Pjf\H has been identified, then one can decide whether a point in Pk fl H exists in 0(k — £(c)) time, returning such a point if it does. Proof: Let i = C(c). If i = k then we are done. Suppose that i < k. We first intersect c with H in constant time and consider H Pi c. If H does not intersect a portion of the boundary which belongs to dPi+i, then H fl c = H fl P,-, and thus H cannot intersect Pk. On the other hand, if H does intersect a portion of the boundary which belongs to dPi+i then we let x' be any point on the intersection, compute c' = C(x') in 0(C(c) — i) time, and apply the algorithm iteratively to c'. Now suppose that the algorithm iterates n times identifying a sequence cells c\,..., cn. Let Co = c be the cell given initially. The total time spent is thus given by YZ=i 0(C(cx) — £(c x _i), which reduces to 0(C(cn) — C(c)) as required. • Chapter 4 Hierarchical Representations We say that a sequence of polytopes P\,..., Pk in dtd is an inner hierarchical representa-tion of a polytope P iff 1. Pi=P 2. Pk is a ci-simplex 3. V(Pi+1)CV(Pt) 4. no two vertices in V(P,) — V(P,+i) are neighbours in P,. Similarly a sequence of polytopes, Pi , . . . , Pk n di.d is an outer hierarchical representation of a polytope P iff 1. Pi = P 2. Pt is a ti-simplex 3. X>(P,+i) C P(P.) 4. no two facets in P(P,) — P(P t +i) are neighbours in Pt. These constructions, which are illustrated in Figures 4.4 and 4.5 are precisely the hierarchical representations of Dobkin and Kirkpatrick[3]. In this chapter, we explore the difference between successive elements of such descriptions, with an eye towards identifying situations under which the resulting cell complexes are simple. We define 17 Figure 4.5: An outer hierarchical description of a polytope P Chapter 4. Hierarchical Representations 19 the cell associated with a vertex v of a polytope P as C(P]v) = P — CH(V(P) — v), and show that the cells associated with independent vertices are disjoint. Moreover, we show that if Pi and P,+i are successive elements in an inner hierarchical description, and S = V(Pi) - V(Pi+1), then then P, - Pi+1 = U e S C(Pn v). Similar results hold for outer hierarchical descriptions. We define the cell associated with a defining hyperplane h of a polytope P as C(P; h) = V(V(P) — h) — P. We show that cells associated with independent defining hyperplanes are disjoint, and that if Pi and Pi+i are successive elements in an outer hierarchical description, and S = T?(P,) —2?(PI+1) thenP, + 1 -P t = U esC(P,;/i). We also show that the complexity of a cell associated with a vertex or defining hy-perplane is functionally dependent (linearly when d < 3) on the size of that vertex's or hyperplane's neighbourhood. Thus, to form a simple cell complex, all that is required is that the neighbourhood of a vertex or defining hyperplane which appears in P,- and is absent from Pi+i be bounded by an appropriate constant. 4.1 Inner Hierarchical Descriptions This section examines the nature of cells in an inner hierarchical description. Towards this end, we let P be an arbitrary convex polytope and let v be one of its vertices. We begin by describing the cell, C(P; v). Let P' = Cri(V(P) - {v}); N = CH{AT{P; V) U {V}) and N' = CH{Af(P; v)). Lemma 4.1 Let P be a polytope and v one of its vertices. If H is a hyperplane such that v e H and M(P; v) C H+ then P C H+ Proof: Suppose H = H(a,c) and let G = G(a',c') be any hyperplane through v which supports P and minimises the angle 9 between the normal vectors a and a' . If 9 = 0, then G = H and H supports P as required. Chapter 4. Hierarchical Representations 20 Suppose that \6\ > 0. Since G minimises 0, there must be another vertex v' of P which lies on G fl H+. Moreover, the closest such vertex to v must be a neighbour of v, contradicting the assumption that Af(P;v) C H+. • L e m m a 4.2 Suppose P is a polytope and v is one of its vertices. If H is a hyperplane such that v e H~ and Af(P; v)) C H+ then V(P) - {v} C H+ Proof: Suppose that H = H(h,c). If v 6 H then Lemma 4.1 applies directly. If v H, then translate H to H' = H(h,c') so that v € H'. By Lemma 4.1 we know that V(P) C H'+. Let W be the set of vertices of P which lie in ~H+ n H'+. We shall show that W = {v}. Clearly, v G W. Suppose with an eye towards contradiction that w is another vertex in W. Let 6 be the maximum angle formed by the ray vw and the ray v + zh (z >= 0) for any w £ W, and consider the cone defined by all points x such that the angle between xv and v + zh equals 0. Observe that any hyperplane containing x and tangent to the cone supports P, and that any vertex w £ W is a neighbour of v by virtue of such a hyperplane containing w and v, and lying tangent to the cone. Of course, no such point w can be a neighbour of v since W C H+ and neighbours of P are constrained to lie in H+. Thus, no vertices of P can lie in H+ as required. • L e m m a 4.3 P = P' U N Proof: It should be clear that both P' and iV are subsets of P, and hence so is their union. Suppose that x is a point in P, but in neither P' nor N. There exists a hyperplane Hi such that x £ Hf, but P' C Hf. Similarly there exists a hyperplane, H2 such that x £ H% but N C H2 . Notice that v £ #+ since if it were, Hi would separate P from x. Thus, v G Hf fl H2 . Consider the hyperplane G through v and Hif\H2. Observe that it Chapter 4. Hierarchical Representations 21 separates x from v and N(P; v), and by Lemma 4.1 from P, contradicting the assertion that I E P . Thus, no such point x exists. • Theorem 4.4 C(P; v) = CH(Af(P; v) U {v}) - CH(Af(P; v)) Proof: From Lemma 4.3, we know that P — P' C N. From their definitions we know that N' C P'. Thus we conclude that P — P' C TV — N'. On the other hand let x be a point in N — N'. Since x N' there exists a hyperplane H such that x g" H+, and N' C H+. Since no hyperplane can separate x from V(N), we must have v ^ H+. We have thus established a situation, in which v € H~, and N(P\v) C H+. From Lemma 4.2 we conclude that V(P) — {v} C H+ and hence P' C H+. Since x £ H+, we must also conclude that x £ P' proving that N — N' C P'. Since N C P it follows that N — N' C P — P'. • Corollary 4.5 In 3c3, */|JV(P; u)| < « then \C(P;v)\ < 6(K + 1) Proof: The boundary of the resulting cell could be represented as a planar graph. Thus, the total number of facets cannot exceed six time the number of vertices. • Unlike cells in an arbitrary cell complex, those that arise from inner hierarchical representations are star shaped. Lemma 4.6 If x e C(P; v) then vx C C(P; v) Proof: Let x be any point in C(P;v). Since x £ P', there must exist a hyperplane H such that P' C H+, and x g H+. Since i g P w e must have v H+, otherwise H would Chapter 4. Hierarchical Representations 22 separate x from V(P). Since P is convex, and both x and v are in P, we can be sure that vx C P. On the other hand, since both v and x are not in H+, and P' C H+, we can be equally sure that vx D P' = 0. Thus, we can conclude that IJaf C C(P; v). • Up until now, we have examined the effect of removing a single vertex v from a convex polytope, and forming the convex hull of those which remain. We have shown that the resulting cell is star-shaped with all points visible from v, and that its complexity depends only on the size of u's neighbourhood. We now show that if two vertices are not neighbours, then the cells resulting from their removal are disjoint. Moreover the order in which they are removed in no way affects the resulting cells. Lemma 4.7 If x is a vertex of P such that x g" Af(P; v) and H is a hyperplane supporting P' at x then H supports P. Proof: Suppose that H does not support P. Then there must be a vertex of P which is not in H+. The only vertex of P which is not also a vertex of P' is v, so v €" H+. However, v $ Af(P; x), and thus we have x £ H and Af(P; x) C H+ and hence P C H+ by Lemma 4.1 • Throughout the remainder of this section, we let P be an arbitrary convex polytope, and v\ and u 2 be two distinct vertices of P. We let P\ — CH(V{P) — {vi} and P2 = CH{V{P) - {v2}). Theorem 4.8 Disjointness: If vx £ Af(P;v2) then C(P;vx) D C(P;v2) = 0 Proof: Suppose, with an eye towards contradiction, i is a point in the intersection of the two cells. Consider the ray r\ starting at v\ and proceeding through x. Such a ray must Chapter 4. Hierarchical Representations 23 penetrate a face fi of Pi, which is contained in a hyperplane Hi such that V(Pi) C H*. Similarly the ray r 2 starting at V2 and proceeding through x must penetrate a face $2 of P2 which is contained in a hyperplane H2 such that V(P2) Q H^-Let z be the point at which r2 penetrates and notice that V2 £ H*, x ^ H*, and hence z G- Hi . Since z lies on /2 , there must be a vertex of /2 which is not in Hi . Such a vertex must also be a vertex of P2, and the only possible such vertex is v\. So here we have a situation in which H2 does not support P since v2 & H*, H2 supports P2 at v\, and Vi £ V(P). From Lemma 4.7 we can conclude that Vi £ M(P; v2), contradicting the original premise. • Lemma 4.9 If vx ^M(P;v2) then Af(P; v2) =Af(Pi;v2). Proof: Suppose x £ Af(P;v2). Then there is a hyperplane H which supports P such that H n P = xuj. Now Px C P, so # n Pi C H fl P. The vertex vt g" M(P; v2) so x ^ U i , aTu2 C Pi, and H C\ Px = ~xv~2. On the other hand, suppose that x £ Af(Pi;v2). Then there is a hyperplane H supporting Pi such that H fl Pi = x~V2~. From Lemma 4.7 we know that H supports P. If vi £ then /f D V(P) = {vi,v2,x}, and there must be an edges between Vi and v2. If ui g" then H D P must remain unchanged. • Theorem 4.10 ^Af(P;v2) then C(Pi;v2) = C(P; u 2) Proof: Follows as a direct consequence of Theorem 4.4 and Lemma 4.9 • Chapter 4. Hierarchical Representations 24 Corollary 4.11 Suppose that R is an independent subset ofV(P) and P' — C7i(V(P) — R). Then P = P'U(U v € i ?C(P;u)). Consider now the inner hierarchical representation, Pi , . . . ,Pk of a polytope P. Let Si = V(Pi) — »y(P,+i) for 1 < i < k — 1. Moreover, suppose that the polytopes P 2 , . . . , Pfc are constructed so that if v € Si, then |A/"(P,;u)| < K for some predetermined constant K. From Theorem 4.8 and Corollary 4.11 we conclude that the cells C(P,-; v) for each v (E Si are the connected components of P, — P,+i. In ft3, if we choose p > 6K then C(Pi,..., Pk) forms a simple polytopal cell complex. Moreover, Corollary 4.5 assures us that a description of the cell associated with each vertex v £ Si is available in (9(«log K) time from the description of P,. Thus the cell complex is adequately represented by DCEL representations (described on page 8) of each polytope in the sequence. 4.2 Outer Hierarchical Descriptions In the previous section, we described the cell complex induced by an inner hierarchical description of a polytope. Here we develop a complimentary description of the cell com-plex induced by an outer hierarchical description. Recall that we define a polytope as the intersection of a finite number of closed half-spaces in Rd. If H is a set of hyperplanes in Rd, we define the polyhedra V(H) = C\heHh+. Of course there is a certain duality between the construction of inner and outer hierarchical representations. In particular, taking the geometric dual of the polytopes P\,... ,Pk in an inner hierarchical representation of P about a point in the interior of Pt yields an outer hierarchical representation Pf,..., P£ of Ps, the dual of P about the same point. Thus it should not be surprising that the results of Section 4.1 have analogues for the cell complexes arising from outer hierarchi-cal representations. However, one of the goals of this thesis is to avoid the use of dual transforms hence we develop separately the results for outer hierarchical representations. Chapter 4. Hierarchical Representations 25 When h is a hyperplane, we define the associated cell as C(P; h) = V(T>(P) — {h}) — P. Throughout the following section, we assume that P is an arbitrary convex polytope, h £ V(P), and that P' = V(V{P) - h). Lemma 4.12 Let g be a hyperplane in T>(P). Ifg £ -V(P; h) then g fl P = g fl P' hence gf]C(P;h) = 0 Proof: Observe that g fl P is a convex polytope in d — 1 dimensions. Since h and g are not neighbours, we know that h fl g D P is not a d — 2 face of P. Thus, hC\P £ T>(g fl P) and hence gC\P' = gC\ P. • Theorem 4.13 C(P; h) = r\xetf(P;h) x+nh+ Proof: Let W = OxeM'iP-yh) x + ^ h+. It follows directly from their definitions that C(P;h) C W. It remains to show that W C C(P;h). Let i be a point in w. Since x $ h+, we know that x £ P. Suppose with an eye towards contradiction that x £ P'. There must be some g £ V(P') such that x <7+. Since C(P;h) C W, there must be some point in C(P; h) which is in g+, thus #+ must partition C(P; h). But, according to Lemma 4.12, g cannot intersect C(P; h), thus establishing a contradiction and proving that x € P'. Since x g P and x £ P', we have also proven that x € C(P; /*) and hence W C C(P;/*). n Corollary 4.14 /n »/\Af(P; v)\ < K then \C(P; v)\ < 6(K + 1) Proof: The boundary of the resulting cell could be represented as a planar graph. Thus, the total number of faces cannot exceed six times the number of facets. • Chapter 4. Hierarchical Representations 26 Throughout the remainder of this section, we assume that P is an arbitrary convex polytope, that hi and hi are two distinct defining hyperplanes. We let Pi = V(T>(P) — {hi}) andP2=V(V(P)-{h2}). Theorem 4.15 C(P; hi) n C(P; h2) - 0 Proof: Let i be a point in C(P\hi). Theorem 4.13 says that x £ h+. On the other hand, C(P; h2) C P2 C hf, proving that the two cells are disjoint. • Theorem 4.16 If hi <£Af(P;h2) then C(Pi\h2) = C(P;h2) Proof: To prove the theorem we need only show that N(Pi\h2) = N(P;h2). For a hyperplane to be in such a neighbourhood, it must be a defining hyperplane. Since the defining hyperplanes if Pi and P differ only by the inclusion or omission of hi which is known not to be in the neighbourhood of h2, the possible candidates are the same. From Lemma 4.12 we know that h2C\ Pi = h2C\ P, so for any hyperplane x, it must follow that x n h2 n Pi = x n h2 n P. • Corollary 4.17 Suppose that R is an independent subset ofV(P) and P'—V(V(P) — R). ThenP = P'U(\JheRC(P;h). As with inner hierarchical descriptions, we now consider the outer hierarchical rep-resentation Pi, . . . , Pt of a polytope P, constructed so that the defining hyperplanes removed from successive polytopes have no more than K neighbours for some predeter-mined constant «. From Theorem 4.15 and Corollary 4.17 we conclude that the cells C((;P)i,h) where h £ T){Pi) - T>(Pi+i) are the connected components of P, - P,+i. Chapter 4. Hierarchical Representations 27 In if we choose p > 6K then the resulting cell will be simple. Thus the sequence Pk, Pk-i, • • • ,Pi forms a simple polytopal cell complex. Moreover, Theorem 4.15 assures us that a description of each cell c C P, — P,_i can be obtained from the description of P, in O(«log«;) time. Chazelle[2] was the first to observe that the inner hierarchical representation of a polytope P induces a spatial sub-division on its interior. In fact his polytope intersection algorithm relies heavily on the ability to trace rays efficiently in such a structure. Here we have extended this technique, by showing that both the inner and outer hierarchical representations result in such a structure. Suppose that P i , . . . , Px is an inner hierarchical representation of a polytope P, constructed so that Af(Pi) v) < K for all v € V(Pi) — V(Pi+i) Suppose further that P1,...,Py is an outer hierarchical representation of the same polytope P, constructed so that N(Pi\h) < K for all h 6 X>(P,) — Z>(P,+i). Let S = Py,..., P 2 , P, P 2 , . . . , Px and observe that C(S) is a ^ -simple polytopal cell complex, and thus inherits all the properties developed in Chapter 3. Kirkpatrick[6] provides a simple argument to show that such hierarchical descriptions can be constructed for arbitrary polyhedra with an appropriately chosen constant K, in 0(n) space and time, and that such descriptions have depth at most 0(log n) depth, where n is the number of edges in P. As discussed in the introduction, hierarchical descriptions with logarithmic depth immediately give rise to an 0(n log n) algorithm for computing 3-polyhedral intersection. To replace the log n term by a constant, we truncate the hierarchical descriptions, so that they contain at most k polytopes for some appropriately chosen constant k. Throughout the remainder of this thesis, we assume that such a polytopal cell complex has been constructed. We use the notation Pk and Pk to refer to the kth polytopes of the inner and outer hierarchical representations of P respectively. Chapter 4. Hierarchical Representations 28 4.3 The Size of Pk and Pk In this final section on hierarchical representations, we consider the question of how quickly the size of successive polytopes in a hierarchical description can be made to diminish. In particular we are interested in relating the combined size of Pk and Pk to the choice of k and K. Before embarking on such a discussion, it behooves us to define precisely what is meant by a polytope's "size". For polytopes in three dimensions or less, the incidence structure on the faces (edges, vertices and facets) can be described by a planar graph. Thus, Euler's formula / + v — e — 2 relates the number of vertices, edges and facets. If / > 2 and v > 2 then e > v and e > / . Thus, for the remainder of this paper, we shall use the number of edges as a measure of the size of a three-dimensional polytope. This metric has the advantage of being invariant under duality, and thus provides no bias towards either inner or outer hierarchical representations. Thus, we define \P\ = \E(P)\ for polytopes in three or less dimensions. Inner (resp. outer) hierarchical representations are build by removing successive sets of independent vertices (resp. defining hyperplanes) with bounded degree. The rate at which the size of the polytope diminishes is thus related to the size of the independent set of low degree vertices (resp. defining hyperplanes) that can be found. Kirkpatrick[6] gives a very straightforward argument which shows that an independent set of at least ^ vertices whose degree does not exceed 11 can be found in 0(n) time, where n is the original number of vertices. Algorithm 4.1, given by Edelsbrunner[4] improves this fraction. The algorithm is initialised with a list L of the vertices of P in non-decreasing order of degree. He leaves as an exercise the problem of showing that it finds an independent set of at least y vertices when K > 12. Chapter 4. Hierarchical Representations 29 Algorithm 4.1 Let J := 0 Let v be the first vertex in L. while deg{v) < K do if v is not marked then Set / := IU {v} Mark all vertices adjacent to v. endif; Set v to the next vertex in L endwhile. Edelsbrunner's result makes no assumptions about the sparsity of edges in the original polytope. Here we generalise his result to include some sensitivity to the ratio of facets to vertices, and hence the number of edges. We begin by defining some terms. • Let / = \L\. • Let Li = { D £ L\deg(v) — i} and let /,• = \L{\. • Let Ai = {v e I\deg(v) = i} and let a,- = \A{\. • Let In be U?=1 A. • Let c be the average degree of the vertices in L. • Let bi be the number of vertices in Li which have edges connecting them to vertices in • Let Xi be the number of edges connecting vertices in Ai to vertices of higher degree. • Let v, / , and e be the number of vertices (resp. faces, edges) on the polytope. • Let 0 = (f/v) + 1 Chapter 4. Hierarchical Representations 30 An immediate consequence of Euler's formula v + f — e = 2is that e < j3v (4.1) Since 2e represents the sum of the degrees of all the vertices of P, we can conclude that c < 2/3. (4.2) Lemma 4.18 £ ? = 1 > 0 Proof: For the purpose of discussion, we associate a direction with edges connecting vertices of unequal degree. We call the vertex of lower degree the tail, and the other the head. We can establish an upper bound on bn, the number of vertices of degree n with edges connecting them to accepted vertices of smaller degree. Each such vertex must be the head of an edge whose tail is an accepted vertex. The number bn of such vertices cannot exceed the number of such edges. Clearly there are at most Y^i=i x« s u c h edges available. Of these, however, at least Y%=i bi have heads of degree less than n. Thus, we can conclude that bn < £ Xi - £ bi (4.3) i=l t'=l We show by induction on n that any non-negative decreasing sequence of coefficients, z\,..., zn, satisfies the following equation: X X * . i - b i ) > 0 (4.4) t=i For a basis, observe that = 0 for i < 3. Assume that Equation 4.4 holds for n < (m —1). nt m—1 m X) *i(Xi ~ bi) = XI (*«• _ Zm){Xi - bi) + Zm J2(Xi ~ hi) «'=1 «=1 i=l m — 1 > (Z< ~ Zm){Xi - bi) + zmbm+1 (4.5) 1=1 Chapter 4. Hierarchical Representations 31 Now, the first term, Z ^ i * ^ — zm)(xi — 6.) is non-negative by our inductive hypoth-esis. The second term zmbm+i is non-negative since both factors are required to be non-negative. Thus, we can conclude that !>,•(*,•-6,-) >0 (4.6) Substituting j ~ for Z{ in equation 4.6 gives m i S T T T £ 0 ( 4 ' 7 » as required. • L e m m a 4.19 | / n | > £ ? = 1 £i Proof: The algorithm will reject a vertex only if it is connected to a vertex already accepted. Consider the /, — a, rejected vertices of degree i. Of these, 6, are rejected because there is an edge connecting them to a vertex in The remaining U — a; — 6; vertices are rejected because of edges connecting them to vertices in A{. There are za, edges incident upon vertices in A,-. However, x,- of them lead to vertices of higher degree. This leaves z'a, — x,- edges available to cause the rejection of a degree i vertices. Thus: /, — a, — b{ < icii — x, giving /,• + x,' - bi a,- > . + 1 (4.8) Now, combining Equation 4.8 and Lemma 4.18 we obtain 1 1 h i+l " /• n r—h-71 /• Chapter 4. Hierarchical Representations 32 as required. • Lemma 4.20 For any sequence of non-negative coefficients, z\,..., zn, and any positive real coefficients A x , . . . , Xn, the following inequality holds: Proof: We first observe the fact that for any positive real A; and Xj we have, Xf + X] Xi Xj Now > 2 (4.10) E ^ 2 = E ( ^ ) 2 + 2 i : E ZiZi (4.11) W=l / t=l t=l j=i+l and, n \ / n \ n n -1 n / \ )2 i / \ \2 E H (S>/A.-) = I>) 2 + E E ( A V A i ^ ( 4 - 1 2 ) <i=l I \i=l ) ,=1 ,=1 j=i+l [Ai)\Aj) Combining Equations 4.10, 4.11 and 4.12 yields the required result. • Lemma 4.21 1 |/| > l/(c+ 1) Proof: By definition, |7| = \IK\. From Lemma 4.19 we know that " I-\i\ > E — • From the definitions of c and /, we have c + i £ f = 1 ( i + !)/,•' (4-13) (4.14) 1Stated without proof as a "hint" to problem 9.9 in[4] Chapter 4. Hierarchical Representations 33 From Lemma 4.20 (when A; = i + 1) we have (E"=l Uf y _U__ ( 4 1 5 ) Combining equations 4.13, 4.14 and 4.15 gives | / | > - j - (4.16) c + 1 as required. • We now turn our attention to establishing a lower bound on \I\, which respects the ratio between the number of vertices, v, and the number of faces, / , on the given polytope by proving the following theorem: Lemma 4.22 If K > 12 then \I\ > ^ Proof: Recall that 3 = (f/v) + 1. The sum of the degrees of all vertices is given by 2e, and can be no less than cl + (K + l)(u — /). Combining with equation 4.1 and regrouping gives ; > (28 - K - l)t , — C — K — 1 which can be combined with Lemma 4.21 to yield (23 - K - l)v ( c - # c - l ) ( c + l ) Of course, we would like to be able to substitute 23 for c in the above equation, while preserving the inequality. Consider the expression as a function of x so that (2B-K-1)V J { } (X-K-1)(X + 1) Observe that the derivative of / with respect to x is given by Chapter 4. Hierarchical Representations 34 Recall from Equation 4.2 that c < 2/3. If we choose K , SO that K > 4/3 (K > 12 will suffice since 8 < 3) then the derivative is negative for x < c. As a result, we can be sure that /(c) > f(28), and hence as required. • Suppose we are given a polytope P with v vertices, / facets and e edges. Previously we defined 8 = (f/v) + 1. We can find and remove an independent set of low degree vertices of size at least j/f+T- The value of 8 is not known for the resulting polytope, but Euler's equation prohibits it from exceeding 3. Thus, at worst we will be able to remove k — 1 more sets each consisting of at least j of the remaining vertices. The result will be a polytope, Pk, such that '^'<-(^i)(ir Now, e = Bv, and \Pk\ < 2\V(Pk)\, so we can conclude that w < m ^ V ( w ^ ) (4-17) Similarly, we obtain an expression for the size of Ph, the polytope which is formed by removing k independent sets of defining hyperplanes. Let 8s = (vff) + 1. Then Adding equations 4.17 and 4.18 gives a bound on the combined size of Pk and Pk. To continue the simplification we first maximise the expression, 1 1 + 28 + 1 2B5 + l Chapter 4. Hierarchical Representations 35 To accomplish this, let a = f/v, and substitute a + 1 for 3, and (a 1 + 1) for 8s. After expansion, this gives 1 + 1 '(« + ^ ') + « ( 4.20) 28 + 1 28s + 1 6(a + a-1) + 13 Substituting a: = o: + a - 1 into equation 4.20 gives 1 + ^ = ^ - (4.21) 28 + 1 28s +1 6x + 13 For positive x, this is a strictly decreasing function, and is thus maximised when x is minimised. Of course, x is minimised when a = a - 1 = 1, giving x > 2, and hence 1 + ^ 7 7 < I (4-22) 28 + 1 28s + 1 ~ 5 Substituting equation 4.22 back into equation 4.19 yields \P*\ + \ P K \ < 6 \ P \ Q Q K ~ 1 . (4.23) The results of this chapter are summarised by the following theorem: Theorem 4.23 Given a (DCEL) representation of polytope P C ft3, it is possible to construct a sequence of nested polytopes S — Pk, Pk~x,..., P 2 , P, P 2 , . . . , Pfc so that C(S) is a simple polytopal cell complex with p < 72, and so that \Pk \ + \Pk\ < 6|P| (|) (f)* \ C h a p t e r 5 C o m p u t i n g P f\Q We now show how to use the cell complexes which are induced by the inner and outer hierarchical representations of two polytopes P and Q to compute their intersection. We assume that polytopes are represented in a (now standard) way using the doubly connected edge list (DCEL) representation described on page 8. To build a description of PPiQ, it will suffice to compute a description of the edges of dPDdQ, with appropriate pointers into the DCEL descriptions of P and Q, along with new pointers for truncated edges of P and Q. Thus, we add two new slots to the representation of an edge to accommodate these two new pointers. Suppose we were to begin by constructing inner and outer hierarchical representations of both P and Q, so that we have available descriptions of the -^simple cell complexes, C(PW,..., P, . . . , Px) and C(Qy,..., Q,..., Qz), with w (resp. x,y,z) large enough so that Pw (resp. Px,Qy,Qz) is a simplex. We call these the complete hierarchical representations of P. Approaches to computing P C\Q which attempt to traverse the boundary of either P or Q, while keeping track of their location in the cell complex induced by the complete hierarchical representations of the other seem doomed to produce 0(nlogn) algorithms at best. The problem is that the complete hierarchical representations have logarithmic depth, all of which might be used during the traversal. To avoid this difficulty, Chazelle limits the depth of his (inner) hierarchical representations to an appropriately chosen constant k. We adopt the same approach, by computing Cp = C(Ph,..., P, . . . , Pk) and Cq = C(Qk,..., Q,..., Qk). We then traverse the edges of the boundary, E, of the 36 Chapter 5. Computing P C\Q 37 Figure 5.6: A perforated facet of P U Q specially designed non-convex polytope, (Pk D Q) U (Qk Pi P). Observe that (Pk Pi Q) D (<5fc O P ) = P f l Q , and that any point on 3 P fl <9<3 lies on E . Note that the facets of E might not be simply connected since, as illustrated in Figure 5.6, facets of P may be perforated by facets of Q and vice versa. To traverse all the edges of E our algorithm will have to cross such perforated facets. There is an alternate dual construction involving the surface E 5 = d((P U Qk) H (Q U Pk)) which also appears to be easy to explore and yields a suitable approximation to P fl Q. E 5 might appear to yield the desired result more directly, since it is the boundary of the intersection of approximations to P and Q, whereas E is the boundary of the union of such approximations. However, E 5 has the draw-back that its composite approximations are non-convex and hence turn out to be somewhat tedious to describe. In light of this, we confine our attention to the surface, E . We begin by recursively computing Pk Pi Qk and Qk D Pk. In section 5.6 we show how the constant k can be chosen so that the overall recurrence remains linear. We then make use of the description of these intersections, and the cell complexes Cp = C(Pk,..., Pk) Chapter 5. Computing P fl Q 38 i P-<C--r-2>- Int(P) and Cq = C(Qk,..., Qk) to traverse the edges of E taking constant time per edge, thus taking 0(|.P| + \Q\) time in total. During the course of this traversal, most of dP f) dQ is explored. It may happen, however that some edges of dP D dQ intersect the interior of facets of E , and hence are not explored during the edge traversal. An example of such an edge arises when a facet g of Q is co-planar with a facet g' of Qk, and intersects a facet / of P which is not co-planar with a facet of Pk. In this event, which is illustrated in Figure 5.7, g f l / is an edge of Q fl P, but crosses the interior of (g' D P) U (g fl P) 1, a facet of E . As it turns out, the edge in this example cannot be traversed in constant time, and thus we would like to be able to delay its treatment until section 5.5. The following lemma says more formally that such an edge is not an edge of E and thus permits us to postpone its treatment: L e m m a 5.1 Suppose that f and g are facets of P and Q respectively, that f fl g is not Recall the notation P = P U dP. Chapter 5. Computing P fl Q 39 contained in an edge of f or g, and that there is no f € F(Pk) such that f C /' . If ff)g is an edge o/E, then there is no g' € F(Qk) such that g C g'. Proof: Suppose that such a g' exists. Let H be the hyperplane containing g and g'. Observe that a = g' fl P is a facet of A, and that b = g Pi Pk is a facet of B. Thus, H supports both A and B, and a U 6 is a facet of E. The line segment / fl g crosses the interior of 6 and hence the interior of a U 6 and hence cannot contain an edge of E. • Although it may seem unfortunate that an edge traversal of E may not cross all the edges of dP H dQ, section 5.5 shows how to use the cell complexes, the descriptions of Pk H Qk and QkC\Pk and information obtained during the edge-traversal of E to traverse those which remain. In fact, implementations need not delay traversing these edges at all. They are treated separately here only to simplify the analysis of the algorithm. To simplify the descriptions of the faces of E, we introduce the following notation: D e f i n i t i o n 5.1 Iff is a d-dimensional polytope, we let be the closure of the interior o / / H E , in dtd. In particular, if / is a two-dimensional polytope (say a facet of P), and / D E C df, then (/)s = 0, since Int(df) = 0 in R2. There are four problems which need to be addressed, before we can claim to have an algorithm for computing dP fl dQ. We must show that individual edges of E can be traversed in sufficiently little time. Since the facets of E need not be simply connected (some facets may be perforated), we must show how to navigate across such perfora-tions. We must be able to locate a starting point on an edge of E. Finally, we need to demonstrate that we can efficiently compute descriptions of all of the edges of dP fl dQ which are not edges of E. To provide a basis for attacking these problems, we begin by classifying and describing the facets of E. Then each problem is addressed in turn. Chapter 5. Computing P Pi Q 40 5.1 Facets of £ Let A = P n Qk and let B = Q D Facets of E are of one of the following three types. 1. facets of A restricted to lie in B 2. facets of B restricted to lie in A 3. The union of co-planar facets, one from A and one from B. Exploiting the obvious symmetry of £ in A and 5, we can ignore facets of type 2, which are obviously symmetric with type 1, and concentrate on facets of type 1 and type 3. Facets of A , of course, are either facets of P restricted to lie inside Qk, or they are facets of Qk restricted to lie inside P. Since they turn out to have somewhat different properties, we consider separately the facets of P which are co-planar with facets of Pk from those which are not. Thus we identify three kinds of facets of A which might contribute two-dimensional components to type 1 or type 3 facets of E . These are the portions of facets of Qk which lie in Pk, the portions of those facets of P which are co-planar with facets of Pk and lie in Qk, and the portions facets of P which are not co-planar with any facet of Pk and lie in Qk. The following three equations describe the portion of each which intersects £. Facets / 6 F(Qk): / n E = fnPnB = fr\Pn(QuPk) = fnp (5.24) Facets / 6 F(P) which are co-planar with a facet of Pk: / H E = ff)QknB Chapter 5. Computing P fl Q 41 = / n g f c n ( Q u P f c ) = fnQk (5.25) Facets / (E F(P) which are are not co-planar with a facet of Pk: / n s = fnQknB = fnQkn(QuPk) = (fnQknQ)u(fr\Qkr\Pk) (5.26) In the first two of these cases, / O E is simply a convex polytope. Thus, provided that / fl E is two dimensional, equations 5.24 and 5.25 accurately describe (/)E- The final case, described by Equation 5.26 requires further study. Observe that since / € F(P), f D Pk C df. Thus, int(/nE) = int((/ n Qk n Q) u (/ n Qk n Pk)) = int((/ n Qk n Q) u (df f)Qkn Pk)) = i n t ( / n g f c n Q ) (5.27) and (/)s consists of the two-dimensional components of (/ D Qk fl Q). Thus, equa-tions 5.24, 5.25 and 5.27 describe the portions of facets of A which contribute two di-mensional components of facets of E. 5.2 Tracing Edges of E We say an edge has been traced through a cell complex C if the sequence of cells which it intersects has been determined. It is our intention to show that given a starting point located in the navigable regions of Cp and Cq, any edge of E can be traced through Cp and Cq in 0(k) time by simulating a walk along the edge, while keeping track of our Chapter 5. Computing P C\Q 42 location in the two cell complexes simultaneously. In light of Theorem 3.11, there is no problem provided during the course of the walk, we remain in the navigable regions of Cp and Cq. Since P D Qk and Q fl Pk are both subsets of Ph and Qk the only way such a walk can leave the navigable regions is to enter Pk or Qk-Let e be an edge of £. If e fl Pk is confined to an edge of Pk we call the intersection trivial. Trivial intersections with Pk or Qk present no difficulty since they remain within the navigable regions of Cp and Cq. Through the following case analysis, it will be shown that any non-trivial intersection of an edge e with Pk (resp. Qk) lies on an edge of PkC\Qk (resp. Qk fl Pk), or on a simple facet of Pk (resp. Qk)- Moreover, the edge or simple facet on which it lies can be identified in 0(k) time. If e is an edge of E and e is contained in an edge of Pk, then e 0 Qk will clearly be an identifiable edge of Pk D Qk, and thus can be followed without difficulty since its description is available from the recursively computed description of Pk fl Qk- Similarly if e is contained in an edge of Qk then e can be followed through Pk-Let T = F(P) U F(Q) U F(Pk) U F(Qk). Edges of E are the intersection of two non-coplanar facets ( / I ) E and (f2)z, for some fi,f2 £ T. Let us classify edges, according the origin of the facets which give rise to them by defining E(Xi,X2) to be the set of edges of E satisfying e = ( / I ) E fl (f2)z for some / i £ F(X\) and f2 £ F(X2). Under such a classification scheme, there are 10 possible types of edges: E(P, P), E(P, Pk), E(P, Q), E(P, Qk), E(Pk, Pk), E(Pk, Q), E(Pk, Qk), E(Q, Q), E(Q, Qk) and E(Qk, Qk). Of course, E(Q,Qk) and E(P,Pk) do not require separate treatment since they are subsets of E(QkQk) and E(Pk, Pk) respectively. We can also exploit the symmetry of E in P and Q, and hence discuss only the following five types of edges: E(P, P), E(P, Q), E(P,Qk), E(Pk,Pk) and E(Pk,Qk). Chapter 5. Computing P PI Q 43 5.2.1 Edges i n E(P, Q) Let / be a facet of P, and g be a facet of Q. Let e = f Dg. Lemma 5.1 says that if (e)s is an edge of E, then either both / and g are co-planar with facets / ' and g' of Pk and Qk respectively, or neither are. If neither are, then both / and g must be simple, and hence point-location can be accomplished in both cell complexes in constant time over the entire edge. Suppose, on the other hand, that both / and g are co-planar with facets / ' and g' of Pk and Qk respectively. If e fl Pk is non trivial, then there exists /o 6 Pk such that / is coplanar with / 0 , and e D Pt C / 0 . Thus, e n Pk Q g' (~l /o, which is, of course, an edge of Pk fl Qh. Similarly if e fl Qk is non-empty, then there is a g0 6 E(Qk) such that e fl Qk = go H / ' , which is an edge of QkC\ Pk. In both cases, the problem remains of identifying (by name) the appropriate edge of Pk fl Qh or Qkf\ Pk- Suppose that we are following e and that it intersects Pfc. In this event, it crosses the boundary of /o, at an edge x which can be determined from the description of Cp. The edge of Pt fl Qk which we must identify, is one of the two edges bounding fo D Qk and incident upon x 0 Qk. 5.2.2 Edges i n E(P, P) Let f\ and / 2 be facets of P, and let e = fx D / 2 . Then e 6 E(P), and e D P^ is trivial. If (e)zC\Q is confined to the boundary of Q, then it is contained in the intersection of a facet of P with a facet of Q, and is subsumed by the discussion of E(P,Q) in section 5.2.1 above. Suppose, on the other hand that (e)s actually punctures <5's interior, and let e' = (e)^ fl Int(Q). We shall show, that e' is contained in an edge of Pk. Since e' is on E, it must be on the boundary of Pk. If it were interior to both Pk and Q then it would be interior to B and hence interior to A U B. Moreover, e' cannot intersect the interior of a facet of Pk. Suppose that e' did intersect the interior of a facet Chapter 5. Computing P D Q 44 g' of Pk. From Equation 5.24 we know that (<7')E = d' ^ Q- Since e' C Int(Q), we can conclude that e' intersects the interior of (g')z, contradicting the original supposition that e' is part of an edge of £. Thus, e' is on the boundary of P f c, but does not intersect the interior of a facet, and hence is confined to the edge of Pk, which contains e. 5.2.3 Edges in E(P, Qk) Let / be a facet of P, g' be a facet of Qk, and e = / fl g'. Clearly, e fl Pk is an edge of Pkf\Qk• Suppose e has a non-trivial intersection with Qk- Then there is a facet g € F(Q) which is co-planar with g', and e fl Qk Q g fl / , which has been discussed in section 5.2.1 above. 5.2.4 Edges in E(Pk, Pk) Let / / and f2' be facets of Pk. Let e = / / D /j'. Since e is an edge of E, its intersection with Pk must be trivial, and its intersection with Qk must be an edge of Qk fl Pk. 5.2.5 Edges in £(P f c , Qfc) Let / ' be a facet of Pk, g' be a facet of Qk, and let e = / ' fl g'. If e intersects Pt (resp. Qk), such an intersection is confined to the boundary of Pk (resp. Qk), and hence is contained in g' fl / 0 (resp. / fl g0) where / 0 (resp. g0) is the facet of Pk (resp. Qk) with which the edges intersects. Clearly g' D f0 (resp. / ' fl ^ r0) is an edge of Qk D Pk (resp. Pfen<9*). We have shown that it is possible to trace each type of edge through Cp and Cq in 0(k), provided the recursively computed descriptions of Pk fl Qk and Qk Pi Pk are available. Given a starting location on each connected component of the edges of E, this Chapter 5. Computing P fl Q 45 would immediately yield an 0G.PI + \Q\) algorithm for traversing all the edges. 5.3 Crossing Perforated Facets Since, some facets of E are not simply connected, a mechanism for traversing individual edges does not immediately lead to a mechanism for traversing entire facet boundaries. Lemma 5.2 The only facets o/E which are not simply connected are comprised of facets of P which are not co-planar with facets of Pk, or facets of Q which are not co-planar with facets of Qk. Proof: Facets of E which are comprised of the union of two facets of A and B will be edge-connected provided the constituent facets are. From our earlier analysis of facets of A (equations 5.24, 5.25 and 5.26) we can see that if / is a facet of Qk or a facet of P which is co-planar with a facet of Pk, then (/)s is a convex polytope, and hence must be edge-connected. • Consider a facet / of P which is not co-planar with any facet of Pk. Then (/)E = / fl Qk Pi Q. Of course / fl Qk is still convex and edge-connected. The disconnectedness of ( /)E arises from the exclusion of the interior of Q, effectively taking a bite out of the facet. Such a bite could partion the facet into several components. Provided that the boundaries of Q and / fl Qk intersect, however, the boundaries of each component will be connected. The more difficult problem arises when Q intersects only the interior of / D Qk. In this case (/)s is perforated by Q, and thus has two disconnected boundaries, namely d{f n Qk), and d(Q fl /). Given the location of a vertex v of d(Q fl (/)s) in Cq, we can discover the location of a point on the boundary of / D Qk in 0(k) time. To accomplish Chapter 5. Computing P fl Q 46 this, we simply start walking in a straight line on / away from Q, tracking our location in the two cell complexes. On the other hand if we have traversed the boundary of Qk fl / , and would like to decide whether Q intersects (/)s, locating a point in the boundary of the intersection if it does, we can rely on the "steepest descent" algorithm given in the proof of Theorem 3.12 to accomplish this in 0(k) time. 5.4 An Edge Traversal Algorithm for E All that remains is to find a starting point for the edge traversal of E. To accomplish this, we begin by constructing the complete inner hierarchical representations of P and Q taking 0(|P| -f \Q\) time. We can rely on the algorithm given in[3] (which uses these hierarchical representations) to provide a witness to the intersection of P and Q in O(log |P| + log |Q|) time. We then navigate through the cell complexes induced by the complete inner hierarchical descriptions of P and Q in any direction until we puncture a facet a of E. This will take at most 0(iog |P| + log \Q)) time. We then continue to navigate in any direction on a until we cross one of its edges. In total, this initialisation takes at most 0(|P| + \Q\) time. To traverse all the edges of E, we start with a located point on the boundary of one of E's facets / . From there, we traverse the edges bounding / , taking O(k) time per edge, and possibly O(k) time to search for a possible perforation of / . We then proceed to explore the facets adjacent to / in the same way. This algorithm takes constant (0(k)) time per edge (actually each edge will be ex-plored twice since it bounds two facets), plus an additional 0(k) time per facet to check for perforations. Thus, in total we take (e + f)O(k) time to complete the entire traversal where e and / are the number of edges and facets in E, plus 0(\P\ + \Q\) time to find a starting point. Of course there are at most 0(\P\ + \Q\) facets and at most 0(\P\ + \Q\) Chapter 5. Computing P C\Q 47 edges in E, so that in total, the entire traversal takes only 0(|-P| + \Q\) time since k is a fixed constant. 5.5 F i l l i n g i n the Gaps In the previous section, we have shown that the edges of E can be traversed in linear time. Of course the end goal is to traverse all of the edges of dP fl dQ. Unfortunately some of these edges may have been missed during the traversal of E, and will need to be dealt with separately. To identify these edges, we examine the treatment of each facet of P with an eye towards intersections with facets of Q which may have been overlooked. We first consider degenerate cases, in which co-planar facets of P and Q intersect. Suppose that / and g are co-planar facets of P and Q respectively, and that / n g ^ 0. In this case, we need to ensure that a description of the facet a = f fl g in F(P D Q) has been constructed. Once the intersection of / and g has been detected, constructing their intersection is easily accomplished by one of the known linear time polygon intersection algorithms such as[8]. Thus, the real problem is to ensure that all such intersections are detected. Let H be the hyperplane containing the two facets. If H separates P and Q, then <T = P C\ Q. This case can be identified at the outset, when a witness to the intersection of P and Q is computed. Suppose on the other hand that P and Q lie on the same side of H. If (without loss of generality) / C g, then locally, the boundary of P D Q is simply the boundary of P. Hence this situation need not even be detected. If neither is strictly interior to the other, then their boundaries will intersect at a vertex of E and hence this situation can be detected during the traversal of E. We now show that non-degenerate cases always involve facets of P and Q, at least one of which is co-planar with a facet of Pk or Qk respectively. Suppose / is a facet of P Chapter 5. Computing P fl Q 48 which is not co-planar with a facet of Pk. The portion of / which contributed to a facet of £ was given by (/)E = f fl Qk fl Q. If / is not co-planar with a facet of Q, and hence that intersections between / and dQ are one-dimensional in nature, we will have traced all intersections of / with dQ except for those which were co-incident with dQk. Thus, when looking for edges of dP fl dQ which are not edges of S, it suffices to examine only facets of P which are co-planar with facets of Pk and facets of Q which are co-planar with facets of Qk. Without any loss of generality, we shall confine our attention to facets of P. Let / be a facet of P which is coplanar with a facet / ' of Pk. Assume that / (and hence /') intersects Q, since if it does not, then there is no edge of dP D dQ to discover on / . Recall from Equation 5.25 that = f D Qk and from Equation 5.24 that (f'h = / ' n Q . Observe that /* = (/)E U (/')E is a facet of £. While tracing the edges of £ we have traversed the entire boundary of /*, while maintaining our location in Cq. As part of this process, any intersection of dQ with df, will have been discovered. Thus, if dQ intersects df, then for each sequence of edges of dP CI dQ inside / we will have identified the two points at which it intersects the boundary of / , and these points will be located in Cq. To trace the remainder of each of these edge sequences, we appeal to an algorithm for intersecting two convex polygons due to O'Rourke et al.[8] Let H be the hyperplane containing / and let g = HDQ. Observe that the edges we wish to traverse are the edges of g which lie inside (/)s- Our traversal of d(/)s has identified the points, dg fl d(f)z-It remains to traverse the edges of g inside (/)s which lie between pairs of such points, taking 0(\f\ + n) time in total, where n is the number of edges traversed. The algorithm of O'Rourke et al. accomplishes precisely this, but relies on explicit descriptions of both / and g. Unfortunately, we have an explicit description only of / and computing the required description of g would take an excessive amount of time. To Chapter 5. Computing P C\Q 49 perform the required reduction, we must show that any question which might be asked of g can be answered from its implicit description (H fl Q) in constant time. Conveniently, given a point on df C\ dg, the algorithm of O'Rourke et al. only requires a description of the portion of dg which actually intersects / . Since / is co-planar with / ' € F(Pk), we can compute the endpoints of such edges simply by tracing through Cq the intersection of relevant facets of Q with H. If we should enter Qk and hence leave the navigable region of Cq we can rely on the description of / ' fl Qk which must be available from the recursively obtained description of Pk fl Qk to guide us. The above discussion assumed that dQ actually intersects the boundary of / and thus that starting points were available. Suppose on the other hand that it does not. If it intersects / at all, dQ must intersect the hyperplane H containing / at points strictly interior to / . To detect this situation, we simply start from any known point on <9(/)s and perform a 'steepest descent' search (see Theorem 3.12) for dQ while remaining on the hyperplane containing / . Once this has been accomplished, we can use the Cq and the recursively obtained description of / ' D Qk to compute dQ fl H taking 0(k) time per edge (facet of Q) traced. 5.6 Time Analysis To analyse the time required by our algorithm as a function of the size of P and Q, we let T(|P|, \Q\) represent the running time. The algorithm proceeds by first computing the inner and outer hierarchical representations of P and Q, using at most 0(|P| + |0J) time. Then we make two recursive calls, requiring running time of T(\Pk\,\Qk\) and T(\Pk\,\Qh\) respectively. Finally, the intersection is computed using an additional ^(l-P| + time. Thus, the entire recurrence is expressed by r(m \Q\) = T(\Pk\, \Qk\) + T(\Pk\, \Qk\) + 0(\P\ + \Q\). Chapter 5. Computing P fl Q 50 To conclude that T(\P\, \Q\) = 0(\P\ + \Q\) we must choose k so that 1^1 + \Qk\ + \Pk\ + \Qk\ < S(\P\ + \Q\) (5.28) for some constant 8 < 1. It suffices, of course, to choose k such that \Pk\ + \Pk\ < 6\P\ and \Qk\ + \Qk\ < 6\Q\. Recall from Theorem 4.23 that + < (I) (I)*" ' Similarly, \Qk\ + \Qk\<Q\Q\(l) ( y ) * " 1 . Thus we need (12/5)(6/7)*-1 < 1, or (6/7) f c _ 1 < 5/12. Letting Jfe = 7 gives (6/7)*-1 < 0.4 < 5/12 as required. Chapter 6 Conclusions This thesis has described in detail a simple algorithm for computing the intersection of two three-dimensional convex polyhedra using 0(n) time and 0(n) space, where n is the combined number of edges in the polyhedra. In the process, we have fully exploited the structure of a polyhedral subdivision of ft3 induced by hierarchical representations of a given polytope. We expect that this induced cell complex will have other applications and hence have set out its properties separately in some detail. To intersect two polyhedra, we use inner and outer hierarchical representations of Dobkin and Kirkpatrick to build simple polyhedral cell complexes around each of their boundaries. This provides a mechanism for detecting intersections between the two boundaries while traversing the edges of one. To avoid logarithmic cost per edge tra-versed, and hence an 0(n log n) algorithm, we limit the depth of the cell complexes to a fixed constant k. This allows us to traverse each edge of the union of approximations to P and Q in constant (O(k)) time, using recursively obtained descriptions of Pk Pi Qk and QkC\Pk. In this way, the problem of intersecting P and Q is reduced to one of navigating in shallow cell complexes close to the boundaries of P and Q. The algorithm which has been presented bears considerable resemblance to that de-scribed by Chazelle[2]. Chazelle proceeds by identifying a point in P fl Q, and then computing the geometric duals Ps and Qs of P and Q about that point. One of the two polytopes is called the "anchor". Assume without loss of generality that it is P. He then 51 Chapter 6. Conclusions 52 triangulates the boundaries of P and P 5 , before computing their inner hierarchical repre-sentations for a sequence of at most k approximating polytopes. Recursively, he computes Pk PI Q and Pk fl Qs, being sure that Q is chosen as the anchor for the recursive calls. Once these preliminaries have been accomplished, the algorithm proceeds to traverse the boundary of P inside Q, and the boundary of Ps inside Qs in search of intersections with the boundary of Q (laces). To accomplish such a traversal, it is necessary to pass from a lace of P fl Q to a corresponding lace on P5 fl Q6. A considerable portion of his paper is devoted to the description of such a correspondence, and the corresponding algorithm for computing such a passage. The algorithm presented here represents a simplification largely because it operates entirely in primal space, avoiding these complexities. Our algorithm is not just a re-interpretation of Chazelle's however. To stay entirely in primal space it is necessary to have two different kinds of navigation: ray tracing, and 'steepest descent'. A second improvement over Chazelle's algorithm is a reduction in the number of recursive calls, and hence the linear constants. As described in his paper, Chazelle's algorithm gives rise to the following recurrence describing its running time where p and q represent the number of edges in P and Q respectively. T(p, q) = 4T(3(6/7)fcp, 3(6/7)fc9) + 0(p + q) To compare the two algorithms fairly, we must refine the analysis of Chazelle's slightly. In the above recurrence, the constant factor 3 in the expressions 3(6/7)fcp and 3(6/7)kq represents the worst case cost of triangulating the boundaries of P, Ps, Q and Q5. Of course, in reality this worst case cannot be exhibited both by triangulating P and by triangulating Ps. To capitalise on this observation we further remark that the running time is really dependent on the sum of p and q rather than on their independent values. The algorithm recursively computes four sub-problems: P£ fl Qsk, Pfi fl Qk, Pk H Qsk and Chapter 6. Conclusions 53 Pk H Qk- To run in 0(n) time, the size of the sub-problems must diminish so that \Pk \ + \Pl\ < <r\P\ and \Qk\ + \Qsk\ < cr\Q\ for some fixed positive a less than (1/2). Suppose that P is a polytope with v, e and / vertices, edges and facets respectively. Let a = e/v and let a5 = e/f. Observe that 1 -f ^ = 1 + \. Let P0 and P 0 5 be triangulated versions of P and Ps respectively. Let / ' and e' be the number of facets and edges of P0. Since PQ is triangulated, we have e' = | / ' . Combining with Euler's equation gives e' = 3v — 6 = ^ — 6. Similarly, we obtain complimentary results for the size of PQ. Combining gives Simplifying gives |i>0| + |*ol = 3e-6<3e. Thus, we can conclude that |PA ; | + |Pj£| < 3(6/7)fce. Letting k = 12 gives | P i 2 | + |P/ 2 | < 0.47|P|, guaranteeing a linear recurrence. On the other hand, our algorithm gives rise to the recurrence which avoids one half of Chazelle's recursive calls, and becomes linear when k > 7. r ( | P | , \Q\) = r ( | P f c | , \Qk\) + T(\Pk\, \Qk\) + 0(\P\ + \Q\) Bibliography [l] B. Chazelle and D. P. Dobkin. Intersection of convex objects in two and three di-mensions. Journal of the Association for Computing Machinery, 34(l):l-27, 1987. [2] Bernard Chazelle. An optimal algorithm for intersecting three-dimensional convex polyhedra. Technical report, Department of Computer Science, Princeton University, February 1989. [3] David P. Dobkin and David G. Kirkpatrick. Fast detection of polyhedral intersection. Theoretical Computer Science, 27:241-253, 1983. [4] H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer-Verlag, Heidel-berg, Germany, 1987. [5] S. Hertel, M . Mantyla, K. Mehlhorn, and J. Nievergelt. Space sweep solves intersec-tion of convex polyhedra. Acta Informatica, 21(5):501—519, 1984. [6] David Kirkpatrick. Optimal search in planar subdivisions. SIAM Journal on Com-puting, 12, No. 1, 1983. [7] D. E. Muller and F. P. Preparata. Finding the intersection of two convex polyhedra. Theoretical Computer Science, 7:217-236, 1978. [8] Joseph O'Rourke, Chi-Bin Chien, Thomas Olson, and David Nad dor. A new linear al-gorithm for intersecting convex polygons. Computer Graphics and Image Processing, 19:384-391, 1982. [9] Preparata and Shamos. Computational Geometry. Springer-Verlag, New York, 1985. 54
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- A simple primal algorithm for intersecting 3-polyhedra...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
A simple primal algorithm for intersecting 3-polyhedra in linear time Martin, Andrew K. 1991
pdf
Page Metadata
Item Metadata
Title | A simple primal algorithm for intersecting 3-polyhedra in linear time |
Creator |
Martin, Andrew K. |
Publisher | University of British Columbia |
Date Issued | 1991 |
Description | This thesis presents, in full, a simple linear time algorithm for intersecting two convex 3-polyhedra P and Q. This differs from the first such algorithm — due to Chazelle — in that it operates entirely in primal space, whereas Chazelle's algorithm relies heavily on duality transforms. We use the hierarchical representations of polyhedra due to Dobkin and Kirkpatrick to induce a cell complexes between coarse approximations, Pk and Pk of P satisfying Pk ⊆ P ⊆ Pk, and similar approximations Qk and Qk of Q satisfying Qk ⊆ Q ⊆ Qk . We show that the structure of such complexes allows intersection queries to be answered efficiently. In particular, the sequence of cells intersected by a ray can be identified in time proportional to the length of the sequence. The algorithm operates by recursively computing the intersections: Pk ∩ Qk and Pk ∩Qk. Then edges of the union of approximations P ∩ Qk and Q ∩ Pk are traversed by tracing their intersection with the two cell complexes. We show that each such edge can be traversed in constant time. In the process, most of the edges of P ∩ Q which lie simultaneously on the boundary of P and Q will be traced. We show that the total time needed to construct those which remain is linear in the size of P and Q. Though based on the same general principles, the algorithm presented here is somewhat simpler than that described by Chazelle, which uses only the cell complexes induced by the inner hierarchical representations of P and Q. By extending Chazelle's search structure to the space exterior to the given polyhedra, we avoid having to operate simultaneously in primal and dual spaces. This permits us to conceptualise the algorithm as traversing the edges of the boundary of (P∩Qk)⋃(Q∩Pk). As a side effect, we avoid one half of Chazelle's recursive calls, which leads to a modest improvement in the asymptotic constants. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-11-23 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0051967 |
URI | http://hdl.handle.net/2429/30114 |
Degree |
Master of Science - MSc |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-UBC_1991_A6_7 M38_5.pdf [ 3.72MB ]
- Metadata
- JSON: 831-1.0051967.json
- JSON-LD: 831-1.0051967-ld.json
- RDF/XML (Pretty): 831-1.0051967-rdf.xml
- RDF/JSON: 831-1.0051967-rdf.json
- Turtle: 831-1.0051967-turtle.txt
- N-Triples: 831-1.0051967-rdf-ntriples.txt
- Original Record: 831-1.0051967-source.json
- Full Text
- 831-1.0051967-fulltext.txt
- Citation
- 831-1.0051967.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0051967/manifest