Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

A convex hull algorithm optimal for point sets in even dimensions Seidel, Raimund 1981

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-UBC_1981_A6_7 S45.pdf [ 2.08MB ]
Metadata
JSON: 831-1.0051821.json
JSON-LD: 831-1.0051821-ld.json
RDF/XML (Pretty): 831-1.0051821-rdf.xml
RDF/JSON: 831-1.0051821-rdf.json
Turtle: 831-1.0051821-turtle.txt
N-Triples: 831-1.0051821-rdf-ntriples.txt
Original Record: 831-1.0051821-source.json
Full Text
831-1.0051821-fulltext.txt
Citation
831-1.0051821.ris

Full Text

A CONVEX HULL ALGORITHM OPTIMAL FOR POINT SETS IN EVEN DIMENSIONS THESIS SUBMITTED IN PARTIAL FULLFILLMENT THE REQUIREMENTS FOR THE DEGREE OF THE FACULTY OF GRADUATE STUDIES (Department o f Computer S c i e n c e ) We a c c e p t t h i s t h e s i s as c o n f o r m i n g t o the r e q u i r e d s t a n d a r d . THE UNIVERSITY OF BRITISH COLUMBIA September 1980 (c) Raimund S e i d e l , 1981 by RAIMUND SEIDEL MASTER OF SCIENCE i n I n p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t o f t h e r e q u i r e m e n t s f o r an advanced degree a t t h e U n i v e r s i t y o f B r i t i s h C o l u m b i a , I a g r e e t h a t t h e L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and s t u d y . I f u r t h e r agree t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y p u r p o s e s may be g r a n t e d by t h e head o f my department o r by h i s o r h e r r e p r e s e n t a t i v e s . I t i s u n d e r s t o o d t h a t c o p y i n g o r p u b l i c a t i o n o f t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l n o t be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . Department o f Co<**.p><A> 6 &r S&^e^c The U n i v e r s i t y o f B r i t i s h C o l u m b i a 2075 Wesbrook P l a c e V a n c ouver, Canada V6T 1W5 Date Sef^i /?<f/ ABSTRACT F i n d i n g the convex h u l l o f a f i n i t e s e t o f p o i n t s i s i m p o r t a n t not o n l y f o r p r a c t i c a l a p p l i c a t i o n s b u t a l s o f o r t h e o r e t i c a l r e a s o n s : a number o f g e o m e t r i c a l p r o b l e m s , such as c o n s t r u c t i n g V o r o n o i diagrams or i n t e r s e c t i n g h y p e r s p h e r e s , can be reduced t o the convex h u l l p r oblem, and a f a s t convex h u l l a l g o r i t h m y i e l d s f a s t a l g o r i t h m s f o r t h e s e o t h e r p roblems. T h i s t h e s i s d e a l s w i t h the problem o f c o n s t r u c t i n g the convex h u l l o f a f i n i t e p o i n t s e t i n R . M a t h e m a t i c a l p r o p e r t i e s o f convex h u l l s are d e v e l o p e d , i n p a r t i c u l a r , t h e i r f a c i a l s t r u c t u r e , t h e i r r e p r e s e n t a t i o n , bounds on the number o f f a c e s , and the c oncept o f d u a l i t y . The main r e s u l t o f t h i s t h e s i s i s an O(nlogn + n^ d +''"^/ 2J) a l g o r i t h m f o r the c o n s t r u c t i o n o f the convex h u l l o f n p o i n t s i n R^. I t i s shown t h a t t h i s a l g o r i t h m i s w o r s t case o p t i m a l f o r even d £ 2 . i i i T a b l e o f C o n t e n t s 1. I n t r o d u c t i o n 1 2. Convex P o l y t opes 4 3. The I n t e r s e c t i o n o f a P o l y t o p e and a H a l f space 18 4. The Convex H u l l A l g o r i t h m 30 5. C o n c l u s i o n 38 R e f e r e n c e s 40 i v Acknowledgement " E i n h e r z l i c h e s Dankeschon" t o D a v i d K i r k p a t r i c k . I do not t h i n k I c o u l d f i n d a b e t t e r s u p e r v i s o r . I want thank A l a n Mackworth f o r h i s c o n s t a n t encouragement and f o r b e i n g a v e r y c a r e f u l second r e a d e r . Thanks a l s o t o my f e l l o w s t u d e n t s , e s p e c i a l l y J i m L i t t l e , f o r t h e i r p a t i e n c e . TO CHINU 1 I_. I n t r o d u c t i o n I n the young f i e l d o f c o m p u t a t i o n a l geometry the convex h u l l problem has been one o f the most s t u d i e d p r o b l e m s . S i m p l y s t a t e d , the i s s u e i s t o f i n d the s m a l l e s t convex s e t c o n t a i n i n g a g i v e n p o i n t s e t . The importance o f the convex h u l l problem i s t w o f o l d . F i r s t , i t has numerous a p p l i c a t i o n s i n e n g i n e e r i n g , p a t t e r n r e c o g n i t i o n , and o t h e r f i e l d s . Second, i t p l a y s a c e n t r a l r o l e i n c o m p u t a t i o n a l geometry, as a number o f o t h e r g e o m e t r i c p r o b l e m s , such as the c o n s t r u c t i o n o f V o r o n o i diagrams, the c o n s t r u c t i o n o f the u n i o n or i n t e r s e c t i o n o f s p h e r e s , and o t h e r problems, can be t r a n s f o r m e d or reduced t o the convex h u l l problem. As e a r l y as 1972 Graham [5] p r e s e n t e d an O(nlogn) convex h u l l a l g o r i t h m f o r p l a n a r p o i n t s e t s . S u b s e q u e n t l y s e v e r a l papers have been p u b l i s h e d a d d r e s s i n g d i f f e r e n t v a r i a n t s o f the problem. J a r v i s [8] deve l o p e d an a l g o r i t h m whose r u n n i n g time depends l i n e a r l y on the p r o d u c t o f the number o f i n p u t p o i n t s and the number o f p o i n t s found on the convex h u l l , P r e p a r a t a [12] d e s i g n e d an O(nlogn) r e a l time a l g o r i t h m , and B e n t l e y and Shamos [1] p r e s e n t e d a l i n e a r e x p e c t e d time a l g o r i t h m f o r s e t s o f n p o i n t s drawn from a d i s t r i b u t i o n f o r which the expected number o f p o i n t s on the h u l l i s O ( n ^ ) , p < l . Yao [15] t a c k l e d the c o m p l e x i t y o f the problem from the o t h e r s i d e and proved t h a t Q (nlogn) time i s n e c e s s a r y t o i d e n t i f y the v e r t i c e s o f the convex h u l l even i f t e s t s i n v o l v i n g q u a d r a t i c f u n c t i o n s o f the 2 i n p u t s a r e a l l o w e d . Thus the a l g o r i t h m s o f Graham and P r e p a r a t a are w o r s t case o p t i m a l . For p o i n t s e t s i n 3-space P r e p a r a t a and Hong [13] d e v e l o p e d an O(nlogn) a l g o r i t h m which i s based on t h e d i v i d e and conquer paradigm. T h i s a l g o r i t h m i s o f c o u r s e o p t i m a l by Yao's r e s u l t . Whereas the convex h u l l problem i n 2 and 3-space seems t o be f a i r l y w e l l u n d e r s t o o d , the s i t u a t i o n i s q u i t e d i f f e r e n t f o r convex h u l l s o f p o i n t s e t s i n d-space, d>3. The o n l y g e n e r a l a l g o r i t h m p u b l i s h e d i s the one by Chand and Kapur [ 4 ] , I t r e l i e s on the so c a l l e d g i f t wrapping p r i n c i p l e and uses l i n e a r time t o dete r m i n e each f a c e t o f the convex h u l l . As the convex h u l l o f n p o i n t s i n can have S f n ^ / ^ J ) f a c e t s [ 1 0 ] , t h i s i m p l i e s t h a t w o r s t case time c o m p l e x i t y o f t h i s a l g o r i t h m i s not b e t t e r than 0 ( n I ( d + 2 ) / 2 J ) . I n t h i s t h e s i s an i n c r e m e n t a l a l g o r i t h m f o r the c o n s t r u c t i o n o f the convex h u l l o f n p o i n t s i n d-space i s p r e s e n t e d which improves on the a l g o r i t h m o f Chand and Kapur. I t i s shown t h a t i t has wo r s t case time c o m p l e x i t y O(nlogn + n ^ ^ 1 ^ ^ ) and t h a t t h i s i s o p t i m a l f o r even d. S e c t i o n 2 o f t h i s t h e s i s d e a l s w i t h the b a s i c m a t h e m a t i c a l p r o p e r t i e s o f p o l y t o p e s . There i s a r i c h t h e o r y d e a l i n g w i t h p o l y t o p e s , but u n f o r t u n a t e l y i t seems t o have been i g n o r e d by computer s c i e n t i s t s . I n S e c t i o n 3 a method f o r the i n t e r s e c t i o n 3 o f a p o l y t o p e and a h a l f s p a c e i s developed on which the convex h u l l a l g o r i t h m p r e s e n t e d i n S e c t i o n 4 i s based. I n the l a s t s e c t i o n the r e s u l t s are d i s c u s s e d and some open problems are p r e s e n t e d . I n p a r t i c u l a r , i t i s noted t h a t the convex h u l l a l g o r i t h m o f t h i s t h e s i s y i e l d s an a l g o r i t h m f o r the c o n s t r u c t i o n o f V o r o n o i diagrams which i s o p t i m a l f o r p o i n t s e t s i n odd d i m e n s i o n s . 4 o I I . Convex P o l y t o p e s T h i s s e c t i o n c o v e r s the b a s i c d e f i n i t i o n s and p r o p e r t i e s o f m u l t i - d i m e n s i o n a l convex p o l y t o p e s . There i s an e x t e n s i v e t h e o r y and l i t e r a t u r e about these o b j e c t s . The d e f i n i t i o n s and p r o p e r t i e s g i v e n i n t h i s s e c t i o n r e p r e s e n t a bare minimum o f f a c t s p e r t i n e n t t o the c o n t e n t o f the subsequent s e c t i o n s . For a more complete t r e a t m e n t o f p o l y t o p e s and r e l a t e d s u b j e c t s the r e a der i s r e f e r r e d t o Gruenbaum's book [ 6 ] , I n the f o l l o w i n g we w i l l d e a l w i t h the d - d i m e n s i o n a l E u c l i d e a n space R , where d i s an a r b i t r a r y p o s i t i v e i n t e g e r . I t i s assumed t h a t the r e ader i s f a m i l i a r w i t h b a s i c n o t i o n s o f l i n e a r a l g e b r a such as subspace, d i m e n s i o n o f a subspace, s c a l a r p r o d u c t , o r t h o g o n a l i t y , e t c . F a m i l i a r i t y w i t h b a s i c t o p o l o g i c a l n o t i o n s such as open and c l o s e d s e t s i s a l s o assumed. For x , y e R , <x,y> w i l l denote the s c a l a r p r o d u c t o f x and y, and f o r a s e t S <= R , i n t S w i l l denote the i n t e r i o r o f S under the t o p o l o g y i n d u c e d by the E u c l i d e a n m e t r i c . D e f i n i t i o n 2.1: L e t a e R = ( a / 0 ) , and c e R. The s e t { x e R | <x,a> = c } i s c a l l e d a h y p e r p l a n e . The s e t {x e R | <x,a> £ c } i s c a l l e d a c l o s e d h a l f s p a c e . I t s h o u l d be c l e a r t h a t c l o s e d h a l f s p a c e c o u l d a l s o be 5 d e f i n e d u s i n g i n s t e a d o f and t h a t i t i s a c l o s e d s e t i n the t o p o l o g i c a l sense. D e f i n i t i o n 2.2: L e t a eR , l e t X be a l i n e a r subspace o f R , and l e t k, - l ^ k s d , be the d i m e n s i o n o f X. (By c o n v e n t i o n , l e t the empty s e t be a subspace o f d i m e n s i o n -1.) H = a+X = {a+x|x e x} cR i s c a l l e d a f l a t . The d i m e n s i o n o f H, d i m ( H ) , i s k. A f l a t o f d i m e n s i o n k i s a l s o c a l l e d a k - f l a t . Examples o f f l a t s a re p o i n t s ( 0 - f l a t ) , l i n e s ( 1 - f l a t ) , and h y p e r p l a n e s ( ( d - l ) - f l a t ) . D e f i n i t i o n 2.3: L e t S cR . The a f f i n e h u l l o f S, a f f S, i s the i n t e r s e c t i o n o f a l l f l a t s c o n t a i n i n g S. I t easy t o prove t h a t the i n t e r s e c t i o n o f a f a m i l y o f f l a t s i s i t s e l f a f l a t . Thus the a f f i n e h u l l o f any s u b s e t o f R d i s a f l a t . For S cR a l e t dim S = d i m ( a f f S). D e f i n i t i o n 2.4^: A s e t S c R i s c a l l e d convex i f f f o r any x,y e S, seg(x,y) = { ( l - r ) x + r y | O ^ r ^ l } c S. Examples o f convex s e t s a re f l a t s and h a l f s p a c e s . Observe t h a t 6 the i n t e r s e c t i o n o f a f a m i l y o f convex s e t s i s a convex s e t . Furthermore the f o l l o w i n g h o l d s : Lemma 2.1: A c l o s e d convex s e t K <= R D i s the i n t e r s e c t i o n o f a l l c l o s e d h a l f s p a c e s c o n t a i n i n g K. P r o o f : [6] 2.2.3. Q.E.D. D e f i n i t i o n 2.5: (3 (3 Le t K c R be a convex s e t and H = {x e R |<a,x>=c} a h y p e r p l a n e . H i s c a l l e d a s u p p o r t i n g h y p e r p l a n e o f K i f e i t h e r i n f { < x , a > | x e K } = C or sup{<x,a>|x e K } = c. We s a y , a s u p p o r t i n g h y p e r p l a n e H o f K s e p a r a t e s K and a p o i n t p e R -K i f p i s not c o n t a i n e d i n the same h a l f s p a c e d e termined by H as K. D e f i n i t i o n 2.6^: L e t K be a convex su b s e t o f R^ and k=dim K. 1) F <= K i s c a l l e d a f a c e o f K i f e i t h e r F = K or F=0 or t h e r e e x i s t s a h y p e r p l a n e H s u p p o r t i n g K, such t h a t K n H=F. 2) A f a c e F w i t h dim F = m i s c a l l an m-face o f K . 3) A ( k - 1 ) - f a c e o f K i s c a l l e d a f a c e t o f K, a 0-face i s c a l l e d a v e r t e x , and a 1-face i s c a l l e d an edge o f K. 4) I f F i s an m-f ace o f K, G an (m + l ) - f a c e , and F c G , then we c a l l F a sub f a c e o f G and G a s u p e r f a c e o f F. 5) A f a c e F o f K i s c a l l e d p r o p e r , i f F^0 and F^K. 7 C l e a r l y , e v e r y f a c e o f a convex s e t i s convex. Furthermore the f o l l o w i n g h o l d s : Lemma 2.2: The i n t e r s e c t i o n o f a f a m i l y o f f a c e s o f a c l o s e d convex s e t K i s a f a c e o f K. P r o o f : [6] 2.4.10. Q.E.D. D e f i n i t i o n 2.7: The convex h u l l o f a s e t A c R ^ , conv A , i s the i n t e r s e c t i o n o f a l l c l o s e d convex s e t s c o n t a i n i n g A . I n view o f Lemma 2.1 an a l t e r n a t i v e d e f i n i t i o n o f conv A i s the i n t e r s e c t i o n o f a l l c l o s e d h a l f s p a c e s c o n t a i n i n g A . For e v e r y A conv A i s c l o s e d and convex. The f o l l o w i n g lemma g i v e s another e q u i v a l e n t d e f i n i t i o n f o r the convex h u l l . Lemma 2.3: L e t P be the convex h u l l o f a s e t A i n R ^ . 1) P c o m p r i s e s e x a c t l y a l l x e R which a re e x p r e s s i b l e i n the d d form x = 7 c.x. , where x . e A , c.^0, and J c . = 1. , i=o 1 1 1 1 i io. 1 2) I f A i s f i n i t e , A = {x^,...,x }, then the r e l a t i v e i n t e r i o r cl o f P c o m p r i s e s e x a c t l y a l l x e R which a re e x p r e s s i b l e i n the n n form x = £ c i x i ' where c^>0, and £ c ^ = !• 8 P r o o f : 1) [6] 2.3.3, 2.3.5. 2) [11] page 11. Q.E.D. D e f i n i t i o n ^ . 8 : A p o l y t o p e i s the convex h u l l o f a f i n i t e s e t o f p o i n t s . A p o l y t o p e P i s c a l l e d a d - p o l y t o p e i f f dim P = d. Lemma 2.4: E v e r y f a c e o f a p o l y t o p e i s a p o l y t o p e . P r o o f : Consequence o f [6] 3.1 .4 . Q.E.D. Lemma 2^5_: L e t P be a p o l y t o p e i n and dim P = d. 1) The number o f d i s t i n c t f a c e s o f P i s f i n i t e . 2) E v e r y ( d - 2 ) - f a c e o f P i s the i n t e r s e c t i o n o f e x a c t l y two f a c e t s . 3) E v e r y k-face o f P i s the i n t e r s e c t i o n o f a t l e a s t d-k f a c e t s o f P. P r o o f : [6] 2.6.3, 2.6 .4 , 3.1.6, 3.1.8. Q.E.D. For a p o l y t o p e P w i t h dim P = d, we denote the number o f i - f a c e s (which i s f i n i t e ) by f ^ P ) . By c o n v e n t i o n f _ 1 (P) =f^ (P) =1, and f i ( P ) = 0 f o r i < - l and i>d. 9 Lemma 2.6_i I f F i s a f a c e o f a p o l y t o p e P and G i s a f a c e o f the p o l y t o p e F, then G i s a l s o a f a c e o f P. P r o o f : [6] 3.1.5. Q.E.D. D e f i n i t i o n 2.9_i L e t P be a p o l y t o p e . The k - s k e l e t o n o f P, s k e l ^ P, i s the s e t o f a l l i - f a c e s o f P, O^i s k . Observe . t h a t the 1 - s k e l e t o n o f a p o l y t o p e can be i n t e r p r e t e d as a g r a p h , where the 0-faces a r e the v e r t i c e s and the 1-faces a r e the edges o f the graph. Of some importance i s the f o l l o w i n g : Lemma 2.7_i The graph r e p r e s e n t i n g the 1 - s k e l e t o n o f a d - p o l y t o p e i s d-connected. P r o o f : [6] 11.3.2. Q.E.D. D e f i n i t i o n 2.10: The f a c i a l graph o f a p o l y t o p e P, F G ( P ) , i s a d i r e c t e d graph whose nodes c o r r e s p o n d t o the f a c e s o f P. FG(P) has an a r c from the node c o r r e s p o n d i n g t o the f a c e F^ o f P t o the node c o r r e s p o n d i n g t o f a c e F 2 i f f F-^  i s a sub f a c e o f F 2 . D e f i n i t i o n 2.11: Two p o l y t o p e s a r e s a i d t o be c o m b i n a t o r i a l l y e q u i v a l e n t i f f t h e i r f a c i a l graphs a r e i s o m o r p h i c . 10 C l e a r l y the f a c i a l graph o f a d - p o l y t o p e P, F G ( P ) , i s an a c y c l i c graph w i t h one sour c e and one s i n k which has d+2 l e v e l s , i . e . a l l d i r e c t e d p a t h s from s o u r c e t o s i n k a r e o f l e n g t h d+1. Fu r t h e r m o r e , as i t i s shown below, the co n v e r s e o f FG(P) ( i . e . FG(P) w i t h the d i r e c t i o n o f a l l a r c s r e v e r s e d ) i s r e a l i z a b l e as * the f a c i a l graph o f some d - p o l y t o p e P . D e f i n i t i o n 2.12: * d . The p o l a r s e t A _ o f A c R i s d e f i n e d by A * = {yeR d|<x,y> £ 1 f o r a l l x e A } . Lemma 2.8^: L e t P be a d - p o l y t o p e and 0 e i n t P. * * * * 1) P i s a d - p o l y t o p e w i t h 0 e i n t P and (P ) = P. 2) I f F i s a k- f a c e o f P then F' = {yeP*|<x,y> = 1 f o r a l l x e F} * i s a ( d - k - l ) - f a c e o f P . 3) The mapping <(> d e f i n e d by (j>(F) = F' i s a 1-1 i n c l u s i o n r e v e r s i n g c orrespondence between the s e t o f f a c e s o f P and * the s e t o f f a c e s o f P . P r o o f : [6] 3.4. Q.E.D. D e f i n i t i o n 2.13: Le t P be a d - p o l y t o p e and 0 e i n t P. * P i s c a l l e d the d u a l o f P. 11 Lemma 2.8 i m p l i e s t h a t the f a c i a l graphs o f a p o l y t o p e and i t s d u a l a r e a n t i - i s o m o r p h i c . Observe t h a t i f v i s a v e r t e x o f P, w i t h 0 e i n t P, then {x e R |<x,v> = l } i s a s u p p o r t i n g h y p e r p l a n e * o f P and c o n t a i n s the f a c e t v' d u a l t o v. I n o t h e r words, i f 0 e i n t P, and V = {v^,...,v } i s the s e t o f v e r t i c e s o f P, then P = n i H ^ l s i s n } , where = { x e R |<x,v i> £ l } and each o f the n h y p e r p l a n e s {x e :Rd | <x,v^> = l } c o n t a i n s a f a c e t o f P*. I n the f o l l o w i n g we i n t r o d u c e some s p e c i a l p o l y t o p e s and s t a t e some o f t h e i r p r o p e r t i e s . D e f i n i t i o n 2.14: 1) A k - s i m p l e x i s a k - p o l y t o p e which i s the convex h u l l o f k+1 p o i n t s i n R , d^k. 2) P i s c a l l e d a s i m p l i c i a l p o l y t o p e , i f f a l l i t s p r o p e r f a c e s a re s i m p l i c e s . k+1 I t s h o u l d be noted t h a t a k - s i m p l e x has p r e c i s e l y i - f a c e s , and t h a t each i - f a c e i s an i - s i m p l e x i t s e l f . Futhermore, a s i m p l e x i s c o m b i n a t o r i a l l y e q u i v a l e n t t o i t s own d u a l . D e f i n i t i o n 2.15: L e t B be a ( d - 1 ) - p o l y t o p e . I f c i s a p o i n t i n R - a f f B, then P = conv(B u { c } ) i s c a l l e d a d-pyramid w i t h b a s i s B. 12 The f a c e s o f P s a t i s f y the f o l l o w i n g r e l a t i o n s h i p w i t h the f a c e s o f B. Lemma 2^53: L e t P be a d-pyramid w i t h b a s i s B and apex c, and l e t F be an i - f a c e o f B. 1) F i s a l s o an i - f a c e o f P and conv(F u { c } ) i s an ( i t l ) - f a c e o f P. 2) E v e r y i - f a c e o f P i s e i t h e r a l s o an i - f a c e o f B or i t i s o f the form conv(G u { c } ) , where G i s an ( i - l ) - f a c e o f B. P r o o f : [6] 4.2. Q.E.D. Us i n g Lemma 2.9, i t easy t o see how the f a c i a l graph o f a pyramid P w i t h b a s i s B and apex c can be e x p r e s s e d i n terms o f the f a c i a l graph o f B. FG(P) c o n s i s t s o f two c o p i e s o f FG(B). The nodes i n one copy c o r r e s p o n d t o the f a c e s o f P which a r e a l s o f a c e s o f B, the nodes i n the o t h e r copy c o r r e s p o n d t o the f a c e s o f P o f the form conv(G u { c } ) , where G i s a f a c e o f B. Each node i n the f i r s t copy c o r r e s p o n d i n g t o a f a c e F o f B has an a r c t o the node i n the second copy c o r r e s p o n d i n g t o the f a c e conv(F u { c } ) . Thus i n graph t h e o r e t i c terms, the u n d e r l y i n g graph o f FG(P) i s the p r o d u c t graph K 2 * FG(B). Observe, t h a t a d - s i m p l e x i s a d-pyramid whose b a s i s i s a ( d - 1 ) - s i m p l e x . Thus the u n d e r l y i n g graph o f the f a c i a l graph o f a d - s i m p l e x i s a (d + l ) - c u b e . (For the graph t h e o r e t i c terms see [7] .) 13 Of c o n s i d e r a b l e i n t e r e s t i s the f a m i l y o f c y c l i c p o l y t o p e s . D e f i n i t i o n 1.16; L e t be the moment c u r v e d e f i n e d by ^ ( t ) : = (t»t , . . . t ) , t e R. The d - p o l y t o p e formed by the convex h u l l o f any n>d d i s t i n c t p o i n t s on the moment c u r v e MLj i s c a l l e d a c y c l i c  p o l y t o p e C ( n , d ) . C y c l i c p o l y t o p e s a re s i m p l i c i a l ( [6] 4.7 ) , and t h e c o m b i n a t o r i a l t ype o f C ( n f d ) i s independent o f the c h o i c e o f the n p o i n t s on M^. That i s , any two d - d i m e n s i o n a l c y c l i c p o l y t o p e s on n v e r t i c e s a re c o m b i n a t o r i a l l y e q u i v a l e n t . The importance o f c y c l i c p o l y t o p e s l i e s i n t h e i r e x t r e m a l n a t u r e . Lemma 2.10: 1) I f P i s a d - p o l y t o p e on n v e r t i c e s , then f k ( p ) ^  f k ( C ( n , d ) ) f o r a l l k. 2) The number o f k - f a c e s o f a c y c l i c p o l y t o p e C(n,d) i s 0 ( n l - d / 2 - i ) . More s p e c i f i c a l l y , f o r 0sk<d f k ( C(n,2s) ) k-i+1 l f o r d=2s i=l s k+2 n - i - 1 i i+1 k-i+1 f k ( C ( n , 2 s + l ) ) ) ( f o r d=2s+l. i = l For k=d-l t h e s e e x p r e s s i o n s e v a l u a t e t o f o r d=2s f d _ l ( C ( n , d ) ) = 2 ( n f o r d=2s+l. P r o o f : 1) [10] , 2) [6] 9.6.1. Q . E . D . 14 The lemma above g i v e s a bound on the number o f f a c e s o f a d - p o l y t o p e on n v e r t i c e s . I t s h o u l d be noted t h a t , by d u a l i t y , the same bounds h o l d f o r the number o f v e r t i c e s o f p o l y t o p e s w i t h n f a c e t s . However; f o r the sake o f r e p r e s e n t a t i o n o f p o l y t o p e s , the s e t o f f a c e s i s r a t h e r u n i n t e r e s t i n g because i t does not e x p l i c i t l y e x p r e s s any o f the g e o m e t r i c o r c o m b i n a t o r i a l s t r u c t u r e o f a p o l y t o p e . The f a c i a l graph o f a p o l y t o p e c a r r i e s such i n f o r m a t i o n . Thus a bound on the s i z e o f a f a c i a l g r a p h , i . e . the number o f i t s nodes and a r c s , i s o f i n t e r e s t . L e t N(P) denote the number o f nodes i n the f a c i a l graph o f a p o l y t o p e P ( i . e . N(P) i s the number o f f a c e s o f P ) , l e t A(P) denote the number o f a r c s i n FG(P) ( i . e . the number o f f a c e - s u b f a c e p a i r s i n P ) , and l e t D(P) = A(P) + N ( P ) . We w i l l g i v e a bound on D(P) i n terms o f the number o f v e r t i c e s o f P i n two s t e p s . F i r s t i t w i l l be argued t h a t i t s u f f i c e s t o c o n s i d e r o n l y s i m p l i c i a l p o l y t o p e s . Second, we w i l l d e r i v e a bound f o r D ( P ) , where P i s a s i m p l i c i a l p o l y t o p e . Lemma 2.11; L e t P be a d - p o l y t o p e , V the s e t o f v e r t i c e s o f P, and v e V . By a p r o c e s s c a l l e d p u l l i n g , v e r t e x v- can be p e r t u r b e d s l i g h t l y t o v', such t h a t the d - p o l y t o p e P 1 = conv( (V-{v}) u{v'} ) has e x a c t l y the f o l l o w i n g k - f a c e s f o r 0£k<d: 15 ( i ) the k - f a c e s o f P which do not c o n t a i n v; r i k-1 k-1 ( i i ) the convex h u l l s o f the type c o n v ( ( v ' } u G ) f where G i s a ( k - 1 ) - f a c e not c o n t a i n i n g v o f a f a c e t o f P which does c o n t a i n v. P r o o f ; [6] 5.2.2. Q.E.D. Lemma 2.12; I f P i s o b t a i n e d from d - p o l y t o p e P by s u c c e s s i v e l y p u l l i n g each * o f the v e r t i c e s o f P, then P i s a s i m p l i c i a l d - p o l y t o p e s a t i s f y i n g 1) f 0 ( P * ) = f ( P ) a n d N(P*) £ N ( P ) , 2) A(P*) ^  A ( P ) . P r o o f ; 1) [6] 5.2.4 2) We o n l y need t o show t h a t p u l l i n g a v e r t e x v o f p o l y t o p e P t o v' t o y i e l d p o l y t o p e P' does not de c r e a s e the number o f f a c e - subface p a i r s . L e t F be a k-fa c e o f P and G a sub f a c e o f F f o r l^k<d. We w i l l show t h a t t h e r e i s a c o r r e s p o n d i n g p a i r o f f a c e s F' and G ' o f P', such t h a t G ' i s a sub f a c e o f F 1 . There a re t h r e e cases t o c o n s i d e r : ( i ) F and G do not c o n t a i n v: then F and G a r e a l s o f a c e s o f P 1 and G i s a su b f a c e o f F; ( i i ) F c o n t a i n s v, G does not c o n t a i n v: F i s not a f a c e o f P'; but G i s a f a c e o f P' and by 16 Lemma 2.11 in d u c e s a f a c e F' = conv(G u { v 1 } ) , and G i s a sub f a c e o f F *; ( i i i ) b o t h F and G c o n t a i n v: F and G must have r e s p e c t i v e s u b f a c e s F and G , such t h a t G i s a subface o f F and both F and G~ do not c o n t a i n v. By Lemma 2.11 F~ and G~ induce f a c e s F' = c o n v ( F ~ u { v ' } ) and G' = conv(G~ u{v'}) o f P 1 such t h a t G 1 i s a sub f a c e o f F' . Q . E . D . Lemma 2.13; For any d - p o l y t o p e P on n v e r t i c e s D(P) = O f n ^ ^ 2 ^ ) . P r o o f : * L e t P be a d - p o l y t o p e on n v e r t i c e s . By Lemma 2.12 D(P) £ D ( P ) f o r some s i m p l i c i a l d - p o l y t o p e P on n v e r t i c e s . As e v e r y f a c e t o f P* i s a ( d - 1 ) - s i m p l e x , c l e a r l y D(P*) < f d - 1 ( P * ) * D ( S d _ 1 ) , where S^ denotes a k - s i m p l e x . As i t was mentioned a f t e r Lemma 2.9, the u n d e r l y i n g graph o f FG(S k_-^) i s a k-cube and k k-1 t h e r e f o r e has 2 v e r t i c e s and k*2 edges. Thus D ( S d _ 1 ) = ( d + 2 ) * 2 d _ 1 . * F u r t h e r m o r e , by Lemma 2.10 f ^ _ ^ ( p ) ^ f d _ ^ ( C ( n , d ) ) . _ s For even d=2s, f d _ 1 ( C ( n f d ) ) = J L - ( n s S ) 1^ . By a r o u t i n e a p p l i c a t i o n o f S t i r l i n g ' s a p p r o x i m a t i o n f o r m u l a one can show t h a t D * S d - l * = ( S + 1 ) * 2 2 S = 0 ( s ! ) . Hence D(P) £ D(P*) < f d _ 1 ( C ( n , d ) ) * D ( S d _ 1 ) = 0 ( n S ) . 17 Using the same method, one can show that D(P) = 0(n S) f o r odd d=2s+l. Thus D(P) = 0(n L d/ 2-J ) f o r any d-polytope on n v e r t i c e s . Q.E.D. 18 I I I . The I n t e r s e c t i o n o f a P o l y t o p e and a H a l f s p a c e I n t h i s s e c t i o n we c o n s i d e r i n some d e t a i l the problem o f i n t e r s e c t i n g a p o l y t o p e and a h a l f s p a c e . The e f f i c i e n t c o n s t r u c t i o n o f such an i n t e r s e c t i o n w i l l be the main t o o l o f the convex h u l l a l g o r i t h m p r e s e n t e d i n the next s e c t i o n . We f o r m a l l y s t a t e the problem as f o l l o w s : G i v e n the f a c i a l graph o f a p o l y t o p e P, a h a l f s p a c e H, and a v e r t e x v o f P not c o n t a i n e d i n H f c o n s t r u c t the f a c i a l g r aph o f the p o l y t o p e P 1 = P o H. The main r e s u l t o f t h i s s e c t i o n a s s e r t s t h a t t h i s p r o b lem can be s o l v e d i n time p r o p o r t i o n a l t o the amount o f change from the f a c i a l graph o f P t o the f a c i a l g raph o f P'. Throughout t h i s s e c t i o n H denotes a c l o s e d h a l f s p a c e i n R d e f i n e d by the h y p e r p l a n e I , H~ denotes the o t h e r c l o s e d h a l f s p a c e d e f i n e d by I , i . e . H = (R - H) u I , and P i s a d - p o l y t o p e . D e f i n i t i o n _3.1: A f a c e F o f P i s c a l l e d a good f a c e w i t h r e s p e c t t o H, i f f F c H and F £ H~, a c u t f a c e w i t h r e s p e c t t o H, i f f F c H and F c H " ( i . e . F c I ) , a bad f a c e w i t h r e s p e c t t o H, i f f F <= H ~ and F 52! H, but no s u b f a c e o f F i s c o n t a i n e d i n I , 19 a t o u c h f a c e w i t h r e s p e c t t o H, i f f F c H~ and F $ H, and one s u b f a c e o f F i s c o n t a i n e d i n I , and a mixed f a c e w i t h r e s p e c t t o H, i f f F <£ H~ and F ^ f l . I n the f o l l o w i n g , when no c o n f u s i o n can a r i s e , the p h rase " w i t h r e s p e c t t o H" w i l l be o m i t t e d , and we w i l l j u s t t a l k about good f a c e s , bad f a c e s , e t c . Observe t h a t e v e r y nonempty f a c e o f P f a l l s i n e x a c t l y one o f the f i v e c a t e g o r i e s i m p l i e d by D e f i n i t i o n 3.1. F i g u r e 3.1 i l l u s t r a t e s t h e s e f i v e d i f f e r e n t t y p e s o f f a c e s f o r the case o f d=2. F i g u r e 3.1: The f i v e t y p e s o f f a c e s . 20 The f o l l o w i n g lemma g i v e s a c h a r a c t e r i z a t i o n o f the type o f a f a c e o f P i n terms o f the t y p e s o f i t s s u b f a c e s o r s u p e r f a c e s . Lemma _3.1: A f a c e F o f P i s ( i ) a good f a c e , i f f a l l i t s s u b f a c e s a re good or c u t f a c e s , ( i i ) a c u t f a c e , i f f a s u p e r f a c e o f F i s a t o u c h f a c e , ( i i i ) a bad f a c e , i f f a l l i t s s u b f a c e s a re bad or touch f a c e s , ( i v ) a touch f a c e , i f f a l l but one s u b f a c e s a re bad or touch f a c e s , (v) a mixed f a c e , i f f a s u b f a c e o f F i s mixed o r , w i t h the e x c e p t i o n o f a t l e a s t two, some s u b f a c e s o f F a r e bad or touch f a c e s . P r o o f ; F o l l o w s s t r a i g h t f o r w a r d l y from D e f i n i t i o n 3.1. Q.E.D. The next two lemmas g i v e a c h a r a c t e r i z a t i o n o f the f a c e s o f P' = H n P i n terms o f the f a c e s o f P, and a c h a r a c t e r i z a t i o n o f the f a c e - s u b f a c e p a i r s o f P 1 i n terms o f f a c e - s u b f a c e p a i r s o f P. Lemma 3.2: ( i ) I f F i s a good f a c e or a c u t f a c e o f P, then F i s a l s o a f a c e o f P'. ( i i ) I f F i s a mixed k-face o f P, the n F n H i s a k- f a c e o f P' and F n I i s a ( k - l ) - f a c e o f P'. 21 ( i i i ) I f F i s a bad f a c e or a touch f a c e o f P, then F i s not a f a c e o f P'. ( i v ) P o i n t s ( i ) and ( i i ) y i e l d a l l f a c e s o f P 1 . P r o o f : ( i ) and ( i i i ) a r e t r i v i a l . ( i i ) I f F i s a mixed k-face o f P, then t h e r e i s a s u p p o r t i n g h y p e r p l a n e X f such t h a t X n P = F. C e r t a i n l y , X n P n H = F n H f and X i s a s u p p o r t i n g h y p e r p l a n e o f P' = P n H. Observe t h a t G = P n I i s a f a c e t o f P'. F n I i s a sub f a c e o f P n H and F n I = (F n H) n G. Thus by Lemma 2.6 F n I i s a ( k - 1 ) - f a c e o f P'. ( i v ) T h i s f o l l o w s as a consequence o f Lemma 2.5 and the f a c t t h a t G = P n I i s the o n l y f a c e t o f P" which i s not c o n t a i n e d i n a f a c e t o f P. Lemma 3.3: L e t G be a f a c e o f P and F a subface o f G. ( i ) I f F i s a good f a c e or a c u t f a c e o f P and G i s a good f a c e or c u t f a c e o f P, then F i s a sub f a c e o f G on the p o l y t o p e P'. ( i i ) I f F i s good and G i s mixed, then F i s a sub f a c e o f G n H on P' . ( i i i ) I f G i s mixed, then G n I i s a sub f a c e o f G n H on P'. ( i v ) I f F and G are mixed, then F n H i s a su b f a c e o f G n H, 22 and F n I i s a sub f a c e o f G n I on P 1 . (v) I f G i s mixed and F i s a touch f a c e , t h e n F n I i s a subf a c e o f G n I on P'. ( v i ) P o i n t s ( i ) t o (v) y i e l d a l l f a c e - s u b f a c e p a i r s on P*. P r o o f ; ( i ) t o (v) f o l l o w s t r a i g h t f o r w a r d l y from D e f i n i t i o n 3.1 and Lemma 3.2. ( v i ) f o l l o w s from Lemma 3.2 and the f a c t t h a t a l l p o s s i b l e t y p e s o f f a c e - s u b f a c e p a i r s a re c o n s i d e r e d . Q.E.D. The p r e c e d i n g lemmas j u s t i f y the f o l l o w i n g a l g o r i t h m , which c o n s t r u c t s the f a c i a l graph o f P' from the f a c i a l graph o f P. We assume t h a t we are d e a l i n g w i t h a v e r s i o n o f the f a c i a l graph i n which e v e r y node c o r r e s p o n d i n g t o a v e r t e x has a s s o c i a t e d w i t h i t the c o o r d i n a t e s o f the v e r t e x . A l g o r i t h m I n t e r s e c t i o n o f a d - p o l y t o p e P and a h a l f s p a c e H. The a l g o r i t h m t a k e s as i n p u t the f a c i a l g raph o f P i n which a l l nodes c o r r e s p o n d i n g t o v e r t i c e s not i n H ( i . e . bad v e r t i c e s ) and t h e i r i n c i d e n t a r c s have been removed. F u r t h e r m o r e , the s e t o f bad eges o f P, BAD^, the s e t o f touch edges o f P, TOUCB^, and the s e t o f mixed edges o f P, MIXED., , a r e assumed t o be known. 23 For k = l , . . . , d BAD k, TOUCH k, and MIXED k s t a n d f o r the s e t o f bad, t o u c h , and mixed edges o f P r e s p e c t i v e l y . A t the b e g i n n i n g o f the a l g o r i t h m BAD k = TOUCH k = MIXED k = 0 f o r a l l k > l . For a f a c e F o f P, sub(F) denotes the s e t o f s u b f a c e s o f F ( i . e . the a r c s o f the f a c i a l graph p o i n t i n g t o the node c o r r e s p o n d i n g t o F ) , sup e r ( F ) denotes the s e t o f s u p e r f a c e s o f F ( i . e . the a r c s o f FG(P) l e a v i n g the node c o r r e s p o n d i n g t o F ) , T-sub(F) sta n d s f o r the s e t o f s u b f a c e s o f F which a r e touch f a c e s , and M-sub(F) s t a n d s f o r the s e t o f s u b f a c e s which a re mixed f a c e s . For a mixed f a c e F o f P, in d u c e d ( F ) denotes F n I , t h e "new" f a c e o f P' induced by F. I t i s assumed t h a t a t the b e g i n n i n g o f the a l g o r i t h m T-sub(F) := M-sub(F) := indu c e d ( F ) := 0 f o r a l l k - f a c e s w i t h k > l . For each edge F e MIXED-^, i t i s assumed t h a t a node c o r r e s p o n d i n g t o the v e r t e x v„ = F n I o f P* has been c r e a t e d , t h a t the c o o r d i n a t e s o f v_ have been computed, and t h a t i n d u c e d ( F ) = v„, v p e s u b ( F ) , super ( v p ) = { F } , s u b ( v p ) = { E } , and v p e super (E) , where E denotes the node c o r r e s p o n d i n g t o the empty f a c e . 24 b e g i n L := 0 f o r k = 2 t o d do b e g i n 1. Determine a l l bad, t o u c h , and mixed k - f a c e s f o r a l l F i n BAD k , do f o r each G i n s u p e r ( F ) do d e l e t e F from sub(G) i n s e r t G i n L d e l e t e F from the f a c i a l graph f o r a l l F i n TOUCH k_ 1 do f o r each G i n sup e r ( F ) do d e l e t e F from sub(G) i n s e r t F i n T-sub(G) i n s e r t G i n L f o r a l l F i n MIXED k_ 1 do f o r each G i n sup e r ( F ) do i n s e r t G i n MIXED, i n s e r t F i n M-subiG) f o r a l l F i n L do I f c a r d i n a l i t y ^ sub(F) ) = 0 then i n s e r t F i n BAD. I f c a r d i n a l i t y ( sub(F) ) = 1 then i n s e r t F i n TOUCH. I f c a r d i n a l i t y ( sub(F) ) > 1 then i n s e r t F i n MIXED? d e l e t e F from L 2. E s t a b l i s h t he new f a c e - s u b f a c e r e l a t i o n s h i p s and  c r e a t e the new f a c e s formed by the i n t e r s e c t i o n o f a mixed f a c e and I. f o r each F i n MIXED, do c r e a t e a ( k - 1 ) - f a c e G i n d u c e d ( F ) := G i n s e r t G i n su b ( F ) super(G) := {F} f o r a l l X i n M-sub(F) do i n s e r t induced(X) i n sub(G) i n s e r t G i n s u p e r ( i n d u c e d ( X ) ) f o r a l l X i n T-sub(F) do L e t Y be the o n l y element i n sub(X) (Y i s a c u t face ) i n s e r t Y i n sub(G) i n s e r t G i n super(Y) 3. Cleanup f o r each F i n MIXED. , do i n d u c e d ( F ) := M-sub(F) := T-sub(F) := 0 f o r each F i n TOUCH. _ 1 do L e t Y be the o n l y element i n su b ( F ) d e l e t e F from super(Y) d e l e t e F from the f a c i a l graph end (of the k-loop) 25 £. F i n a l Cleanup i f MIXED d ? 0 then (P n H i s a d - p o l y t o p e ) MIXED, c o n t a i n s e x a c t l y one element, the node c o r r e s p o n d i n g t o P. induced(P) := M-sub(P) := T-sub(P) := 0 i f TOUCH d 0 then (P n H i s a ( d - 1 ) - p o l y t o p e ) TOUCH, c o n t a i n s e x a c t l y one element, t h e node c o r r e s p o n d i n g t o P. P has e x a c t l y one f a c e t l e f t : the f a c e F = P n I . d e l e t e P from s u p e r ( F ) d e l e t e P from the f a c i a l graph end (of A l g o r i t h m 3.1). For a p o l y t o p e P and a h a l f s p a c e H, l e t D(P,H) denote the number o f bad f a c e s and touch f a c e s o f P w i t h r e s p e c t t o H p l u s the number o f a r c s o f the f a c i a l graph i n c i d e n t t o nodes c o r r e s p o n d i n g t o such f a c e s . F u r t h e r m o r e , l e t M(P,H) denote the number o f mixed f a c e s o f P p l u s the number o f a r c s between nodes c o r r e s p o n d i n g t o such f a c e s . Observe, t h a t D(P,H) i s the number o f nodes and a r c s d e l e t e d from the f a c i a l graph o f P. A l s o n o t e , the M(P,H) = 0 ( N ) , where N i s the s i z e o f the f a c i a l graph o f the f a c e t P n I o f P 1 . The f o l l o w i n g h o l d s : Lemma 3>*.1: A l g o r i t h m 3.1 c o r r e c t l y d e t e r m i n e s the f a c i a l graph o f P' = P n H i n time 0( D(P,H) + M(P,H) ). P r o o f : C o r r e c t n e s s f o l l o w s from Lemmas 3.1 t o 3.3. W i t h r e s p e c t t o the time bounds o b s e r v e t h e f o l l o w i n g . The a l g o r i t h m c o n s i d e r s o n l y nodes and a r c s which are e i t h e r d e l e t e d from the f a c i a l graph or 26 a r e r e l a t e d t o the i n s e r t i o n o f a new node or a r c . Only a c o n s t a n t amount o f time needs t o be spent on each o f t h e s e nodes and a r c s i f a p p r o p r i a t e p o i n t e r s t r u c t u r e s t o m a n i p u l a t e the v a r i o u s s e t s a re used. Q.E.D. A l g o r i t h m 3.1 assumes t h a t the nodes c o r r e s p o n d i n g t o bad v e r t i c e s o f P and t h e i r i n c i d e n t a r c s have been removed from the f a c i a l g r a p h . I t a l s o assumes t h a t the s e t s o f bad edges, t o u c h edges, and mixed edges a re known. The next lemma shows t h a t the subgraph o f s k e l ^ P induced by these v e r t i c e s and edges i s con n e c t e d . T h i s i m p l i e s t h a t i f o n l y one bad v e r t e x o f P i s known, a l l the v e r t i c e s and edges mentioned above can be found by a depth f i r s t s e a r c h , which t r a v e r s e s o n l y bad, t o u c h , and mixed edges o f P. Thus t h i s s e a r c h can be performed i n time p r o p o r t i o n a l t o the number o f t h e s e edges p l u s the number o f bad v e r t i c e s . Lemma 3.5_: L e t P be a d - p o l y t o p e and H a h a l f s p a c e as s p e c i f i e d a t the b e g i n n i n g o f t h i s s e c t i o n . The graph formed by the edges and v e r t i c e s o f P which a r e not c o n t a i n e d i n H i s co n n e c t e d . P r o o f ; L e t H" be (R d-H) u I . C l e a r l y P = P nH i s a d - p o l y t o p e and F = P n I i s a f a c e t o f P . The bad, t o u c h , and mixed edges o f P c o r r e s p o n d t o the 27 edges o f P which a re not c o n t a i n e d i n F. S i m i l a r l y , the bad v e r t i c e s o f P are the v e r t i c e s o f P~ not c o n t a i n e d i n F. Thus we o n l y need t o show t h a t the graph formed by the v e r t i c e s and edges o f the p o l y t o p e P which a re not c o n t a i n e d i n the f a c e t F i s c o n n e c t e d . But t h i s i s i m p l i e d by the f o l l o w i n g Lemma 3.6. Q.E.D. Lemma 3.6: L e t P be a d - p o l y t o p e , d > l , and l e t F be a f a c e t o f P. The graph formed by the v e r t i c e s and edges o f P which a re not c o n t a i n e d i n F i s c o n n e c t e d . P r o o f ; We have t o show t h a t f o r each p a i r v,w o f v e r t i c e s o f P not c o n t a i n e d i n F t h e r e i s a p a t h from v t o w c o n t a i n i n g no v e r t i c e s or edges o f F. I n d u c t i o n on the dimensio n d: ( i ) The statement i s o b v i o u s l y t r u e f o r d=2. The removal o f an edge from a p o l y g o n l e a v e s a c h a i n o f edges, ( i ) Assume the statement i s t r u e f o r e v e r y ( d - 1 ) - p o l y t o p e . We c o n s i d e r t h r e e c a s e s : a) v and w l i e both on a f a c e t G does not i n t e r s e c t F: There must be a p a t h from v t o w on G because by Lemma 2.7 the graph formed by s k e l 1 G i s ( d - 1 ) - c o n n e c t e d . b) v and w l i e both on a f a c e t G which i n t e r s e c t s F: The i n t e r s e c t i o n o f G an F must be c o n t a i n e d i n a f a c e t o f G. Hence t h e r e i s a p a t h from v t o w c o n t a i n i n g no edges 28 or v e r t i c e s o f F by the i n d u c t i v e a s s u m p t i o n , c) v and w l i e on d i f f e r e n t f a c e t s G and G' o f P: ^ Because the d u a l o f P i s a d - p o l y t o p e the graph formed by i t s i - s k e l e t o n i s d-connected. T h e r e f o r e t h e r e i s a sequence o f f a c e t s o f P, G ,...,G k, such t h a t G=G Q, G'=Gk, F i s not c o n t a i n e d i n the sequence, and f o r 0<i£k, G^ and G i - 1 s h a r e v e r t i c e s . Thus, by v i r t u e o f a) and b) one can compose a p a t h from v t o w c o n t a i n i n g o n l y v e r t i c e s and edges o f the f a c e t s G^ and not c o n t a i n i n g any v e r t e x o r edge o f F. Q.E.D. Theorem .3.1: G i v e n the f a c i a l graph o f a d - p o l y t o p e P, a c l o s e d h a l f s p a c e H d e f i n e d by the h y p e r p l a n e I , and a v e r t e x v o f P not c o n t a i n e d i n H, the f a c i a l graph o f the p o l y t o p e P' = Pifii H can be c o n s t r u c t e d i n time 0(D(P,H) + M(P,H)), where D(P,H) denotes the number o f nodes and edges d e l e t e d from F G ( P ) , and M(P,H) denotes the s i z e o f the f a c i a l graph o f the f a c e t o f P* which i s c o n t a i n e d i n I . P r o o f : As a consequence o f Lemma 3.5, a depth f i r s t s e a r c h s t a r t i n g a t v e r t e x v through the graph formed by s k e l ^ P can be used t o c o n d i t i o n the f a c i a l graph o f P t o s e r v e as an a p p r o p r i a t e i n p u t f o r A l g o r i t h m 3.1. F u r t h e r m o r e , the depth f i r s t s e a r c h a l s o y i e l d s the s e t s o f bad, t o u c h , and mixed edges o f P, so t h a t A l g o r i t h m 3.1 can be a p p l i e d t o render the f a c i a l graph o f P 1 . 29 The time n e c e s s a r y t o p e r f o r m the depth f i r s t s e a r c h i s p r o p o r t i o n a l t o the number o f bad, t o u c h , and mixed edges o f P. T h i s number i s c e r t a i n l y l e s s than D(P,H) + M(P,H). A l g o r i t h m 3.1 t a k e s time 0(D(P,H) + M(P,H)) by Lemma 3 . 4 . Q.E.D. 30 IV. The Convex H u l l A l g o r i t h m T h i s s e c t i o n c o n t a i n s the main r e s u l t o f t h i s t h e s i s : a g e n e r a l convex h u l l a l g o r i t h m which i s worst case o p t i m a l f o r p o i n t s e t s i n even d i m e n s i o n s . The main i d e a o f the a l g o r i t h m i s t o c o n s t r u c t the convex h u l l o f a p o i n t s e t i n c r e m e n t a l l y a f t e r t h e s e t has been p r e s o r t e d . B e f o r e we can d e s c r i b e any d e t a i l s o f the a l g o r i t h m , we have t o s e t t l e the i s s u e o f r e p r e s e n t a t i o n . By d e f i n i t i o n the convex h u l l o f a f i n i t e p o i n t s e t i s a p o l y t o p e . We w i l l r e p r e s e n t a p o l y t o p e P by an augmented v e r s i o n o f i t s f a c i a l graph F G ( P ) . The m o d i f i c a t i o n s o f FG(P) a r e as f o l l o w s : 1) Each node o f FG(P) which c o r r e s p o n d s t o a v e r t e x o f P has a s s o c i a t e d w i t h i t the c o o r d i n a t e s o f the v e r t e x . 2) Each node o f FG(P) which c o r r e s p o n d s to a f a c e t F o f P has a s s o c i a t e d w i t h i t a v e c t o r u„ which i s o r t h o g o n a l t o r F. As shown i n Lemma 2.13, the s i z e o f the augmented f a c i a l graph o f a d - p o l y t o p e P = conv S, where S c o n t a i n s n p o i n t s , i s 0(nL<V 2J). L e t us now t u r n our a t t e n t i o n t o the c o n c e p t o f d u a l i t y . R e c a l l , t h a t i f the d i r e c t i o n o f a l l a r c s o f a f a c i a l graph FG(P) a r e r e v e r s e d , the r e s u l t i n g graph i s the f a c i a l graph o f * some p o l y t o p e P , the d u a l o f P. We argue t h a t under c e r t a i n c o n d i t i o n s t h i s i s even t r u e f o r an augmented f a c i a l g r a p h . 31 Assume t h a t the i n t e r i o r o f a p o l y t o p e P c o n t a i n s the o r i g i n , and l e t F be a f a c e t o f P. By Lemma 2.8, the v e r t e x F* o f P d u a l t o F i s the s e t {y e P |<x,y> = 1 f o r a l l x e F } which c o n t a i n s j u s t one element, the v e c t o r u„ normal t o F which r i s s c a l e d and o r i e n t e d i n such a way t h a t <x,u.;,> = 1 f o r a l l x i n F, and <x,u p> £ 1 f o r a l l x i n P. We c a l l such a u p the n o r m a l i z e d complement o f F. I f i n the augmented f a c i a l graph o f a p o l y t o p e P w i t h 0 e i n t P the v e c t o r a s s o c i a t e d w i t h each node c o r r e s p o n d i n g t o a f a c e t F i s the n o r m a l i z e d complement o f F, then FG(P) w i t h i t s a r c s r e v e r s e d i s the augmented f a c i a l graph * o f P . I n o t h e r words, such a graph can be i n t e r p r e t e d i n two ways: as the augmented f a c i a l graph o f P, or as the augmented * f a c i a l graph o f P . How can we make use o f t h i s d u a l i t y i n a convex h u l l a l g o r i t h m ? We e x p l o i t d u a l i t y by r e d u c i n g the convex h u l l problem t o an i n t e r s e c t i o n problem. R e c a l l , t h a t by the d e f i n i t i o n o f p o l a r i t y and Lemma 2.8, i f P = conv V and 0 e i n t P, then P = r t{H v|v i n v}, where H v = {x eR |<x,v> * l } . I t f o l l o w s , t h a t f o r any qeR , (conv(Pu{q})) = (conv(Vu{q})) = * = (P n H ). As our r e p r e s e n t a t i o n o f p o l y t o p e s does not d i s t i n g u i s h between d u a l s , t h i s i m p l i e s t h a t the problem o f f i n d i n g the convex h u l l o f P u{q} can be reduced t o * the problem o f i n t e r s e c t i n g P w i t h the h a l f s p a c e H . I n the p r e v i o u s s e c t i o n we p r e s e n t e d an a l g o r i t h m which c o n s t r u c t s such an i n t e r s e c t i o n . However, t h i s a l g o r i t h m makes 32 ie ic ic the a s s u m p t i o n s , t h a t P n H / P , and t h a t a bad v e r t e x o f P , * * i . e . a v e r t e x o f P which i s not a v e r t e x o f P n H , i s known. In the f o l l o w i n g we show how t h e s e assumptions can be met i n an i n c r e m e n t a l convex h u l l a l g o r i t h m . D e f i n i t i o n £.1: L e t p,q e R , p = ( p X r . . . p d ) , q = ( q 1 / . . . q d ) . p i s s a i d t o be l e x i c o g r a p h i c a l l y s m a l l e r than q, p <T q, i f p l < q l ' o r i f p l = q l a n d (P2'-*'P a , ) *L ( q 2 " " q d ) * Observe, t h a t a s e t o f n p o i n t s i n R d can be s o r t e d i n t o l e x i c o g r a p h i c a l o r d e r i n time 9 ( n l o g n ) . The ne x t lemma draws a fundamental c o n n e c t i o n between l e x i c o g r a p h i c a l o r d e r and convex h u l l s . Lemma 4 _ . l : L e t S c R d be a f i n i t e s e t o f d i s t i n c t p o i n t s , l e t P = conv S, and l e t p be the maximum element o f S under the l e x i c o g r a p h i c a l o r d e r i n g . F u r t h e r m o r e , l e t q be a p o i n t i n R d w i t h p <r q, and L i l e t Q = conv(S u { q } ) . 1) p i s a v e r t e x o f P and qd P. 2) There i s a f a c e t o f P which c o n t a i n s p and which i s not a f a c e t o f Q. P r o o f : F i r s t note t h a t i t i s always p o s s i b l e t o r o t a t e t h e c o o r d i n a t e system such t h a t the l e x i c o g r a p h i c a l o r d e r i n g o f S u {q} i s 33 p r e s e r v e d but a l l the p o i n t s i n S u{q} d i f f e r i n t h e i r f i r s t c o o r d i n a t e . We assume t h a t such a r o t a t i o n has been a p p l i e d . We want t o make i t c l e a r however, t h a t t h i s assumption i s made o n l y f o r the sake o f s i m p l i c i t y o f the p r o o f . I n the a l g o r i t h m t o be p r e s e n t e d such a r o t a t i o n never need be performed. 1) L e t u = ( 1 , 0 , . . . , 0 ) . By our assumption a l l elements o f S d i f f e r e n t from p have a s t r i c t l y s m a l l e r f i r s t c o o r d i n a t e . Hence <x-p,u> < 0 f o r a l l x e S , x^p, and as a consequence o f Lemma 2.3, <x-p,u> < 0 f o r a l l x e p , x,*p. As <p-p,u> = 0, H = {x e R |<x-p,u> = 0} i s a s u p p o r t i n g h y p e r p l a n e o f P, P nH = {p}f and p i s a v e r t e x o f P. By assumption q has a s t r i c t l y g r e a t e r f i r s t c o o r d i n a t e than p. Thus <q-p,u> > 0 and t h e r e f o r e H s e p a r a t e s q from P, and q I P. 2) L e t A = { F 1 , . . . , F k } be the s e t o f f a c e t s o f P which c o n t a i n p. By Lemma 2.5 k£d. For i = l , . . . , k l e t a^ be a v e c t o r o r t h o g o n a l t o F., o r i e n t e d such t h a t <x-p,a.> £ 0 f o r a l l x 1 1 k i n P. Note, t h a t by d u a l i t y and Lemma 2.3 u = \ c.a., where i=l 1 1 c ^ O f o r a l l i . As p < L q and as t h e i r f i r s t c o o r d i n a t e a re assumed t o be d i f f e r e n t , <q-p,u> > 0. But k k <q-p,u> = <q-p, ][ c^a^> = £c.<q-p,a.>. As a l l c^ a r e non i=l i=l n e g a t i v e , <q-p,a^> > 0 f o r some j , l ^ j ^ k . But then c l e a r l y F j cannot be a f a c e t o f Q = conv(P u { q } ) . Q.E.D. 34 The f o l l o w i n g c o r o l l a r y i s the d u a l f o r m u l a t i o n o f Lemma 4.1. C o r o l l a r y 4.1: L e t S cR be a f i n i t e s e t o f d i s t i n c t p o i n t s , l e t P = conv S, and l e t 0 e i n t P. L e t p be the maximal element o f S under the d l e x i c o g r a p h i c a l o r d e r i n g and l e t q be a p o i n t i n R wi t h p <_ q. Li 1) The h y p e r p l a n e {x eR d|<x,p> = l } c o n t a i n s a f a c e t p' o f P*, and P* nH 4 P*, where H = {xeR d|<x,q> s l } . * 2) There i s a v e r t e x o f P c o n t a i n e d i n the f a c e t p' which i s * not a v e r t e x o f P n H . q P r o o f : F o l l o w s i m m e d i a t e l y from Lemma 4.1 and d u a l i t y . Q.E.D. We now have a l l the t o o l s needed t o s p e c i f y the a l g o r i t h m f o r the c o n s t r u c t i o n o f the convex h u l l o f a f i n i t e p o i n t s e t . A l g o r i t h m £.1: C o n s t r u c t i o n o f a d - d i m e n s i o n a l convex h u l l . The a l g o r i t h m t a k e s as i n p u t a s e t S c R o f n d i s t i n c t p o i n t s . I t o u t p u t s the augmented f a c i a l g raph o f conv S as i t i s s p e c i f i e d a t the b e g i n n i n g o f t h i s s e c t i o n . 1. S o r t S i n t o l e x i c o g r a p h i c a l o r d e r . Having s o r t e d S f we can w r i t e S = { s ^ , . . . , s }, where f o r l i i < n , s. < L s . + 1 . For l s j ^ n l e t S.. = { s e S|s < L s^}, l e t P.. = conv S ^  , and l e t P n +-^ = conv S = P. 2. C o n s t r u c t i o n o f an i n i t i a l ( d - 1 ) - p o l y t o p e . L e t k, d£k<n, be such t h a t dim S^ = d-1, - b u t dim 35 Sk+1 = d * d—1 Embed a f f S k i n R and i n d u c t i v e l y c o n s t r u c t the f a c i a l graph o f the ( d - 1 ) - p o l y t o p e P k = conv S^. (By c o n v e n t i o n l e t the f a c i a l graph o f the (- 1 ) - p o l y t o p e (the empty s e t ) be a graph c o n s i s t i n g o f one node.) By D e f i n i t i o n 2.15 P k + i = c o n v ( P ^ u ^ s k ^ * s a ^ ~ P y r a m i ^ w i t h b a s i s P k and apex s^. C o n s t r u c t the f a c i a l graph o f P k + ^ from FG(P k) as s p e c i f i e d a f t e r Lemma 2.9. T r a n s l a t e a l l p o i n t s o f S, such t h a t the o r i g i n i s c o n t a i n e d i n the i n t e r i o r o f P k + i ' (Lemma 2.3 c h a r a c t e r i z e s the i n t e r i o r p o i n t s o f a p o l y t o p e . ) A s s o c i a t e w i t h each node o f F G ( P k + ^ ) c o r r e s p o n d i n g t o a v e r t e x o f P^+i the c o o r d i n a t e s o f t h i s v e r t e x , and a s s o c i a t e w i t h each node o f F G ( P k + ^ ) c o r r e s p o n d i n g t o a f a c e t the the n o r m a l i z e d complement o f t h i s f a c e t . 3. I n s e r t the r e m a i n i n g p o i n t s . For i = k + l t o n+1 do C o n s t r u c t P^+i = c o n v ( P ^ u { s ^ } ) . As the o r i g i n i s c o n t a i n e d i n the i n t e r i o r o f P., t h i s * can be done by i n t e r s e c t i n g P^ and l H i = {x g R |<x,s i> £ l } . * * By C o r o l l a r y 4.1 P^ n f P ^ and one o f the v e r t i c e s o f * * P^ c o n t a i n e d i n the f a c e t o f P^ d u a l t o the v e r t e x * s i - l o f P i 1 S a k a d v e r t e x °f p i w i t h r e s p e c t t o . * I n t e r p r e t FG(P^) as the f a c i a l graph o f P^ and f i n d a * v e r t e x c o n t a i n e d i n the f a c e t s! , o f P. which i s not i - i I c o n t a i n e d i n H.. 36 A p p l y Theorem 3.1 t o c o n s t r u c t the augmented f a c i a l graph * * o f P^ +2 = P i n H i * B y d u a l i t y t h i s g raph can a l s o be i n t e r p r e t e d as the f a c i a l graph o f p^ +^» 4. Cleanup Undo the t r a n s l a t i o n o f s t e p 2 a p p l i e d t o the p o i n t s o f S. Theorem £.1^ L e t S <= R d be a s e t o f n d i s t i n c t p o i n t s w i t h dim S = d > 1. A l g o r i t h m 4.1 c o r r e c t l y d e t e r m i n e s the augmented f a c i a l graph o f conv S i n time 0(nL(<3+l)/2j^^ T h i s i s w o r s t c a s e o p t i m a l f o r even d. P r o o f : The c o r r e c t n e s s o f the a l g o r i t h m f o l l o w s from Theorem 3.1, d u a l i t y , and C o r o l l a r y 4.1. For the time bound c o n s i d e r the f o l l o w i n g : The s o r t i n s t e p 1 c l e a r l y r e q u i r e s time O ( n l o g n ) . Step 2: The k can be found i n 0(k) t i m e . By i n d u c t i o n , the f a c i a l graph o f P^ can be c o n s t r u c t e d i n time 0(k L^/ 2J) . The augmented f a c i a l g raph o f the pyramid Pk+1 c a n fc^en d e a r l y a l s o be c o n s t r u c t e d i n time 0 ( k ^ d / / " ^ ) . U s i n g Lemma 2.3, the t r a n s l a t i o n r e q u i r e d can be de t e r m i n e d i n 0(k) t i m e , and i t can be a p p l i e d t o a l l p o i n t s o f S i n l i n e a r t i m e . F u r t h e r m o r e , the a p p r o p r i a t e new v a l u e s can be a s s o c i a t e d w i t h the nodes o f FG(P^ +^) c o r r e s p o n d i n g t o v e r t i c e s and f a c e t s o f P k + ^ i n time 0 ( k L d / 2 - l ) . 37 Step 3: By Lemma 2.10 and d u a l i t y , the f a c e t s ! ^ o f P.^  can c o n t a i n a t most 0 ( i U d _ 1 ) / 2 J ) v e r t i c e s . U s i n g the f a c i a l graph o f * P^, a l l these v e r t i c e s , and i n p a r t i c u l a r a bad v e r t e x w i t h r e s p e c t t o H^, can be found i n time 0 ( i L ( d - 1 ) / 2 J ) m A p p l y i n g Theorem 3.1, i t t a k e s time 0 ( M ( P ? , H I ) + D ( P ? , H ^ ) ) * t o i n t e r s e c t P i and H.^. As remarked b e f o r e Lemma 3.4, * M ( P I , H I ) i s p r o p o r t i o n a l t o the s i z e o f the f a c i a l g raph o f * the newly c r e a t e d f a c e t s j o f Thus by Lemma 2.13 M(P*,H.) i s O U ^ - D / 2 - ] ) . * Observe, t h a t D ( P I , H I ) i s p r o p o r t i o n a l t o the number o f * * nodes and a r c s d e l e t e d from FG(P^) when P^ i s i n t e r s e c t e d w i t h H.. As o n l y 0(M(P*,R\)) = O ( i L ( d _ 1 ) / 2 J ) f a c e s a r e c r e a t e d f o r e v e r y i>k, T L M P * , H . ) < 0 ( J D / 2 J ) + ' . n f 1 o ( 1 L ( d - l ) / 2 J ) = 0 { n l ( d + l ) / 2 J N i=k+l i=k+l Thus ^ O W P * , ^ + D ( P * , H . ) ) = 0 ( n l - ( d + 1 ) / 2 J ) i s the t o t a l i=K+l time needed f o r s t e p 3. As s t e p 4 can c l e a r l y be performed i n l i n e a r t i m e , the t o t a l w o r s t case time c o m p l e x i t y o f the e n t i r e a l g o r i t h m i s O(nlogn + n ^ ( d + 1 ) / 2 J ) . For even d > 2 t h i s i s o p t i m a l because by Lemma 2.13 the s i z e o f the d e s c r i p t i o n o f the f a c i a l graph o f conv S can be 0 ( n L d / / 2 - l ) . For d = 2 t h i s i s o p t i m a l because t h e r e i s an ft(nlogn) lower bound f o r the c o n s t r u c t i o n o f the convex h u l l o f a p l a n a r p o i n t s e t [15]. Q.E.D. 38 V. C o n c l u s i o n The main r e s u l t o f t h i s t h e s i s i s a convex h u l l a l g o r i t h m w i t h O(nlogn + n ^ d + 1 ^ / 2 J ) w o r s t case time c o m p l e x i t y . I n the f o r m u l a t i o n o f the a l g o r i t h m the c o n c e p t o f d u a l i t y i s used e x t e n s i v e l y . I t s h o u l d be noted however, t h a t i t seems p o s s i b l e t o r e f o r m u l a t e t h i s convex h u l l a l g o r i t h m w i t h o u t the use o f d u a l i z a t i o n . Gruenbaum's ( [ 6 ] , p.78) c h a r a c t e r i z a t i o n o f the f a c e s o f the p o l y t o p e c o n v ( P u { v } ) i n terms o f the f a c e s o f the p o l y t o p e P c o u l d be used f o r t h i s purpose. I n Theorem 4.1 i t i s c l a i m e d t h a t the convex h u l l a l g o r i t h m p r e s e n t e d i n t h i s t h e s i s i s w o r s t case o p t i m a l f o r p o i n t s e t s i n even d i m e n s i o n s . But the convex h u l l problem c o u l d a l s o be f o r m u l a t e d i n a t o t a l l y d i f f e r e n t way: g i v e n a s e t S <= R d o f n p o i n t s , i d e n t i f y the p o i n t s o f S which are v e r t i c e s o f conv S. I n t h i s case the s i z e o f the f a c i a l graph o f conv S i s not a lower bound f o r t h i s problem any more. T h e r e f o r e i t i s p o s s i b l e t h a t t h e r e i s a s o l u t i o n f o r t h i s problem whose w o r s t case time c o m p l e x i t y i s b e t t e r than O(nlogn + n L t / 2 j j ^  F Q r t ^ e p l a n a r case however, Yao [15] proved t h a t t h i s v a r i a n t o f the problem has s t i l l a lower bound o f Q. (nlogn) . F i n d i n g an o p t i m a l convex h u l l a l g o r i t h m f o r p o i n t s e t s was one o f the major open problems s t a t e d i n the work o f Brown [ 3 ] . He showed t h a t a number o f g e o m e t r i c a l problems c o u l d be reduced t o the convex h u l l problem by the use o f g e o m e t r i c t r a n s f o r m a t i o n . I n p a r t i c u l a r , he showed t h a t c o n s t r u c t i n g the 0 39 V o r o n o i diagram o f a s e t S c R u i s e q u i v a l e n t t o c o n t r u c t i n g the (3 "Hi convex h u l l o f a s e t S' c R , where a l l p o i n t s o f S' l i e on a h y p e r s p h e r e . As K l e e [9] showed, t h a t the d e s c r i p t i o n o f a V o r o n o i diagram i n R d can be o f s i z e 0 ( n ! - ^ d + ^ ^ / 2 J ) , the convex h u l l a l g o r i t h m p r e s e n t e d i n t h i s t h e s i s a l s o y i e l d s a V o r o n o i diagram a l g o r i t h m which i s o p t i m a l f o r p o i n t s e t s i n odd d i m e n s i o n . Rather r e c e n t l y , two a l g o r i t h m s f o r V o r o n o i diagrams i n a r b i t r a r y d i m e n s i o n s ( [ 2 ] , [ 1 4 ] ) , were p u b l i s h e d , which a r e based on a s i m i l a r i n c r e m e n t a l approach as the convex h u l l a l g o r i t h m o f t h i s t h e s i s . However, the s u b q u a d r a t i c time bounds c l a i m e d i n these papers seem t o be based on assumptions about the d i s t r i b u t i o n o f the i n p u t p o i n t s and c l e a r l y cannot be w o r s t case bounds by K l e e ' s lower bound r e s u l t . A v e r y s t r i k i n g p o i n t o f the main r e s u l t i n t h i s t h e s i s i s the f a c t t h a t the convex h u l l a l g o r i t h m i s o p t i m a l f o r even d i m e n s i o n s , whereas t h i s cannot be shown f o r odd d i m e n s i o n s . N a t u r a l l y the q u e s t i o n a r i s e s whether t h e r e i s a convex h u l l a l g o r i t h m f o r p o i n t s e t s i n odd d i m e n s i o n s g r e a t e r than t h r e e w i t h w o r s t case time c o m p l e x i t y 0(n ) , which i s a t r i v i a l l ower bound o f the problem, as the f a c i a l graph o f the convex h u l l o f n p o i n t s can have t h i s s i z e . I t i s i n t e r e s t i n g t o note t h a t even f o r the t h r e e d i m e n s i o n a l case no i n c r e m e n t a l a l g o r i t h m w i t h o p t i m a l , i . e . O ( n l o g n ) , w o r s t case time c o m p l e x i t y i s known even i f a p r e s o r t i s a l l o w e d . T h i s seems t o suggest t h a t i f t h e r e i s an 0 ( n ^ d ^ 2 J ) a l g o r i t h m f o r odd d i m e n s i o n s , i t w i l l have t o use an approach e n t i r e l y d i f f e r e n t from the one taken by the a l g o r i t h m p r e s e n t e d i n t h i s t h e s i s . 40 REFERENCES [I] B e n t l e y , J . L . and Shamos, M.I., D i v i d e and Conquer f o r L i n e a r E x p e c t e d Time, I n f o . P r o c . L e t t e r s 7, 2, Feb. 1978, pp.87-91. [2] Bowyer, A., Computing D i r i c h l e t T e s s e l l a t i o n s , The Computer J o u r n a l , v o l . 24, no.2, 1981, pp.162-166. [3] Brown, K.Q., Geometric Transforms f o r F a s t Geometric A l g o r i t h m s , Ph.D. t h e s i s , Dept. o f Comp. S c i . , C a r n e g i e M e l l o n U n i v . , Dec. 1979. [4] Chand, D.R. and Kapur, S.S. An A l o r i t h m f o r Comvex P o l y t o p e s , J.ACM 17, 1, J a n . 1970, pp.78-86. [5] Graham, R., An E f f i c i e n t A l g o r i t h m f o r D e t e r m i n i n g the Convex H u l l o f a P l a n a r S e t , I n f o . P r o c . L e t t e r s 1, 4, June 1972, pp.132-133. [6] Gruenbaum, B., Convex P o l y t o p e s , W i l e y I n t e r s c i e n c e , 1967. [7] H a r a r y , F., Graph Theory, A d d i s o n - Wesley, 1969. [8] J a r v i s , R.A., On the I d e n t i f i c a t i o n o f the Convex H u l l o f a F i n i t e S e t o f P o i n t s i n t h e P l a n e , I n f o . P r o c . L e t t e r s 2, 1973, pp.18-21. [9] K l e e , V., On the C o m p l e x i t y o f d - d i m e n s i o n a l V o r o n o i Diagrams, A r c h . Math., v o l . 34, 1980, pp.75-80. [10] M c M u l l e n , P., The Maximum Number o f Faces o f a Convex P o l y t o p e , Mathematika 17, 1970, pp.179-184. [ I I ] M c M u l l e n , P. and Shephard, G.C, Convex P o l y t o p e s and the Upper Bound C o n j e c t u r e , London M a t h l S o c i e t y L e c t u r e Note S e r i e s 3, Cambridge U n i v . P r e s s , 1971. 41 [12] P r e p a r a t a , F., An O p t i m a l Real-Time A l g o r i t h m f o r P l a n a r Convex H u l l s , C.ACM 22, 7, J u l y 1979, pp.402-405. [13] P r e p a r a t a , F. and Hong, S . J . , Convex H u l l s o f F i n i t e S e t s o f P o i n t s i n Two and Three Dimensions, C.ACM 20, 7, 1977, pp.87-93. [14] Watson, D.F., Computing the n - d i m e n s i o n a l Delaunay T e s s e l l a t i o n w i t h A p p l i c a t i o n t o V o r o n o i P o l y t o p e s , The Computer J o u r n a l , v o l . 24, no.2, 1981, pp.167-172. [15] Yao, A., A Lower Bound t o F i n d i n g Convex H u l l s , Rep. STAN-CS-79-733, Dept. o f Comp. S c i . , S t a n f o r d U n i v . , A p r i l 1979. 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

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>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051821/manifest

Comment

Related Items