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 by RAIMUND SEIDEL  THESIS SUBMITTED IN PARTIAL F U L L F I L L M E N T THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in THE FACULTY OF GRADUATE STUDIES (Department  o f Computer  Science)  We a c c e p t t h i s t h e s i s a s c o n f o r m i n g to the required standard.  THE UNIVERSITY OF B R I T I S H COLUMBIA S e p t e m b e r 1980 (c) Raimund S e i d e l , 1981  In p r e s e n t i n g  this  thesis i n partial  f u l f i l m e n t of the  r e q u i r e m e n t s f o r an a d v a n c e d d e g r e e a t t h e of B r i t i s h Columbia, I agree that it  freely  the L i b r a r 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 .  agree that p e r m i s s i o n f o r extensive for  University  s c h o l a r l y p u r p o s e s may  for  financial  of  Co<**.p><A> 6 &r  The U n i v e r s i t y o f B r i t i s h 2075 W e s b r o o k P l a c e V a n c o u v e r , Canada V6T 1W5 Date  Sef^i  thesis  S&^e^c  Columbia  /?<f/  my  It is thesis  s h a l l n o t be a l l o w e d w i t h o u t my  permission.  Department  further  be g r a n t e d by t h e h e a d o f  copying or p u b l i c a t i o n of t h i s  gain  I  make  copying of t h i s  d e p a r t m e n t 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 . understood that  shall  written  ABSTRACT  Finding  the  important not theoretical  convex  only  for  reasons:  hull  of  practical  reduced  algorithm  thesis  hull  properties facial faces, thesis  the  of of  deals a  finite  is  construction  the  point  an of  of  set  in  R  is for as can  hull  problems.  .  the  Mathematical  developed, i n p a r t i c u l a r , t h e i r b o u n d s on  O(nlogn + n^ ''"^/ J) 2  The  i s worst case optimal  the  number  main r e s u l t of  algorithm  the convex h u l l o f n p o i n t s  that this algorithm  a f a s t convex  problem of c o n s t r u c t i n g  duality. d+  also  problems, such  for these other  representation,  concept  but  i n t e r s e c t i n g hyperspheres,  the  convex h u l l s are  structure, their and  with  set of points  applications  c o n v e x h u l l p r o b l e m , and  y i e l d s fast algorithms  This convex  to  finite  a number o f g e o m e t r i c a l  c o n s t r u c t i n g V o r o n o i diagrams or be  a  i n R^.  f o r even  for  of this the  I t i s shown d£2.  iii  Table of Contents 1. I n t r o d u c t i o n 2. C o n v e x P o l y t o p e s 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 s p a c e 4. The C o n v e x H u l l A l g o r i t h m 5. C o n c l u s i o n References  1 4 18 30 38 40  iv  Acknowledgement  " E i n h e r z l i c h e s Dankeschon" t o David Kirkpatrick. I do not think I could find a b e t t e r s u p e r v i s o r . I want t h a n k A l a n M a c k w o r t h f o r h i s c o n s t a n t e n c o u r a g e m e n t and f o r b e i n g a very careful second reader. Thanks a l s o t o my f e l l o w s t u d e n t s , especially Jim L i t t l e , for their patience.  TO CHINU  1  I_.  Introduction  In  the  h u l l problem stated,  young  field  i s to find  a given point set. First,  role  in  the s m a l l e s t convex  i t h a s numerous a p p l i c a t i o n s  i nengineering,  other  fields.  computational  problems,  diagrams,  the  such  as  construction  Second,  geometry, the  of  construction  the  As  a s 1972  hull algorithm  union  depends  linearly  point  or i n t e r s e c t i o n of  on  designed  an O ( n l o g n )  real  points  drawn  complexity  that convex  sets.  Subsequently  of  the  convex  to  convex several  running  hull,  expected time a l g o r i t h m f o r which  i s O(n^), p<l.  the problem  time points  Preparata  t i m e a l g o r i t h m , and B e n t l e y and  from a d i s t r i b u t i o n  number o f p o i n t s on t h e h u l l the  reduced  t h e p r o d u c t o f t h e number o f i n p u t  t h e number o f p o i n t s f o u n d on  n  or  [8] d e v e l o p e d an a l g o r i t h m whose  Shamos [1] p r e s e n t e d a l i n e a r of  Voronoi  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 t h e Jarvis  [12]  of  Graham [5] p r e s e n t e d a n O ( n l o g n )  for planar  problem.  and  a  problem.  early  papers  i t plays  a s a number o f o t h e r  s p h e r e s , and o t h e r p r o b l e m s , c a n be t r a n s f o r m e d hull  set containing h u l l problem i s  geometric  the convex  Simply  The i m p o r t a n c e o f t h e c o n v e x  p a t t e r n r e c o g n i t i o n , and central  t h e convex  h a s b e e n one o f t h e m o s t s t u d i e d p r o b l e m s .  the issue  twofold.  o f c o m p u t a t i o n a l geometry  Yao  for  sets  the expected [15]  tackled  f r o m t h e o t h e r s i d e and p r o v e d  Q (nlogn) time i s necessary t o i d e n t i f y the v e r t i c e s o f the h u l l even  i f tests  involving quadratic  functions of the  2  inputs are allowed. are worst case  For  paradigm.  algorithm  a n d Hong  i s o f course optimal  t h e convex  h u l l problem  of  point  algorithm published  by  conquer  by Y a o ' s  s e t s i n d - s p a c e , d>3.  i s t h e one  and  result.  seems t o  i s quite different f o r  Chand  The o n l y  and  Kapur  general [4], I t  on t h e so c a l l e d g i f t w r a p p i n g p r i n c i p l e and uses  time t o d e t e r m i n e each f a c e t o f t h e convex hull  [13] d e v e l o p e d  i n 2 and 3-space  w e l l understood, the s i t u a t i o n  hulls  relies  Preparata  a l g o r i t h m w h i c h i s based on t h e d i v i d e  Whereas  convex  s e t s i n 3-space  This  be f a i r l y  o f Graham a n d P r e p a r a t a  optimal.  point  an O ( n l o g n )  Thus t h e a l g o r i t h m s  of  n points  in  c a n have  than  In  0 ( n I  this  (  d  +  2  )  /  2  As t h e  facets  S f n ^ / ^ J )  i m p l i e s t h a t worst case time complexity better  hull.  linear convex  [10],  of this algorithm  this  i s not  J ) .  thesis  an  incremental  hull  presented  on t h e a l g o r i t h m o f Chand a n d K a p u r .  It  i s shown  that  O(nlogn + n ^ ^  Section  improves  2  1  ^ ^ )  i t  has  and t h a t t h i s  points  case  i s optimal  o f this thesis deals with  properties  of  polytopes,  but unfortunately  computer  worst  n  f o r the  c o n s t r u c t i o n o f t h e convex which  of  algorithm  polytopes.  scientists.  There  In Section  i n d-space  time  i s  complexity  f o r even d .  the basic mathematical  i s a rich  theory  dealing  with  i t seems t o have b e e n i g n o r e d by 3 a method f o r t h e i n t e r s e c t i o n  3  of  a  polytope  h u l l algorithm section  the  and  a halfspace  presented results  i n Section  are  presented.  In p a r t i c u l a r ,  algorithm  of  this  i s d e v e l o p e d on w h i c h t h e 4 is  discussed i t is  thesis  and  noted yields  based.  dimensions.  the  some o p e n p r o b l e m s that an  the  convex  algorithm  c o n s t r u c t i o n of Voronoi diagrams which i s o p t i m a l i n odd  In  convex last are hull  for  the  for point  sets  4  II.  Convex  This  Polytopes  s e c t i o n c o v e r s the  multi-dimensional theory  and  convex  b a s i c d e f i n i t i o n s and  polytopes.  There  l i t e r a t u r e about these o b j e c t s .  properties given  i n t h i s section represent  facts  t o the c o n t e n t of the  pertinent  a more c o m p l e t e t r e a t m e n t o f p o l y t o p e s reader  the  Euclidean It  following  space R  we  , where d i s an  i s assumed t h a t t h e  linear  algebra  s u c h as  reader  y,  etc.  s u c h as open and  For and  x,ye R  Definition  extensive  d e f i n i t i o n s and  bare  minimum  and  the  deal  related subjects  [6],  with  the  arbitrary  d-dimensional  positive  integer.  basic notions  sets  i s also  denote the  int S  i n d u c e d by  will  basic  of  topological  assumed.  s c a l a r product of x denote the  the E u c l i d e a n  i n t e r i o r of  and S  metric.  2.1:  Let  a e R = ( a / 0 ) , and  The  set  {xe R  | <x,a> = c } i s c a l l e d a  The  set  {x e R  | <x,a> £ c } i s c a l l e d a c l o s e d  halfspace.  be  could  It  of For  F a m i l i a r i t y with  , <x,y> w i l l  topology  a  i s f a m i l i a r with  closed  f o r a s e t S <= R ,  under the  The  an  subspace, dimension of a subspace, s c a l a r  product, orthogonality, notions  will  is  of  subsequent s e c t i o n s .  i s r e f e r r e d t o Gruenbaum's book  In  properties  should  c e  clear  R.  that  closed  hyperplane.  halfspace  also  be  o  5  defined the  using  instead of  and t h a t i t i s a c l o s e d  set i n  t o p o l o g i c a l sense.  2.2:  Definition Let a eR -l^ksd,  ,  l e tX  be  a  linear  be t h e d i m e n s i o n  of  subspace o f R ,  X.  (By  empty s e t be a s u b s p a c e o f d i m e n s i o n H = a+X = {a+x|x e x} c R H, d i m ( H ) , i s k.  i s called  A flat  and l e t k,  convention,  l e t the  -1.) a flat.  of dimension  k  The d i m e n s i o n o f  is  also  called  a  k-flat.  Examples  of  flats  are  points  hyperplanes  ( ( d - l ) - f l a t ).  Definition  2.3:  Let  .  S cR  The a f f i n e  of a l l f l a t s c o n t a i n i n g  It  (0-flat),  flat.  a  For S cR  Definition A  flat.  set  a  ( 1 - f l a t ) , and  h u l l o f S, a f f S, i s t h e  intersection  S.  easy t o prove t h a t the i n t e r s e c t i o n  itself  lines  Thus t h e a f f i n e  of a family of  flats  h u l l o f any s u b s e t o f R  l e t dim S = d i m ( a f f  d  is is a  S).  2.4^: S cR  is  called  convex  i f f for  a n y x , y e S,  s e g ( x , y ) = { ( l - r ) x + r y | O ^ r ^ l } c S.  Examples o f convex  s e t s a r e f l a t s and h a l f s p a c e s .  Observe  that  6  the  intersection  of  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 holds:  Lemma A  2.1:  closed  halfspaces Proof:  convex  s e t K <= R  i s the intersection  D  of a l l closed  c o n t a i n i n g K.  [6] 2.2.3.  Definition  2.5:  (3 K cR  Let  Q.E.D.  be  a  convex  (3 H = {x e R |<a,x>=c}  s e t and  a  hyperplane. H  i s called  a  supporting  hyperplane  of  inf{<x,a>|xeK} = C  o r sup{<x,a>|x e K } = c .  We s a y , a s u p p o r t i n g  hyperplane H o f  point  p e R -K  i f p  K  i s not contained  K  i f  separates i n t h e same  K  either  and  a  halfspace  d e t e r m i n e d by H as K.  D e f i n i t i o n 2.6^: L e t K be a c o n v e x s u b s e t 1)  F <= K i s c a l l e d exists  o f R ^ a n d k=dim K .  a face o f K i f either  a hyperplane H supporting  F = K o r F=0 o r  there  K , s u c h t h a t K n H=F.  2)  A face F w i t h dim F = m i s c a l l  an m - f a c e o f K .  3)  A  a f a c e t o f K, a 0 - f a c e i s  4)  (k-1)-face  K  i scalled  called  a v e r t e x , and a 1-face i s c a l l e d  If F  i s an m-f ace  o f K, G an ( m + l ) - f a c e ,  and F c G ,  F a subface  o f G and G a s u p e r f a c e  o f F.  we c a l l 5)  of  A face F o f K i s c a l l e d proper,  an edge o f K .  i f F^0 a n d F ^ K .  then  7  C l e a r l y , e v e r y face o f a convex following  Lemma  s e t i s convex.  Furthermore  the  holds:  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 c o n v e x  set K  i s a f a c e o f K.  Proof:  [6] 2.4.10.  Q.E.D.  D e f i n i t i o n 2.7: The  h u l l o f a s e t A c R ^ , conv A , i s t h e i n t e r s e c t i o n  convex  of a l l c l o s e d convex  sets containing A .  I n v i e w 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 c o n v A intersection of a l l closed A conv A  i s closed  another e q u i v a l e n t  Lemma  and  convex.  definition  For every  lemma  gives  hull.  hull of a set A i n R ^ .  x =  d  i n the  d  i=o  1  1  1  I f A i s f i n i t e , A = {x^,...,x  of  P  c  i  x  i  1  }, t h e n t h e r e l a t i v e cl  n £  iio.  1  exactly a l l x eR  comprises  x =  which a r e e x p r e s s i b l e  7 c . x . , where x . e A , c . ^ 0 , a n d J c . = 1. ,  2)  form  following  f o r t h e convex  P comprises e x a c t l y a l l x e R  form  The  containing A .  2.3:  L e t P be t h e c o n v e x 1)  halfspaces  i s the  interior  which a r e e x p r e s s i b l e i n the  n ' w h e r e c^>0, a n d £ ^ c  =  !•  8  Proof: 1)  [6] 2.3.3, 2.3.5.  2)  [11] p a g e 1 1 . Q.E.D.  Definition ^.8: A polytope polytope  Lemma Every  i s the convex h u l l o f a f i n i t e  P i scalled  a d-polytope  setof  points.  A  i f f dim P = d.  2.4: face o f a polytope  i s a polytope.  P r o o f : C o n s e q u e n c e 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  in  and dim P = d.  1)  The number o f d i s t i n c t  2)  Every  faces o f P i s f i n i t e .  (d-2)-face o f P i s the  intersection  of  exactly  two  facets. 3)  Every  k-face  o f P i s t h e 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 ,  For  a polytope  (which  3.1.6, 3.1.8.  P w i t h d i m P = d , we d e n o t e t h e number o f i - f a c e s  i s finite)  by f ^ P ) .  f ( P ) = 0 f o r i < - l and i > d . i  Q.E.D.  By c o n v e n t i o n  f _ (P) = f ^ (P) =1, a n d 1  9  Lemma 2.6_i If 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 t h e p o l y t o p e  t h e n G i s a l s o a f a c e o f P.  Proof:  [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 . set  The k - s k e l e t o n o f P,  s k e l ^ P,  i s the  o f a l l i - f a c e s o f P, O ^ i s k .  O b s e r v e . t h a t t h e 1 - s k e l e t o n o f a p o l y t o p e c a n be i n t e r p r e t e d a s a g r a p h , where t h e 0 - f a c e s the edges o f t h e g r a p h .  a r e t h e v e r t i c e s and t h e 1 - f a c e s  Of some i m p o r t a n c e  are  i s the following:  Lemma 2.7_i The  graph  representing  the  1-skeleton  of  a  d-polytope  i s  d-connected. Proof:  [6] 1 1 . 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 ) ,  whose n o d e s c o r r e s p o n d from  t o t h e f a c e s o f P.  t h e node c o r r e s p o n d i n g  corresponding  to the face  i sa directed FG(P) has  graph  an a r c  F^ o f P t o t h e node  t o f a c e F 2 i f f F-^ i s a s u b f a c e  of F 2 .  D e f i n i t i o n 2.11: Two their  polytopes  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  f a c i a l graphs a r e isomorphic.  10  Clearly  t h e f a c i a l g r a p h 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  g r a p h w i t h one s o u r c e a n d one s i n k w h i c h h a s  d+2  all  a r e o f l e n g t h d+1.  directed  paths  from  source  to  sink  levels, i . e .  F u r t h e r m o r e , a s i t i s shown b e l o w , t h e c o n v e r s e o f FG(P)  the  with the d i r e c t i o n  FG(P)  (i.e.  o f a l l a r c s reversed) i s r e a l i z a b l e as *  f a c i a l g r a p h 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 . s e t A _ o f A c R i s d e f i n e d by  The p o l a r  A*  = {yeR |<x,y> d  £ 1 for a l lxeA } .  Lemma 2.8^: Let 1) 2)  P be * P i I fF F' =  a d - p o l y t o p e and 0 e i n t P. * * * s a d - p o l y t o p e w i t h 0 e i n t P a n d (P ) = P. i s a k-face o f P then { y e P * | < x , y > = 1 f o r a l l x e F}  *  is a (d-k-l)-face of P . 3)  The m a p p i n g reversing the  Proof:  <(> d e f i n e d correspondence *  by  (j>(F) = F'  i sa  1-1  inclusion  between t h e s e t o f f a c e s o f P and  s e tof faces of P . [ 6 ] 3.4.  D e f i n i t i o n 2.13: L e 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 t h e d u a l o f P.  Q.E.D.  11  Lemma 2.8 i m p l i e s t h a t t h e f a c i a l g r a p h s o f a p o l y t o p e dual  are  anti-isomorphic.  w i t h 0 e i n t P, t h e n * of  P  and i t s  O b s e r v e t h a t i f v i s a v e r t e x o f P,  {x e R |<x,v> = l } i s a s u p p o r t i n g  and c o n t a i n s t h e f a c e t v ' d u a l t o v .  hyperplane  I n other words, i f  0 e i n t P, and V = { v ^ , . . . , v } i s t h e s e t o f v e r t i c e s o f P, P  = niH^lsisn},  n hyperplanes  In  the  where  then  = { x R |<x,v > £ l } a n d e a c h o f t h e e  i  {x e :R | <x,v^> = l } c o n t a i n s a f a c e t o f P*. d  following  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-simplex  i s a k-polytope  which i s t h e convex h u l l o f  k+1 p o i n t s i n R , d^k. 2)  P  i s called  a  s i m p l i c i a l polytope,  i f f a l l i t s proper  faces are simplices.  k+1 I t s h o u l d be n o t e d and  t h a t a k-simplex  t h a t e a c h i - f a c e i s an  simplex  has p r e c i s e l y  i-simplex  itself.  i-faces, Futhermore,  a  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 If  (d-1)-polytope.  c i s a p o i n t i n R - a f f B, t h e n P = c o n v ( B u { c } )  a d - p y r a m i d w i t h b a s i s B.  i s called  12  The of  faces of P s a t i s f y  the following  relationship with  the faces  B.  Lemma 2^53: Let  P  be  a d-pyramid  w i t h b a s i s B a n d a p e x c , a n d l e t F be an  i - f a c e o f B. 1)  2)  F  i s a l s o an i - f a c e o f P a n d c o n v ( F u { c } ) i s an  of  P.  Every the  i-face of P i seither  a l s o an i - f a c e o f B o r i t i s o f  f o r m c o n v ( G u { c } ) , where G i s an ( i - l ) - f a c e  Proof:  [6] 4.2.  Using  Lemma 2.9,  (itl)-face  o f B. Q.E.D.  i t easy  to  see  how  the f a c i a l graph o f a  p y r a m i d P w i t h b a s i s B and apex c c a n be e x p r e s s e d i n terms the The  facial  g r a p h o f B.  F G ( P ) c o n s i s t s o f two c o p i e s o f F G ( B ) .  nodes i n one copy c o r r e s p o n d t o t h e f a c e s  also  faces  of  node  P  which  i n the f i r s t  face  of  conv(F u { c } ) . g r a p h o f FG(P)  Observe, (d-1)-simplex.  Thus  B.  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 h a s  an a r c t o t h e node i n t h e s e c o n d c o p y c o r r e s p o n d i n g t o t h e i n graph  theoretic  i s the product graph K  2  face  terms, the underlying  * FG(B).  t h a t a d - s i m p l e x i s a d - p y r a m i d whose b a s i s  i s a  Thus t h e u n d e r l y i n g g r a p h o f t h e f a c i a l g r a p h o f  a d-simplex i s a (d+l)-cube. [7] .)  are  o f B, t h e n o d e s i n t h e o t h e r c o p y c o r r e s p o n d t o t h e  f a c e s o f P o f t h e form conv(G u { c } ) , where G i s a Each  of  (For t h e graph t h e o r e t i c  terms see  13  Of c o n s i d e r a b l e i n t e r e s t  Definition Let  i s the family o f c y c l i c polytopes.  1.16; be t h e moment c u r v e d e f i n e d by  t e R.  The  d-polytope  distinct  points  polytope  C(n,d).  Cyclic  on  polytopes  formed  the  are  ^ ( t )  b y t h e c o n v e x h u l l o f a n y n>d  moment c u r v e MLj i s c a l l e d  simplicial  ( [6]  c o m b i n a t o r i a l type o f C(n d) i s independent That  4.7 ) ,  and t h e  i s , a n y two d - d i m e n s i o n a l c y c l i c  on n v e r t i c e s a r e 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 . cyclic  a cyclic  of the choice of the  f  n p o i n t s o n M^.  (t»t , . . . t ) ,  : =  polytopes l i e s  i n their  polytopes  The i m p o r t a n c e o f  extremal nature.  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 , for  2)  f k  (  p  )^ f (C(n,d)) k  a l l k.  The number o f  k-faces  of  a  0( l- / -i).  More s p e c i f i c a l l y ,  f (  )  d  2  n  k  then  C(n,2s)  k  polytope  C(n,d)  is  f o r 0sk<d  l  i=l  f (C(n,2s+l))  cyclic  k-i+1  s k+2 n - i - 1 i+1 ) (k-i+1 i  for  d=2s  for  d=2s+l.  for  d=2s  for  d=2s+l.  i=l  For k=d-l these e x p r e s s i o n s e v a l u a t e t o  f _l(C(n,d)) d  = 2(  n  P r o o f : 1) [10] , 2) [6] 9.6.1.  Q.E.D.  14  The  lemma  above  gives  a  d-polytope  on n v e r t i c e s .  the  bounds  same  with n facets. polytopes, does  not  a  for  the  graph,  t h a t , by  duality,  of  of  representation  of  i s r a t h e r u n i n t e r e s t i n g because i t  express  structure  sake  any  of  a polytope.  c a r r i e s such i n f o r m a t i o n .  facial  t h e number o f f a c e s o f a  I t s h o u l d be n o t e d  set of faces  explicitly  on  f o r t h e number o f v e r t i c e s o f p o l y t o p e s  However;  the  combinatorial polytope  hold  bound  the  geometric  or  The f a c i a l g r a p h o f a  Thus a b o u n d on t h e s i z e  of  i . e . t h e number o f i t s n o d e s and a r c s , i s o f  interest.  L e t N ( P ) d e n o t e t h e number o f n o d e s i n t h e f a c i a l g r a p h a  polytope  denote the  P ( i . e . N ( P ) i s t h e number o f f a c e s o f P ) , l e t A ( P ) number  face - subface  We  will  of  arcs  in  FG(P)  ( i . e . the  number  of  p a i r s i n P ) , and l e t D(P) = A ( P ) + N ( P ) .  give  a  bound  v e r t i c e s o f P i n two s t e p s . suffices  of  on D(P) i n t e r m s o f t h e number o f First  i tw i l l  be  to consider only s i m p l i c i a l polytopes.  d e r i v e a bound f o r D ( P ) , w h e r e P i s a s i m p l i c i a l  argued  that  S e c o n d , we  i t will  polytope.  Lemma 2.11; L e t P be a d - p o l y t o p e , By to  a process v',  V t h e s e t o f v e r t i c e s o f P, and v e V .  c a l l e d p u l l i n g , v e r t e x v- c a n be p e r t u r b e d  such t h a t the d-polytope  e x a c t l y the f o l l o w i n g k-faces  P  1  = conv(  f o r 0£k<d:  slightly  (V-{v}) u { v ' } ) has  15  (i)  t h e k - f a c e s o f P w h i c h do n o t c o n t a i n v ;  (ii)  t h e convex  r i k-1 h u l l s o f the type conv((v'} u G )  k-1 where G  f  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. Proof;  [6] 5.2.2.  Q.E.D.  Lemma 2.12; If 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 *  of the v e r t i c e s satisfying 1) f * (  P  )  =  f  (  of P  )  P,  then a  n  P  is a  d-polytope  N(P*) £ N ( P ) ,  d  0  2)  simplicial  each  A(P*)^ A(P).  Proof; 1) 2)  [ 6 ] 5.2.4 We  only  need t o show t h a t p u l l i n g  t o v ' t o y i e l d p o l y t o p e P' face - subface  does  not  a vertex v of polytope P decrease  t h e number  pairs.  L e t F be a k - f a c e o f P a n d G a s u b f a c e o f F f o r l ^ k < d . show P',  that  there  We  will  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' a n d G ' o f  such t h a t G ' i s a subface o f F . 1  There  a r e three cases t o c o n s i d e r :  (i)  F a n d G do n o t 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  (ii)  of  1  a n d G i s a s u b f a c e o f F;  F c o n t a i n s v , G does n o t c o n t a i n v : F i s n o t a f a c e o f P'; b u t G  is a  face  of  P'  and by  16  Lemma 2.11  induces  a f a c e F' = c o n v ( G u { v } ) , and G i s a 1  s u b f a c e o f F *; (iii)  b o t h F and G c o n t a i n v : F a n d G must have r e s p e c t i v e G  i s a subface o f F  subfaces F  and b o t h F  By Lemma 2.11 F~ and G~ i n d u c e and  G' = c o n v ( G ~  u{v'})  of P  that  and G~ do n o t c o n t a i n v . faces  such  1  and G , s u c h  F' = c o n v ( F ~  that G  u{v'})  i s a subface o f  1  F' . Q.E.D.  Lemma 2.13; F o r a n y 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  Proof: * By Lemma 2.12 D ( P ) £ D ( P )  Let  P be a d - p o l y t o p e  for  some s i m p l i c i a l d - p o l y t o p e  P  of  P*  c l e a r l y D(P*) < f  where  is a S^  on n v e r t i c e s .  (d-1)-simplex,  denotes  a  on n v e r t i c e s .  k-simplex.  As  i t was  As e v e r y d - 1  facet  (P*)*D(S _ ),  mentioned  d  1  after  Lemma 2.9, t h e u n d e r l y i n g g r a p h o f FG(S _-^) i s a k - c u b e a n d k k-1 therefore has 2 vertices and k*2 edges. Thus D(S _ ) = (d+2)*2 . * F u r t h e r m o r e , by Lemma 2.10 f ^ _ ^ ( ) ^ f _^(C(n,d)). _ s F o r e v e n d=2s, f _ ( C ( n d ) ) = J L - ( ) 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 o n e k  d _ 1  d  1  p  d  n  d  can D(P)  show  1  that  f  D  * d-l* S  =  £ D(P*) < f _ ( C ( n , d ) ) * D ( S _ ) d  1  S  s  d  1  (  S + 1  )*2  2 S  = 0(n ). S  = 0(s!).  Hence  17  Using  t h e same method, one c a n show t h a t  D(P) = 0 ( n ) S  f o r odd  d=2s+l. Thus D(P) = 0 ( n L  d  / -J ) f o r any d - p o l y t o p e on n v e r t i c e s . 2  Q.E.D.  18  III.  The  In  I n t e r s e c t i o n of a Polytope  this  s e c t i o n we  intersecting  a  polytope  construction  of  such  an  consider and  and  a  Halfspace  i n some d e t a i l  a  halfspace.  intersection w i l l  the convex h u l l a l g o r i t h m p r e s e n t e d  in  The be  the  the problem  efficient  the main t o o l  next  of  of  section.  We  a h a l f s p a c e H,  and  f o r m a l l y s t a t e t h e p r o b l e m as f o l l o w s :  Given  the f a c i a l graph o f a p o l y t o p e  a v e r t e x v o f P not c o n t a i n e d graph of the polytope  The  P  1  in H  = P o  P,  construct  f  the  facial  H.  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 problem can  solved  i n time  proportional  t o t h e amount o f  f a c i a l graph of P t o the f a c i a l graph of  Throughout d e f i n e d by halfspace  the  change  from  defined  by  I,  I,  H~  i.e.  denotes H  =  the  P'.  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 hyperplane  be  (R  the - H)  in R  other  closed  u I , and  P is a  d-polytope.  Definition  _3.1:  A face F of P i s c a l l e d a g o o d f a c e w i t h r e s p e c t t o H, a c u t f a c e w i t h r e s p e c t t o H, a bad subface  face of  with  i f f F c H and i f f F c H and  r e s p e c t t o H,  F i s contained  in I,  F£  H~,  F c H " (i.e.F c I),  i f f F <= H ~ and  F 52! H,  but  no  19  a touch  f a c e w i t h r e s p e c t t o H,  subface  of F i s contained  in I,  a m i x e d f a c e w i t h r e s p e c t t o H,  In  the  respect  following, t o H"  f a c e s , bad falls  in  Definition  be o m i t t e d ,  faces, etc. exactly  i f f F <£ H~  one  of  the  we  will  3.1:  The  five  illustrates  types of f a c e s f o r the case of  F $ H,  and  one  and F ^ f l .  arise,  Observe t h a t every  F i g u r e 3.1  Figure  and  and  and  when no c o n f u s i o n c a n  will  3.1.  i f f F c H~  the phrase  just  talk  nonempty  categories these  five  d=2.  f i v e types of  faces.  "with  about good face  of  implied  P by  different  20  The  following  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 t h e types 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 face 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 r e good o r c u t f a c e s ,  (ii)  a c u t face, i f fa superface o f F i s a touchface,  (iii)  a bad f a c e , i f f a l l i t s subfaces a r e bad o r touch  (iv)  a  touch  faces,  f a c e , i f f a l l b u t one s u b f a c e s a r e b a d o r t o u c h  faces, (v)  a  mixed  face,  i f f a subface 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 t w o , some s u b f a c e s o f F a r e b a d o r touch  faces.  Proof; 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  The  n e x t two lemmas g i v e a  3.1.  characterization  of  Q.E.D.  the  faces  of  P' = H n P i n t e r m s o f t h e 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 face - subface p a i r s o f P  1  i n terms o f f a c e - subface  pairs  o f P.  Lemma  3.2:  (i)  I f F i s a good f a c e o r a c u t f a c e o f P, t h e n F i s a l s o  a  f a c e o f P'. (ii)  I f F i s a m i x e d k - f a c e o f P, t h e 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  (iii)  I f F i s a b a d f a c e o r a t o u c h f a c e o f P, t h e n F i s n o t a f a c e o f P'.  (iv)  Points  ( i ) and ( i i ) y i e l d a l l f a c e s o f P . 1  Proof: ( i ) and ( i i i ) (ii)  are t r i v i a l .  I f F i s a m i x e d k - f a c e o f P, t h e n t h e r e hyperplane  X  X n P n H = F n H P'  = P  n  such  f  f  X n P = F.  that  and X i s a  supporting  supporting Certainly,  hyperplane  of  H.  Observe t h a t G = P n I i s a f a c e t subface  is a  of  P n H  and  of  F n I  P'.  F n I = (F n H) n G.  is a  Thus  by  Lemma 2.6 F n I i s a ( k - 1 ) - f a c e o f P'. (iv)  This  follows  a s a c o n s e q u e n c e o f Lemma 2.5 and t h e f a c t  that G = P n I i sthe only contained  Lemma  facet  of  P"  which  i s not  i n a f a c e t o f P.  3.3:  L e t G be a f a c e o f P and F a s u b f a c e o f G. (i)  I f F i s a good f a c e o r a c u t f a c e o f P and G face  or  is a  good  c u t f a c e o f P, t h e n F i s a s u b f a c e o f G o n t h e  p o l y t o p e P'. (ii)  I f F i s g o o d and G i s m i x e d , t h e n F i s a s u b f a c e o f G n H on P' .  (iii)  I f G i s m i x e d , t h e n G n I i s a s u b f a c e o f G n H o n P'.  (iv)  I f F and G a r e m i x e d , t h e n F n H i s a s u b f a c e  of  G n H,  22  and (v)  F n I i s a s u b f a c e o f G n I on P . 1  I f G i s mixed and F i s a  touch  face,  then F n I  is a  s u b f a c e o f G n I o n P'. (vi)  Points  ( 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*.  Proof; (i)  to  (v) f o l l o w  straightforwardly  from  D e f i n i t i o n 3.1 a n d  Lemma 3.2. (vi)  f o l l o w s f r o m Lemma 3.2 and t h e f a c t t h a t a l l p o s s i b l e  types  of face - subface p a i r s are considered. Q.E.D.  The  preceding  constructs  lemmas j u s t i f y  the following algorithm,  t h e f a c i a l g r a p h o f P' f r o m t h e f a c i a l g r a p h o f P.  We assume t h a t we a r e d e a l i n g w i t h a v e r s i o n o f t h e f a c i a l in with  which  which  every  node  i t the coordinates  corresponding  to a vertex  graph  has a s s o c i a t e d  o f the vertex.  Algorithm 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  The  algorithm  takes  nodes c o r r e s p o n d i n g and  their  H.  as input the f a c i a l graph o f P i n which a l l to v e r t i c e s not i n H  i n c i d e n t a r c s h a v e been r e m o v e d .  (i.e.  bad  vertices)  Furthermore, the s e t  o f bad e g e s o f P, BAD^, t h e s e t o f t o u c h e d g e s o f P, TOUCB^, a n d the  s e t o f m i x e d e d g e s o f P, MIXED., , a r e assumed t o be known.  23  For  k=l,...,d  touch,  and  B A D , TOUCH , a n d M I X E D k  k  mixed edges o f P r e s p e c t i v e l y .  the a l g o r i t h m BAD  k  = TOUCH  F o r a f a c e F o f P, s u b ( F )  k  = MIXED  F ) , super(F)  a  is  T-sub(F)  t o t h e node  t h e node  corresponding  mixed  face  assumed  corresponding  F o f P, i n d u c e d ( F )  to  F ) , T-sub(F)  a r e touch  f o r the s e t o f subfaces which  f a c e o f P' i n d u c e d It  pointing  f o r the s e t o f subfaces o f F which  M-sub(F) s t a n d s For  = 0 fora l l k>l.  denotes the s e t o f superfaces o f F ( i . e . the  a r c s o f FG(P) l e a v i n g stands  k  At the beginning of  denotes the s e t o f subfaces o f F ( i . e .  the a r c s o f the f a c i a l graph to  stand f o r the s e t o f bad,  k  are  f a c e s , and  mixed  faces.  d e n o t e s F n I , t h e "new"  by F. that  at  the  := M - s u b ( F ) := i n d u c e d ( F )  beginning := 0  of  the  algorithm  f o r a l l k-faces  with  k>l. F o r e a c h edge F e MIXED-^, i t i s assumed t h a t a node to  the  vertex  v„ = F n I  of  P*  has  been c r e a t e d , t h a t t h e  c o o r d i n a t e s o f v_ have been computed, and t h a t v  p  esub(F),  super ( v ) = { F } , p  sub(v ) p  w h e r e E d e n o t e s t h e node c o r r e s p o n d i n g  corresponding  = {E},  induced(F) and v  p  = v„,  e s u p e r (E) ,  t o t h e empty f a c e .  24  begin L := 0 f o r k = 2 t o d do begin 1. Determine a l l b a d , t o u c h , and mixed k - f a c e s f o r a l l F i n B A D , do f o r e a c h G i n s u p e r ( F ) do d e l e t e F f r o m s u b ( G ) insert G i n L d e l e t e F from t h e f a c i a l graph k  for  a l l F i n T O U C H _ do f o r e a c h G i n s u p e r ( F ) do d e l e t e F f r o m s u b ( G ) i n s e r t F i n T-sub(G) insert G i n L  for  a l l F i n M I X E D _ do f o r e a c h G i n s u p e r ( F ) do i n s e r t insert  for  k  k  1  1  a l l F i n L do I f c a r d i n a l i t y ^ sub(F) I f c a r d i n a l i t y ( sub(F) I f c a r d i n a l i t y ( sub(F) d e l e t e F from L  G i n MIXED, F i n M-subiG)  ) = 0 then i n s e r t ) = 1 then i n s e r t ) > 1 then i n s e r t  F i n BAD. F i n TOUCH. F i n MIXED?  2. E s t a b l i s h t h e 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 create t h e new f a c e s f o r m e d b y t h e i n t e r s e c t i o n o f a m i x e d f a c e a n d I. f o r e a c h F i n MIXED, do create a (k-1)-face G i n d u c e d ( F ) := G i n s e r t G i n sub(F) s u p e r ( G ) := {F} f o r a l l X i n M - s u b ( F ) do i n s e r t i n d u c e d ( X ) i n sub(G) insert G i nsuper(induced(X)) f o r a l l X i n T - s u b ( F ) do L e t Y be t h e o n l y element i n sub(X) (Y i s a c u t f a c e ) i n s e r t Y i n sub(G) i n s e r t G i n super(Y) 3. for  Cleanup e a c h F i n MIXED. , do i n d u c e d ( F ) := M - s u b ( F ) := T - s u b ( F ) := 0 f o r e a c h F i n TOUCH. _ do L e t Y be t h e o n l y e l e m e n t i n s u b ( F ) d e l e t e F from super(Y) d e l e t e F from t h e f a c i a l graph ( o f the k-loop) 1  end  25  £. F i n a l C l e a n u p i f MIXED ? 0 then (P n H i s a d - p o l y t o p e ) MIXED, contains exactly one element, t h e node c o r r e s p o n d i n g t o P. i n d u c e d ( P ) := M - s u b ( P ) := T - s u b ( P ) := 0 i f TOUCH 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 exactly one element, the node corresponding t o P. P h a s e x a c t l y one f a c e t l e f t : t h e face F = P n I . d e l e t e P from super(F) d e l e t e P from the f a c i a l graph end ( o f A l g o r i t h m 3 . 1 ) . d  d  For number  a polytope  P and a h a l f s p a c e H, l e t D(P,H)  denote  the  o f bad f a c e s and t o u c h 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  t h e number o f corresponding  arcs  the  t o such f a c e s .  number o f m i x e d corresponding  of  facial  graph  incident  to  nodes  F u r t h e r m o r e , l e t M(P,H) d e n o t e t h e  f a c e s o f P p l u s t h e number o f a r c s b e t w e e n n o d e s  t o such f a c e s .  Observe,  o f n o d e s and a r c s d e l e t e d f r o m t h e  t h a t D(P,H) i s t h e number  facial  graph  of  P.  n o t e , t h e M(P,H) = 0 ( N ) , w h e r e N i s t h e s i z e o f t h e f a c i a l of the facet P n I o f P . 1  The f o l l o w i n g  Also graph  holds:  Lemma 3>*.1 :  Algorithm  3.1  correctly  determines  the  facial  graph  of  P' = P n H i n t i m e 0 ( D(P,H) + M(P,H) ) .  Proof: Correctness  f o l l o w s f r o m Lemmas 3.1 t o 3.3.  time bounds o b s e r v e t h e f o l l o w i n g .  With respect t o the  The a l g o r i t h m c o n s i d e r s  only  n o d e s and a r c s w h i c h a r e e i t h e r d e l e t e d f r o m t h e f a c i a l g r a p h o r  26  are r e l a t e d  to the insertion of a  new  node  or  arc.  Only  a  c o n s t a n t amount o f t i m e n e e d s t o be s p e n t on e a c h o f t h e s e n o d e s and  arcs i f appropriate pointer  structures  to  manipulate  the  v a r i o u s s e t s a r e used. Q.E.D.  A l g o r i t h m 3.1 assumes t h a t t h e n o d e s c o r r e s p o n d i n g v e r t i c e s o f P and t h e i r f a c i a l graph. edges,  i n c i d e n t a r c s have b e e n removed f r o m t h e  I t a l s o assumes t h a t t h e s e t s o f b a d e d g e s ,  and mixed  subgraph  e d g e s a r e known.  o f s k e l ^ P induced  connected.  This  by  implies  a  mixed  depth  first  these  that i f  e d g e s o f P.  search, which Thus t h i s  touch  The n e x t lemma shows t h a t t h e vertices  and  edges  is  o n l y one b a d v e r t e x o f P i s  known, a l l t h e v e r t i c e s and e d g e s m e n t i o n e d by  t o bad  above c a n  t r a v e r s e s o n l y bad,  search can  be  be  found  t o u c h , and  performed  in  time  p r o p o r t i o n a l t o t h e number o f t h e s e e d g e s p l u s t h e number o f b a d vertices.  Lemma 3.5_: Let  P  be  a  d-polytope  beginning o f this The  graph  formed  and H a h a l f s p a c e a s s p e c i f i e d  a t the  section. b y t h e e d g e s and v e r t i c e s o f P w h i c h  are not  contained i n H i s connected. Proof; L e t H" be ( R - H ) u I . d  Clearly P  .  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  The b a d , t o u c h , a n d m i x e d  edges  of  P  correspond  to the  27  edges  of  P  w h i c h a r e n o t c o n t a i n e d i n F.  Similarly,  t h e bad  v e r t i c e s o f P a r e t h e v e r t i c e s o f P~ n o t c o n t a i n e d i n F. we  only  need  t o show t h a t t h e g r a p h f o r m e d  edges o f t h e p o l y t o p e P i s connected.  Thus  by t h e v e r t i c e s a n d  which a r e not c o n t a i n e d i n the f a c e t  But this  F  i s i m p l i e d by t h e f o l l o w i n g Lemma 3.6. Q.E.D.  3.6:  Lemma  L e t P be a d - p o l y t o p e , d > l , a n d l e t F be a f a c e t o f P. The g r a p h f o r m e d contained  by t h e v e r t i c e s a n d e d g e s o f P  which  are not  i n F i s connected.  Proof; We  have  to  show  that  contained i nF there i s a  f o r e a c h p a i r v,w o f v e r t i c e s o f P n o t path  from  v  to  w  containing  no  v e r t i c e s o r e d g e s o f F.  I n d u c t i o n on t h e d i m e n s i o n d: (i)  The s t a t e m e n t i s o b v i o u s l y t r u e f o r d=2.  The r e m o v a l o f an  edge f r o m a p o l y g o n l e a v e s a c h a i n o f e d g e s , (i)  Assume t h e s t a t e m e n t 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 a)  three cases:  v a n d w l i e b o t h o n a f a c e t G d o e s n o t i n t e r s e c t F: T h e r e must be a p a t h f r o m v t o w on G b e c a u s e the graph formed  b)  by s k e l  1  b y Lemma 2.7  G i s (d-1)-connected.  v a n d w l i e b o t h on a f a c e t G w h i c h i n t e r s e c t s F: The G.  i n t e r s e c t i o n o f G a n F must be c o n t a i n e d i n a f a c e t o f Hence t h e r e i s a p a t h f r o m v t o w c o n t a i n i n g  no e d g e s  28  or c)  v e r t i c e s o f F by t h e i n d u c t i v e  v and w l i e on d i f f e r e n t  ^  Because its  G  f a c e t s G and G' o f  i-skeleton  is  d-connected.  o f f a c e t s o f P, G  Therefore  s  h  a  r  e  k  is a  Q  and  k  f o r 0<i£k, G^  and  vertices.  T h u s , by v i r t u e o f a) and b) one to  there  by  ,...,G , s u c h t h a t G=G , G'=G ,  i s not c o n t a i n e d i n the sequence,  i-1  P:  the d u a l o f P i s a d - p o l y t o p e the graph formed  sequence F  assumption,  c a n compose a p a t h f r o m v  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  facets  G^  and n o t 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: Given  the  f a c i a l g r a p h 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  d e f i n e d by t h e h y p e r p l a n e I , and a v e r t e x v o f P in  H,  the  constructed  facial  graph  of  the  s i z e of the f a c i a l  contained  contained  P' = Pifii H  can  i n t i m e 0 ( D ( P , H ) + M ( P , H ) ) , where D(P,H) d e n o t e s  number o f n o d e s and e d g e s d e l e t e d the  polytope  not  graph  of  H  be the  f r o m F G ( P ) , a n d M(P,H) d e n o t e s the  facet  of  P*  which  is  i n I.  Proof: As  a consequence  o f Lemma 3.5,  a depth f i r s t  v e r t e x v t h r o u g h t h e g r a p h f o r m e d by  skel^ P  search s t a r t i n g can  be  used  c o n d i t i o n t h e f a c i a l g r a p h o f P t o s e r v e a s an a p p r o p r i a t e for  A l g o r i t h m 3.1.  yields  the  A l g o r i t h m 3.1  sets  Furthermore, the of  depth  b a d , t o u c h , and m i x e d  c a n be a p p l i e d  first  at  search  e d g e s o f P, so  to render the f a c i a l graph o f  to  input also that P . 1  29  The  time  necessary  to  perform  the depth  first  search  p r o p o r t i o n a l t o t h e number o f b a d , t o u c h , and m i x e d e d g e s o f This  number  i s  certainly  less  than  is P.  D(P,H) + M ( P , H ) .  A l g o r i t h m 3.1 t a k e s t i m e 0 ( D ( P , H ) + M(P,H)) b y Lemma 3 . 4 . Q.E.D.  30  IV.  The C o n v e x H u l l  This general point is  section  convex sets  contains  hull  the  the convex h u l l  t h e s e t has been  Before  we  main r e s u l t o f t h i s t h e s i s :  a l g o r i t h m which i s worst  i n even d i m e n s i o n s .  to construct  after  Algorithm  can  The of  hull  represent  of  a  point  The  describe  algorithm  incrementally  any d e t a i l s o f t h e a l g o r i t h m ,  point  set  has a s s o c i a t e d w i t h  of  the  We  its  will facial  which corresponds to a vertex of P of the  u„ w h i c h r  has  vertex.  which corresponds to a f a c e t i t a vector  we  a r e as f o l l o w s :  i t the c o o r d i n a t e s  E a c h node o f FG(P)  definition  version  m o d i f i c a t i o n s o f FG(P)  associated with  By  i s a polytope.  P by an augmented  E a c h node o f F G ( P )  2)  set  for  presorted.  finite  a polytope  graph FG(P). 1)  a  optimal  main i d e a o f the  have t o s e t t l e t h e i s s u e o f r e p r e s e n t a t i o n . convex  case  a  F  of  i s orthogonal  P to  F. As  shown  i n Lemma 2.13,  of a d-polytope  t h e s i z e o f t h e augmented f a c i a l  P = c o n v S,  where  S  contains  n  graph  points,  is  0(nL<V J). 2  Let Recall, FG(P)  us  now  t u r n our a t t e n t i o n t o the concept o f  that i f the d i r e c t i o n are  reversed,  of a l l arcs  the r e s u l t i n g  of  a  duality.  facial  graph i s the f a c i a l  graph  graph  of  * some p o l y t o p e  P , t h e d u a l o f P.  c o n d i t i o n s t h i s i s even  We  argue  that  under  t r u e f o r an augmented f a c i a l  certain  graph.  31  Assume t h a t t h e i n t e r i o r origin, of P  of  a  and l e t F be a f a c e t o f P.  dual  to  F  which contains  i s the  polytope  P  contains  the  B y Lemma 2.8, t h e v e r t e x F*  s e t {y e P |<x,y> = 1  j u s t one e l e m e n t , t h e v e c t o r  for a l l x eF }  u„ n o r m a l  t o F which  r  is  s c a l e d and o r i e n t e d i n s u c h a way t h a t <x,u.;,> = 1 f o r a l l x  in  F,  and  <x,u > £ 1  f o r a l l x i n P.  p  normalized  c o m p l e m e n t o f F.  a polytope  P  corresponding then  We c a l l  such a u t h e p  I f i n t h e augmented f a c i a l g r a p h o f  w i t h 0 e i n t P t h e v e c t o r a s s o c i a t e d w i t h each to a facet F i s the normalized  FG(P) w i t h  i t s arcs reversed  complement  node  of  i s t h e augmented f a c i a l  F,  graph  * of P . ways:  I n other  w o r d s , s u c h a g r a p h c a n be i n t e r p r e t e d  i n two  as  t h e augmented f a c i a l g r a p h o f P, o r a s t h e augmented * f a c i a l graph o f P .  How c a n we make u s e  of  this  algorithm?  We  exploit  problem  an  intersection  to  definition  of  =  duality  by  problem.  Recall,  and  = rt{H |v  i n v}, where H  v  in a  reducing  polarity  0 e i n t P, t h e n P It  duality  Lemma 2.8,  not  n H ).  As  distinguish  problem o f f i n d i n g  our  representation  between  duals,  t h e convex  hull  t h e convex that  hull  by t h e  i f P = conv V  and  = {x eR |<x,v> * l } .  v  f o l l o w s , t h a t f o r a n y qeR , ( c o n v ( P u { q } ) ) * (P  convex  = (conv(Vu{q})) of  this  polytopes  implies  h u l l o f P u { q } c a n be  =  does  that  the  reduced  to  * the problem o f i n t e r s e c t i n g In  the previous  P  with  section  c o n s t r u c t s s u c h an i n t e r s e c t i o n .  the halfspace H .  we p r e s e n t e d  an a l g o r i t h m  However, t h i s a l g o r i t h m  which makes  32  ie  the  assumptions, that P *  i.e. In  a vertex  of P  ic  nH  ic  / P , and t h a t a bad v e r t e x *  of P ,  n H , is  known.  which i s not a vertex  of P  t h e f o l l o w i n g we show how t h e s e a s s u m p t i o n s c a n be met i n an  incremental  convex  hull  algorithm.  D e f i n i t i o n £.1: L e t p,q e R , p = ( p r . . . p ) , X  d  q=(q /...q ). 1  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 p  l  <  q  l '  Observe,  o  r  i  that  f  l  p  =  a  l  q  a  set  l e x i c o g r a p h i c a l order fundamental  n  (P2'-*'P  d  of  n  , ) a  *L  points  (  T  q,  i f  2"" d * q  R  in  i n time 9(nlogn).  connection  q  than q, p <  d  )  c a n be s o r t e d  into  The n e x t lemma d r a w s  between l e x i c o g r a p h i c a l order  a  and c o n v e x  hulls.  Lemma 4 _ . l : S cR  Let  be  d  a finite  s e t o f d i s t i n c t p o i n t s , l e t P = conv  and l e t p be t h e maximum e l e m e n t o f S u n d e r ordering.  F u r t h e r m o r e , l e t q be a p o i n t  the  in R  d  S,  lexicographical with p <  r  q , and  Li  l e t Q = conv(S u {q}). 1)  p i s a vertex  2)  There  o f P and qd P.  i s a f a c e t o f P which contains  p and w h i c h  is  not  a  f a c e t o f Q.  Proof: First system  note such  that i t i s always p o s s i b l e t o r o t a t e the that  the  lexicographical  ordering  coordinate  o f S u {q} i s  33  preserved  i n S u{q}  but a l l the points  differ  in  their  first  coordinate. We assume t h a t s u c h a r o t a t i o n h a s been a p p l i e d . it  clear  h o w e v e r , t h a t t h i s a s s u m p t i o n i s made o n l y  of s i m p l i c i t y o f the proof. s u c h a r o t a t i o n n e v e r need  1)  We want t o make  Let  u=  In the algorithm  be  presented  be p e r f o r m e d .  (1,0,...,0).  different  to  f o r t h e sake  our assumption a l l elements o f S  By  from p have a s t r i c t l y  smaller  first  coordinate.  Hence <x-p,u> < 0 f o r a l l x e S , x ^ p , and a s a c o n s e q u e n c e  of  Lemma 2.3, <x-p,u> < 0 f o r a l l x e p , x,*p.  As  H = {x e R |<x-p,u> = 0}  h y p e r p l a n e o f P,  P nH = {p}f  is  a  and p i s a v e r t e x o f P.  By a s s u m p t i o n q h a s a s t r i c t l y p.  supporting  <p-p,u> = 0,  greater  first  coordinate  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  than  q f r o m P, and  q I P. 2)  L e t A = { F , . . . , F } be t h e s e t o f f a c e t s o f P w h i c h 1  p.  By  contain  k  Lemma 2.5  k£d.  For  i=l,...,k  l e t a ^ be a v e c t o r  orthogonal  t o F., o r i e n t e d s u c h t h a t <x-p,a.> £ 0 f o r a l l x k N o t e , t h a t by d u a l i t y and Lemma 2.3 u = \ c . a . , w h e r e 1  in  P.  c^O As  1  i=l  1  1  for a l l i . p <  L  q  and  as t h e i r  first  coordinate  <q-p,u> > 0. But k k <q-p,u> = <q-p, ][ c^a^> = £c.<q-p,a.>.  a r e assumed t o be  different,  i=l  negative, Fj  i=l  <q-p,a^> > 0 f o r some j , l ^ j ^ k .  c a n n o t be a f a c e t o f Q = c o n v ( P  As  a l l c ^ a r e non But then  clearly  u{q}). Q.E.D.  34  The  following corollary  i s the dual  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: Let and  S cR  be a f i n i t e  l e t 0 e i n t P.  setof  L e t p be  distinct points,  l e t P = c o n v S,  t h e maximal element o f S under t h e d  lexicographical ordering  1)  The and  and l e t q be a p o i n t  in R  h y p e r p l a n e {x eR |<x,p> = l } c o n t a i n s d  4 P*, w h e r e H  P* n H  w i t h p <_  q.  Li  a f a c e t p' o f P*,  = {xeR |<x,q> s l } . d  * 2)  There  i s a vertex of P * a vertex of P n H . q  not  contained  i n t h e f a c e t p' w h i c h i s  Proof: Follows We  immediately  now  f r o m Lemma 4.1 a n d d u a l i t y .  have a l l t h e  Q.E.D.  t o o l s needed t o s p e c i f y t h e 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 t h e convex h u l l o f a f i n i t e p o i n t  set.  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  hull.  The  algorithm  takes  as i n p u t a s e t S c R  I t outputs  t h e augmented  specified  a t the beginning  1.  facial  graph  convex  of n distinct of  conv  S  as  points. i tis  of this section.  Sort S into l e x i c o g r a p h i c a l order. Having sorted S lii<n, For  s. <  lsj^n  L  s.  f  + 1  we c a n  write  S = {s^,...,s  },  where f o r  .  l e t S.. = { s e S|s <  L  s^},  l e t P.. = c o n v S ^ , a n d l e t  P -^ = c o n v S = P. n+  2.  C o n s t r u c t i o n o f an i n i t i a l Let  k,  d£k<n,  be  such  (d-1)-polytope. that  dim  S^ = d - 1 , - b u t d i m  35  S  k+1  =  d  *  Embed a f f S  in R  k  d—1  and i n d u c t i v e l y c o n s t r u c t t h e f a c i a l  graph o f the (d-1)-polytope  = c o n v S^.  k  (By  convention  (the  empty s e t ) be a g r a p h c o n s i s t i n g o f one node.)  By  P  k +  l e t the f a c i a l graph o f the  Definition  with basis P ^  k  2.15  k i  P  conv(P^ u ^ k ^ *  =  s  +  and a p e x s ^ .  Construct  from FG(P ) as s p e c i f i e d k  Translate a l l points contained  in  of  the  S,  (-1)-polytope  s  ^~Py  a  the f a c i a l  after  Lemma 2.9.  such  that  interior  characterizes the i n t e r i o r  3.  P  of  points of a  P  the  k+i'  origin  polytope.)  e a c h node o f F G ( P ^ ) c o r r e s p o n d i n g  vertex of  P^+i  the  associate  with  e a c h node o f F G ( P ^ ) c o r r e s p o n d i n g  facet  the the normalized  k +  As t h e o r i g i n can i  vertex,  to a and to a  complement o f t h i s f a c e t .  points.  t o n+1 do  C o n s t r u c t P^+i  H  this  k +  I n s e r t the remaining i=k+l  of  is  (Lemma 2.3  with  coordinates  i^  graph o f  Associate  For  r a m  be  conv(P^  =  i s contained done  = {x g R  u{s^}). i n the i n t e r i o r  by  intersecting  of  P., * P^l  this and  |<x,s > £ l } . i  * * By C o r o l l a r y 4.1 P^ n f P^ * P^ c o n t a i n e d i n t h e f a c e t  and one o f t h e v e r t i c e s o f * o f P^ d u a l t o t h e v e r t e x * i - l i k °f i with respect to . * I n t e r p r e t F G ( P ^ ) a s t h e f a c i a l g r a p h o f P^ and f i n d a * vertex contained i n t h e f a c e t s! , o f P. w h i c h i s n o t i-i I c o n t a i n e d i n H.. s  o  f  P  1  S  a  a d  v  e  r  t  e  x  p  36  A p p l y Theorem 3.1 t o c o n s t r u c t t h e augmented f a c i a l * * of  P^ 2  =  i  P  +  n  H  i*  B  duality  y  this  graph  i n t e r p r e t e d as the f a c i a l graph o f 4.  p  can  graph  also  be  ^ ^» +  Cleanup  Undo t h e 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 t h e p o i n t s o f S.  Theorem £.1^ Let  S <= R  be a s e t o f  d  n  distinct  points  with  d i m 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 t h e augmented f a c i a l g r a p h o f conv S i n time 0(nL(<3+l)/2j^^  This i s worst  case  optimal  for  from  Theorem  3.1,  e v e n d. Proof: The c o r r e c t n e s s  of  the  d u a l i t y , and C o r o l l a r y  algorithm  follows  4.1.  F o r t h e t i m e bound c o n s i d e r t h e 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 Step  r e q u i r e s time O(nlogn).  2: The k c a n be f o u n d i n 0(k)  time.  By i n d u c t i o n , t h e f a c i a l g r a p h o f P^ c a n be time P  k+1  0(k L^/ J) . 2  c  a  Using  n  ^  fc  en  dearly  a l s o be c o n s t r u c t e d i n t i m e  Lemma 2.3, t h e t r a n s l a t i o n  time.  Furthermore,  associated with  in  The augmented f a c i a l g r a p h o f t h e p y r a m i d  r e q u i r e d c a n be  i n 0(k) t i m e , and i t c a n be a p p l i e d linear  constructed  the  nodes  v e r t i c e s and f a c e t s o f P  k +  ^  to a l lpoints  0(k^  d / /  "^).  determined of  S  in  t h e a p p r o p r i a t e new v a l u e s c a n be of  FG(P^ ^)  corresponding  +  i n time 0 ( k L / - l ) . d  2  to  37  S t e p 3: By  Lemma 2.10 and d u a l i t y , t h e f a c e t s ! ^ o f P.^ c a n c o n t a i n  a t most 0 ( i U ) / J ) v e r t i c e s . Using the f a c i a l graph o f * P^, a l l t h e s e v e r t i c e s , and i n p a r t i c u l a r a b a d v e r t e x w i t h d _ 1  2  r e s p e c t t o H ^ , c a n be f o u n d i n t i m e Applying  Theorem 3.1,  i t takes  0(iL(  d - 1  )/ J) 2  m  time 0 ( M ( P ? , H ) +  D(P?,H^))  I  *  to i n t e r s e c t P and H.^. A s r e m a r k e d before Lemma 3.4, * M(P ,H ) 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 graph o f * the newly c r e a t e d f a c e t s j o f Thus b y Lemma 2.13 i  I  I  M(P*,H.)  is  O U ^ - D /  2  - ] ) .  * Observe, that D ( P , H ) i s p r o p o r t i o n a l * I  nodes  and  w i t h H.. created  arcs  As  to  I  deleted  only  t h e number  of  *  f r o m FG(P^) when P^ i s i n t e r s e c t e d = O(i L  0(M(P*,R\))  ( d _ 1 ) / 2  J )  faces  are  f o r every i>k,  0(J / J) D  <  TLMP*,H.)  2  i=k+l  '. f o( L(d-l)/2J n  +  1  1  )  0  =  {  n  l(d l)/2J +  N  i=k+l  Thus ^ O W P * , ^  + D(P*,H.))  =  0(nl-  ( d + 1 )  / J) i s the t o t a l 2  i=K+l  t i m e needed f o r s t e p 3.  As  s t e p 4 c a n c l e a r l y be p e r f o r m e d i n l i n e a r  worst  case  O(nlogn For  +  n^  time ( d + 1 )  complexity  of  time,  the entire  the  algorithm  2  even d > 2 t h i s  i s o p t i m a l b e c a u s e b y Lemma 2.13 t h e s i z e o f  i s o p t i m a l because there  i s an  -l) . lower  bound f o r t h e c o n s t r u c t i o n o f t h e c o n v e x h u l l o f a p l a n a r  point  [15].  this  d / / 2  ft(nlogn)  set  d = 2  is  / J).  t h e d e s c r i p t i o n o f t h e f a c i a l g r a p h o f c o n v S c a n be 0 ( n L For  total  Q.E.D.  38  V.  Conclusion  The  main  r e s u l t of t h i s  with O(nlogn + formulation  of  extensively. to  n ^  polytope  ^ /  2  J )  this  be  the  convex  h u l l algorithm without  conv(Pu{v}) i n terms o f the  i t i s claimed  t h a t the convex h u l l  in  a  identify  this  case  t h e s i s i s worst case o p t i m a l the convex  s i z e of  the  complexity case has  He to  of  more.  n  Therefore  L t / 2 j j^  a l o w e r bound o f  of  be of  d  n  conv  S. a  i t i s possible  F Q r  t  ^  p  e  the  l  time a  n  a  r  problem  Q. ( n l o g n ) .  convex h u l l  algorithm  for point sets  was  t h e m a j o r o p e n p r o b l e m s s t a t e d i n t h e work o f B r o w n [ 3 ] .  showed t h a t a number o f g e o m e t r i c a l the  a s e t S <= R  [15] p r o v e d t h a t t h i s v a r i a n t o f  F i n d i n g an o p t i m a l one  given  in  f a c i a l graph o f conv S i s not  i s b e t t e r than O(nlogn + Yao  the  also  i s a s o l u t i o n f o r t h i s p r o b l e m whose w o r s t c a s e  however, still  the  algorithm  could  the p o i n t s of S which are v e r t i c e s the  of  of  for point sets  problem  t o t a l l y d i f f e r e n t way:  l o w e r bound f o r t h i s p r o b l e m any there  hull  use  faces of  I n Theorem 4.1  points,  that  characterization  purpose.  formulated  i s used  the  used f o r t h i s  But  the  n o t e d h o w e v e r , t h a t i t seems p o s s i b l e  P c o u l d be  even d i m e n s i o n s .  In  concept of d u a l i t y  Gruenbaum's ( [ 6 ] , p.78)  in this  algorithm  worst case time complexity.  algorithm  the polytope  presented  In  1  I t should  dualization. of  +  the  reformulate  faces  d  t h e s i s i s a convex h u l l  convex  transformation.  hull  problem  I n p a r t i c u l a r , he  by  p r o b l e m s c o u l d be the  use  of  reduced  geometric  showed t h a t c o n s t r u c t i n g  the  0  39  diagram of a set S c R  Voronoi  i s equivalent to contructing  u  the  (3 "Hi  h u l l o f a s e t S' c R  convex  hypersphere.  As  Voronoi diagram hull  Klee  in R  algorithm  d  , where a l l p o i n t s o f S'  [9]  showed,  ! - ^  d  ^ ^ /  +  2  J  )  ,  the  which  dimension.  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  in  a r b i t r a r y dimensions  based  on  a  similar  algorithm of this claimed the  in  is  these  optimal  incremental  point  sets  published,  approach  in  odd  diagrams  which  are  as the convex  hull  However, t h e s u b q u a d r a t i c t i m e bounds  p a p e r s seem t o be b a s e d  on a s s u m p t i o n s  about  d i s t r i b u t i o n o f t h e i n p u t p o i n t s and c l e a r l y c a n n o t be  worst  c a s e b o u n d s by K l e e ' s l o w e r bound A the  for  ( [ 2 ] , [ 1 4 ] ) , were  thesis.  convex  i n t h i s thesis also y i e l d s a Voronoi  diagram a l g o r i t h m Rather  a  that the d e s c r i p t i o n of a  c a n be o f s i z e 0 ( n  presented  l i e on  very s t r i k i n g  p o i n t o f the main r e s u l t  f a c t t h a t the convex  dimensions, Naturally  whereas  result.  hull  this  algorithm  cannot  for  point  there  bound  of  even  algorithm  for with  the  three  optimal,  c o m p l e x i t y i s known e v e n suggest  that  a  i f  there  will  even  dimensions. convex  hull  ) , which  is  a  trivial  the p r o b l e m , as t h e f a c i a l g r a p h o f the  h u l l o f n p o i n t s can have t h i s s i z e . that  is  for  s e t s i n odd d i m e n s i o n s g r e a t e r t h a n t h r e e  w i t h worst case time c o m p l e x i t y 0(n lower  thesis i s  optimal  be shown f o r odd  the q u e s t i o n a r i s e s whether  algorithm  is  in this  dimensional  i.e.  an  case  O(nlogn),  i f a presort is  I t i s interesting  d  2  have t o use an a p p r o a c h  to  note  incremental  worst  i s allowed.  0(n^ ^ J)  no  convex  case  time  T h i s seems t o  algorithm  dimensions,  i t  entirely  f r o m t h e one  t a k e n by t h e a l g o r i t h m p r e s e n t e d i n t h i s  for  odd  different thesis.  40  REFERENCES  [I]  B e n t l e y , J . L . and Shamos, M.I., D i v i d e and C o n q u e r f o r L i n e a r E x p e c t e d T i m e , Info. Proc. L e t t e r s 7, 2, F e b . 1 9 7 8 , p p . 8 7 - 9 1 .  [2]  B o w y e r , 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 Journal, vol. 24, pp.162-166.  no.2,  1981,  [3]  B r o w n , K.Q., Geometric Transforms f o r Fast Geometric Algorithms, Ph.D. t h e s i s , D e p t . 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]  C h a n d , D.R. and K a p u r , 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 . 1 9 7 0 , p p . 7 8 - 8 6 .  [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 t h e C o n v e x H u l l of a Planar Set, Info. Proc. L e t t e r s 1, 4, J u n e 1 9 7 2 , p p . 1 3 2 - 1 3 3 .  [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 T h e o r y , A d d i s o n - W e s l e y , 1969.  [8]  J a r v i s , R.A., On t h e I d e n t i f i c a t i o n o f t h e C o n v e x H u l l o f Set o f P o i n t s i n the Plane, Info. Proc. L e t t e r s 2, 1 9 7 3 , p p . 1 8 - 2 1 .  a  Finite  [9]  K l e e , V., On t h e 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 D i a g r a m s , Arch. M a t h . , v o l . 34, 1 9 8 0 , p p . 7 5 - 8 0 .  [10]  M c M u l l e n , P., The Maximum Number o f F a c e s o f a C o n v e x M a t h e m a t i k a 17, 1970, pp.179-184.  [II]  Polytope,  M c M u l l e n , P. and S h e p h a r d , G . C , C o n v e x P o l y t o p e s and t h e Upper Bound C o n j e c t u r e , L o n d o n M a t h l S o c i e t y L e c t u r e N o t e S e r i e s 3, C a m b r i d g e Univ. P r e s s , 1971.  41  [12]  P r e p a r a t a , F., An Optimal Real-Time A l g o r i t h m f o r Planar Hulls, C.ACM 2 2 , 7, J u l y 1 9 7 9 , p p . 4 0 2 - 4 0 5 .  Convex  [13]  P r e p a r a t a , F. a n d 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 T h r e e Dimensions, C.ACM 2 0 , 7, 1 9 7 7 , p p . 8 7 - 9 3 .  [14]  W a t s o n , D.F., Computing t h e 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 Voronoi Polytopes, The Computer Journal, vol. 24, no.2, 1981, pp.167-172.  [15]  Y a o , A., A Lower Bound t o F i n d i n g C o n v e x H u l l s , Rep. STAN-CS-79-733, D e p t . 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