$ od -c -N 50000 [Cyan]<PreISLCedar>Stolfi>Geo>Tracings.mail!1
0000000 * s t a r t * \r 0 1 9 8 5 0 0
0000020 0 9 5 U S \r g v M s g I D :
0000040 R a m s h a w . p a $ 3 #
0000060 1 4 @ 2 0 - A u g - 8 3 1 1 :
0000100 5 1 : 4 5 P D T \r C a t e g o
0000120 r i e s : T r a c i n g s \r D
0000140 a t e : 2 0 A u g 8 3 1
0000160 1 : 5 1 : 4 5 P D T \r F r o m
0000200 : R a m s h a w . p a \r S u b
0000220 j e c t : E u r e k a ! I
0000240 ' v e f o u n d i t ! (
0000260 P e r h a p s ! ) \r T o : G u
0000300 i b a s , S t o l f i \r c c :
0000320 R a m s h a w \r \r I t h i n
0000340 k t h a t I h a v e f i
0000360 g u r e d o u t t h e r e
0000400 a l p r o d u c t r u l e !
0000420 O f c o u r s e , I ' v
0000440 e t h o u g h t t h a t b
0000460 e f o r e a n d b e e n w
0000500 r o n g , s o d o n ' t g
0000520 e t t o o e x c i t e d .
0000540 A t l e a s t , I h a v
0000560 e a r u l e t h a t w o
0000600 r k s c o r r e c t l y i n
0000620 e v e r y e x a m p l e t
0000640 h a t I h a v e t r i e d
0000660 s o f a r , i n c l u d i
0000700 n g t h o s e w i t h f u
0000720 l l t u r n s o f a r b i
0000740 t r a r y m u l t i p l i c i
0000760 t y . \r \r T h e c e n t r a l
0001000 i d e a o f t h i s n e
0001020 w a p p r o a c h i s t o
0001040 a d d i n o n e m o r e
0001060 k i n d o f t h i n g w
0001100 h e n c o m p u t i n g p r
0001120 o d u c t s i n a d d i t i
0001140 o n t o e v e r y t h i n g
0001160 t h a t w e u s e d t o
0001200 b e t h r o w i n g i n .
0001220 I n p a r t i c u l a r ,
0001240 s u p p o s e t h a t b o
0001260 t h L a n d R i n c l u
0001300 d e a t u r n a t a p
0001320 o i n t p . U n d e r t
0001340 h e o l d r u l e s , t h
0001360 e s e t w o t u r n s i n
0001400 f l u e n c e d e a c h o t
0001420 h e r a s f o l l o w s :
0001440 t h e L t u r n c o n t
0001460 r i b u t e d t o t h e w
0001500 i n d i n g n u m b e r o f
0001520 L a t p , w h i c h a
0001540 f f e c t e d t h e m u l t
0001560 i p l i c i t y w i t h w h
0001600 i c h t h e R w a s i n
0001620 c l u d e d ; a n d v i c
0001640 e v e r s a . U n d e r
0001660 m y n e w r u l e s , t h
0001700 i s c o n t i n u e s t o
0001720 h a p p e n a s b e f o r e
0001740 . B u t i n a d d i t i
0001760 o n , I p r o p o s e t h
0002000 a t t h e t w o t u r n s
0002020 a l s o h a v e a d i r
0002040 e c t i m p a c t o n e a
0002060 c h o t h e r : t h e y
0002100 c a u s e u s t o a d d
0002120 a t u r n c o r r e s p o n
0002140 d i n g t o t h e i r i n
0002160 t e r s e c t i o n w i t h
0002200 m u l t i p l i c i t y t h e
0002220 n e g a t i v e o f t h e
0002240 p r o d u c t o f t h e i
0002260 r m u l t i p l i c i t i e s
0002300 . W i e r d , e h ? I
0002320 n e v e r w o u l d h a v
0002340 e g u e s s e d i t , a n
0002360 d m a y b e i t ' s a l l
0002400 w r o n g . B u t i t
0002420 d o e s s o l v e a n a w
0002440 f u l l o t o f p r o b l
0002460 e m s . \r \r T h u s , m y p
0002500 r o p o s e d r u l e s f o
0002520 r p r o d u c t : \r \r i ) A
0002540 d d e a c h t u r n o r
0002560 m o v e o f L a s o f t
0002600 e n a s i t i s w o u n
0002620 d b y R ; \r \r i i ) A d d
0002640 e a c h t u r n o r m o
0002660 v e o f R a s o f t e n
0002700 a s i t i s w o u n d
0002720 b y L ; \r \r i i i ) A d d
0002740 p a t c h i n g t u r n s :
0002760 f o r e a c h p a i r o
0003000 f s t a t e s x , y w i
0003020 t h p o s ( x ) = p o s ( y )
0003040 a n d \r \t \t a n g l e ( x ) <
0003060 a n g l e ( y ) < a n g l e ( x
0003100 ) + p i , \r a d d t h e t u
0003120 r n f r o m x t o y w
0003140 i t h m u l t i p l i c i t y
0003160 o n e - h a l f o f t h e
0003200 q u a n t i t y : \r \t \t m + (
0003220 L , x ) * m - ( R , y ) + m
0003240 - ( L , x ) * m + ( R , y ) +
0003260 m + ( R , x ) * m - ( L , y )
0003300 + m - ( R , x ) * m + ( L ,
0003320 y ) . \r \r i v ) A d d n e w
0003340 f u n n y t u r n s : f
0003360 o r a l e f t t u r n i
0003400 n L w i t h m u l t i p l
0003420 i c i t y t L a n d a c
0003440 o i n c i d e n t l e f t t
0003460 u r n i n R w i t h m u
0003500 l t i p l i c i t y t R , a
0003520 d d t h e i n t e r s e c t
0003540 i o n o f t h e t w o t
0003560 u r n s t o t h e p r o d
0003600 u c t w i t h m u l t i p l
0003620 i c i t y \r \t \t - t L * t R . \r
0003640 \r T r y i t , y o u ' l l
0003660 l i k e i t . \r \r L y l e \r \r
0003700 \r * s t a r t * \r 0 1 1 9 7 0
0003720 0 0 9 4 U S \r g v M s g I D
0003740 : G u i b a s . p a $ 3 #
0003760 1 4 @ 2 0 - A u g - 8 3 1 8 :
0004000 4 0 : 1 8 P D T \r C a t e g o
0004020 r i e s : T r a c i n g s \r D
0004040 a t e : 2 0 A u g 8 3 1
0004060 8 : 4 0 : 1 8 P D T \r F r o m
0004100 : G u i b a s . p a \r S u b j
0004120 e c t : R e : E u r e k a !
0004140 I ' v e f o u n d i t !
0004160 ( P e r h a p s ! ) \r I n -
0004200 r e p l y - t o : " R a m s h
0004220 a w ' s m e s s a g e o f
0004240 2 0 A u g 8 3 1 1 : 5 1 :
0004260 4 5 P D T " \r T o : R a m s
0004300 h a w \r c c : G u i b a s ,
0004320 S t o l f i \r \r L y l e : \r \r I
0004340 h a v e n o t y e t h a
0004360 d t h e c h a n c e t o
0004400 p l a y w i t h y o u r r
0004420 u l e e x t e n s i v e l y ,
0004440 b u t s t y l i s t i c a l
0004460 l y ( I t h i n k ) i t
0004500 w o u l d b e p r e f e r a
0004520 b l e t o h a v e o n e
0004540 t h a t i s e x p r e s s e
0004560 d e i t h e r ( 1 ) p u r
0004600 e l y i n t e r m s o f
0004620 m o v e s a n d t u r n s
0004640 g i v i n g r i s e t o o
0004660 t h e r m o v e s a n d t
0004700 u r n s , o r ( 2 ) p u r
0004720 e l y i n t e r m s o f
0004740 p a i r s o f s t a t e s
0004760 g i v i n g r i s e t o o
0005000 t h e r s t a t e s . S i n
0005020 c e p r o d u c t r e q u i
0005040 r e s t h e i n t r o d u c
0005060 t i o n o f p a t c h i n g
0005100 t u r n s , a r u l e o
0005120 f s t y l e ( 1 ) c a n
0005140 o n l y w o r k i f a l l
0005160 m o v e s o f L a n d
0005200 R a r e d e c o m p o s e d
0005220 a t a l l c o m m o n p
0005240 o i n t s o f L a n d R
0005260 . A r u l e o f s t y l
0005300 e ( 2 ) w o u l d b e c
0005320 l o s e r t o a f i b e r
0005340 p r o d u c t d e f i n i t
0005360 i o n a n d p r o b a b l y
0005400 h a s t o h a v e e m b
0005420 e d d e d i n i t o u r
0005440 w i n d i n g n u m b e r c
0005460 o n v e n t i o n s . I n p
0005500 a r t i c u l a r , c a s e s
0005520 ( i ) a n d ( i i ) o f
0005540 y o u r r u l e s h o u l
0005560 d t h e n b e c o m e c o
0005600 n s e q u e n c e s . C a s e
0005620 ( i i i ) i s a l r e a d
0005640 y e s s e n t i a l l y i n
0005660 a ( s t a t e , s t a t e )
0005700 = > s t a t e f o r m ,
0005720 a n d c a s e ( i v ) c a
0005740 n b e c a p t u r e d b y
0005760 s a y i n g t h a t t w o
0006000 c o i n c i d e n t t u r n
0006020 i n g s t a t e s o f L
0006040 a n d R g i v e r i s e
0006060 t o t h e s a m e t u r n
0006100 i n g s t a t e i n L R
0006120 w i t h c o e f f i c i e n t
0006140 - 1 . \r \r \t L e o \r \r \r * s
0006160 t a r t * \r 0 0 7 7 1 0 0 0 9
0006200 5 U S \r g v M s g I D : R
0006220 a m s h a w . p a $ 3 # 1 4
0006240 @ 2 8 - A u g - 8 3 0 : 1 6
0006260 : 0 6 P D T \r C a t e g o r i
0006300 e s : T r a c i n g s \r D a t
0006320 e : 2 8 A u g 8 3 0 :
0006340 1 6 : 0 6 P D T \r F r o m :
0006360 R a m s h a w . p a \r S u b j e
0006400 c t : m i n o r t w i d d l
0006420 e t o L e o ' s p r o d u
0006440 c t f o r m u l a \r T o : G
0006460 u i b a s , S t o l f i \r c c
0006500 : R a m s h a w \r \r L e o a
0006520 n d J o r g e , \r \r I w o r
0006540 k e d o n p r o v i n g t
0006560 h e r e l a t i o n b e t w
0006600 e e n w i n d i n g n u m b
0006620 e r o f t h e p r o d u c
0006640 t a n d p r o d u c t o f
0006660 t h e w i n d i n g n u m
0006700 b e r s t h i s e v e n i n
0006720 g . I t t u r n s o u t
0006740 t h a t , w i t h t h e
0006760 a d d i t i o n o f o n e
0007000 m o r e t e r m t o L e o
0007020 ' s f o r m u l a , w e a
0007040 r r i v e a t a f o r m u
0007060 l a t h a t a l w a y s h
0007100 o l d s , e v e n i f t h
0007120 e t w o t r a c i n g s b
0007140 e i n g m u l t i p l i e d
0007160 i n c l u d e o p p o s i t e
0007200 s t a t e s . T h e a d
0007220 d i t i o n a l t e r m d i
0007240 d n ' t s h o w u p i n
0007260 L e o ' s a n a l y s i s b
0007300 e c a u s e i t i s o n l
0007320 y n o n z e r o w h e n t
0007340 h e t w o f a c t o r s d
0007360 o i n c l u d e o p p o s i
0007400 t e m o v e s . T h e c
0007420 o m p l e t e f o r m u l a
0007440 i s o n m y w h i t e b o
0007460 a r d i n b r o w n . I
0007500 w i l l t r y a n d T e
0007520 X o u t t h e p r o o f
0007540 t o m o r r o w , \r \r L y l e \r
0007560 \r * s t a r t * \r 0 0 8 6 2 0
0007600 0 0 9 5 U S \r g v M s g I D
0007620 : R a m s h a w . p a $ 3
0007640 # 1 4 @ 2 6 - S e p - 8 3 1 3
0007660 : 1 8 : 0 1 P D T \r C a t e g
0007700 o r i e s : T r a c i n g s \r
0007720 D a t e : 2 6 S e p 8 3
0007740 1 3 : 1 8 : 0 1 P D T \r F r o
0007760 m : R a m s h a w . p a \r S u
0010000 b j e c t : t r a c i n g s :
0010020 a n e m b a r a s s i n g
0010040 a d m i s s i o n \r T o : S
0010060 t o l f i , G u i b a s \r C c
0010100 : R a m s h a w \r \r I a m
0010120 s t a r t i n g t o r e w r
0010140 i t e m y t r a c i n g s
0010160 p r o o f s t o h a n d l e
0010200 t h e p i e c e w i s e r
0010220 e a l a n a l y t i c c a s
0010240 e , i n s t e a d o f t h
0010260 e p i e c e w i s e l i n e
0010300 a r c a s e ( a l l i n
0010320 t h e p l a n e , t h o u g
0010340 h ; n o h i g h e r d i
0010360 m e n s i o n s y e t ) .
0010400 I h a v e f i n i s h e d
0010420 t h e p r o o f o f b a l
0010440 a n c e f o r c o n v o l u
0010460 t i o n , a n d I ' m w o
0010500 r k i n g o n t h e p r o
0010520 o f o f i n t e g r a l i t
0010540 y f o r c o n v o l u t i o
0010560 n . I n t h e p r o c e
0010600 s s , I d i s c o v e r e d
0010620 a n e m b a r a s s i n g
0010640 t h i n g : m y p o l y g
0010660 o n a l p r o o f i s w r
0010700 o n g ! ! O n p a g e 2
0010720 o f m y p r e - L a b o r
0010740 D a y n o t e s , n e a r
0010760 t h e e n d o f t h e
0011000 p a g e , I c l a i m " t
0011020 h e t h i r d s u m s i m
0011040 p l i f i e s b y a l g e b
0011060 r a t o . . . " ; b
0011100 u t i t d o e s n ' t .
0011120 I s h a l l p a t c h t h
0011140 e p o l y g o n a l v e r s
0011160 i o n f i r s t , t h e n
0011200 r e t u r n t o e x t e n d
0011220 i n g t h e a r g u m e n t
0011240 s t o t h e p i e c e w i
0011260 s e r e a l a n a l y t i c
0011300 c a s e , \r \r L y l e \r \r \r *
0011320 s t a r t * \r 0 0 6 2 8 0 0 0
0011340 9 5 U S \r g v M s g I D :
0011360 R a m s h a w . p a $ 3 # 1
0011400 4 @ 2 6 - S e p - 8 3 1 4 : 5
0011420 3 : 4 9 P D T \r C a t e g o r
0011440 i e s : T r a c i n g s \r D a
0011460 t e : 2 6 S e p 8 3 1 4
0011500 : 5 3 : 4 9 P D T \r F r o m :
0011520 R a m s h a w . p a \r S u b j
0011540 e c t : p r o o f s t a t e
0011560 \r T o : G u i b a s , S t o
0011600 l f i \r C c : R a m s h a w \r
0011620 \r T h e c o r r e c t p r o
0011640 o f o f i n t e g r a l i t
0011660 y o f t h e c o n v o l u
0011700 t i o n e n d s u p l o o
0011720 k i n g a l o t m o r e
0011740 l i k e t h e l a s t p a
0011760 r t o f t h e p r o o f
0012000 o f t h e c o n v o l u t i
0012020 o n t h e o r e m . F o r
0012040 d e t a i l s i f y o u '
0012060 r e c u r i o u s , l o o k
0012100 a t \r \t / M a x c / R a m s h
0012120 a w / T r a c i n g s . p r e s
0012140 s . \r F o r t h e c u r r e
0012160 n t s t a t e o f m y p
0012200 r o o f s i n t h e p i e
0012220 c e w i s e r e a l a n a l
0012240 y t i c c a s e ( o n l y
0012260 b a l a n c e a n d i n t e
0012300 g r a l i t y o f c o n v o
0012320 l u t i o n a r e d o n e
0012340 s o f a r , a n d n o t a
0012360 t i o n s a r e s t i l l
0012400 s u b j e c t t o c h a n g
0012420 e ) s e e \r \t / M a x c / R a
0012440 m s h a w / S m o o t h T r a c
0012460 i n g s . p r e s s . \r \r L y l
0012500 e \r \r * s t a r t * \r 0 3 0 2 0
0012520 0 0 0 9 5 U S \r g v M s g
0012540 I D : R a m s h a w . p a $
0012560 3 # 1 4 @ 2 8 - S e p - 8 3
0012600 1 6 : 2 2 : 2 3 P D T \r C a t
0012620 e g o r i e s : T r a c i n g
0012640 s \r D a t e : 2 8 S e p 8
0012660 3 1 6 : 2 2 : 2 3 P D T \r F
0012700 r o m : R a m s h a w . p a \r
0012720 S u b j e c t : h e r e i s
0012740 m y m e s s a g e t o A
0012760 n d y O d l y z k o \r T o :
0013000 S t o l f i \r C c : \r \r - - -
0013020 - - - - - - - - - - - - - - - -
*
0013060 - - - \r D a t e : 2 8 S e p
0013100 8 3 1 5 : 3 7 : 2 6 P D T
0013120 \r F r o m : R a m s h a w . p
0013140 a \r S u b j e c t : o r d e r
0013160 i n g a n a l y t i c c u r
0013200 v e s \r T o : r e s e a r c h
0013220 ! r a b b i t ! a m o @ B e r k
0013240 e l e y . A R P A \r C c : G r
0013260 e e n e , G u i b a s , R a
0013300 m s h a w \r \r A n d y , \r \r I f
0013320 f ( x ) a n d g ( x ) a
0013340 r e r e a l a n a l y t i c
0013360 f u n c t i o n s d e f i n
0013400 e d i n a n e i g h b o r
0013420 h o o d o f x = 0 , w e
0013440 c a n o r d e r f a n d
0013460 g u n a m b i g u o u s l y
0013500 b a s e d u p o n t h e i r
0013520 v a l u e s j u s t t o
0013540 t h e r i g h t o f x = 0
0013560 , t h a t i s , f o r a
0013600 l l s u f f i c i e n t l y
0013620 s m a l l p o s i t i v e v
0013640 a l u e s o f x . I f
0013660 f ( 0 ) > g ( 0 ) , t h e n
0013700 f m u s t a c t u a l l y
0013720 e x c e e d g o n a n e
0013740 i g h b o r h o o d ; i f
0013760 f ( 0 ) = g ( 0 ) b u t f '
0014000 ( 0 ) > g ' ( 0 ) , t h e n
0014020 f m u s t e x c e e d g
0014040 o n a n e i g h b o r h o o
0014060 d ; a n d s o o n .
0014100 T h i s o r d e r i n g r e
0014120 l a t i o n o f " e x c e e
0014140 d i n g f o r s m a l l p
0014160 o s i t i v e x " c o r r e
0014200 s p o n d s t o l e x i c o
0014220 g r a p h i c o r d e r o n
0014240 t h e c o e f f i c i e n t
0014260 s o f t h e p o w e r s
0014300 e r i e s . \r \r I n t r y i n
0014320 g t o e x t e n d L e o ,
0014340 J o r g e , a n d m y s
0014360 t u f f o n k i n e t i c
0014400 g e o m e t r y , I h a v e
0014420 r u n a c r o s s t h e
0014440 f o l l o w i n g p a r a m e
0014460 t r i c v a r i a n t o f
0014500 t h e a b o v e p r o b l e
0014520 m ; y o u c a n p r o b
0014540 a b l y s o l v e i t i n
0014560 y o u r s l e e p . \r \r S u
0014600 p p o s e t h a t , i n s t
0014620 e a d o f a n a l y t i c
0014640 f u n c t i o n s , w e h a
0014660 v e a n a l y t i c c u r v
0014700 e s i n t h e p l a n e :
0014720 x ( t ) a n d y ( t )
0014740 a r e r e a l a n a l y t i
0014760 c f u n c t i o n s o f t
0015000 f o r t i n [ 0 , 1 ] .
0015020 E v e n t h o u g h w e
0015040 a r e d e a l i n g w i t
0015060 h p a r a m e t r i c c u r
0015100 v e s , w e a r e n o t
0015120 i n t e r e s t e d i n t h
0015140 e d e t a i l s o f t h e
0015160 p a r a m e t r i z a t i o n
0015200 . T h e r e f o r e , i f
0015220 t w o c u r v e s c a n
0015240 b e m a d e e q u a l o n
0015260 a n e i g h b o r h o o d
0015300 o f 0 b y s o m e r e p
0015320 a r a m e t r i z a t i o n ,
0015340 w e s h a l l c o n s i d e
0015360 r t h e m t o b e t h e
0015400 s a m e c u r v e . ( I
0015420 ' m r e a l l y d e a l i n
0015440 g w i t h t h e g e r m s
0015460 o f c u r v e s , I g u
0015500 e s s . ) L e t u s r u
0015520 l e o u t t h e c u r v e
0015540 s t h a t d o n ' t m o v
0015560 e a t a l l , t h a t i
0015600 s , w h e r e b o t h t h
0015620 e f u n c t i o n s x ( t )
0015640 a n d y ( t ) a r e c o
0015660 n s t a n t f u n c t i o n s
0015700 . O n t h e o t h e r
0015720 h a n d , w e s h a l l a
0015740 l l o w t h e f i r s t f
0015760 e w d e r i v a t i v e s o
0016000 f b o t h x ( t ) a n d
0016020 y ( t ) t o b e s i m u l
0016040 t a n e o u s l y z e r o .
0016060 F o r e x a m p l e , t h
0016100 e s t a n d a r d c u s p
0016120 w i t h x ( t ) = t ^ 2 a n
0016140 d y ( t ) = t ^ 3 i s a
0016160 p e r f e c t l y l e g i t i
0016200 m a t e c u r v e l e a v i
0016220 n g t h e o r i g i n . \r \r
0016240 C o n s i d e r t w o c u r
0016260 v e s t h a t l e a v e t
0016300 h e o r i g i n . T h e i
0016320 r s l o p e s a t t = 0
0016340 a r e w e l l - d e f i n e d
0016360 , b e c a u s e w e h a v
0016400 e r u l e d o u t t h e
0016420 c o n s t a n t c u r v e s .
0016440 I f t h e i r s l o p e
0016460 s a t t = 0 a r e n ' t
0016500 e q u a l , t h a t t e l l
0016520 s u s r i g h t a w a y
0016540 w h a t t h e i r r e l a t
0016560 i v e l o c a t i o n s a r
0016600 e n e a r t h e o r i g i
0016620 n . B u t s u p p o s e
0016640 t h a t t h e i r s l o p e
0016660 s a t t = 0 a r e b o t
0016700 h z e r o ; i n f a c t
0016720 , s u p p o s e t h a t t
0016740 h e y b o t h l e a v e t
0016760 h e o r i g i n t a n g e n
0017000 t t o t h e p o s i t i v
0017020 e x - a x i s . T h i s
0017040 m e a n s t h a t e a c h
0017060 c u r v e w i l l d e t e r
0017100 m i n e y a s a f u n c
0017120 t i o n o f x f o r a l
0017140 l s u f f i c i e n t l y s
0017160 m a l l p o s i t i v e x ,
0017200 a l t h o u g h t h i s f
0017220 u n c t i o n a l r e l a t i
0017240 o n s h i p w o n ' t n e c
0017260 e s s a r i l y b e r e a l
0017300 a n a l y t i c . \r \r M y q
0017320 u e s t i o n i s w h e t h
0017340 e r o r n o t s u c h c
0017360 u r v e s c a n b e o r d
0017400 e r e d b y t h e i r b e
0017420 h a v i o r n e a r 0 i n
0017440 t h e s a m e w a y t h
0017460 a t a n a l y t i c f u n c
0017500 t i o n s c a n b e . A
0017520 s s u m i n g t h a t t w o
0017540 c u r v e s a r e n ' t c
0017560 o i n c i d e n t , w i l l
0017600 o n e o f t h e m a l w a
0017620 y s b e a b o v e t h e
0017640 o t h e r t h r o u g h o u t
0017660 s o m e n e i g h b o r h o
0017700 o d o f t h e o r i g i n
0017720 ? T h e o n l y a l t e
0017740 r n a t i v e t h a t I c
0017760 a n s e e i s t h a t t
0020000 h e t w o c u r v e s w o
0020020 u l d c r o s s e a c h o
0020040 t h e r i n f i n i t e l y
0020060 o f t e n i n e v e r y n
0020100 e i g h b o r h o o d o f t
0020120 h e o r i g i n , a n d I
0020140 d o u b t t h a t a n a l
0020160 y t i c c u r v e s c o u l
0020200 d d o s u c h a t h i n
0020220 g . O n t h e o t h e r
0020240 h a n d , I d o n ' t s
0020260 e e a p r o o f r i g h t
0020300 o f f t h a t i t c o u
0020320 l d n ' t h a p p e n . \r \r L
0020340 y l e \r \r - - - - - - - - -
0020360 - - - - - - - - - - - - - - - -
0020400 - - - - - - - - - - - - - \r \r *
0020420 s t a r t * \r 0 0 6 1 3 0 0 0
0020440 9 5 U S \r g v M s g I D :
0020460 R a m s h a w . p a $ 3 # 1
0020500 4 @ 2 9 - S e p - 8 3 1 5 : 1
0020520 3 : 5 8 P D T \r C a t e g o r
0020540 i e s : T r a c i n g s \r D a
0020560 t e : 2 9 S e p 8 3 1 5
0020600 : 1 3 : 5 8 P D T \r F r o m :
0020620 R a m s h a w . p a \r S u b j
0020640 e c t : S m o o t h T r a c i
0020660 n g s . t e x , . p r e s s \r
0020700 T o : G u i b a s , S t o l
0020720 f i \r C c : R a m s h a w \r \r
0020740 T h e l a t e s t v e r s i
0020760 o n o f S m o o t h T r a c
0021000 i n g s . p r e s s o n m y
0021020 M a x c d i r e c t o r y
0021040 h a s t h e f o r m u l a s
0021060 d e s c r i b i n g t h e
0021100 l o c a l b e h a v i o r o
0021120 f w i n d i n g n u m b e r
0021140 s , d e f i n e s t h e p
0021160 r o d u c t , a n d s h o w
0021200 s t h a t p r o d u c t s
0021220 a r e a l w a y s b a l a n
0021240 c e d t r a c i n g s . T
0021260 h e n o t a t i o n s a n d
0021300 p r o o f s c a n p r o b
0021320 a b l y b e c l e a n e d
0021340 u p a l o t ; b u t ,
0021360 f o r n o w , I a m g o
0021400 i n g t o p l u n g e o n
0021420 a n d s e e i f I c a
0021440 n g e t t h r o u g h g e
0021460 n e r a l i z i n g t h e r
0021500 e s t o f t h e p r o o f
0021520 s i n m y w r i t e - u p
0021540 i n s t e a d , \r \r L y l
0021560 e \r \r \r * s t a r t * \r 0 0 8 4
0021600 1 0 0 0 9 5 U S \r g v M s
0021620 g I D : R a m s h a w . p a
0021640 $ 3 # 1 4 @ 2 9 - S e p - 8 3
0021660 1 7 : 1 3 : 5 0 P D T \r C a
0021700 t e g o r i e s : T r a c i n
0021720 g s \r D a t e : 2 9 S e p
0021740 8 3 1 7 : 1 3 : 5 0 P D T \r
0021760 F r o m : R a m s h a w . p a
0022000 \r S u b j e c t : W h o o p s
0022020 : a n o t h e r b u g d
0022040 i s c o v e r e d \r T o : G u
0022060 i b a s , S t o l f i \r C c :
0022100 R a m s h a w \r \r I ' m n o
0022120 w w o r k i n g o n t h e
0022140 i n t e g r a l i t y o f
0022160 p r o d u c t . O n c e a
0022200 g a i n , t h e ` ` p r o o
0022220 f ' ' t h a t I g a v e
0022240 i n t h e p o l y g o n a l
0022260 c a s e i s w r o n g ,
0022300 s o I s h a l l h a v e
0022320 t o f i x i t b e f o r e
0022340 g e n e r a l i z i n g i t
0022360 . I n p a r t i c u l a r
0022400 , I c l a i m e d t h a t
0022420 t h e m u l t i p l i c i t
0022440 i e s o f t h e m o v i n
0022460 g s t a t e s i n t h e
0022500 p r o d u c t w e r e ` ` c
0022520 l e a r l y ' ' i n t e g e r
0022540 s , s i n c e n o d i v i
0022560 s i o n s b y t w o w e r
0022600 e i n v o l v e d i n t h
0022620 e f o r m u l a f o r t h
0022640 e m . B U T : t h e w
0022660 i n d i n g n u m b e r s i
0022700 n v o l v e d m a y v e r y
0022720 w e l l b e h a l f - i n
0022740 t e g r a l i n s t e a d o
0022760 f i n t e g r a l ; t h i
0023000 s c a s e a r i s e s , f
0023020 o r e x a m p l e , w h e n
0023040 y o u m u l t i p l y a
0023060 t r a c i n g t i m e s i t
0023100 s e l f . I n e e d t o
0023120 p r o v e t h a t t h e
0023140 t w o h a l f - i n t e g e r
0023160 s i n v o l v e d w h e n
0023200 A w i n d s B a n d B
0023220 w i n d s A a l w a y s s
0023240 u m t o a n i n t e g e r
0023260 , \r \r L y l e \r \r \r * s t
0023300 a r t * \r 0 0 3 1 4 0 0 0 9 5
0023320 U S \r g v M s g I D : R a
0023340 m s h a w . p a $ 3 # 1 4 @
0023360 3 0 - S e p - 8 3 1 3 : 4 5 :
0023400 3 5 P D T \r C a t e g o r i e
0023420 s : T r a c i n g s \r D a t e
0023440 : 3 0 S e p 8 3 1 3 : 4
0023460 5 : 3 5 P D T \r F r o m : R
0023500 a m s h a w . p a \r S u b j e c
0023520 t : s t a t u s o f t r a
0023540 c i n g s \r T o : G u i b a s
0023560 , S t o l f i \r C c : R a m
0023600 s h a w \r \r B u g r e p a i r
0023620 e d ; S m o o t h T r a c i
0023640 n g s . p r e s s n o w p r
0023660 o v e s b a l a n c e a n d
0023700 i n t e g r a l i t y f o r
0023720 b o t h c o n v o l u t i o
0023740 n a n d p r o d u c t . \r \r
0023760 L y l e \r \r \r * s t a r t * \r 0
0024000 1 4 5 0 0 0 0 9 5 U S \r g
0024020 v M s g I D : R a m s h a w .
0024040 p a $ 3 # 1 4 @ 2 - O c t
0024060 - 8 3 1 1 : 5 7 : 0 6 P D T
0024100 \r C a t e g o r i e s : T r a
0024120 c i n g s \r D a t e : 2 O
0024140 c t 8 3 1 1 : 5 7 : 0 6 P
0024160 D T \r F r o m : R a m s h a w
0024200 . p a \r S u b j e c t : P S
0024220 t o : o r d e r i n g a n a
0024240 l y t i c c u r v e s \r T o :
0024260 r e s e a r c h ! r a b b i t
0024300 ! a m o @ B e r k e l e y . A R
0024320 P A \r C c : S t o l f i , G
0024340 r e e n e , G u i b a s , G
0024360 N e l s o n , R a m s h a w \r
0024400 \r A n d y , t h e r e s u l
0024420 t t h a t I w a s a s k
0024440 i n g a b o u t w o u l d
0024460 b e a n e a s y c o n s e
0024500 q u e n c e o f t h e f o
0024520 l l o w i n g L e m m a , w
0024540 h i c h I s u s p e c t t
0024560 o b e t r u e . \r \r L e m m
0024600 a . L e t x ( t ) a n d
0024620 y ( t ) b e r e a l a n
0024640 a l y t i c f u n c t i o n s
0024660 o f t i n a n e i g h
0024700 b o r h o o d o f t = 0 .
0024720 S u p p o s e t h a t x (
0024740 0 ) = 0 b u t t h a t x
0024760 i s n o t i d e n t i c a l
0025000 l y z e r o ; i n p a r
0025020 t i c u l a r , a s s u m e
0025040 t h a t t h e p o w e r s
0025060 e r i e s o f x ( t ) a t
0025100 t = 0 t a k e s t h e f
0025120 o r m \r \t x ( t ) = c * t ^
0025140 k + d * t ^ ( k + 1 ) +
0025160 . . . \r f o r s o m e p
0025200 o s i t i v e i n t e g e r
0025220 k a n d p o s i t i v e r
0025240 e a l c o n s t a n t c .
0025260 S i n c e w e a r e a s
0025300 s u m i n g t h a t c > 0 ,
0025320 w e h a v e x ( t ) > 0
0025340 f o r t s u f f i c i e n t
0025360 l y s m a l l a n d p o s
0025400 i t i v e . T h u s , f o
0025420 r s u f f i c i e n t l y s
0025440 m a l l p o s i t i v e x ,
0025460 w e c a n t h i n k o f
0025500 y a s a f u n c t i o n
0025520 o f x . N o w , y ' s
0025540 d e p e n d e n c e u p o n
0025560 x w i l l n o t i n g
0025600 e n e r a l b e a n a l y t
0025620 i c . T h e c l a i m o
0025640 f t h i s l e m m a i s
0025660 t h a t y w i l l a l w a
0025700 y s b e a n a n a l y t i
0025720 c f u n c t i o n o f x ^
0025740 ( 1 / k ) . \r \r O n c e t h i
0025760 s L e m m a i s p r o v e
0026000 n , t h e r e s u l t i n
0026020 t h e e a r l i e r m e s
0026040 s a g e f o l l o w s b y
0026060 a s i m p l e t r i c k :
0026100 i f o n e o f t h e y
0026120 ' s i s a n a l y t i c a
0026140 s a f u n c t i o n o f
0026160 x ^ ( 1 / m ) a n d t h e
0026200 o t h e r i s a n a l y t i
0026220 c a s a f u n c t i o n
0026240 o f x ^ ( 1 / n ) , t h e y
0026260 w i l l b o t h b e a n
0026300 a l y t i c a s f u n c t i
0026320 o n s o f x ^ ( 1 / ( m * n
0026340 ) ) . \r \r A s f a r a s p
0026360 r o v i n g t h e L e m m a
0026400 g o e s , i t i s p r e
0026420 t t y e a s y t o c o m p
0026440 u t e t h e p o w e r s e
0026460 r i e s o f y a s a f
0026500 u n c t i o n o f x ^ ( 1 /
0026520 k ) . T h e q u e s t i o
0026540 n o f u n i f o r m c o n
0026560 v e r g e n c e r e m a i n s
0026600 t o b e t a c k l e d ,
0026620 h o w e v e r . \r \r L y l e \r \r
0026640 \r * s t a r t * \r 0 0 3 4 8 0
0026660 0 0 9 5 U S \r g v M s g I D
0026700 : R a m s h a w . p a $ 3
0026720 # 1 4 @ 3 - O c t - 8 3 1 7
0026740 : 0 2 : 3 1 P D T \r C a t e g
0026760 o r i e s : T r a c i n g s \r
0027000 D a t e : 3 O c t 8 3
0027020 1 7 : 0 2 : 3 1 P D T \r F r o
0027040 m : R a m s h a w . p a \r S u
0027060 b j e c t : t r a c i n g s \r
0027100 T o : G u i b a s , S t o l
0027120 f i \r C c : R a m s h a w \r \r
0027140 L a t e s t v e r s i o n o
0027160 f S m o o t h T r a c i n g s
0027200 i n c l u d e s p r o o f
0027220 o f t h e f o r m u l a f
0027240 o r t h e w i n d i n g n
0027260 u m b e r o f a p r o d u
0027300 c t t r a c i n g . C o n
0027320 v o l u t i o n t h e o r e m
0027340 i s a l l t h a t ' s l
0027360 e f t , \r \r L y l e \r \r \r * s t
0027400 a r t * \r 0 1 3 5 5 0 0 0 9 5
0027420 U S \r g v M s g I D : R a
0027440 m s h a w . p a $ 3 # 1 4 @
0027460 2 2 - O c t - 8 3 1 6 : 5 7 :
0027500 5 2 P D T \r C a t e g o r i e
0027520 s : T r a c i n g s \r D a t e
0027540 : 2 2 O c t 8 3 1 6 : 5
0027560 7 : 5 2 P D T \r F r o m : R
0027600 a m s h a w . p a \r S u b j e c
0027620 t : R e : n e w t h e o r
0027640 y o f p l a n a r c u r v
0027660 e s \r I n - r e p l y - t o :
0027700 " N e w l i n ' s m e s s a g
0027720 e o f 1 8 O c t 8 3 1
0027740 0 : 4 9 : 1 5 P D T ( T u e
0027760 s d a y ) " \r T o : N e w l i
0030000 n \r C c : S t o l f i , G u
0030020 i b a s , R a m s h a w , M
0030040 a l l g r e n \r \r J a c k , I
0030060 s e n t y o u a c o p y
0030100 o f t h e p a p e r o n
0030120 t h e s u b j e c t t h a
0030140 t L e o , J o r g e , a n
0030160 d I w r o t e f o r F O
0030200 C S . I t p r e s e n t s
0030220 t h e c o r r e c t d e f
0030240 i n i t i o n s a n d p r o
0030260 o f s f o r t h e p o l y
0030300 g o n a l c a s e , a l t h
0030320 o u g h t h e p r e s e n t
0030340 a t i o n i s s o m e w h a
0030360 t t e r s e a t t i m e s
0030400 . I h a v e e x t e n d
0030420 e d t h e d e f i n i t i o
0030440 n s t o h a n d l e p i e
0030460 c e w i s e r e a l a n a l
0030500 y t i c c u r v e s , w h i
0030520 c h I n o w b e l i e v e
0030540 t o b e t h e " r i g h
0030560 t " f r a m e w o r k ( f o
0030600 r c u r v e s i n t h e
0030620 p l a n e a n y w a y ; s
0030640 u r f a c e s i n t h r e e
0030660 - s p a c e a r e l e s s
0030700 c l e a r t o m e ) , c o
0030720 n t i n u i n g t o b u i l
0030740 d o n J o r g e ' s e x t
0030760 e n d e d d e f i n i t i o n
0031000 o f w i n d i n g n u m b
0031020 e r a s d i s c u s s e d
0031040 i n D e a l e r . A n d
0031060 I h a v e w o r k e d t h
0031100 r o u g h s o m e o f t h
0031120 e p r o o f s f o r c u r
0031140 v e s a s w e l l , b u t
0031160 n o t y e t t h e m o s
0031200 t i m p o r t a n t o n e :
0031220 t h e p r o o f o f t
0031240 h e C o n v o l u t i o n T
0031260 h e o r e m . A n d r i g
0031300 h t a t t h e m o m e n t
0031320 , I ' m t a k i n g a b
0031340 r e a k f r o m t r y i n g
0031360 t o g e t t h a t p r o
0031400 o f t o w o r k o n T e
0031420 X 8 2 ( t r a n s l a t e d
0031440 f r o m P a s c a l t o C
0031460 e d a r , s o t h a t w e
0031500 c a n s t o p u s i n g
0031520 t h e T e X o n M A X C )
0031540 . \r \r W h y d o n ' t y
0031560 o u g l a n c e a t t h e
0031600 p a p e r , a n d s e e
0031620 i f i t m a k e s s e n s
0031640 e . T h e n c a l l m e
0031660 s o m e t i m e , a n d w
0031700 e ' l l c o n s i d e r w h
0031720 a t f a c e t s o f t h e
0031740 t h e o r y y o u o r t
0031760 h e S D D A d v a n c e d
0032000 D e v e l o p m e n t f r i d
0032020 a y l u n c h m e e t i n g
0032040 m i g h t l i k e t o h
0032060 e a r m o r e a b o u t , \r
0032100 \r L y l e \r \r \r * s t a r t * \r
0032120 0 0 9 3 2 0 0 0 9 5 U S \r
0032140 g v M s g I D : R a m s h a w
0032160 . p a $ 3 # 1 4 @ 1 - N o
0032200 v - 8 3 1 6 : 5 0 : 5 1 P S
0032220 T \r C a t e g o r i e s : T r
0032240 a c i n g s \r D a t e : 1
0032260 N o v 8 3 1 6 : 5 0 : 5 1
0032300 P S T \r F r o m : R a m s h a
0032320 w . p a \r S u b j e c t : S o
0032340 , y o u l i k e g e o m e
0032360 t r y ? \r T o : J a m e s . S
0032400 a x e @ C M U - C S - A , G u
0032420 i b a s , G r e e n e , S t
0032440 o l f i , G N e l s o n , P
0032460 l a s s \r C c : S w i n e h a
0032500 r t , R a m s h a w \r \r L e t
0032520 k > = 2 b e a n i n t e
0032540 g e r . C o n s t r u c t
0032560 a n e q u i l a t e r a l t
0032600 r i a n g l e o f s i d e
0032620 l e n g t h ( k ^ 2 - 1 ) .
0032640 C h o o s e o n e s i d e
0032660 o f t h i s t r i a n g l
0032700 e t o b e t h e b a s e
0032720 , a n d d i v i d e i t
0032740 i n t o t w o p a r t s o
0032760 f l e n g t h s ( k ^ 2 - 2
0033000 * k ) a n d ( 2 * k - 1 ) .
0033020 P r o v e t h a t t h e
0033040 d i s t a n c e f r o m t
0033060 h e p o i n t o f d i v i
0033100 s i o n o n t h e b a s e
0033120 t o t h e o p p o s i t e
0033140 v e r t e x i s t h e I
0033160 N T E G R A L q u a n t i t y
0033200 ( k ^ 2 - k + 1 ) . \r \r T
0033220 h i s n i c e f a c t w a
0033240 s d i s c o v e r e d b y
0033260 P a u l M i e l k e o f W
0033300 a b a s h C o l l e g e ( o
0033320 r U n i v e r s i t y ? ) ,
0033340 w h o u s e d i t a s t
0033360 h e b a s i s o f a p r
0033400 e t t y p i c t u r e . V
0033420 a r i o u s p r e t t y p i
0033440 c t u r e s c a n b e d r
0033460 a w n t a k i n g a d v a n
0033500 t a g e o f t h e f a c t
0033520 t h a t ( k ^ 2 - 2 * k ) ,
0033540 w h i c h i s t h e l e
0033560 n g t h o f o n e p a r t
0033600 o f t h e b a s e , a l
0033620 s o h a p p e n s t o b e
0033640 ( ( k - 1 ) ^ 2 - 1 ) , w h
0033660 i c h i s t h e s i d e
0033700 l e n g t h o f t h e f i
0033720 g u r e w i t h k _ ( k - 1
0033740 ) . \r \r L y l e \r \r \r * s t a
0033760 r t * \r 0 1 0 2 0 0 0 0 9 4
0034000 U S \r g v M s g I D : s t o
0034020 l f i . p a $ 3 # 1 4 @ 1
0034040 - N o v - 8 3 1 8 : 3 7 : 1 5
0034060 P S T \r C a t e g o r i e s :
0034100 T r a c i n g s \r D a t e :
0034120 1 - N o v - 8 3 1 8 : 3 7 :
0034140 1 5 P S T \r F r o m : s t o
0034160 l f i . p a \r S u b j e c t :
0034200 G e o m e t r y b o o k -
0034220 C h . 8 \r T o : G u i b a s \r
0034240 c c : s t o l f i \r \r L e o
0034260 , \r \r [ i v y ] < S t o l f i
0034300 > G B > G B b 0 8 . t e x c o
0034320 n t a i n s w h a t I g o
0034340 t s o f a r o n c h a p
0034360 t e r 8 ( m i n u s t h e
0034400 " i n t e r m e z z o " o n
0034420 g e o m e t r i c a l p r i
0034440 m i t i v e s a n d t h e
0034460 q u a d r a t i c m a p p i n
0034500 g ) . \r \r S e c t i o n s 1
0034520 a n d 2 , a n d s e c t i
0034540 o n 3 u p t o a l g o r
0034560 i t h m 7 , a r e r e a s
0034600 o n a b l y c o n s i s t e n
0034620 t ( I h o p e ) . S e c t
0034640 i o n 2 A a n d e v e r y
0034660 t i n g a f t e r a l g o r
0034700 i t h m 7 i s s t i l l
0034720 r a w j u n k c o p i e d
0034740 f r o m t h e S T O C p a
0034760 p e r a n d f r o m o l d
0035000 e r v e r s i o n s o f t
0035020 h i s c h a p t e r , a n d
0035040 i s t h e r e m o s t l y
0035060 a s a p l a c e h o l d e
0035100 r . \r \r C o u l d y o u h
0035120 e l p m e s o r t t h i s
0035140 m e s s o u t ? I f I
0035160 g o o n w r i t i n g a s
0035200 I h a v e d o n e s o
0035220 f a r , I a m a f r a i d
0035240 t h e c h a p t e r w i l
0035260 l n o t b e f i n i s h e
0035300 d b e f o r e 1 9 9 4 , a
0035320 n d w i l l b e a f e w
0035340 t h o u s a n d p a g e s
0035360 l o n g . P l e a s e , c h
0035400 o p i t d o w n ! ! ! \r \r
0035420 G B b 0 8 . t e x \ i n p u t
0035440 s t h e f o l l o w i n g
0035460 T E X m a c r o s : \r \r B a s
0035500 i c M a c r o s . t e x T R 1
0035520 0 F o n t s . t e x G B M a c
0035540 r o s . t e x G e o M a c r o
0035560 s . t e x K i n e M a c r o s
0035600 . t e x Q u a d M a c r o s .
0035620 t e x T R 1 0 G B W i d e F o
0035640 r m a t . t e x \r \r a l l i n
0035660 t h e d i r e c t o r y [
0035700 i v y ] < S t o l f i > T E X >
0035720 . \r \r t h a n k s a l o t ,
0035740 \r \r j o r g e \r * s t a r t * \r
0035760 0 6 5 7 8 0 0 0 9 5 U S \r
0036000 g v M s g I D : R a m s h a w
0036020 . p a $ 3 # 1 4 @ 2 - N o
0036040 v - 8 3 9 : 0 4 : 4 3 P S
0036060 T \r C a t e g o r i e s : T r
0036100 a c i n g s \r D a t e : 2
0036120 N o v 8 3 9 : 0 4 : 4 3
0036140 P S T \r F r o m : R a m s h a
0036160 w . p a \r S u b j e c t : F Y
0036200 I : J i m S a x e ' s r
0036220 e s p o n s e t o m y m e
0036240 s s a g e a b o u t M i e l
0036260 k e \r T o : G u i b a s , G
0036300 r e e n e , S t o l f i , G
0036320 N e l s o n , P l a s s , S
0036340 w i n e h a r t \r C c : R a m
0036360 s h a w \r \r \r - - - - - - - - -
0036400 - - - - - - - - - - - - - - - -
0036420 - - - - - - - - - - - - - \r R e
0036440 c e i v e d : f r o m C M U
0036460 - C S - A . A R P A b y P A
0036500 R C - M A X C . A R P A ; 2
0036520 N O V 8 3 0 0 : 0 1 : 3 6
0036540 P S T \r R e c e i v e d : f
0036560 r o m [ 1 2 8 . 2 . 2 5 4 . 1
0036600 9 2 ] b y C M U - C S - P T
0036620 w i t h C M U F T P ; 2
0036640 N o v 8 3 0 2 : 2 1 : 1 5
0036660 E S T \r D a t e : 2 N o v
0036700 8 3 0 2 : 1 3 E S T \r F r
0036720 o m : J a m e s . S a x e @ C
0036740 M U - C S - A . A R P A ( C 4
0036760 1 0 J S 3 0 ) \r T o : R a m s
0037000 h a w . p a \r S u b j e c t :
0037020 S o , y o u l i k e g e o
0037040 X X X n u m b e r t h e o r
0037060 y ? \r C C : J a m e s . S a x
0037100 e @ C M U - C S - A . A R P A \r
0037120 I n - R e p l y - T o : " R a
0037140 m s h a w . p a @ P A R C - M A
0037160 X C . A R P A ' s m e s s a g
0037200 e o f 1 N o v 8 3 1 9
0037220 : 5 0 - E S T " \r M e s s a g e
0037240 - I d : < 0 2 N o v 8 3 . 0 2
0037260 1 3 0 6 . J S 3 0 @ C M U - C S
0037300 - A > \r \r L e t x a n d y
0037320 b e a n y n o n - z e r o
0037340 i n t e g e r s , w i t h
0037360 x < > - y . T a k e \r
0037400 a = | x ^ 2 - 3 ( y ^ 2 )
0037420 + 2 x y | , \r b = |
0037440 4 x y | , a n d \r c
0037460 = | x ^ 2 + 3 ( y ^ 2 ) | . \r
0037500 T h e n t h e a n g l e C
0037520 s u b t e n d e d b y s i
0037540 d e c i n a t r i a n g
0037560 l e w i t h s i d e s a ,
0037600 b , \r a n d c i s e i t
0037620 h e r 6 0 d e g r e e s o
0037640 r 1 2 0 d e g r e e s .
0037660 T o s e e t h i s , n o t
0037700 e f i r s t \r t h e c o n d
0037720 i t i o n s o n x a n d
0037740 y g u a r a n t e e t h a t
0037760 a , b , a n d c a r e
0040000 s t r i c t l y \r p o s i t i
0040020 v e . T h e n , b y t h
0040040 e s e c o n d l a w o f
0040060 c o s i n e s , w e h a v e
0040100 \r c ^ 2 = a ^ 2 +
0040120 b ^ 2 - 2 a b ( c o s C
0040140 ) , \r o r e q u i v a l e n t
0040160 l y \r c o s C = (
0040200 a ^ 2 + b ^ 2 - c ^ 2 ) / 2 a b
0040220 \r = [ ( x
0040240 x x x + 4 x x x y - 2 x x y y -
0040260 1 2 x y y y + 9 y y y y ) + ( 1
0040300 6 x x y y ) - ( x x x x + 6 x x
0040320 y y + 9 y y y y ) ] / 2 a b \r
0040340 = ( 4 x x x
0040360 y + 8 x x y y - 1 2 x y y y ) /
0040400 | 2 ( x x + 2 x y - 3 y y ) ( 4
0040420 x y ) | \r =
0040440 + - 1 / 2 . \r I f w e t a
0040460 k e x = 2 k - 1 a n d
0040500 y = 1 , w e g e t \r
0040520 a = ( 4 k ^ 2 - 4 k + 1
0040540 ) + ( 4 k - 2 ) - 3 =
0040560 4 k ^ 2 - 4 , \r b =
0040600 8 k - 4 , a n d \r
0040620 c = ( 4 k ^ 2 - 4 k + 1 )
0040640 + 3 = 4 k ^ 2 - 4 k + 4
0040660 , \r o r e q u i v a l e n t l
0040700 y , \r a / 4 = k ^ 2
0040720 - 1 , \r b / 4 = 2 k
0040740 - 1 , a n d \r c / 4
0040760 = k ^ 2 - k + 1 . \r T h i s
0041000 l a s t i s t h e f a m i
0041020 l y o f v a l u e s f o u
0041040 n d b y M i e l k e . \r \r N
0041060 o w w h a t ' s r e a l l y
0041100 g o i n g o n h e r e ?
0041120 C o n s i d e r a t r i a
0041140 n g l e A B C , w i t h s
0041160 i d e s \r a , b , a n d c
0041200 o p p o s i t e v e r t i c
0041220 e s A , B , a n d C ,
0041240 r e s p e c t i v e l y . W
0041260 e w a n t t o f i n d \r i
0041300 n t e g e r v a l u e s f o
0041320 r t h e l e n g t h s o f
0041340 a , b , a n d c s u c
0041360 h t h a t a n g l e C w
0041400 i l l b e \r 6 0 d e g r e e
0041420 s . D r o p a p e r p e
0041440 n d i c u l a r f r o m A
0041460 i n t e r s e c t i n g l i n
0041500 e B C a t p o i n t D .
0041520 \r T h e n w e h a v e \r
0041540 s i n B = B D / c =
0041560 ( a - b / 2 ) / c
0041600 [ a r a t i o n a l n
0041620 u m b e r ] , a n d \r
0041640 c o s B = A D / c = b
0041660 ( 3 ^ 0 . 5 ) / 2 c
0041700 [ a r a t i o n a l m u l
0041720 t i p l e o f 3 ^ 0 . 5 ] .
0041740 \r S o t h e p r o b l e m
0041760 i s t o i d e n t i f y a
0042000 l l a n g l e s B s u c h
0042020 t h a t s i n B i s r
0042040 a t i o n a l \r a n d c o s
0042060 B i s a r a t i o n a l
0042100 m u l t i p l e o f t h e
0042120 s q u a r e r o o t o f 3
0042140 , o r e q u i v a l e n t l
0042160 y , \r t o f i n d a l l i
0042200 n t e g e r s o l u t i o n s
0042220 o f t h e e q u a t i o n
0042240 p ^ 2 + 3 q ^ 2 = r ^
0042260 2 . I c a n \r s h o w t
0042300 h a t ( m u l t i p l e s )
0042320 o f a l l s u c h s o l u
0042340 t i o n s a r e f o u n d
0042360 b y t a k i n g \r p
0042400 = x ^ 2 - 3 y ^ 2 , \r
0042420 q = 2 x y , a n d \r
0042440 r = x ^ 2 + 3 y ^
0042460 2 , \r f o r a p p r o p r i a
0042500 t e x a n d y . I t
0042520 i s e a s y t o v e r i f
0042540 y t h a t a n y i n t e g
0042560 e r v a l u e s \r f o r x
0042600 a n d y g i v e v a l i d
0042620 v a l u e s f o r p , q
0042640 , a n d r . T o s h o
0042660 w t h a t ( s o m e \r m u l
0042700 t i p l e o f ) a n y t r
0042720 i p l e t ( p , q , r ) s u
0042740 c h t h a t p ^ 2 + 3 q
0042760 ^ 2 = r ^ 2 c a n b e \r
0043000 g e n e r a t e d b y s o m
0043020 e p a i r ( x , y ) , j u
0043040 s t m a k e x / y = 3 q
0043060 / ( r - p ) . \r \r A t t h i s
0043100 p o i n t , i t w o u l d
0043120 s e e m t h a t w e k n
0043140 o w a l l t h e r e i s
0043160 t o k n o w a b o u t \r t h
0043200 e c l a s s o f a n g l e
0043220 s ( l e t ' s c a l l t h
0043240 e m M i e l k e a n g l e s
0043260 f o r w a n t o f a b
0043300 e t t e r \r t e r m ) w h o s
0043320 e c o s i n e s a r e r a
0043340 t i o n a l a n d w h o s e
0043360 s i n e s a r e r a t i o
0043400 n a l m u l t i p l e s \r o f
0043420 t h e s q u a r e r o o t
0043440 o f 3 . N o t s o .
0043460 U s i n g t h e t r i g o
0043500 n o m e t r i c f o r m u l a
0043520 s f o r \r s i n ( A + B ) a
0043540 n d c o s ( A + B ) , i t
0043560 i s e a s y t o s h o w
0043600 t h a t t h e M i e l k e
0043620 a n g l e s f o r m \r a g r
0043640 o u p u n d e r a d d i t i
0043660 o n . W h a t i s t h e
0043700 s t r u c t u r e o f t h
0043720 i s g r o u p ? \r \r A s a
0043740 s t a r t i n g p o i n t ,
0043760 w e c a n c o n s i d e r
0044000 w h a t i s k n o w n a b
0044020 o u t t h e r e l a t e d \r
0044040 g r o u p o f P y t h a g o
0044060 r e a n a n g l e s - - t h a
0044100 t i s , t h o s e a n g l
0044120 e s h a v i n g r a t i o n
0044140 a l \r s i n e a n d r a t i
0044160 o n a l c o s i n e . T h
0044200 e P y t h a g o r e a n a n
0044220 g l e s c o r r e s p o n d
0044240 t o \r s o l u t i o n s o f
0044260 t h e D i o p h a n t i n e
0044300 e q u a t i o n p ^ 2 + q ^ 2
0044320 = r ^ 2 , a n d ( m u l t i
0044340 p l e s o f ) \r a l l P y t
0044360 h a g o r e a n t r i p l e s
0044400 c a n b e f o u n d b y
0044420 t a k i n g \r p =
0044440 x ^ 2 - y ^ 2 , \r q =
0044460 2 x y , a n d \r r
0044500 = x ^ 2 + y ^ 2 , \r f o r a
0044520 p p r o p r i a t e ( x , y )
0044540 . F o r a n y p r i m e
0044560 n u m b e r r w h i c h
0044600 i s e q u i v a l e n t t o
0044620 \r 1 m o d 4 , t h e r e
0044640 i s a u n i q u e ( u p
0044660 t o i n t e r c h a n g i n g
0044700 x a n d y ) s o l u t i
0044720 o n i n \r i n t e g e r s t
0044740 o t h e e q u a t i o n x
0044760 ^ 2 + y ^ 2 = r ^ 2 . T
0045000 h i s s o l u t i o n g i v
0045020 e s a u n i q u e \r ( u p
0045040 t o i n t e r c h a n g i n g
0045060 p a n d q ) n o n t r i
0045100 v i a l P y t h a g o r e a n
0045120 t r i p l e ( p , q , r ) \r
0045140 f o r e a c h p r i m e r
0045160 e q u i v a l e n t t o 1
0045200 m o d 4 . E x a m p l e
0045220 s a r e ( 3 , 4 , 5 ) [ b
0045240 a s e d \r o n 2 ^ 2 + 1 ^ 2 =
0045260 5 ] , ( 5 , 1 2 , 1 3 ) [ b
0045300 a s e d o n ( 3 ^ 2 + 2 ^ 2
0045320 = 1 3 ) ] , ( 1 5 , 8 , 1 7 )
0045340 [ b a s e d o n \r 4 ^ 2 + 1
0045360 ^ 2 = 1 7 ] , e t c . T h
0045400 e s e P y t h a g o r e a n
0045420 a n g l e s , t o g e t h e r
0045440 w i t h t h e r i g h t \r
0045460 a n g l e , g e n e r a t e
0045500 t h e e n t i r e g r o u p
0045520 o f P y t h a g o r e a n
0045540 a n g l e s . M o r e o v e
0045560 r , \r e a c h P y t h a g o r
0045600 e a n a n g l e i s u n i
0045620 q u e l y g e n e r a t e d ,
0045640 e x c e p t f o r t h e \r
0045660 p o s s i b i l i t y o f a
0045700 d d i n g i n a n y m u l
0045720 t i p l e o f f o u r e x
0045740 t r a r i g h t a n g l e s
0045760 . \r F o r a n y s u m o f
0046000 t h e s e g e n e r a t o r
0046020 s , t h e r ( h y p o t e
0046040 n u s e ) o f t h e s u m
0046060 ( w h e n \r r e d u c e d t
0046100 o l o w e s t t e r m s b
0046120 y d i v i d i n g o u t a
0046140 l l c o m m o n f a c t o r
0046160 s o f p , q , \r a n d r
0046200 ) i s e q u a l t o t h
0046220 e p r o d u c t o f t h e
0046240 h y p o t e n u s e s o f
0046260 t h e g e n e r a t o r s . \r
0046300 F o r e x a m p l e , b y
0046320 a d d i n g t h e 0 , 1 ,
0046340 o r - 1 i n s t a n c e s
0046360 e a c h o f t h e a n g
0046400 l e s \r i n t h e ( 3 , 4 ,
0046420 5 ) a n d ( 5 , 1 2 , 1 3 )
0046440 t r i a n g l e s [ i . e .
0046460 , a r c s i n 3 / 5 a n d
0046500 \r a r c s i n 5 / 1 3 ] , a
0046520 n d n o r m a l i z i n g t
0046540 o t h e f i r s t q u a d
0046560 r a n t , w e o b t a i n
0046600 a l l \r n i n e s o l u t i o
0046620 n s t o p ^ 2 + q ^ 2 =
0046640 6 5 ^ 2 ( p > = 0 , q > 0 ) :
0046660 \r p = 0 , q = 6 5
0046700 p = 3 9 , q = 5
0046720 2 p = 5 2 ,
0046740 q = 3 9 \r p = 2 5 , q =
0046760 6 0 p = 3 3 ,
0047000 q = 5 6 p =
0047020 6 3 , q = 1 6 \r p = 6 0
0047040 , q = 2 5 p
0047060 = 1 6 , q = 6 3
0047100 p = 5 6 , q = 3 3 \r S i m
0047120 i l a r l y , m u l t i p l y
0047140 i n g a r c s i n 3 / 5 b
0047160 y 0 , 1 , 2 , - 1 , o r -
0047200 2 g i v e s a l l f i v e
0047220 \r s o l u t i o n s t o p ^
0047240 2 + q ^ 2 = 2 5 ^ 2 ( p >
0047260 = 0 , q > 0 ) : \r p = 0
0047300 , q = 2 5 p = 1 5 , q =
0047320 2 0 p = 2 4 , q = 7
0047340 p = 2 0 , q = 1 5 q
0047360 = 7 , p = 2 4 \r T h e s e r e
0047400 s u l t s a b o u t t h e
0047420 P y t h a g o r e a n g r o u
0047440 p a r e b a s e d o n a
0047460 f o r m u l a d u e \r t o
0047500 J a c o b i f o r c o u n t
0047520 i n g t h e n u m b e r o
0047540 f w a y s ( z e r o o r
0047560 m o r e ) i n w h i c h a
0047600 n y \r i n t e g e r i s e x
0047620 p r e s s i b l e a s t h e
0047640 s u m o f t w o s q u a
0047660 r e s . I d o n ' t k n
0047700 o w t h e \r d e t a i l s o
0047720 f t h e m a t h e m a t i c
0047740 s u s e d t o d e r i v e
0047760 t h i s . T h e a r t i
0050000 c l e i n t h e \r E n c y c
0050020 l o p e d i c D i c t i o n a
0050040 r y o f M a t h e m a t i c
0050060 s s a y s " . . . t h e
0050100 e q u a t i o n [ E Q U A T I
0050120 O N ] \r l e a d s t o [ F O
0050140 R M U L A F O R # O F S
0050160 O L U T I O N S ] . T h i s
0050200 r e s u l t w a s o b t a
0050220 i n e d b y \r C . G . J .
0050240 J a c o b i ( 1 8 2 9 ) .
0050260 . . " H o w e v e r , [ E
0050300 Q U A T I O N ] i n v o l v e
0050320 s t h e D e d e k i n d \r z
0050340 e t a f u n c t i o n , a n
0050360 d I d o n ' t h a v e m
0050400 y a c t t o g e t h e r w
0050420 e l l e n o u g h t o f o
0050440 l l o w \r a n y a r g u m e n
0050460 t s i n v o l v i n g D e d
0050500 e k i n d z e t a f u n c t
0050520 i o n s , n o r d o I k
0050540 n o w w h a t \r m e t h o d
0050560 J a c o b i u s e d ( p r e
0050600 s u m a b l y i t w a s s
0050620 o m e t h i n g e l s e , s
0050640 i n c e D e d e k i n d \r w a
0050660 s b o r n i n 1 8 3 1 ) .
0050700 \r \r G e t t i n g b a c k t
0050720 o t h e M i e l k e g r o
0050740 u p , I a m i n c l i n e
0050760 d t o c o n j e c t u r e
0051000 o n t h e \r b a s i s o f
0051020 a n a l o g y t o t h e P
0051040 y t h a g o r e a n g r o u p
0051060 t h a t t h e r e i s s
0051100 o m e s e t o f \r g e n e r
0051120 a t o r s s u c h t h a t
0051140 e a c h e l e m e n t o f
0051160 t h e M i e l k e g r o u p
0051200 i s u n i q u e l y \r e x p
0051220 r e s s i b l e a s a s u
0051240 m o f i n t e g e r m u l
0051260 t i p l e s o f g e n e r a
0051300 t o r s ( u p t o \r c o n g
0051320 r u e n c e m o d u l o 6 0
0051340 d e g r e e s ) . I ' d
0051360 b e i n t e r e s t e d i n
0051400 h e a r i n g i f y o u \r
0051420 o r a n y o n e e l s e c
0051440 a n p r o v e ( o r d i s
0051460 p r o v e ) t h i s a n d /
0051500 o r c h a r a c t e r i z e \r
0051520 a s e t o f g e n e r a t
0051540 o r s . A l s o , i s t
0051560 h e r e a n i n t e r e s t
0051600 i n g g e n e r a l i z a t i
0051620 o n \r f r o m t h e P y t h
0051640 a g o r e a n a n d M i e l
0051660 k e g r o u p s t o s o m
0051700 e i n f i n i t e f a m i l
0051720 y o f \r r e l a t e d g r o
0051740 u p s , o r w i l l a t t
0051760 e m p t s a t g e n e r a l
0052000 i z a t i o n f a i l f o r
0052020 r e a s o n s \r h a v i n g
0052040 t o d o w i t h t h e i
0052060 m p o s s i b i l i t y o f
0052100 t e s s e l a t i n g t h e
0052120 p l a n e w i t h \r p e n t a
0052140 g o n s , h e p t a g o n s ,
0052160 e t c . ? \r \r \t \t \t \t - - J i
0052200 m \r \r P . S . , \r \t I w o u l
0052220 d n ' t b e s u r p r i s e
0052240 d i f s o m e o n e h a d
0052260 a l r e a d y s t u d i e d
0052300 t h i s \r s t u f f . I t
0052320 m i g h t b e a d v i s a
0052340 b l e t o c h e c k t h e
0052360 l i t e r a t u r e b e f o
0052400 r e t h r o w i n g \r a r o u
0052420 n d t h e t e r m " M i e
0052440 l k e g r o u p " i n c o
0052460 n t e x t s w h e r e s o m
0052500 e o n e i s l i k e l y t
0052520 o \r s t a r t s p r e a d i n
0052540 g i t . \r \t \t \t \t - - J i m \r
0052560 \r - - - - - - - - - - - - - - -
0052600 - - - - - - - - - - - - - - - -
0052620 - - - - - - - \r \r \r * s t a r t
0052640 * \r 0 0 9 9 4 0 0 0 9 6 U S
0052660 \r g v M s g I D : R a m s h
0052700 a w . p a $ 3 # 2 3 5 @ 1 3
0052720 - N o v - 8 3 1 4 : 4 6 : 5 2
0052740 P S T \r C a t e g o r i e s :
0052760 T r a c i n g s \r D a t e :
0053000 1 3 N o v 8 3 1 4 : 4 7 :
0053020 0 0 P S T \r F r o m : R a m
0053040 s h a w . p a \r S u b j e c t :
0053060 n p o i n t s i n t h e
0053100 p l a n e , w i t h k t
0053120 o t h e l e f t o f a
0053140 l i n e \r T o : G u i b a s ,
0053160 G r e e n e , S t o l f i ,
0053200 P l a s s \r C c : R a m s h
0053220 a w \r \r D a n r e d u c e d
0053240 t h e p r o b l e m t o f
0053260 i n d i n g a n u p p e r
0053300 b o u n d o n t h e n u m
0053320 b e r o f t r a n s p o s i
0053340 t i o n s t h a t o c c u r
0053360 b e t w e e n t h e k ' t
0053400 h a n d ( k + 1 ) s t p l
0053420 a c e s w h i l e t h e p
0053440 e r m u t a t i o n ( n , n
0053460 - 1 , . . . , 2 , 1 ) i
0053500 s s o r t e d w i t h ( n
0053520 \ c h o o s e 2 ) t r a n s
0053540 p o s i t i o n s . U s i n
0053560 g t h i s r e d u c t i o n
0053600 , I c a n p r o v e a n
0053620 O ( n ^ ( 3 / 2 ) ) b o u n
0053640 d . B u t I t h i n k
0053660 t h a t t h e r e a l t r
0053700 u t h i s l i n e a r - - -
0053720 i n p a r t i c u l a r , (
0053740 2 - 1 / k ) * n f o r t h e
0053760 t r a n s p o s i t i o n v
0054000 e r s i o n , t w i c e t h
0054020 a t f o r t h e p o i n t
0054040 s i n t h e p l a n e . \r
0054060 \r M i k e c o n s t r u c t e
0054100 d a c o n f i g u r a t i o
0054120 n o f 1 0 p o i n t s i
0054140 n t h e p l a n e s u c h
0054160 t h a t t h e m o n o s t
0054200 r o f i c t r a c i n g d i
0054220 v i d i n g t h e m i n t
0054240 h e p a t t e r n ( 3 , 1
0054260 , 6 ) h a s 3 0 s e g m
0054300 e n t s i n i t . A r
0054320 o u g h s k e t c h ( o f
0054340 t h e p o i n t s w i t h o
0054360 u t a n y l i n e s ) i s
0054400 i n o r a n g e o n m y
0054420 w h i t e b o a r d , \r \r
0054440 L y l e \r \r \0 \0 \0 \0 006 \0 \0 235 312 \0
0054460 O \0 \0 002 230 \0 J 232 002 320 b s 004 234 030 230
0054500 034 J 232 002 235 004 234 \f 230 020 J 232 002 235 \a 234
0054520 5 230 < J 232 002 235 002 234 037 230 ! J 232 002 235
0054540 002 234 \t 230 \v J 230 \0 J 230 221 005 227 \0 205 227
0054560 \0 \0 \0 \0 003 . \0 \0 003 203 \0 \0 * s t a
0054600 r t * \r 0 1 0 2 2 0 0 0 9 6
0054620 U S \r g v M s g I D : R a m
0054640 s h a w . p a $ 3 # 2 3 5 @
0054660 1 5 - N o v - 8 3 9 : 2 2 :
0054700 5 2 P S T \r C a t e g o r i e
0054720 s : T r a c i n g s \r D a t e
0054740 : 1 5 N o v 8 3 9 : 2
0054760 2 : 5 5 P S T \r F r o m : R
0055000 a m s h a w . p a \r S u b j e c
0055020 t : t r a n s p o s i t i o n
0055040 s a r o u n d t h e m i d
0055060 d l e \r T o : G u i b a s ,
0055100 G r e e n e , S t o l f i \r C
0055120 c : M e g i d d o , R a m s
0055140 h a w \r \r Y e s t e r d a y ,
0055160 N i m r o d c l a i m e d t
0055200 h a t a n o n l i n e a r
0055220 n u m b e r o f t r a n s p
0055240 o s i t i o n s w a s p o s
0055260 s i b l e . H e r e i s
0055300 a n e x a m p l e w i t h
0055320 n * l o g ( n ) t h a t I
0055340 c o n s t r u c t e d l a s t
0055360 n i g h t : D i v i d e
0055400 t h e s e q u e n c e ( 1 ,
0055420 2 , 3 , . . . , n ) i
0055440 n t o t h i r d s , c a l l
0055460 e d A , B , a n d C .
0055500 O u r i n t i a l s t a t
0055520 e i s \r \t C R | B R |
0055540 A R \r w h e r e t h e " R
0055560 " d e n o t e s r e v e r s
0055600 e d , a n d " F " s h a l
0055620 l l a t e r d e n o t e f
0055640 o r w a r d . P e r f o r m
0055660 t h e f o l l o w i n g a
0055700 l g o r i t h m : \r \t C R |
0055720 B R | A R - > \r \t C R
0055740 | B F | A R - > \r \t C
0055760 R | A R | B F - > \r
0056000 \t C R | A F | B F -
0056020 > \r \t A F | C R | B F
0056040 - > \r \t A F | C F | B
0056060 F - > \r \t A F | B F |
0056100 C F . \r I f f ( n ) i s
0056120 t h e n u m b e r o f t r
0056140 a n s p o s i t i o n s a c r
0056160 o s s t h e m i d l i n e ,
0056200 w e f i n d t h a t \r \t
0056220 f ( n ) = 3 * f ( n / 3 ) + 3 *
0056240 ( n / 6 ) , \r s o f ( n ) = O
0056260 ( n * l o g ( n ) ) . \r \r I ' m
0056300 p r e t t y s u r e t h a
0056320 t t h i s c a n a c t u a
0056340 l l y b e r e a l i z e d
0056360 b y a s e t o f n p o
0056400 i n t s i n t h e p l a n
0056420 e a s w e l l , \r \r L y l e
0056440 \r \t \r \r \0 \0 \0 \0 006 \0 \0 235 312 \0 O \0
0056460 \0 002 230 \0 J 232 002 320 b s 004 234 030 230 034 J
0056500 232 002 235 004 234 \f 230 020 J 232 002 235 \a 234 " 230
0056520 ) J 232 002 235 002 234 030 230 032 J 232 002 235 002 234
0056540 022 230 024 J 230 \0 J 230 276 005 227 \0 205 227 \0 \0
0056560 \0 \0 003 J \0 \0 003 237 \0 \0 * s t a r t
0056600 * \r 0 0 7 4 2 0 0 0 9 5 U S
0056620 \r g v M s g I D : G u i b a
0056640 s . p a $ 3 # 1 8 3 @ 1 5 -
0056660 N o v - 8 3 1 1 : 4 3 : 0 3
0056700 P S T \r C a t e g o r i e s :
0056720 T r a c i n g s \r D a t e : 1
0056740 5 N o v 8 3 1 1 : 4 2 : 5
0056760 2 P S T \r F r o m : G u i b
0057000 a s . p a \r S u b j e c t : A
0057020 n o t h e r c u r i o u s f
0057040 a c t \r T o : R a m s h a w ,
0057060 G r e e n e , S t o l f i ,
0057100 M e g i d d o \r c c : G u i
0057120 b a s \r \r A f t e r a c o n
0057140 v e r s a t i o n w i t h N
0057160 i m r o d t h e f o l l o w
0057200 i n g f a c t e m e r g e d
0057220 , f o r w h i c h I n o
0057240 w h a v e a p r o o f . \r
0057260 \r I n t h e g e o m e t r i
0057300 c d u a l o f t h e o r
0057320 i g i n a l p r o b l e m o
0057340 n e i s g i v e n n o r
0057360 i e n t e d l i n e s i n
0057400 t h e p l a n e w h o s e
0057420 o r i e n t a t i o n s a r e
0057440 c o n s i s t e n t , i n
0057460 t h e s e n s e t h a t t
0057500 h e r e i s s o m e p o i
0057520 n t t h a t i s t o t h
0057540 e l e f t ( o r t h e r
0057560 i g h t ) o f a l l t h e
0057600 l i n e s . I f o n e c
0057620 o n s t r u c t s c i r c u i
0057640 t s b y r e p l a c i n g
0057660 e a c h l i n e c r o s s i
0057700 n g " X " b y " > < " i
0057720 n a w a y c o n s i s t e
0057740 n t w i t h t h e o r i e
0057760 n t a t i o n s , t h e n t
0060000 h e n u m b e r o f c i r
0060020 c u i t s i s i n d e p e n
0060040 d e n t o f t h e a r r a
0060060 n g e m e n t a n d a l w a
0060100 y s e q u a l t o c e i l
0060120 i n g ( n / 2 ) . \r \r \t L e o \r
0060140 * s t a r t * \r 0 0 7 9 2 0 0
0060160 0 9 6 U S \r g v M s g I D :
0060200 R a m s h a w . p a $ 3 #
0060220 2 3 5 @ 1 9 - N o v - 8 3 2 1
0060240 : 2 3 : 0 4 P S T \r C a t e g
0060260 o r i e s : T r a c i n g s \r
0060300 D a t e : 1 9 N o v 8 3
0060320 2 1 : 2 3 : 0 2 P S T \r F r o
0060340 m : R a m s h a w . p a \r S u
0060360 b j e c t : s t a t u s r e
0060400 p o r t \r T o : Y a o , P l
0060420 a s s , S t o n e , G r e e
0060440 n e , G u i b a s , S t o l
0060460 f i , v a n L e u n e n , M
0060500 B r o w n \r C c : R a m s h a
0060520 w \r \r I w a s n ' t a r o u
0060540 n d W e d n e s d a y t h r
0060560 o u g h F r i d a y b e c a
0060600 u s e I c a m e d o w n
0060620 w i t h t h i s s e a s o n
0060640 ' s s t o m a c h f l u .
0060660 I t ' s a b a d i e - - -
0060700 I s t r o n g l y r e c o m
0060720 m e n d t h a t y o u a v
0060740 o i d i t . L i v e h e
0060760 a l t h y , g e t l o t s
0061000 o f s l e e p , a n d l a
0061020 y i n a s t o r e o f
0061040 P e p t o - B i s m o l j u s
0061060 t i n c a s e t h e s e
0061100 m e a s u r e s d o n ' t s
0061120 u f f i c e . \r \r I m a y b
0061140 e i n f o r a f e w h
0061160 o u r s M o n d a y m o r n
0061200 i n g , b u t t h e n I
0061220 s h a l l b e l e a v i n g
0061240 o n a p e r s o n a l t
0061260 r i p t h r o u g h T h a n
0061300 k s g i v i n g . K e e p
0061320 t h e f a i t h ; I m
0061340 a y e v e n b e b a c k
0061360 i n t i m e t o w r i t e
0061400 m y p e r f o r m a n c e
0061420 a p p r a i s a l . \r \r L y l e
0061440 \r \r \r \0 \0 \0 006 \0 \0 235 312 \0 O \0 \0 002
0061460 230 \0 J 232 002 320 b s 004 234 030 230 034 J 232 002
0061500 235 004 234 \f 230 020 J 232 002 235 \a 234 017 230 026 J
0061520 232 002 235 002 234 > 230 @ J 232 002 235 002 234 \t 230
0061540 \v J 230 \0 J 230 317 003 227 \0 205 227 \0 \0 \0 \0
0061560 002 d \0 \0 002 271 \0 \0 * s t a r t * \r
0061600 0 1 7 9 3 0 0 0 9 6 U S \r
0061620 g v M s g I D : s t o l f i .
0061640 p a $ 8 9 # 1 3 2 @ 3 0 - N
0061660 o v - 8 3 1 8 : 2 0 : 2 1 P
0061700 S T \r C a t e g o r i e s : T
0061720 r a c i n g s \r D a t e : 3 0
0061740 N o v 8 3 1 8 : 2 0 : 0 6
0061760 P S T \r F r o m : s t o l f
0062000 i . p a \r S u b j e c t : V o
0062020 r o n o i o n a s p h e r
0062040 e \r T o : G u i b a s \r C c :
0062060 s t o l f i \r \r L e o : w e
0062100 r e y o u a w a r e o f
0062120 t h e f a c t b e l o w ?
0062140 I ( s h a m e , s h a m e )
0062160 w a s n o t , i n s p i
0062200 t e o f a l l o u r t i
0062220 n k e r i n g w i t h t h e
0062240 l a m b d a m a p p i n g
0062260 a n d s p h e r i c a l p r
0062300 o j e c t i o n s t o e x p
0062320 l a i n p l a n a r V o r o
0062340 n o i d i a g r a m s . . . \r
0062360 \r - - - - - - - - - - - - - - -
0062400 - - - \r \r R e c e i v e d : f
0062420 r o m S U - A I . A R P A b
0062440 y P A R C - M A X C . A R P A
0062460 ; 2 9 N O V 8 3 2 1 : 1
0062500 4 : 3 2 P S T \r D a t e : 2
0062520 9 N o v 8 3 2 1 : 0 4 P
0062540 S T \r F r o m : K e n C l a
0062560 r k s o n < K L C @ S U - A I
0062600 . A R P A > \r S u b j e c t :
0062620 g e o m e t r y q u e s t i o
0062640 n \r T o : s t o l f i . P
0062660 A , K L C @ S U - A I . A R P
0062700 A \r \r \r H i . I ' v e r u
0062720 n i n t o s o m e t h i n g
0062740 I ' m s u r e y o u k n
0062760 o w s o m e t h i n g a b o
0063000 u t . C a n \r a n a n a l
0063020 o g o f t h e I n C i r c
0063040 l e t e s t b e u s e d
0063060 t o c o m p u t e s p h e r
0063100 i c a l V o r o n o i d i a
0063120 g r a m s ? \r I t h i n k t
0063140 h a t t h e a p p r o p r i
0063160 a t e I n C i r c l e t e s
0063200 t i s e v e n s i m p l e
0063220 r t h a n t h e o n e \r d
0063240 e s c r i b e d i n y o u r
0063260 S T O C ( F O C S ? ) p a
0063300 p e r , b u t I ' m n o t
0063320 s u r e . \r \r I s i t r e
0063340 a l l y o n l y r e q u i r
0063360 e d o f t h e I n C i r c
0063400 l e t e s t t h a t i t
0063420 t e s t i f a p o i n t
0063440 D \r i s i n s i d e t h e
0063460 c i r c l e o f p o i n t s
0063500 A , B , a n d C ? \r \r W h
0063520 a t d o e s i t m e a n
0063540 f o r a p o i n t t o l
0063560 i e t o t h e l e f t o
0063600 f a c i r c l e ? I s
0063620 t h i s a \r d u a l i t y
0063640 n o t i o n o r s o m e t h
0063660 i n g ? \r \r A n y h e l p y
0063700 o u c a n g i v e m e w
0063720 o u l d b e a p p r e c i a
0063740 t e d . . . i n c i d e n t a
0063760 l l y , t h e s o o n e r \r
0064000 t h e b e t t e r . . . i f
0064020 y o u ' r e r e a d i n g t
0064040 h i s T u e s d a y n i g h
0064060 t , c o u l d y o u c a l
0064100 l m e a t \r 4 9 7 - 9 5 5 8
0064120 ? \r \r t h a n k s , \r K e n \r \r
0064140 R e c e i v e d : f r o m S
0064160 U - A I . A R P A b y P A R
0064200 C - M A X C . A R P A ; 3 0
0064220 N O V 8 3 1 6 : 1 2 : 2 2
0064240 P S T \r D a t e : 3 0 N o v
0064260 8 3 1 6 : 0 9 P S T \r F r
0064300 o m : K e n C l a r k s o n
0064320 < K L C @ S U - A I . A R P A
0064340 > \r S u b j e c t : g e o m e
0064360 t r y q u e s t i o n \r T
0064400 o : s t o l f i . P A , K L
0064420 C @ S U - A I . A R P A \r \r \r A
0064440 h a h ! T h e " s p h e r
0064460 i c a l D e l a u n e y t r
0064500 i a g u l a t i o n " o f a
0064520 s e t o f p o i n t s o
0064540 n a s p h e r e i s \r j u
0064560 s t t h e 3 D c o n v e x
0064600 h u l l o f t h o s e p
0064620 o i n t s ! \r \r - K e n \r ( I '
0064640 m p r e t t y s u r e - -
0064660 t h e c i r c u m c i r c l
0064700 e D e l a u n e y p r o p e
0064720 r t y a n d t h e h u l l
0064740 p r o p e r t y \r c o i n c i
0064760 d e ) \r \r - - - - - - - - - - -
0065000 - - - \r \r j o r g e \r \0 \0 \0 006 \0
0065020 \0 235 312 \0 h \0 \0 002 230 \0 J 232 001 234 034 230
0065040 034 J 232 001 317 b 017 230 017 J 232 002 320 b s \a
0065060 234 025 230 034 J 232 002 236 002 234 \b 230 \n J 232 002
0065100 236 002 234 \b 230 \n J 230 \0 J 230 267 001 J 230 023
0065120 J 232 001 317 f 332 006 230 332 006 J 232 001 237 224 003
0065140 230 224 003 J 230 017 J 230 005 227 \0 205 227 \0 \0 \0
0065160 \0 006 4 \0 \0 006 242 \0 \0 * s t a r t *
0065200 \r 0 0 3 3 6 0 0 0 9 5 U S
0065220 \r g v M s g I D : G u i b a s
0065240 . p a $ 3 # 1 8 3 @ 3 0 - N
0065260 o v - 8 3 1 9 : 0 5 : 3 9 P
0065300 S T \r C a t e g o r i e s : T
0065320 r a c i n g s \r D a t e : 3 0
0065340 - N o v - 8 3 1 9 : 0 6 : 2 1
0065360 P S T \r F r o m : G u i b a
0065400 s . p a \r S u b j e c t : V o
0065420 r o n o i o n a s p h e r
0065440 e \r T o : S t o l f i \r c c :
0065460 K L C @ S U - A I . A R P A ,
0065500 G u i b a s \r \r I n f a c t
0065520 t h e i n t e r s e c t i o
0065540 n o f t h e p l a n e s
0065560 u p p o r t i n g a c o n v
0065600 e x h u l l f a c e w i t
0065620 h t h e s p h e r e i s
0065640 t h e c o r r e s p o n d i n
0065660 g D e l a u n a y c i r c l
0065700 e . \r \r \t L . \r * s t a r t *
0065720 \r 0 4 6 6 5 0 0 0 9 6 U S
0065740 \r g v M s g I D : s t o l f i
0065760 . p a $ 8 9 # 1 3 2 @ 3 0 -
0066000 N o v - 8 3 2 0 : 1 2 : 3 8
0066020 P S T \r C a t e g o r i e s :
0066040 T r a c i n g s \r D a t e : 3
0066060 0 N o v 8 3 2 0 : 1 2 : 3
0066100 4 P S T \r F r o m : s t o l
0066120 f i . p a \r S u b j e c t : V
0066140 o r o n o i o n a S p h e
0066160 r e \r T o : K e n C l a r k
0066200 s o n < K L C @ S U - A I . A
0066220 R P A > \r C c : s t o l f i ,
0066240 G u i b a s \r \r W e l l , i
0066260 t s e e m s y o u f o u n
0066300 d t h e a n s w e r b e f
0066320 o r e I e v e n r e a d
0066340 t h e q u e s t i o n . C
0066360 o n f o u n d m e , I h a
0066400 d n ' t t h o u g h t m u c
0066420 h a b o u t V o r o n o i
0066440 o n t h e s p h e r e ( u
0066460 s i n g s p h e r i c a l d
0066500 i s t a n c e ) ; I g u e s
0066520 s I e x p e c t e d t h e
0066540 m t o b e s o m e w h a t
0066560 m o r e c o m p l e x t h
0066600 a n V o r o n o i s o n E
0066620 u c l i d e a n s p a c e s ,
0066640 a s i s t h e c a s e
0066660 o f V o r o n o i s u s i n
0066700 g o t h e r n o n - E u c l
0066720 i d e a n m e t r i c s . I
0066740 n s t e a d , t h e f o r m
0066760 e r s e e m t o b e s i
0067000 m p l e r t h a n t h e l
0067020 a t t e r . A m a z i n g .
0067040 ( H o w e v e r , I a m s
0067060 u r e o t h e r V o r o n o
0067100 s o p h e r s m u s t h a v
0067120 e n o t i c e d i t b e f
0067140 o r e ) . \r \r I k n e w v e
0067160 r y w e l l t h a t ( D e
0067200 l a u n a y o n t h e p l
0067220 a n e ) = ( C o n v e x h
0067240 u l l o n t h e s p h e r
0067260 e ) u n d e r s t e r e o g
0067300 r a p h i c p r o j e c t i o
0067320 n , b u t I f a i l e d
0067340 t o n o t i c e t h a t t
0067360 h e l a t t e r w a s t h
0067400 e D e l a u n a y o f t h
0067420 e s p h e r i c a l p r o b
0067440 l e m , t o o . \r \r
0067460 A s u s e d i n o u r a
0067500 l g o r i t h m , t h e I n
0067520 C i r c l e t e s t i n d e
0067540 e d h a s o n l y t o t
0067560 e s t i f a p o i n t D
0067600 i s i n s i d e t h e c
0067620 i r c l e o f p o i n t s
0067640 A , B , a n d C , w h e r
0067660 e A B C i s a c c w o
0067700 r i e n t e d t r i a n g l e
0067720 . H o w e v e r , w e b
0067740 e l i e v e t h e s i m p l
0067760 e s t i m p l e m e n t a t i
0070000 o n o f I n C i r c l e (
0070020 b y e v a l u a t i o n o f
0070040 t h e 4 x 4 d e t e r m i
0070060 n a n t g i v e n i n o u
0070100 r S T O C p a p e r ) g e
0070120 n e r a l i z e s t h i s t
0070140 o m e a n " p o i n t D
0070160 i s o n t h e l e f t s
0070200 i d e o f t h e o r i e n
0070220 t e d c i r c l e A B C " .
0070240 T h i s i s t h e c i r
0070260 c l e p a s s i n g t h r o
0070300 u g h t h e t h r e e p o
0070320 i n t s a n d o r i e n t e
0070340 d f r o m A t o B t o
0070360 C ; i t s l e f t s i d
0070400 e i s i t s i n t e r i o
0070420 r ( i n t h e u s u a l
0070440 s e n s e ) i f A B C i s
0070460 a c c w t r i a n g l e ,
0070500 a n d i s t h e e x t e
0070520 r i o r i f A B C i s a
0070540 c w t r i a n g l e . \r \r T
0070560 h i s g e n e r a l i z a t i
0070600 o n i s n e c e s s a r y
0070620 f o r t h e s p h e r i c a
0070640 l p r o b l e m , w h e r e
0070660 t h e n o t i o n s o f
0070700 " i n t e r i o r " a n d "
0070720 e x t e r i o r " o f a c
0070740 i r c l e b e c o m e s o m
0070760 e w h a t a m b i g u o u s .
0071000 T h e l e f t s i d e o
0071020 f t h e o r i e n t e d c
0071040 i r c l e A B C t h e n c
0071060 o r r e s p o n d s t o t h
0071100 a t s i d e o f t h e p
0071120 l a n e p a s i n g t h r o
0071140 u g h A , B , C f r o m w
0071160 h i c h A B C i s s e e n
0071200 a s a c c w t r i a n g
0071220 l e . B y t h e a p p r o
0071240 p r i a t e d e f i n i t i o
0071260 n s , t h i s i s a l s o
0071300 t h e l e f t s i d e o
0071320 f t h e o r i e n t e d p
0071340 l a n e d e f i n e d b y
0071360 t h e p o i n t s A B C .
0071400 S o , I n C i r c l e ( A B
0071420 C D ) = " D i s t o t
0071440 h e l e f t o f t h e o
0071460 r i e n t e d p l a n e A B
0071500 C " = " A B C D i s a
0071520 p o s i t i v e l y o r i e n
0071540 t e d t e t r a h e d r o n "
0071560 . T h e s p h e r i c a l
0071600 I n C i r c l e t e s t i s
0071620 t h e n t h e s a m e a
0071640 s t h e p l a n a r o n e
0071660 , m i n u s t h e q u a d
0071700 r a t i c m a p p i n g ( o
0071720 r s t e r e o g r a p h i c
0071740 p r o j e c t i o n ) \r
0071760 \r T h e p l a n a r D e l a
0072000 u n a y c o n d i t i o n (
0072020 A B C i s a D e l a u n a
0072040 y t r i a n g l e i f f n
0072060 o o t h e r s i t e i s
0072100 i n s i d e t h e c i r c l
0072120 e A B C ) t h e n b e c o
0072140 m e s " A B C i s a f a
0072160 c e o f t h e s p h e r i
0072200 c a l D e l a u n a y i f f
0072220 n o o t h e r s i t e i
0072240 s t o t h e l e f t o f
0072260 t h e o r i e n t e d p l
0072300 a n e A B C " , w h i c h
0072320 i s p r e c i s e l y t h e
0072340 c o n d i t i o n f o r A
0072360 B C t o b e a f a c e
0072400 o f t h e c o n v e x h u
0072420 l l o f a l l s i t e s .
0072440 \r \r I c a n e v e n s e e
0072460 n o w a m o r e g e n e
0072500 r a l p r i n c i p l e b e
0072520 h i n d t h i s . L e t S
0072540 b e a m e t r i c s p a
0072560 c e o f d i m e n s i o n
0072600 2 ( i . e . , a s u r f a
0072620 c e p l u s a d i s t a n
0072640 c e f u n c t i o n d e f i
0072660 n e d o n i t s p o i n t
0072700 s ) . D e f i n e a " c i
0072720 r c l e " o n S a s a
0072740 s e t o f t h e f o r m
0072760 [ x : d i s t ( x , c )
0073000 < r ] , f o r s o m e
0073020 p o i n t c i n S a n
0073040 d s o m e r a d i u s r .
0073060 N o w c o n s i d e r a
0073100 m a p p i n g f , f r o m
0073120 S i n t o a n o t h e r
0073140 m e t r i c s p a c e S '
0073160 ( w i t h s o m e u n r e l
0073200 a t e d d i s t a n c e d i
0073220 s t ' ) , t h a t m a p s
0073240 c i r c l e s o f S i n t
0073260 o c i r c l e s o f S ' .
0073300 T h e n t h e D e l a u
0073320 n a y d i a g r a m o f a
0073340 s e t o f p o i n t s P
0073360 i n S i s t o p o l o g
0073400 i c a l l y e q u i v a l e n
0073420 t t o t h e D e l a u n a
0073440 y d i a g r a m o f f ( P
0073460 ) i n S ' . \r \r T h i s c
0073500 o n c l u s i o n i s t r i
0073520 v i a l , o f c o u r s e ,
0073540 i f f p r e s e r v e s
0073560 d i s t a n c e s ( d i s t '
0073600 ( f ( x ) , f ( y ) ) = d i
0073620 s t ( x , y ) ) o r a t l
0073640 e a s t t h e o r d e r i n
0073660 g o f d i s t a n c e s (
0073700 d i s t ( x , c ) < d i s
0073720 t ( y , c ) i m p l i e s d
0073740 i s t ' ( f ( x ) , f ( c ) )
0073760 < d i s t ' ( f ( y ) , f (
0074000 c ) ) ) ; i n t h i s c a
0074020 s e f a l s o m a p s a
0074040 V o r o n o i d i a g r a m
0074060 o n S i n t o a V o r
0074100 o n o i d i a g r a m o n
0074120 S ' . T h i s i s f o r
0074140 e x a m p l e t h e c a s e
0074160 o f o u r q u a d r a t i
0074200 c m a p p i n g l a m b d a
0074220 : ( x , y ) - - > ( x , y
0074240 , x 2 + y 2 ) , w h e r e d
0074260 i s t o n t h e p a r a b
0074300 o l o i d z = x 2 + y 2 i s
0074320 t h e h o r i z o n t a l
0074340 d i s t a n c e ( i g n o r i
0074360 n g t h e z c o o r d i n
0074400 a t e ) . \r \r H o w e v e r ,
0074420 s o m e q u i t e i n t e r
0074440 e s t i n g t r a n s f o r m
0074460 a t i o n s p r e s e r v e
0074500 c i r c l e s w i t h o u t
0074520 s a t i s f y i n g e i t h e
0074540 r o f t h i s p r o p e r
0074560 t i e s . A m o n g t h e m
0074600 a r e t h e " i n v e r s
0074620 i o n s o f t h r e e - s p
0074640 a c e a r o u n d a s p h
0074660 e r e Z " ( m a p e a c h
0074700 p o i n t p i n s p a c
0074720 e t o t h e p o i n t p
0074740 ' o n t h e s a m e r a
0074760 y f r o m t h e c e n t e
0075000 r c o f Z , a t a d
0075020 i s t a n c e d i s t ( c ,
0075040 p ' ) = 1 / d i s t ( c , p )
0075060 ) . A n y s u c h i n v e
0075100 r s i o n f m a p s a n y
0075120 s p h e r e S t o a n o
0075140 t h e r s p h e r e S ' ,
0075160 a n d c i r c l e s o n S
0075200 t o c i r c l e s o n S
0075220 ' , b u t d o e s n o t
0075240 p r e s e r v e t h e o r d
0075260 e r i n g o f d i s t a n c
0075300 e s , a n d d o e s n o t
0075320 m a p c e n t e r s i n t
0075340 o c e n t e r s . \r \r T h e
0075360 s t e r e o g r a p h i c p r
0075400 o j e c t i o n h i s j u
0075420 s t a s p e c i a l c a s
0075440 e o f i n v e r s i o n .
0075460 I n f a c t , i t i s a
0075500 d e g e n e r a t e c a s e
0075520 , s i n c e t h e p l a n
0075540 e i s t h e o n l y s p
0075560 h e r e w h e r e a c i r
0075600 c l e d o e s n o t c o r
0075620 r e s p o n d t o a p l a
0075640 n a r s e c t i o n . T o
0075660 e v a l u a t e I n C i r c l
0075700 e ( A B C D ) o n a s p h
0075720 e r e w e o n l y n e e d
0075740 t o t e s t w h e t h e r
0075760 D i s o n t h e l e f
0076000 t s i d e o f t h e p l
0076020 a n e A B C ; t o e v a l
0076040 u a t e I n C i r c l e ( A B
0076060 C D ) o n t h e p l a n e
0076100 , w e h a v e t o m a p
0076120 i t f i r s t o n t o a
0076140 n o n - d e g e n e r a t e
0076160 s p h e r e , o r o n t o
0076200 o u r p a r a b o l o i d . \r
0076220 \r W e l l , e n o u g h r a
0076240 m b l i n g s f o r n o w .
0076260 T h a n k s f o r t h e
0076300 o b s e r v a t i o n , \r \r j o
0076320 r g e \r \r P S : I g u e s s
0076340 t h e a b o v e a l s o
0076360 c o n f i r m s D r . B .
0076400 B o a r d F l a m e r ' s L
0076420 a w , " t h e i n f o r m a
0076440 t i o n d e n s i t y o f
0076460 a m e s s a g e i s i n v
0076500 e r s e l y p r o p o r t i o
0076520 n a l t o t h e s q u a r
0076540 e o f i t s l e n g t h "
0076560 . . . \r \r \0 \0 \0 006 \0 \0 235 312
0076600 \0 204 \0 \0 002 230 \0 J 232 001 234 034 230 034 J 232
0076620 001 234 017 230 017 J 232 002 320 b s \a 234 025 230 034
0076640 J 232 002 235 002 234 037 230 ! J 232 002 235 002 234 020
0076660 230 022 J 230 \0 J 230 275 003 J 230 310 001 J 232 001
0076700 234 276 004 230 276 004 J 232 001 234 201 005 230 201 005 J
0076720 232 001 234 260 002 230 260 002 J 230 227 004 J 230 314 003
0076740 J 230 344 003 J 230 244 003 J 230 C J 230 237 001 J
0076760 230 002 227 \0 205 227 \0 \0 \0 \0 021 P \0 \0 021 332
0077000 \0 \0 * s t a r t * \r 0 2 0 0 8
0077020 0 0 0 9 5 U S \r g v M s g I
0077040 D : G u i b a s . p a $ 3
0077060 # 1 8 3 @ 5 - D e c - 8 3
0077100 9 : 3 8 : 3 1 P S T \r C a t e
0077120 g o r i e s : T r a c i n g s
0077140 \r D a t e : 5 - D e c - 8 3
0077160 9 : 3 8 : 3 9 P S T \r F r
0077200 o m : G u i b a s . p a \r S u
0077220 b j e c t : R a n d o m \r T o
0077240 : S t o l f i \r c c : G u i
0077260 b a s \r \r I ' m s t i l l p
0077300 r e o c c u p i e d w i t h
0077320 p e r f o r m a n c e a p p r
0077340 a i s a l s t o d a y . Y o
0077360 u m i g h t w a n t t o
0077400 t r y a n d v e r i f y t
0077420 h e f o l l o w i n g s t a
0077440 t e m e n t s : \r \r T a k e n
0077460 p o i n t s i n t h e p
0077500 l a n e , n o t h r e e c
0077520 o l l i n e a r . L e t k
0077540 b e a n i n t e g e r b e
0077560 t w e e n 0 a n d n - 1 .
0077600 S w e e p a l i n e p a
0077620 r a l l e l t o i t s e l f
0077640 u n t i l t h e r e a r e
0077660 e x a c t l y k p o i n t
0077700 s t o t h e l e f t o f
0077720 t h e l i n e , a n d o
0077740 n e o n t h e l i n e (
0077760 i g n o r e f o r t h e m
0100000 o m e n t t h e c a s e w
0100020 h e r e t h e r e c o u l d
0100040 b e t w o ) . N o w r o
0100060 t a t e t h e l i n e c c
0100100 w a r o u n d t h a t p o
0100120 i n t u n t i l a n o t h e
0100140 r i s h i t . W h e n t
0100160 h i s o c c u r s s w i t c
0100200 h t h e c e n t e r o f
0100220 r o t a t i o n t o t h e
0100240 n e w p o i n t a n d c o
0100260 n t i n u e r o t a t i n g
0100300 c c w , r e p e a t i n g t
0100320 h i s p r o c e s s . \r \r C l
0100340 a i m 1 . T h e l i n e
0100360 e v e n t u a l l y r e t u r
0100400 n s t o i t s o r i g i n
0100420 a l p o s i t i o n ; \r \r C l
0100440 a i m 2 . I f l i s a
0100460 l i n e h a v i n g t h e
0100500 p r o p e r t y d e s c r i
0100520 b e d i n t h e a b o v e
0100540 p a r a g r a p h , t h e n
0100560 o u r r o t a t i n g l i
0100600 n e w i l l a t s o m e
0100620 p o i n t p a s s t h r o u
0100640 g h l ; \r \r C l a i m 3 .
0100660 T h i s p r o c e s s d e f
0100700 i n e s a m o n o s t r o f
0100720 i c p o l y g o n , i n t
0100740 h e o b v i o u s w a y :
0100760 t h e c a r g o e s f w d
0101000 w h e n t h e n e w p i
0101020 v o t p o i n t i s a h e
0101040 a d o n t h e l i n e ,
0101060 a n d b k w d , w h e n i
0101100 t i s b e h i n d . \r \r C l
0101120 a i m 4 . T h e c o l l e
0101140 c t i o n o f a l l p o i
0101160 n t s o f t h e p l a n e
0101200 l y i n g t o t h e " n
0101220 - k " s i d e o f a l l
0101240 s i d e s o f t h i s m o
0101260 n o s t r o f i c t r a c i n
0101300 g m a y b e e m p t y .
0101320 T h i s w i l l s u r e l y
0101340 b e t h e c a s e w h e
0101360 n k > n / 2 . H o w e v
0101400 e r , b y H e l l y , t h
0101420 i s c o l l e c t i o n w i
0101440 l l b e n o n - e m p t y
0101460 w h e n k = < n / 3 . W
0101500 h e n t h e c o l l e c t i
0101520 o n i s n o n - e m p t y ,
0101540 i t s p o i n t s d e f i
0101560 n e a c o n v e x p o l y
0101600 g o n . T h i s c o n v e x
0101620 p o l y g o n i s c h a r
0101640 a c t e r i z e d b y t h e
0101660 p r o p e r t y t h a t a
0101700 n y l i n e t h r o u g h
0101720 e a c h o f i t s p o i n
0101740 t s d i v i d e s t h e n
0101760 g i v e n p o i n t s i n
0102000 t w o g r o u p s o f w
0102020 h i c h t h e s m a l l e s
0102040 t i s a t l e a s t o f
0102060 s i z e m i n { k , n - k }
0102100 a n d t h e l a r g e s t
0102120 i s a t m o s t m a x {
0102140 k , n - k } . \r \r C l a i m 5
0102160 . C o n s i d e r i n g a l
0102200 l k , w e g e t c e i l
0102220 i n g ( n / 2 ) s u c h m o
0102240 n o s t r o f i c t r a c i n
0102260 g s . \r \r O p e n q u e s t i
0102300 o n : w h a t i s t h e
0102320 m a x i m u m n u n b e r o
0102340 f s i d e s o n s u c h
0102360 a t r a c i n g ? \r \r - - - -
0102400 - - - - - - - - - - - - - - - -
0102420 - - - - - - - - - \r \r A t y o
0102440 u r c o n v e n i e n c e ,
0102460 p l e a s e \r \r 1 . c h e c k
0102500 w i t h E d T a f t a b
0102520 o u t d u m p i n g o u r
0102540 f i l e s o n t a p e \r \r 2
0102560 . c h e c k w i t h K a t
0102600 e a b o u t a n y p a p e
0102620 r w o r k y o u m a y n e
0102640 e d t o f i l l o u t t
0102660 o c o n t i n u e o n t h
0102700 e p a y r o l l i n 1 9 8
0102720 4 . \r \r \t L . \r \r \r * s t a r t
0102740 * \r 0 0 5 3 2 0 0 0 9 5 U S
0102760 \r g v M s g I D : M e g i d
0103000 d o . P A $ 3 # 7 3 @ 1 0 -
0103020 D e c - 8 3 1 3 : 4 7 : 4 0
0103040 P S T \r C a t e g o r i e s :
0103060 T r a c i n g s \r D a t e : 1
0103100 0 D e c . 1 9 8 3 1 : 4 0
0103120 p m P S T ( S a t u r d a
0103140 y ) \r F r o m : M e g i d d o
0103160 . P A \r S u b j e c t : 4 - p
0103200 a r t i t i o n i n g i n t
0103220 h e p l a n e \r T o : G u i
0103240 b a s , G r e e n e , R a m
0103260 s h a w , S t o l f i , C l
0103300 a r k s o n , Y a o \r c c :
0103320 M e g i d d o \r \r ( G i v e n
0103340 n p o i n t s f i n d
0103360 t w o s t r a i g h t l i n
0103400 e s t h a t p a r t i t i o
0103420 n t h e m i n t o f o u r
0103440 e q u a l s e t s ) \r \r I
0103460 f o u n d t h e w a y t o
0103500 d o i t d e t e r m i n i
0103520 s t i c a l l y i n l i n e
0103540 a r t i m e . I t ' s ( o
0103560 n c e a g a i n ! ) b a s e
0103600 d \r o n f i n d i n g m e d
0103620 i a n s i n l i n e a r t
0103640 i m e , a n d c a n b e
0103660 i m p l e m e n t e d m o r e
0103700 e f f i c i e n t l y w i t
0103720 h \r r a n d o m s e l e c t i
0103740 o n s . \r \r N i m r o d \r \r * s
0103760 t a r t * \r 0 3 1 2 4 0 0 0 9
0104000 6 U S \r g v M s g I D : s
0104020 t o l f i . p a $ 8 9 # 1 3
0104040 2 @ 1 3 - D e c - 8 3 1 0 : 0
0104060 6 : 2 8 P S T \r C a t e g o r
0104100 i e s : T r a c i n g s \r D a
0104120 t e : 1 3 D e c 8 3 1 0
0104140 : 0 6 : 1 4 P S T \r F r o m :
0104160 s t o l f i . p a \r S u b j e
0104200 c t : L i n e s i n s p a
0104220 c e \r T o : G u i b a s , R
0104240 a m s h a w \r C c : s t o l f
0104260 i \r \r I w a s t r y i n g
0104300 t o g e n e r a l i z e t h
0104320 e t h e o r y o f t h e
0104340 t w o - s i d e d p l a n e
0104360 t o h i g h e r d i m e n s
0104400 i o n s , a n d I a m h
0104420 a v i n g s o m e t r o u b
0104440 l e . I g u e s s I a m
0104460 m i s s i n g s o m e t h i
0104500 n g t r i v i a l . \r \r C o n
0104520 s i d e r o r d i n a r y t
0104540 h r e e - d i m e n s i o n a l
0104560 E u c l i d e a n s p a c e
0104600 c o m p l e t e d w i t h
0104620 t h e " p l a n e a t i n
0104640 f i n i t y " U , w i t h
0104660 t h e c o n v e n t i o n t
0104700 h a t a p o i n t a t i
0104720 n f i n i t y i n t h e d
0104740 i r e c t i o n d i s t h
0104760 e s a m e a s t h e o n
0105000 e i n t h e d i r e c t i
0105020 o n - d . T h e r e s u l
0105040 t i n g m a n i f o l d i s
0105060 c a l l e d ( i f I a m
0105100 n o t m i s t a k e n ) t
0105120 h r e e - d i m e n s i o n a l
0105140 p r o j e c t i v e s p a c
0105160 e , a n d i s h o m e o m
0105200 o r p h i c t o t h e " s
0105220 u r f a c e " o f a f o u
0105240 r - d i m e n s i o n a l s p
0105260 h e r e i n w h i c h d i
0105300 a m e t r i c a l l y o p p o
0105320 s i t e p o i n t s a r e
0105340 i d e n t i f i e d . D e n o
0105360 t e i t b y P 3 . \r \r C o
0105400 n s i d e r t h e s e t L
0105420 o f a l l s t r a i g h t
0105440 l i n e s i n t h i s m
0105460 a n i f o l d ( i . e . , a
0105500 l l s t r a i g h t l i n e
0105520 s i n o r d i n a r y t h
0105540 r e e - s p a c e p l u s t
0105560 h e l i n e s o n U ) .
0105600 T h i s s e t i s a F
0105620 O U R - d i m e n s i o n a l
0105640 m a n i f o l d ( d o y o u
0105660 b u y t h a t ? ) . \r \r Q u
0105700 e s t i o n n u m b e r 1 :
0105720 W h a t i s t h e t o p
0105740 o l o g y o f L ? M y
0105760 e a s y g u e s s i s t h
0106000 a t i t i s h o m e o m o
0106020 r p h i c t o f o u r - d
0106040 i m e n s i o n a l p r o j e
0106060 c t i v e s p a c e , i . e
0106100 . P 4 . H o w e v e r , I
0106120 h a v e n o t b e e n a
0106140 b l e t o p r o v e i t
0106160 i s n o t s o m e t h i n g
0106200 e l s e , f o r e x a m p
0106220 l e P 2 x P 2 . [ I n
0106240 g e n e r a l , t h e s e
0106260 t L [ d ' , d ] o f a l
0106300 l d ' - d i m e n s i o n a l
0106320 s u b s p a c e s o f d -
0106340 d i m e n s i o n a l s p a c
0106360 e i s a m a n i f o l d
0106400 w i t h d i m e n s i o n d
0106420 ' ' = ( d ' - 1 ) ( d - d '
0106440 ) . Q u e s t i o n n u m b
0106460 e r 1 t h e n g e n e r a
0106500 l i z e s t o : i s L [ d
0106520 ' , d ] h o m e o m o r p h
0106540 i c t o P d ' ' , o r t
0106560 o P ( d - 1 ) x P ( d - d
0106600 ' ) ? ] \r \r Q u e s t i o n n
0106620 u m b e r 2 : H o w s h o
0106640 u l d w e r e p r e s e n t
0106660 a l i n e i n t h r e e
0106700 - s p a c e ? I f L i s
0106720 i n d e e d h o m e o m o r p
0106740 h i c t o P 4 , i t s h
0106760 o u l d b e p o s s i b l e
0107000 t o c h a r a c t e r i z e
0107020 a l i n e b y F I V E
0107040 " h o m o g e n e o u s c o e
0107060 f f i c i e n t s " < A , B
0107100 , C , D , E > , s u c h
0107120 t h a t < A B C D E > a
0107140 n d < A ' B ' C ' D ' E ' >
0107160 a r e t h e s a m e l i n
0107200 e i f f o n e i s a n
0107220 o n z e r o m u l t i p l e
0107240 o f t h e o t h e r . I f
0107260 L i s P 2 x P 2 , t
0107300 h e n t h e r e s h o u l d
0107320 b e a r e p r e s e n t a
0107340 t i o n u s i n g t w o s
0107360 e t s o f t h r e e c o e
0107400 f f i c i e n t s , < A B C
0107420 | D E F > , w i t h e a c
0107440 h h a l f d e t e r m i n e
0107460 d u p t o a n I N D E P
0107500 E N D E N T n o n - z e r o
0107520 s c a l a r f a c t o r . I
0107540 n e i t h e r c a s e , t
0107560 h e t e s t s f o r a p
0107600 o i n t b e i n g o n t h
0107620 e l i n e , t w o l i n e
0107640 s i n t e r s e c t i n g ,
0107660 a n d s o f o r t h s h o
0107700 u l d b e n i c e l y s y
0107720 m m e t r i c o n a l l t
0107740 h o s e c o e f f i c i e n t
0107760 s . \r \r I f o u n d n e i t
0110000 h e r . I f o u n d a n
0110020 i c e , s y m m e t r i c a l
0110040 r e p r e s e n t a t i o n
0110060 u s i n g S I X c o e f f i
0110100 c i e n t s : I f a = [
0110120 x a y a z a w a ] a n d
0110140 b = [ x b y b z b w b ]
0110160 a r e t w o d i s t i n c
0110200 t p o i n t s o n t h e
0110220 l i n e ( i n h o m o g e n
0110240 e o u s c o o r d i n a t e s
0110260 ) , t h e n t a k e \r
0110300 \t | x a y a | \r A
0110320 x y = \t | |
0110340 \r \t | x b y b
0110360 | \r \r \t | x a
0110400 z a | \r A x z = \t |
0110420 | \r \t |
0110440 x b z b | \r \r a n d s
0110460 i m i l a r l y f o r A x w
0110500 , A y z , A y w , A z w .
0110520 \r \r T h e n a p o i n t p
0110540 = [ x p y p z p w p ] i
0110560 s o n t h e l i n e i f
0110600 f \r \r ( A y z x p - A x
0110620 z y p + A x y z p ) ^ 2
0110640 + \r ( A y w x p - A x
0110660 w y p + A x y w p ) ^ 2
0110700 + \r ( A z w x p - A x
0110720 w z p + A x z w p ) ^ 2
0110740 + \r ( A z w y p - A y
0110760 w z p + A y z w p ) ^ 2
0111000 = 0 \r \r ( I n c i d e n t a
0111020 l l y , t h e t e r m s w
0111040 i t h i n t h e p a r e n t
0111060 h e s i s a r e t h e c o
0111100 e f f i c i e n t s o f t h
0111120 e e q u a t i o n o f t h
0111140 e p l a n e a b p i n h
0111160 o m o g e n e o u s c o o r d
0111200 i n a t e s . ) \r \r I t i s
0111220 e a s y t o s e e t h a
0111240 t m u l t i p l y i n g a l
0111260 l t h e A # # b y a n
0111300 o n z e r o c o n s t a n t
0111320 g i v e s a n e q u i v a l
0111340 e n t i n e q u a l i t y ,
0111360 b u t c a n n o t q u i t e
0111400 s e e h o w t o e x p r
0111420 e s s t h e o t h e r d e
0111440 g r e e o f f r e e d o m
0111460 p r e s e n t i n t h e A
0111500 # # s , a n d n e i t h e r
0111520 r e c o m b i n e t h e m
0111540 i n t o f i v e e q u a l l
0111560 y s i g n i f i c a n t c o
0111600 e f f i c i e n t s . H e l p
0111620 ! . \r \r T h a n k s , \r \r j o
0111640 r g e \r \0 \0 \0 \0 006 \0 \0 235 312 \0
0111660 u \0 \0 002 230 \0 J 232 002 320 b s 004 234 030 230
0111700 034 J 232 002 235 004 234 \v 230 017 J 232 002 235 \a 234
0111720 020 230 027 J 232 002 235 002 234 021 230 023 J 232 002 235
0111740 002 234 \b 230 \n J 230 \0 J 230 231 001 J 230 260 003
0111760 J 230 277 001 J 230 307 003 J 230 355 004 J 230 335 002
0112000 J 230 262 001 J 230 \0 J 230 203 001 J 230 211 002 J
0112020 230 021 227 \0 205 227 \0 \0 \0 \0 \v Z \0 \0 \v 325
0112040 \0 \0 * s t a r t * \r 0 1 0 6 7
0112060 0 0 0 9 4 U S \r g v M s g I
0112100 D : R a m s h a w . p a $
0112120 3 # 8 @ 1 3 - D e c - 8 3 1 1
0112140 : 2 9 : 0 7 P S T \r C a t e g
0112160 o r i e s : T r a c i n g s \r
0112200 D a t e : 1 3 D e c 8 3
0112220 1 1 : 2 9 : 1 4 P S T \r F r o
0112240 m : R a m s h a w . p a \r S u
0112260 b j e c t : R e : L i n e s
0112300 i n s p a c e \r I n - r e p
0112320 l y - t o : " s t o l f i ' s
0112340 m e s s a g e o f 1 3 D
0112360 e c 8 3 1 0 : 0 6 : 1 4 P
0112400 S T " \r T o : s t o l f i \r C
0112420 c : G u i b a s , R a m s h
0112440 a w \r \r Q u i c k c o m m e n
0112460 t s : \r \r 1 ) I n t h
0112500 e n o n - p r o j e c t i v e
0112520 c a s e , t h e m a n i f
0112540 o l d s f o r m e d b y a
0112560 l l k - d i m e n s i o n a l
0112600 s u b s p a c e s o f a n
0112620 n - d i m e n s i o n a l s
0112640 p a c e i s c a l l e d a
0112660 G r a s s m a n m a n i f o
0112700 l d . G r a s s m a n m a
0112720 n i f o l d s a r e p r e t
0112740 t y c o m m o n e x a m p l
0112760 e c a s e s i n d i f f e
0113000 r e n t i a l g e o m e t r y
0113020 b o o k s . M y s e n s
0113040 e i s t h a t t h e y a
0113060 r e a p r e t t y r i c h
0113100 c l a s s o f m a n i f o
0113120 l d s , t o p o l o g i c a l
0113140 l y ; t h e y a r e n ' t
0113160 a l l h o m e o m o r p h i
0113200 c t o v e c t o r s p a c
0113220 e s , o r s o m e t h i n g
0113240 l i k e t h a t . I w
0113260 o u l d g u e s s t h a t
0113300 t h e s a m e i s t r u e
0113320 i n t h e p r o j e c t i
0113340 v e c a s e a s w e l l .
0113360 \r \r 2 ) M y f i r s t
0113400 g u e s s w o u l d b e
0113420 t h a t t h e o t h e r d
0113440 e g r e e o f f r e e d o m
0113460 c o m e s f r o m t h e
0113500 f a c t t h a t n o t a l
0113520 l 6 - t u p l e s o f n u
0113540 m b e r s c a n o c c u r
0113560 a s < A x y , A x z , A y
0113600 z , A x w , A y w , A z w
0113620 > ; t h e r e i s p r o
0113640 b a b l y s o m e p o l y n
0113660 o m i a l i d e n t i t y o
0113700 n t h e s e s i x v a l u
0113720 e s t h a t i s n o n z e
0113740 r o . \r \r L y l e \r \r \r \0 \0
0113760 \0 \0 006 \0 \0 235 312 \0 X \0 \0 002 230 \0 J 232
0114000 002 320 b s 004 234 030 230 034 J 232 002 235 004 234 \f
0114020 230 020 J 232 002 235 \a 234 024 230 033 J 232 002 235 \v
0114040 234 . 230 9 J 232 002 235 002 234 \b 230 \n J 232 002
0114060 235 002 234 021 230 023 J 230 \0 J 230 311 005 227 \0 205
0114100 227 \0 \0 \0 \0 003 p \0 \0 003 316 \0 \0 * s t
0114120 a r t * \r 0 1 9 7 9 0 0 0 9 6
0114140 U S \r g v M s g I D : s t
0114160 o l f i . p a $ 8 9 # 1 3 2
0114200 @ 1 4 - D e c - 8 3 7 : 3 9
0114220 : 1 7 P S T \r C a t e g o r i
0114240 e s : T r a c i n g s \r D a t
0114260 e : 1 4 D e c 8 3 7 :
0114300 3 8 : 5 4 P S T \r F r o m :
0114320 s t o l f i . p a \r S u b j e c
0114340 t : R e : L i n e s i n
0114360 s p a c e \r I n - r e p l y - t
0114400 o : " R a m s h a w ' s m e
0114420 s s a g e o f 1 3 D e c
0114440 8 3 1 1 : 2 9 : 1 4 P S T "
0114460 \r T o : R a m s h a w \r C c :
0114500 s t o l f i , G u i b a s \r
0114520 \r T h a n k s f o r t h e
0114540 h i n t . I h a v e l o o
0114560 k e d u p G r a s s m a n n
0114600 m a n i f o l d s o n t h
0114620 e E D M . I h a v e n
0114640 o t d e c y p h e r e d e v
0114660 e r y t h i n g y e t , b u
0114700 t i t s e e m s t h e y
0114720 a r e r e a l l y w h a t
0114740 I a m a f t e r . \r \r T h e
0114760 E D M d e f i n e s a G
0115000 r a s s m a n n m a n i f o l
0115020 d G n , k a s t h e s e
0115040 t o f a l l L I N E A R
0115060 k - d i m e n s i o n a l s u
0115100 b s p a c e s o f R ^ n .
0115120 N o w t h e r e i s a
0115140 o n e - t o - o n e c o r r e
0115160 s p o n d e n c e b e t w e e
0115200 n t h o s e s u b s p a c e
0115220 s a n d t h e ( k - 1 ) -
0115240 d i m e n s i o n a l P R O J
0115260 E C T I V E ( ~ a f f i n e )
0115300 s u b s p a c e s o f ( n
0115320 - 1 ) - d i m e n s i o n a l
0115340 p r o j e c t i v e s p a c e
0115360 , w h i c h i s w h a t
0115400 I w a s a f t e r . \r \r A c
0115420 t u a l l y , t h e t h i n
0115440 g I R E A L L Y w a s a
0115460 f t e r i s w h a t t h e
0115500 y c a l l t h e O R I E N
0115520 T E D G r a s s m a n n m a
0115540 n i f o l d G ' n , k , t h
0115560 e s e t o f a l l o r i
0115600 e n t e d k - d i m . l i n
0115620 e a r s u b s p a c e s o f
0115640 R ^ n , w h i c h a r e
0115660 i n o n e - t o - o n e c o
0115700 r r e s p o n d e n c e w i t
0115720 h t h e o r i e n t e d (
0115740 k - 1 ) - d i m . a f f i n e
0115760 s u b s p a c e s o f ( n
0116000 - 1 ) - d i m . t w o - s i d
0116020 e d s p a c e . I n p a r
0116040 t i c u l a r , t h e s e t
0116060 o f o r i e n t e d l i n
0116100 e s i n t w o - s i d e d
0116120 t h r e e - s p a c e i s G
0116140 ' 4 , 2 . \r \r T h e E D M s
0116160 a y s t h a t G ' n , k i
0116200 s h o m e o m o r p h i c t
0116220 o S O ( n ) / S O ( k ) x
0116240 S O ( n - k ) , w h e r e S
0116260 O ( k ) i s t h e g r o u
0116300 p o f ( o r i e n t a t i o
0116320 n - p r e s e r v i n g ) r o
0116340 t a t i o n s i n R ^ k .
0116360 I t a l s o s a y s t h a
0116400 t G n , 1 i s e q u i v a
0116420 l e n t t o P ( n - 1 ) ,
0116440 a n d t h a t G ' n , 1 i
0116460 s e q u i v a l e n t t o
0116500 t h e ( n - 1 ) - d i m e n s
0116520 i o n a l s p h e r e . I t
0116540 s a y s n o t h i n g a b
0116560 o u t g e n e r a l G ' n ,
0116600 k s , s o I m u s t a s
0116620 s u m e t h e y a r e o r
0116640 i g i n a l b e a s t s i n
0116660 d e e d . T h e r e f o r e ,
0116700 t h e r e i s n o h o m
0116720 o g e n e o u s f i v e - p a
0116740 r a m e t e r r e p r e s e n
0116760 t a t i o n f o r l i n e s
0117000 i n s p a c e ( n o r a
0117020 d o u b l y h o m o g e n e
0117040 o u s t h r e e - p l u s - t
0117060 h r e e - p a r a m e t e r o
0117100 n e ) . \r \r I w i l l t r y
0117120 y o u r s u g g e s t i o n
0117140 a n d l o o k f o r i d
0117160 e n t i t i e s i n v o l v i
0117200 n g t h e A i j . M y
0117220 n e x t g u e s s i s t h
0117240 a t t h e r e i s s o m e
0117260 " p s e u d o - h o m o g e n
0117300 e o u s " r e p r e s e n t a
0117320 t i o n , s a y u s i n g
0117340 s i x c o e f f i c i e n t s
0117360 i n a 3 b y 2 a r r
0117400 a y , d e t e r m i n e d u
0117420 p t o m u l t i p l i c a t
0117440 i o n b y a n o r t h o g
0117460 o n a l 2 b y 2 m a t r
0117500 i x w i t h p o s i t i v e
0117520 d e t e r m i n a n t . O r
0117540 s o m e t h i n g l i k e
0117560 t h i s . \r \r T h a n k s .
0117600 S e e y o u , \r \r j o r g e
0117620 \r \r \r \0 \0 \0 \0 006 \0 \0 235 312 \0 n \0 \0
0117640 002 230 \0 J 232 002 320 b s 004 234 030 230 034 J 232
0117660 002 235 004 234 \v 230 017 J 232 002 235 \a 234 024 230 033
0117700 J 232 002 235 \v 234 / 230 : J 232 002 235 002 234 \t
0117720 230 \v J 232 002 235 002 234 020 230 022 J 230 \0 J 230
0117740 233 001 J 230 240 002 J 230 330 002 J 230 336 003 J 230
0117760 261 002 J 230 031 J 230 \0 227 \0 205 227 \0 \0 \0 \0
0120000 006 350 \0 \0 \a \ \0 \0 * s t a r t * \r
0120020 0 0 3 8 6 0 0 0 9 5 U S \r
0120040 g v M s g I D : M e g i d d o
0120060 . P A $ 3 # 7 3 @ 1 4 - D e
0120100 c - 8 3 9 : 0 5 : 5 4 P S
0120120 T \r C a t e g o r i e s : T r
0120140 a c i n g s \r D a t e : 1 4
0120160 D e c . 1 9 8 3 9 : 0 5 a
0120200 m P S T ( W e d n e s d a y
0120220 ) \r F r o m : M e g i d d o .
0120240 P A \r S u b j e c t : R e :
0120260 4 - p a r t i t i o n i n g i
0120300 n t h e p l a n e \r T o :
0120320 G u i b a s , Y a o \r c c :
0120340 G r e e n e , R a m s h a w
0120360 , S t o l f i , C l a r k s
0120400 o n , M e g i d d o \r \r W e
0120420 l l . I i n d e e d k n o
0120440 w h o w t o d o i t i
0120460 n l i n e a r - t i m e .
0120500 P l e a s e s t o p b y a
0120520 n d I ' l l s h o w \r y o u
0120540 i f y o u a r e i n t e
0120560 r e s t e d . \r \r N i m r o d 001
0120600 M e s s a g e 002 \r \r * s t a r t
0120620 * \r 0 2 3 3 6 0 0 0 9 5 U S
0120640 \r g v M s g I D : G u i b a
0120660 s . p a $ 3 # 1 8 3 @ 1 4 -
0120700 D e c - 8 3 1 2 : 5 5 : 4 0
0120720 P S T \r C a t e g o r i e s :
0120740 T r a c i n g s \r D a t e : 1
0120760 4 - D e c - 8 3 1 2 : 5 5 : 2
0121000 4 P S T \r F r o m : G u i b
0121020 a s . p a \r S u b j e c t : R
0121040 e : L i n e s i n s p a c
0121060 e , 2 - n d m e s s a g e \r
0121100 T o : S t o l f i \r c c : R
0121120 a m s h a w , G u i b a s \r \r
0121140 Y o u a r e r i g h t . I
0121160 n s o l i d a n a l y t i c
0121200 g e o m e t r y t h e m o
0121220 s t c o m m o n r e p r e s
0121240 e n t a t i o n o f a l i
0121260 n e i s v i a a s i x t
0121300 u p l e t o f n u m b e r s
0121320 ( p , q , r , a , b , c ) ,
0121340 w h e r e y o u c a n t h
0121360 i n k o f ( p , q , r ) a
0121400 s a p o i n t o n t h e
0121420 l i n e , a n d o f ( a
0121440 , b , c ) a s a p o i n t
0121460 ( o t h e r t h a n t h e
0121500 o r i g i n ) o n a l i
0121520 n e t h r o u g h t h e o
0121540 r i g i n a n d p a r a l l
0121560 e l t o t h e g i v e n
0121600 o n e . W h e n a , b ,
0121620 a n d c a r e n o r m a l
0121640 i z e d s o t h a t a ^ 2
0121660 + b ^ 2 + c ^ 2 = 1 , t h e y
0121700 a r e c a l l e d t h e
0121720 d i r e c t i o n a l c o s i
0121740 n e s o f t h e l i n e .
0121760 \r \r T h e r e a r e t w o
0122000 f a m i l i e s o f l i n e
0122020 a r t r a n s f o r m a t i o
0122040 n s o n ( p , q , r , a , b
0122060 , c ) t h a t l e a v e t
0122100 h e l i n e i n v a r i a n
0122120 t . T h e f i r s t i s
0122140 ( a ' , b ' , c ' ) _ ( l a
0122160 m b d a a , l a m b d a b
0122200 , l a m b d a c ) f o r
0122220 s o m e n o n - z e r o c o
0122240 n s t a n t l a m b d a . T
0122260 h e s e c o n d i s ( p '
0122300 , q ' , r ' ) _ ( p + m
0122320 u a , q + m u b , r
0122340 + m u c ) , f o r s o
0122360 m e c o n s t a n t m u .
0122400 T h e s e a r e c o n v e n
0122420 i e n t l y e x p r e s s e d
0122440 b y v i e w i n g t h e
0122460 l i n e a s a 2 X 3 m a
0122500 t r i x [ p , q , r / / a , b
0122520 , c ] a n d a s s e r t i n
0122540 g t h a t t h e l i n e
0122560 i s i n v a r i a n t b y
0122600 l e f t m u l t i p l i c a t
0122620 i o n w i t h n o n - s i n
0122640 g u l a r m a t r i c e s o
0122660 f t h e f o r m [ 1 , m u
0122700 / / 0 , l a m b d a ] . O f
0122720 c o u r s e y o u w a n t
0122740 t o r e s t r i c t l a m b
0122760 d a t o b e p o s i t i v
0123000 e f o r t h e o r i e n t
0123020 e d c a s e . \r \r S o m e o
0123040 t h e r u s e f u l f a c t
0123060 s a b o u t t h i s r e p
0123100 r e s e n t a t i o n a r e
0123120 ( w e d i d h a v e l o t
0123140 s o f g e o m e t r y i n
0123160 h i g h s c h o o l ! ) : \r
0123200 \r C o n d i t i o n f o r l
0123220 i n e s l a n d l ' t o
0123240 b e c o p l a n a r i s \r
0123260 \r \t d e t r m i n a n t [ a , a
0123300 ' , p - p ' / / b , b ' , q - q
0123320 ' / / c , c ' , r - r ' ] =
0123340 0 . \r \t \r C o n d i t i o n f
0123360 o r l i n e s l a n d l
0123400 ' t o b e p e r p e n d i
0123420 c u l a r i s \r \r \t a a ' +
0123440 b b ' + c c ' = 0 . \r
0123460 \t \r D i s t a n c e f r o m
0123500 p o i n t ( x , y , z ) t o
0123520 l i n e l i s d , w h
0123540 e r e \r \r \t d ^ 2 = ( X ^ 2
0123560 + Y ^ 2 + Z ^ 2 ) / ( a ^ 2 + b
0123600 ^ 2 + c ^ 2 ) , w i t h \r \t \r
0123620 \t \t \t X = b ( z - r ) - c (
0123640 y - q ) \t \t \t \t \t \t i n c i d e
0123660 n t a l l y , X , Y , a n
0123700 d Z ( = 0 ) a r e t h e
0123720 e q u a t i o n s \r \t \t \t Y
0123740 = c ( x - p ) - a ( z - r ) ,
0123760 a n d \t \t \t \t \t o f t h e
0124000 p r o j e c t i o n s o f t
0124020 h e l i n e o n t h e c
0124040 o o r d i n a t e \r \t \t \t Z =
0124060 a ( y - q ) - b ( x - p ) \t \t
0124100 \t \t \t \t p l a n e s ( I t h
0124120 i n k . . . ) \r \t \t \t \r \t I
0124140 a m s u r e y o u r f o r
0124160 m u l a f o r a p o i n t
0124200 o n t h e l i n e a c t
0124220 u a l l y c o m p u t e s t
0124240 h e d i s t a n c e a n d
0124260 i s e q u i v a l e n t t o
0124300 t h e a b o v e . \r \t \r D i
0124320 s t a n c e d b e t w e e n
0124340 l i n e l a n d l ' : \r
0124360 \r \t S e t ( b y a n a l o g
0124400 y w i t h y o u r n o t a
0124420 t i o n ) , D x y = a b '
0124440 - b a ' , D y z = b c ' -
0124460 c b ' , D z x = c a ' - a
0124500 c ' . T h e n \r \t \r \t d ^ 2
0124520 = [ D y z ( p - p ' ) +
0124540 D z x ( q - q ' ) + D x y
0124560 ( r - r ' ) ] ^ 2 / ( D y
0124600 z ^ 2 + D z x ^ 2 + D x
0124620 y ^ 2 ) . \r \t \r U n f o r t u n
0124640 a t e l y t h i s r e p r e
0124660 s e n t a t i o n m a y n o
0124700 t m e s h s o w e l l w
0124720 i t h h o m e g e n e o u s
0124740 r e p r e s e n t a t i o n s
0124760 f o r p o i n t s a n d p
0125000 l a n e s . I w i l l p o
0125020 n d e r t h i s s o m e m
0125040 o r e . \r \r T h a n k s t o
0125060 b o t h y o u a n d L y l
0125100 e f o r t h e d i s c u s
0125120 s i o n o f G r a s s m a n
0125140 n m a n i f o l d s . I t
0125160 w a s a m o s t e n t i r e
0125200 l y n e w t o m e a n d
0125220 q u i t e i n f o r m a t i
0125240 v e . \r \r \t L . \r \t * s t a r t
0125260 * \r 0 3 5 5 3 0 0 0 9 6 U S
0125300 \r g v M s g I D : g n e l s
0125320 o n . p a $ 3 # 2 1 8 @ 1 5
0125340 - D e c - 8 3 1 6 : 1 3 : 2 6
0125360 P S T \r C a t e g o r i e s :
0125400 T r a c i n g s \r D a t e :
0125420 1 5 D e c 8 3 1 6 : 1 3 :
0125440 2 3 P S T \r F r o m : g n e
0125460 l s o n . p a \r S u b j e c t :
0125500 C o r n e r - s t i t c h i n
0125520 g , u n p a r s i n g , t h
0125540 e p r e d i c a t e c a l c
0125560 u l u s , a n d g u a r d e
0125600 d c o m m a n d s \r T o : C
0125620 S L ^ , I D L ^ \r R e p l y -
0125640 t o : S u b h a n a . p a \r \r
0125660 A c o u p l e o f m o n t
0125700 h s a g o I r e s o l v e
0125720 d t o k e e p m y t e c
0125740 h n i c a l j o u r n a l m
0125760 o r e n e a t l y t h a n
0126000 b e f o r e . A s a r e
0126020 s u l t I n o w h a v e
0126040 s e v e r a l j o u r n a l
0126060 e n t r i e s o n t h e a
0126100 b o v e t o p i c s . I
0126120 c o u l d p u t t h e s e
0126140 e n t r i e s i n t h e C
0126160 S L n o t e b o o k , b u t
0126200 m a n y o f t h e m a r
0126220 e h a n d w r i t t e n , a
0126240 n d a n y w a y i t s e e
0126260 m s s i m p l e r j u s t
0126300 t o l e t p e o p l e k n
0126320 o w t h e y e x i s t a n
0126340 d p r o v i d e c o p i e s
0126360 o n r e q u e s t . S o
0126400 s e n d S u b h a n a o r
0126420 m e a m e s s a g e i f
0126440 y o u w a n t c o p i e s
0126460 o f a n y o f t h e f
0126500 o l l o w i n g . \r \r A b o u t
0126520 c o r n e r - s t i t c h e d
0126540 d a t a s t r u c t u r e s
0126560 : \r \r C G N 1 . E n n u m e r
0126600 a t i o n o f r e c t a n g
0126620 u l a r r e g i o n s i n
0126640 c o r n e r - s t i t c h e d
0126660 d a t a s t r u c t u r e s .
0126700 A d e s c r i p t i o n
0126720 o f t h e S h a n d - M c C
0126740 r e i g h t b o u n d e d s
0126760 p a c e t r a v e r s a l a
0127000 l g o r i t h m f o r r e c
0127020 t a n g u l a r r e g i o n s
0127040 i n c o r n e r - s t i t c
0127060 h e d d a t a s t r u c t u
0127100 r e s . \r \r C G N 2 . F i n d
0127120 i n g p o s i t i o n s i n
0127140 c o r n e r - s t i t c h e d
0127160 d a t a s t r u c t u r e s
0127200 . I n h i s d e a l e r
0127220 , M a r k S h a n d d e s
0127240 c r i b e d h o w t o h o
0127260 m e i n o n t h e t i l
0127300 e c o n t a i n i n g a g
0127320 i v e n ( x , y ) p o s i
0127340 t i o n , b y f o l l o w i
0127360 n g c o r n e r - s t i t c h
0127400 e s i n t h e d i r e c t
0127420 i o n o f t h e g o a l .
0127440 B u t s i n c e , i n s
0127460 u c h a d a t a s t r u c
0127500 t u r e , n o r t h w a r d
0127520 m o v e m e n t i s a c c o
0127540 m p a n i e d b y e a s t -
0127560 w a r d d r i f t , a n d
0127600 w e s t w a r d m o v e m e n
0127620 t i s a c c o m p a n i e d
0127640 b y s o u t h w a r d d r
0127660 i f t , i t i s d i f f i
0127700 c u l t t o t a c k t o w
0127720 a r d s t h e n o r t h - w
0127740 e s t . ( O r s o u t h -
0127760 e a s t . ) A p p a r a n t
0130000 l y n o n e o f t h o s e
0130020 w h o h a v e u s e d t
0130040 h i s d a t a s t r u c t u
0130060 r e h a v e b o t h e r e d
0130100 t o p r o v e t h a t t
0130120 h e l o o p t e r m i n a t
0130140 e s . T h i s n o t e s
0130160 u p p l i e s s o m e t h i n
0130200 g o f a p r o o f . \r
0130220 \r C G N 3 . A c o r r e c t
0130240 i o n t o C G N 2 . T h
0130260 i s n o t e r e c o r d s
0130300 a n o b s e r v a t i o n o
0130320 f J i m S a x e t h a t
0130340 w a s r e l a y e d t o m
0130360 e b y L y l e R a m s h a
0130400 w : t h a t a t h e o r e
0130420 m o f L e o G u i b a s
0130440 a n d F r a n c e s Y a o
0130460 p r o v i d e s a s i m p l
0130500 e r p r o o f t h a n t h
0130520 a t p r e s e n t e d i n
0130540 C G N 2 . C G N 3 r e c o
0130560 r d s t h e n e w p r o o
0130600 f . \r \r C G N 6 . C o r r e
0130620 c t i n g t h e C o r r e c
0130640 t i o n . I n C G N 3 I
0130660 t r a n s c r i b e d L e o
0130700 a n d F r a n c e s ' p r
0130720 o o f , t r a n s l a t i n g
0130740 i t f r o m E n g l i s h
0130760 i n t o t h e p r e d i c
0131000 a t e c a l c u l u s a s
0131020 I d i d s o , s i n c e
0131040 t h i s i s t h e s t y l
0131060 e o f p r o o f t h a t
0131100 I p r e f e r . B u t I
0131120 m a d e a m i s t a k e ,
0131140 w h i c h H o w a r d S t u
0131160 r g i s f o u n d . C G N
0131200 6 p r e s e n t s a c o r
0131220 r e c t p r o o f . \r \r A b o
0131240 u t t h e p r e d i c a t e
0131260 c a l c u l u s a n d g u
0131300 a r d e d c o m m a n d s \r \r
0131320 C G N 4 . C o m b i n i n g
0131340 S a t i s f i a b i l i t y P
0131360 r o c e d u r e s b y E q u
0131400 a l i t y S h a r i n g .
0131420 T h i s d e s c r i b e s a
0131440 s i m p l e m e t h o d f
0131460 o r c o m b i n i n g t h e
0131500 o r e m - p r o v e r s f o r
0131520 d i f f e r e n t t h e o r
0131540 i e s i n t o a c o m b i
0131560 n e d t h e o r e m - p r o v
0131600 e r f o r t h e c o m b i
0131620 n e d t h e o r i e s .
0131640 T h e m e t h o d i s u s
0131660 e d i n t h e h e a r t
0131700 o f t h e J u n o 2 i n
0131720 t e r p r e t e r , t o c o
0131740 o r d i n a t e t h e a p p
0131760 l i c a t i o n o f t h e
0132000 g e o m e t r i c c o n s t r
0132020 a i n t - s o l v e r a n d
0132040 t h e p a t t e r n - m a t c
0132060 h i n g c o n s t r a i n t
0132100 s o l v e r . \r \r C G N 5 .
0132120 P r e d i c a t e A l g e b r
0132140 a . A n i n t r o d u c t
0132160 i o n t o t h e p r e d i
0132200 c a t e c a l c u l u s , a
0132220 s I u n d e r s t a n d i
0132240 t . \r \r C G N 7 . F r o m p
0132260 r e d i c a t e s t o r e l
0132300 a t i o n s a n d f u n c t
0132320 i o n s . T h i s i s a
0132340 c o n t i n u a t i o n o f
0132360 C G N 5 , d i s c u s s i n
0132400 g t h e t r e a t m e n t
0132420 o f p a r t i a l f u n c t
0132440 i o n s . \r \r C G N 1 0 . G u
0132460 a r d e d C o m m a n d s i
0132500 n 5 3 e a s y s t e p s .
0132520 T h i s i s a s u m m
0132540 a r y o f t h e p r o g r
0132560 a m m i n g n o t a t i o n
0132600 t h a t I u s e . \r \r A b o
0132620 u t u n p a r s i n g o r
0132640 p r e t t y - p r i n t i n g \r
0132660 \r C G N 8 . U n p a r s i n
0132700 g . T h i s n o t e d e
0132720 s c r i b e s a n a l g o r
0132740 i t h m f o r u n p a r s i
0132760 n g ( o r p r e t t y - p r
0133000 i n t i n g ) . T h e a l g
0133020 o r i t h m i s i n t e r e
0133040 s t i n g b e c a u s e i t
0133060 m a k e s n o n - t r i v i
0133100 a l u s e o f e x c e p t
0133120 i o n - h a n d l i n g . \r \r C
0133140 G N 9 . U n p a r s i n g
0133160 c o n t i n u e d . A s p
0133200 a r t o f t h e J u n o
0133220 s y s t e m I h a v e i m
0133240 p l e m e n t e d a g e n e
0133260 r a l - p u r p o s e f o r m
0133300 a t t i n g p a c k a g e ,
0133320 w h i c h M i k e S p r e i
0133340 t z e r h a s c o n n e c t
0133360 e d t o I O t o y e i l
0133400 d f o r m a t t i n g I O
0133420 s t r e a m s , w h i c h a
0133440 c c e p t f o r m a t t i n g
0133460 c o m m a n d s a s w e l
0133500 l a s c h a r a c t e r s .
0133520 C G N 9 a p p l i e s t
0133540 h e g e n e r a l m e t h o
0133560 d o f C G N 8 t o t h e
0133600 p a r t i c u l a r f o r m
0133620 a t t i n g c o m m a n d s
0133640 u s e d i n M i k e ' s a
0133660 n d m y p a c k a g e .
0133700 I f y o u w a n t t o r
0133720 e a l l y u n d e r s t a n d
0133740 t h e f o r m a t t i n g
0133760 c o d e s , y o u p r o b a
0134000 b l y h a v e t o r e a d
0134020 C G N 8 a n d C G N 9 .
0134040 \r \0 \0 \0 006 \0 \0 235 312 \0 d \0 \0 002 230 \0
0134060 J 232 002 320 b s 004 234 030 230 034 J 232 002 235 004
0134100 234 \f 230 020 J 232 002 235 \a 234 K 230 R J 232 002
0134120 235 002 234 \f 230 016 J 232 002 235 \b 234 \f 230 024 J
0134140 230 \0 J 232 \a 234 233 003 317 i & 234 254 \n 236 1
0134160 234 277 005 236 $ 234 357 004 230 360 030 227 \0 205 227 \0
0134200 \0 \0 \0 \r 030 \0 \0 \r 202 \0 \0 * s t a r
0134220 t * \r 0 3 1 6 6 0 0 0 9 6 U
0134240 S \r g v M s g I D : s t o l
0134260 f i . p a $ 8 9 # 1 3 2 @ 1
0134300 6 - D e c - 8 3 8 : 2 6 : 4
0134320 7 P S T \r C a t e g o r i e s
0134340 : T r a c i n g s \r D a t e :
0134360 1 6 D e c 8 3 8 : 2 6
0134400 : 2 3 P S T \r F r o m : s t
0134420 o l f i . p a \r S u b j e c t :
0134440 R e : L i n e s i n s p
0134460 a c e , 2 - n d m e s s a g
0134500 e \r I n - r e p l y - t o : "
0134520 G u i b a s ' m e s s a g e
0134540 o f 1 4 - D e c - 8 3 1 2 :
0134560 5 5 : 2 4 P S T " \r T o : G
0134600 u i b a s \r C c : S t o l f i
0134620 , R a m s h a w \r \r L e o ,
0134640 t h a n k s f o r t h e l
0134660 e c t u r e . I k n e w I
0134700 w a s m i s s i n g s o m
0134720 e t h i n g t r i v i a l . .
0134740 . \r \r I h a v e s p e n t
0134760 s o m e t i m e t r y i n g
0135000 t o e x t e n d t h e (
0135020 p , q , r / / a , b , c ) r e
0135040 p r e s e n t a t i o n t o
0135060 i n c l u d e l i n e s a t
0135100 i n f i n i t y , w i t h o
0135120 u t m u c h s u c c e s s .
0135140 F r u s t r a t i n g ; i t
0135160 s e e m s s o c l o s e .
0135200 . . \r \r O n t h e o t h e r
0135220 h a n d , I t h i n k I
0135240 h a v e f o u n d a n i
0135260 d e n t i t y t h a t m y
0135300 s i x c o e f f i c i e n t s
0135320 A i j m u s t s a t i s f
0135340 y , n a m e l y A x y A z w
0135360 - A x z A y w + A x w A
0135400 y z = 0 . N o w l e t
0135420 \r \r A x y = P x y +
0135440 Q z w , \t A z w = P x y -
0135460 Q z w , \r A x z = Q x
0135500 z - P y w , \t A y w = Q
0135520 x z + P y w , \r A x w
0135540 = P x w + Q y z , \t A y z
0135560 = P x w - Q y z \r \r ( i
0135600 . e . , P x y = ( A x y
0135620 + A z w ) / 2 , Q z w = (
0135640 A x y - A z w ) / 2 , e t
0135660 c . ) T h e n t h e i d e
0135700 n t i t y b e c o m e s \r \r
0135720 P x y ^ 2 - Q z w ^ 2
0135740 - Q x z ^ 2 + P y w
0135760 ^ 2 + P x w ^ 2 - Q y
0136000 w ^ 2 = 0 \r \r o r \r \r P
0136020 x y ^ 2 + P y w ^ 2 +
0136040 P x w ^ 2 = Q z w
0136060 ^ 2 + Q x z ^ 2 + Q y w
0136100 ^ 2 \r \r I f P ' s a n d Q
0136120 ' s a r e a n y r e a l
0136140 n u m b e r s s a t i s f y n
0136160 g t h i s i d e n t i t y ,
0136200 t h e n t h e P ' s a r
0136220 e a l l z e r o i f f t
0136240 h e Q ' s a r e a l l z
0136260 e r o . T h e r e i s a
0136300 o n e - t o - o n e c o r r e
0136320 s p o n d e n c e b e t w e e
0136340 n t h e P Q ' s a n d t
0136360 h e A ' s , a n d t h e
0136400 f o r m e r a r e a l l z
0136420 e r o i f f t h e l a t t
0136440 e r a r e a l l z e r o .
0136460 N o t e a l s o t h a t
0136500 s c a l i n g a l l P ' s
0136520 a n d Q ' s b y a c o n
0136540 s t a n t d o e s t h e s
0136560 a m e t o t h e A ' s (
0136600 a n d t h e r e f o r e l e
0136620 a v e s t h e l i n e u n
0136640 c h a n g e d ) . \r \r T h i s
0136660 s u g g e s t s r e p r e s e
0136700 n t i n g a l i n e b y
0136720 s i x n u m b e r s < P 1 ,
0136740 P 2 , P 3 / / Q 1 , Q 2 ,
0136760 Q 3 > s u c h t h a t n
0137000 o t a l l t h r e e P ' s
0137020 a r e z e r o , a n d n
0137040 o t a l l t h r e e Q ' s
0137060 a r e z e r o , w i t h
0137100 t h e c o n v e n t i o n t
0137120 h a t \r \r ( P x y , P y
0137140 w , P x w ) = ( P 1 ,
0137160 P 2 , P 3 ) / s q r t ( P 1 ^
0137200 2 + P 2 ^ 2 + P 3 ^ 2 ) \r
0137220 ( Q x y , Q y w , Q x w )
0137240 = ( Q 1 , Q 2 , Q 3 ) / s
0137260 q r t ( Q 1 ^ 2 + Q 2 ^ 2 + Q 3
0137300 ^ 2 ) \r \r F r o m t h e s e
0137320 w e c a n c o m p u t e
0137340 s i x n o n - z e r o A ' s
0137360 s a t i s f y i n g t h e
0137400 i d e n t i t y a b o v e .
0137420 A n o t h e r s e x t u p l
0137440 e t < P 1 ' , P 2 ' , P 3
0137460 ' / / Q 1 ' , Q 2 ' , Q 3 '
0137500 > p r o d u c e s t h e s
0137520 a m e A ' s ( w i t h t h
0137540 e s a m e s i g n s ) i f
0137560 f \r \r ( P 1 ' , P 2 ' ,
0137600 P 3 ' ) = a l p h a ( P 1
0137620 , P 2 , P 3 ) \r ( Q 1
0137640 ' , Q 2 ' , Q 3 ' ) = b
0137660 e t a ( Q 1 , Q 2 , Q 3 ) \r
0137700 \r w i t h a l p h a > 0 ,
0137720 b e t a > 0 . ( I f a
0137740 l p h a < 0 , b e t a <
0137760 0 i t w i l l p r o d u
0140000 c e t h e n e g a t i v e s
0140020 o f t h o s e A ' s ) \r
0140040 \r T h i s i s a l l v e r
0140060 y n i c e ( a s s u m i n g
0140100 I d i d n ' t m a k e s
0140120 o m e h o r r i b l e m i s
0140140 t a k e i n t h e d e r i
0140160 v a t i o n s a b o v e ) ,
0140200 b u t I s t i l l h a v e
0140220 t o c h e c k w h e t h
0140240 e r e v e r y s e t o f
0140260 A ' s g e n e r a t e d b y
0140300 t h i s p r o c e s s c o
0140320 r r e s p o n d s t o s o m
0140340 e l i n e , a n d w h e t
0140360 h e r t h o s e l i n e s
0140400 a r e a l l d i s t i n c t
0140420 . N o t e t h a t t h e
0140440 c o l l e c t i o n o f t h
0140460 o s e A ' s i s a f o u
0140500 r - d i m e n s i o n a l m a
0140520 n i f o l d , s o t h e r e
0140540 c a n b e a n y o t h e
0140560 r i d e n t i t i e s t o
0140600 b e s a t i s f i e d , n o
0140620 r d e g r e e s o f f r e
0140640 e d o m . T h e r e m a y
0140660 b e p a t h o l o g i c a l
0140700 s u b s e t s o f s m a l
0140720 l e r d i m e n s i o n , t
0140740 h o u g h . \r \r I n f a c t
0140760 , t h e r e a r e h i n t
0141000 s t h a t s o m e t h i n g
0141020 m u s t b e w r o n g .
0141040 I f t h e r e p r e s e n t
0141060 a t i o n a b o v e w e r e
0141100 r e a l l y o n e - t o - o
0141120 n e , t h e n t h e s e t
0141140 o f a l l O R I E N T E D
0141160 l i n e s i n t w o - s i
0141200 d e d p r o j e c t i v e t
0141220 h r e e - s p a c e , t h a t
0141240 w e k n o w i s t h e
0141260 o r i e n t e d G r a s s m a
0141300 n n m a n i f o l d G ' 4 ,
0141320 2 , w o u l d b e h o m e
0141340 o m o r p h i c t o S 2 x
0141360 S 2 ( t h e s p h e r e
0141400 s q u a r e d ) , w h i c h
0141420 w o u l d b e s u r p r i s
0141440 i n g . ( A l s o , t h e
0141460 s e t o f t h e N O N - O
0141500 R I E N T E D l i n e s i n
0141520