UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Pattern recognition in circuit networks Radke, John D. 1982

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

Item Metadata

Download

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

Full Text

PATTERN RECOGNITION IN CIRCUIT NETWORKS by JOHN D. RADKE B.A. W i l f r i d Laurier University, 1975 M.A. W i l f r i d Laurier University, 1977 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in THE FACULTY OF GRADUATE STUDIES (Department of Geography) We accept this thesis as conforming to the required standard. THE UNIVERSITY OF BRITISH COLUMBIA November, 1982 © John D. Radke, 1982 I n p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t o f t h e r e q u i r e m e n t s f o r an a d v a n c e d d e g r e e a t t h e U n i v e r s i t y o f B r i t i s h C o l u m b i a , I a g r e e t h a t t h e L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e a n d s t u d y . I f u r t h e r a g r e e t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y p u r p o s e s may be g r a n t e d by t h e h e a d o f my d e p a r t m e n t o r by h i s o r h e r r e p r e s e n t a t i v e s . I t i s u n d e r s t o o d t h a t c o p y i n g o r p u b l i c a t i o n o f t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l n o t be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . The U n i v e r s i t y o f B r i t i s h C o l u m b i 1956 Main M a l l V a n c o u v e r , C a n a d a V6T 1 Y 3 / D e p a r t m e n t o f ^CTQ(fM?{ D E - 6 ( 3 / 8 1 ) ABSTRACT This d i s s e r t a t i o n introduces an a n a l y t i c approach to the problem of c i r c u i t network p a t t e r n r e c o g n i t i o n . The approach involves a two-stage methodology which i s described i n d e t a i l . I n i t i a l l y , a t h e o r e t i c a l process i s used to generate a bench mark, or y a r d s t i c k , to which d e s c r i p t i o n s of form can be o r i e n -ted; secondly, a l i n k - b y - l i n k examination of c i r c u i t network s t r u c t u r e i s undertaken to determine each l i n k ' s r e l a t i o n s h i p to the bench mark. The graphs composing the bench mark have a continuous s t r u c t u r a l d i s t r i b u t i o n , ranging from completely connected to rudimentary graphs. A comprehensive d e s c r i p t i o n of these graphs i s presented, and several p r o p e r t i e s of the bench mark are examined and compared to those of known f a m i l i e s of c i r c u i t graphs. I t i s argued that the bench mark introduced here i s more f l e x i b l e than other y a r d s t i c k s because i t s generative process creates a continuous spectrum of graph s t r u c t u r e s . The i n t e r n a l l i n k - b y - l i n k approach a l s o allows compari-sons to be made w i t h i n the l i n k s t r u c t u r e of the e m p i r i c a l network and thus an intra-network examination of the network's pa t t e r n i s p o s s i b l e . Such comparison aids i n r e v e a l i n g trends w i t h i n the l i n k s t r u c t u r e of a given e m p i r i c a l c i r c u i t network. F i n a l l y , an i l l u s t r a t i o n of the a p p l i c a t i o n of the pro-posed approach i s presented. Three road networks, a l l l o c a t e d i n western Canada, are chosen as examples of e m p i r i c a l planar networks and the major a i r l i n e network of Canada i s used as a non-planar example. i i TABLE OF CONTENTS Chapter Page A b s t r a c t i i Table of Contents i i i L i s t of T a b l e s v L i s t of F i g u r e s v i CHAPTER 1: F i e l d of Study 1.1 I n t r o d u c t i o n 1 1.1.1 The M o t i v a t i o n 3 1.1.2 I m p l i c a t i o n s 7 1 .2 The C i r c u i t 8 1.2.1 N a t u r a l vs. S y n t h e t i c 13 1.2.2 Morphology v s . F u n c t i o n a l i t y 15 1.3 R e l a t e d L i t e r a t u r e 17 1.4 P a t t e r n R e c o g n i t i o n 25 1.5 Research O b j e c t i v e s 29 1.6 Summary of Chapter 1 33 CHAPTER 2: A n a l y t i c a l Forum 2.1 I n t r o d u c t i o n 36 2.2 Network A n a l y s i s 37 2.3 T h e o r e t i c a l Concepts of the Graph 39 2.4 Map P a t t e r n s 52 2.5 P o i n t P a t t e r n A n a l y s i s 53 2.6 L i n e P a t t e r n A n a l y s i s 61 2.7 Area P a t t e r n A n a l y s i s 64 2.8 Planar D i m e n s i o n a l i t y 65 2.9 Summary of Chapter 2 67 i i i CHAPTER 3: The Approach t o P a t t e r n R e c o q n i t i o n 3.1 I n t r o d u c t i o n 69 3.2 Skeletons 72 3.3 A Known Family of Planar Skeletons 76 3.4 Proposed Methodology 83 3.5 Summary of Chapter 3 120 CHAPTER 4: E m p i r i c a l I l l u s t r a t i o n 4.1 I n t r o d u c t i o n 123 4.2 Link Thresholds 125 4.3 Some H y p o t h e t i c a l Networks 127 4.4 D e l i n e a t i o n of the Sample Space 137 4.5 Recognizing P a t t e r n s i n E m p i r i c a l Networks 138 4.6 Observing 0 Value D i s t r i b u t i o n s 158 4.7 Summary of Chapter 4 164 CHAPTER 5: Summary 5.1 Overview 167 5.2 Developments Beyond t h i s Study 171 5.3 A l t e r n a t i v e Approaches 173 5.4 Co n c l u s i o n 174 BIBLIOGRAPHY 176 APPENDICES A a-shapes 182 B Quadrat D i v i s i o n s 183 i v LIST OF TABLES Table Page 3.1 Bench Mark Properties. 93 4.1 C o e f f i c i e n t of Va r i a t i o n . 163 v LIST OF FIGURES F i g u r e Page 1.1 Network C l a s s i f i c a t i o n I . 10 1.2 Graphic r e p r e s e n t a t i o n of network c l a s s e s . 12 1.3 Network C l a s s i f i c a t i o n I I . 14 1.4 Network C l a s s i f i c a t i o n I I I . 16 1.5 Network C l a s s i f i c a t i o n IV. 27 2.1 P o i n t s and l i n k s i n graph G(V;E). 42 2.2 Adjacent and t o p o l o g i c a l neighbours. 42 2.3 Complete graph. 44 2.4 Adjacent l i n k s or edges. 44 2.5 Regular or P-valent graph. 45 2.6 N u l l or 0-valent graph. 45 2.7 A Path. 47 2.8 E u c l i d e a n Path with weighted l e n g t h s . 47 2.9 A C i r c u i t . 48 2.10 A Plane graph. 48 2.11 A Tree graph. 50 2.12 A F o r e s t or A c y c l i c graph. 50 2.13 Connected graph, Subgraph, Minimum Spanning Tree. 51 2.14 Quadrat A n a l y s i s of a p o i n t p a t t e r n . 54 2.15 E u c l i d e a n Nearest Neighbour measurements. 56 2.16 Measuring angles i n Delaunay T r i a n g l e s . 58 2.17 Standard D e v i a t i o n a l E l l i p s e , Convex H u l l . 60 v i F i g u r e Page 2.18 Plane tangent to the e a r t h ' s s u r f a c e . 66 3.1 Medial A x i s F u n c t i o n endo-skeleton. 74 3.2 L i n k i n g V(G) endo-skeleton. 74 3.3 Minimum Spanning Tree of p o i n t set V(G). 77 3.4 Delaunay T r i a n g u l a t i o n of p o i n t set V(G). 77 3.5 Voronoi Diagram of p o i n t set V(G). 79 3.6 G a b r i e l Graph c o n s t r u c t i o n . 81 3.7 G a b r i e l Graph of p o i n t s e t V(G). 81 3.8 R e l a t i v e Neighbourhood Graph c o n s t r u c t i o n . 84 3.9 R e l a t i v e Neighbourhood Graph of p o i n t set V(G). 84 3.10 C o n s t r u c t i o n l i n e f o r the c e n t r e s of the 'Lune' arcs.[where 0£1] 88 3.11 'Lune' c o n s t r u c t i o n f o r 0£1. 90 3.12 Rotated c o n s t r u c t i o n l i n e f o r the c e n t r e s of the 'Lune' a r c s . [ where O£0£1 ] 94 3.13 'Lune* c o n s t r u c t i o n f o r 0S/3S1 . 95 3.14 Degenerative Graph. 99 3.15 Bench Mark /^-skeletons. 100 3.16 S t r u c t u r a l i n v a r i a n c e of the Bench Mark at v a r y i n g s c a l e s . 102 3.17 Forming a non-planar l i n k . [ 0<1 ] 103 3.18 Mosaic of 0 value l i n k s i n an observed c i r c u i t graph. 108 3.19 Observed c i r c u i t graph and a b s t r a c t e d p o i n t set V(G). 110 3.20 C o r r i d o r search space f o r V i and V j . 111 3.21 V(COR) with a l l other p o i n t s omitted. 111 3.22 D i v i s i o n of V(COR) search space. 113 v i i F i g u r e Page 3.23 Search space when 0<1. 113 3.24 Search space when 0>1. 113 3.25 In search of C\ and C J . [ O£0<1 3 115 3.26 L o c a t i o n of c ; . [ O^0<1 ] 115 3.27 In search of C j . [ 02i1 ] 117 3.28 L o c a t i o n o£ C j . [ 0£1 ] 118 3.29 L o c a t i o n of C j . [ 0£ ] 118 3.30 Observed graph with 0 values a s s i g n e d to each l i n k . 121 4.1 Link 0 v a l u e s of a r e g u l a r hexagonal network. 128 4.2 Regular p o i n t p a t t e r n square l a t t i c e . 129 4.3 L i n k 0 v a l u e s of a r e g u l a r square network. 129 4.4 Link 0 valu e s of a r e g u l a r t r i a n g u l a r network. 131 4.5 Planar c i r c u i t graph of a h y p o t h e t i c a l network. 132 4.6 L i n k 0 valu e s of the h y p o t h e t i c a l network. 133 4.7 'Link Thresholds' of the h y p o t h e t i c a l network, [ e x i s t i n g l i n k s with low 0 va l u e s ] 134 4.8 'Link Thresholds' of the h y p o t h e t i c a l network. [0 - s k e l e t o n l i n k s m i s s i n g from the observed graph G T ( V ; E ) ] 1.36 4.9 Planar c i r c u i t graph of the S a l t s p r i n g I s l a n d road network. 139 4.10 Link 0 v a l u e s of the S a l t s p r i n g I s l a n d network. 140 4.11 'Link Thresholds' of the S a l t s p r i n g I s l a n d network. [ e x i s t i n g l i n k s with low 0 v a l u e s ] 143 4.12 'Link Thresholds' of the S a l t s p r i n g I s l a n d network. [ 0 - s k e l e t o n l i n k s m i s s i n g from the observed graph Gp(V;E) ] 144 v i i i F i g u r e Page 4.13 Planar c i r c u i t graph of the B r i t i s h Columbia major road network. 146 4.14 Link 0 v a l u e s of the B r i t i s h Columbia network. 147 4.15 'Link T h r e s h o l d s ' of the B r i t i s h Columbia network. [ e x i s t i n g l i n k s with low 0 v a l u e s ] 149 4.16 'Link T h r e s h o l d s ' of the B r i t i s h Columbia network. [ 0-skeleton l i n k s m issing from the observed graph G 0(V;E) ] 150 4.17 Planar c i r c u i t graph of the Saskatchewan major road network. 152 4.18 Link 0 v a l u e s of the Saskatchewan network. 153 4.19 'Link T h r e s h o l d s ' of the Saskatchewan network. [ e x i s t i n g l i n k s with low 0 v a l u e s ] 154 4.20 'Link Thresholds' of the Saskatchewan network. [ 0-skeleton l i n k s m i s s i n g from the observed graph Gw(V;E)] 156 4.21 Non-planar c i r c u i t graph of the Canadian major a i r l i n e network. 157 4.22 'Link Thresholds' of the Canadian a i r l i n e network. [ e x i s t i n g l i n k s with low 0 v a l u e s ] 159 4.23 'Link Thresholds' of the Canadian a i r l i n e network. [B-skeleton l i n k s m i s s i n g from the observed graph Go(V;E) ] 160 ix Chapter 1 : FIELD OF STUDY 1*1 I n t r o d u c t i o n C i r c u i t s , whether i n t h e i r elemental form, l i n k s , or t h e i r composite form, c i r c u i t networks, o f t e n pass unrecognized or undetected i n the everyday world. Too o f t e n we take f o r granted the s p a t i a l s t r u c t u r e of the surrounding landscape, and, as a r e s u l t , make only meagre attempts to observe the world at v a r y i n g s c a l e s . Seldom do we take time t o recognize the u n d e r l y i n g s t r u c t u r e of the system i n which we are embedded. For example, we t r a v e l i n capsule form from one a i r p o r t to another e x p e r i e n c i n g only the o r i g i n and the d e s t i n a t i o n . M i l l i o n s of telephone c a l l s are made each day without regard f o r the e x i s t e n c e of hardware other than the c a l l box. In both i n s t a n c e s , a form of network e x i s t s which f a l l s i n t o the category of c i r c u i t networks. 1 The purpose of t h i s d i s s e r t a t i o n i s to f i n d a s o l u t i o n t o the problem of r e c o g n i z i n g p a t t e r n s i n c i r c u i t networks. 1 S p e c i f i c a l l y , the problem of comparing measurable c h a r a c t e r i s t i c s of i n d i v i d u a l l i n k s w i t h i n a network, as w e l l as between networks, i s s o l v e d . 2 To do so a t h e o r e t i c a l bench mark i s generated to which c i r c u i t networks can be compared. The concept behind t h i s bench mark i s not u n l i k e the 'Poisson' which has been used to t h e o r e t i c a l l y generate expected d i s t r i b u t i o n s of p o i n t s to which e m p i r i c a l p o i n t p a t t e r n s can be r e f e r r e d . 3 The concept of the bench mark developed here can a l s o be c o n s i d e r e d analogous to the use of C h r i s t a l l e r ' s hexagonal s t r u c t u r e s as i d e a l or extreme s i t u a t i o n s to which e m p i r i c a l p a t t e r n s can be measured.* Both the Poisson and the C h r i s t a l l e r i a n hexagonal s t r u c t u r e are l i m i t e d i n the sense that they represent d i s c r e t e bench marks composed of one i d e a l s t r u c t u r e . The t h e o r e t i c a l bench mark developed i n t h i s t h e s i s i s much 1 T h i s i n t r o d u c t i o n i s meant as a synopsis of what t h i s t h e s i s embodies. T h e r e f o r e the statement i s b r i e f and u n c l u t t e r e d with d e f i n i t i o n s of the terms used. Formal d e f i n i t i o n s of these terms appear i n the f o l l o w i n g t e x t as they are employed. 2 There e x i s t s measures which d e s c r i b e a networks s p a t i a l s t r u c t u r e but t o date there i s no framework through which r e l a t i v e q u a n t i t a t i v e comparisons can be made between two networks. 3 P.J. T a y l o r , Q u a n t i t a t i v e Methods i n Geography, (Boston: Houghton M i f f l i n Company, 1977). * W i l l i a m Bunge T h e o r e t i c a l Geography, Lund S t u d i e s i n Geography, S e r i e s C, No.1, Second E d i t i o n (1966). 2 more complex and c o n s i s t s of a continuous range of c i r c u i t networks. The obvious advantage i s , measurements can not only be made with r e s p e c t to extreme s t r u c t u r e s , such as the upper and lower bounds i n the proposed bench mark, they can be made along the e n t i r e spectrum that e x i s t s between them. The M o t i v a t i o n S e v e r a l approaches t o the study of c i r c u i t networks e x i s t . Some of the e a r l i e r work was i d e o g r a p h i c , but most of the l a t e r r e s e a r c h i s nomothetic, s e a r c h i n g f o r laws, r e g u l a r i t y and order. T h i s l a t t e r approach e n t a i l s employing the s c i e n t i f i c approach i n a quest f o r theory from which e x p l a n a t i o n and p r e d i c t i o n can e v e n t u a l l y be made. In the e a r l y stages of theory development, models are o f t e n i n t r o d u c e d which seek t o o b t a i n r e g u l a r i t y and order. At f i r s t , these models u s u a l l y r e q u i r e s t r i c t assumptions that a b s t r a c t the uniqueness of r e a l i t y i n order t o r e v e a l some g e n e r a l i t i e s t h a t may prove u s e f u l . F u r t h e r development u s u a l l y e n t a i l s r e l a x i n g the o r i g i n a l assumptions i n order t o make the theory more a p p l i c a b l e t o c e r t a i n phenomena. T h i s t h e s i s i s concerned with b u i l d i n g theory which can a i d i n the r e c o g n i t i o n of s p a t i a l s t r u c t u r e i n c i r c u i t networks. The approach possesses a methodology which i n v o l v e s s t r i c t assumptions t h a t a b s t r a c t r e a l i t y . The m o t i v a t i o n behind t h i s attempt i s that such a ge n e r a l approach, with l i t t l e m o d i f i c a t i o n to the developed theory, can a i d i n the r e c o g n i t i o n of p a t t e r n s i n other d i s c i p l i n e s b esides geography. In the area of c i r c u i t network morphology, one of the unsolved problems of p a t t e r n r e c o g n i t i o n e x i s t s i n the examination of the s p a t i a l s t r u c t u r e of two u n r e l a t e d c i r c u i t networks. No scheme e x i s t s which uses a t h e o r e t i c a l p r o c e s s t o generate a s t r u c t u r e which can be used as a yard s t i c k , or bench mark to which e m p i r i c a l networks can be compared. T h i s t h e s i s attempts such a scheme. In the present study, form (morphology) i n c i r c u i t networks i s examined. S p e c i f i c a l l y , r e l a t i o n s h i p s between a network's form and a t h e o r e t i c a l g e n e r a t i v e process are e x p l o r e d i n an attempt to c h a r a c t e r i z e i t s s p a t i a l s t r u c t u r e . I t i s argued t h a t a l l c i r c u i t networks are a subset of a completely connected network which i s generated by co n n e c t i n g each member of the s e t of p o i n t s ( i n t e r s e c t i o n s , v e r t i c e s , nodes) i n the network to a l l other members. An 4 incomplete c i r c u i t network d i f f e r s from the former by having fewer l i n k s . T h e r e f o r e , the d i f f e r e n c e between a c i r c u i t network and i t s complete form i s a r e s u l t of the stage of the process which generates i t s l i n k s . Hence, the complete network form can be used as a bench mark from which to measure the form of the e x i s t i n g network. Before the i m p l i c a t i o n s of t h i s approach are examined, a d i s c u s s i o n of the m o t i v a t i o n behind t h i s form-process approach i s presented. Form: Geographers are o f t e n concerned with "the s p a t i a l arrangement of phenomena". 5 Bunge s t a t e s that "geography i s the s c i e n c e of l o c a t i o n s . " 6 Eichenbaum and Gale argue that " s i n c e geography i s , by d e f i n i t i o n , a s c i e n c e , i t must t h e r e f o r e be the s c i e n c e of space." 7 Geographers such as Schaefer and Bunge would have us b e l i e v e that the geographer's r o l e i s to study the world v o i d of a time dimension, s t r i c t l y i n terms of i t s s p a t i a l v i s i b i l i t y . F o l l o w i n g Eichenbaum and G a l e 8 , form i s the v i s i b l e aspect of a t h i n g , u s u a l l y taken i n the narrow sense of shape or c o n f i g u r a t i o n , as d i s t i n g u i s h e d from such p r o p e r t i e s as c o l o u r . Form in the a b s t r a c t i m p l i e s something g e o m e t r i c a l , d e t a i l i n g the measurable p r o p e r t i e s of 5 F.K. Schaefer " E x c e p t i o n a l i s m i n Geography: A M e t h o d o l o g i c a l Examination," Annals of the A s s o c i a t i o n of  American Geographers Vol.43, No.3 (1953) p.243. 6 W i l l i a m Bunge, T h e o r e t i c a l Geography (1966) p.200. 7 Jack Eichenbaum and Stephen Gale, "Form, F u n c t i o n , and Process: A M e t h o d o l o g i c a l I n q u i r y , " Economic Geography, Vol.47, No.4 (1971) p.532. 8 I b i d . 5 phenomena at a p o i n t i n t i m e . 9 However, a p u r e l y s p a t i a l or m o r p h o l o g i c a l p o s i t i o n i s too a b s t r a c t , and i f "we s l i c e through one time at one t i m e l e s s i n s t a n t , we do not get a p u r e l y s p a t i a l c r o s s - s e c t i o n ; we get nothing a t a l l " . 1 0  Process; A new approach f o r the geographer was f i r s t a b s t r a c t l y i n t r o d u c e d by G i l b e r t 1 1 , and l a t e r r e i n f o r c e d by C u r r y 1 2 , D a c e y 1 3 , Hagerstrand 1 *, and most r e c e n t l y , G e t i s and B o o t s 1 5 . In t h i s new approach the quest i s seen as not only t h a t of i d e n t i f y i n g form, but a l s o of r e v e a l i n g f u n c t i o n and p r o c e s s . Process can be d e f i n e d as a continuous or r e g u l a r a c t i o n , or s u c c e s s i o n of a c t i o n s , t a k i n g p l a c e or c a r r i e d on i n a d e f i n i t e manner, l e a d i n g to some r e s u l t . 1 6 T h e r e f o r e , by r e v e a l i n g process we reach not a b s o l u t e e x p l a n a t i o n , but a h i g h e r l e v e l of e x p l a n a t i o n than otherwise p o s s i b l e . Although the contemporary p o s i t i o n c o n c e n t r a t e s on f u n c t i o n - p r o c e s s , we must keep i n mind that i n order to determine the o r i g i n s of s p a t i a l 9 Schaefer, E x p e c t a t i o n s i n geography, (1953) p.244. 1 0 J.M. B l a u t "Space and Process," The P r o f e s s i o n a l  Geographer, Vol.13, No.1 (1961) p.7. 1 1 G.N. G i l b e r t , "Convexity of H i l l T ops,"Journal of  Geology, Vol.17 (1969) pp.344-50. 1 2 L. Curry, "The Random S p a t i a l Economy: An E x p l o r a t i o n i n Settlement Theory," Annals of the A s s o c i a t i o n of  American Geographers, Vol.54, No.1~Tl964) pp.138-46. 1 3 Michael Dacey, "A P r o b a b i l i t y Model of C e n t r a l Place L o c a t i o n s , " Annals of the A s s o c i a t i o n of American  Geographers, Vol.56, No.3 (1966) pp.550-68. i a T. Hagerstrand, "Innovation D i f f u s i o n as a S p a t i a l P r ocess," T r a n s l a t e d by A.Pred (Chicago: U n i v e r s i t y of Chicago Press,1967) 1 5 Arthur G e t i s and Barry N. Boots, Models of S p a t i a l  Processes, (Cambridge: Cambridge U n i v e r s i t y Press, 1978) 1 6 Eichenbaum and Gale, Form, F u n c t i o n and Process, (1971) p.533. 6 s t r u c t u r e , or "the geometry of a geographic s i t u a t i o n , we must be a b l e to d e s c r i b e i t . " 1 7 I t i s with t h i s form-process dichotomy i n mind t h a t t h i s t h e s i s i s undertaken. J_.j_.2 I m p l i c a t i o n s A c i r c u i t network i s an example of one medium i n which the form or s p a t i a l s t r u c t u r e of a geographic phenomenon 1 8 can be re p r e s e n t e d . T h i s d i s s e r t a t i o n supplements the e x i s t i n g l i t e r a t u r e by a d d r e s s i n g two urgent needs i n c i r c u i t network r e c o g n i t i o n : f i r s t l y , the t h e o r e t i c a l g e n e r a t i o n of a spectrum of graphs which can be used as bench marks f o r the examination and comparison of r e a l world c i r c u i t networks; and secondly, the development of a l i n k - b y - l i n k a n a l y s i s 1 9 of a c i r c u i t network u s i n g a t h e o r e t i c a l benchmark. S e v e r a l b e n e f i t s can r e s u l t from t h i s r e s e a r c h . Although the methodology does not attempt to e x p l a i n the 1 7 Barry N. Boots, "Comments on Using E i g e n f u n c t i o n s to Measure S t r u c t u r a l P r o p e r t i e s of Geographic Networks," Environment and Planning Vol.14, No.8 (1982) pp.1063-1072. 1 8 For i n s t a n c e , the a i r l i n e or communication examples mentioned e a r l i e r . 1 9 The l i n k - b y - l i n k a n a l y s i s i n v o l v e s the examination of the r e l a t i o n s h i p of each l i n k , i n an observed network, with the p o i n t s w i t h i n i t s search space or domain. The search space or domain i s d i s c u s s e d i n d e t a i l i n Chapter 7 processes which generate c i r c u i t networks, comparisons made to a t h e o r e t i c a l l y generated bench mark make i t p o s s i b l e to c h a r a c t e r i z e the i n d i v i d u a l l i n k s i n a network. F o l l o w i n g t h i s , a c o l l e c t i v e examination of the c h a r a c t e r i z e d l i n k s i n the network, makes i t p o s s i b l e t o d e t e c t p a t t e r n . F u r t h e r , i f the form of an observed c i r c u i t network i s c o r r e l a t e d with that of a t h e o r e t i c a l l y generated network, p a r a l l e l s can be c o n s i d e r e d to e x i s t between t h e i r g e n e r a t i v e p r o c e s s e s . Although t h i s technique does not all o w c o n c l u d i n g statements to be made concerning the g e n e r a t i v e process of the observed network, knowing the ge n e r a t i v e process of a t h e o r e t i c a l c o r r e l a t e can a i d i n attempts to b e t t e r hypothesize process i n the observed network. In other words, i t allows one t o ask more i n f o r m a t i v e q u e s t i o n s about the network under study. The approach f o l l o w e d i n t h i s t h e s i s a l s o a l l o w s f o r f u t u r e r e l a x a t i o n of some of the s t r i c t assumptions i n the t h e o r e t i c a l g e n e r a t i v e p r o c e s s . As assumptions are r e l a x e d , the t h e o r e t i c a l g e n e r a t i v e process can approximate more c l o s e l y e m p i r i c a l s i t u a t i o n s , and bench marks can be c o n s t r u c t e d which are t a i l o r e d to s p e c i f i c a p p l i c a t i o n s . _ . 2 The C i r c u i t Although a comprehensive statement of d e f i n i t i o n s i s presented i n the second chapter of t h i s t h e s i s , working 8 e x p l a n a t i o n s of a few terms are needed at t h i s time. Though many u n r e l a t e d d i s c i p l i n e s have approached the study of c i r c u i t networks, the c o n c e p t u a l d e f i n i t i o n a p p l i e d i n most cases has managed to r e t a i n some semblance of the l a t i n r o o t , ' c i r c u i t u s ' . . . a going round. When some phenomenon e x i s t s i n one p a r t i c u l a r l o c a t i o n , geographers denote the l o c a t i o n as a p o i n t . I f a p o i n t e x i s t s , a p o i n t p a t t e r n i s s a i d to e x i s t . I f some i n t e r a c t i o n takes p l a c e between the p o i n t s , the p a t t e r n i s then d e s c r i b e d as a l i n e p a t t e r n or a network c o n s i s t i n g of both p o i n t s and l i n e s . Among those paradigms which attempt to i l l u s t r a t e s p a t i a l s t r u c t u r e , the most common i s that of Haggett ( f i g u r e 1.1), which demonstrates the r e l a t i o n s h i p s between f e a t u r e s w i t h i n networks. T o p o l o g i c a l l y , H a g g e t t 2 0 c l a s s i f i e s networks i n t o two b a s i c groups, each a f u n c t i o n of i t s d i m e n s i o n a l i t y . P l a n a r networks are r e p r e s e n t e d on two-dimensional s u r f a c e s , and non-planar networks i n three or more dimensional s p a c e . 2 1 Within each category, the networks Peter Haggett and R.J.Chorley, Network A n a l y s i s i n  Geography, (London: Edward A r n o l d L t d . , 1969) p.7. The term 'planar' i s not d e f i n e d as i t has t r a d i t i o n a l l y been i n Graph Theory. Here the p o i n t s or v e r t i c e s of a network are embedded i n a p l a n e . I f a network i s d e f i n e d as being p l a n a r , i t s l i n k s are as w e l l embedded i n the plane. I f a network i s s a i d to be non-planar, i t s l i n k s are not embedded i n the plane and can i n t e r s e c t at l o c a t i o n s other than p o i n t s . 9 NETWORK CLASSIFICATION I To p o l o g i c a l C l a s s i f i c a t i o n of Networks t Linear flow systems Linear b a r r i e r s Source: Modified a f t e r P.Haggett and R.J.Chorley, Network A n a l y s i s i n Geography,(London: Edward Arnold, 1969). Figure 1.1 10 are f u r t h e r c l a s s i f i e d on the b a s i s of the f u n c t i o n s of the l i n e s i n the networks. When the l i n e s i n a network represent an a b s t r a c t i o n of some medium of i n t e r a c t i o n between p o i n t s , the network belongs to the fa m i l y of ' l i n e a r flow systems.' In c o n t r a s t , when the l i n e bounds some area or c e l l , the network f a l l s i n t o the c l a s s of ' l i n e a r b a r r i e r s ' or c e l l u l a r n e t w o r k s 2 2 . Haggett c o n s t r u c t s a f i n a l s u b - c l a s s i f i c a t i o n of networks w i t h i n ' l i n e a r flow systems.' L i n e a r flow i s s p l i t i n t o three t o p o l o g i c a l groups with a d i s t i n c t v a r i a t i o n i n geometric s t r u c t u r e between them. The f i r s t , a path, i s simply a p a t t e r n with each p o i n t i n the network connected by a maximum of two l i n e s to the r e s t of the p a t t e r n . No two p o i n t s are connected to each other by more than one route ( f i g u r e 1.2a). The second group, a t r e e , c o n t a i n s a l l the p r o p e r t i e s of a path except some p o i n t s may have more than two l i n e s c o nnecting them to the r e s t of the network ( f i g u r e 1.2b). The t h i r d group, the c i r c u i t , d i f f e r s from the t r e e only i n that i t c o n t a i n s c l o s e d loops, or c i r c u i t s , thus making i t f u n c t i o n a l l y p o s s i b l e to t r a v e l away from and r e t u r n to a given p o i n t i n a network using d i f f e r e n t l i n e s as a medium. The t h i r d sub-group of l i n e a r flow systems, c i r c u i t s , 2 2 Haggett and Chorley,Network A n a l y s i s (1969). 11 C i r c u i t C e l l Figure 1 . 2 12 has a s i m i l i a r form t o that of c e l l u l a r networks i n l i n e b a r r i e r systems. T h e r e f o r e u s i n g Haggett's paradigm, r e l y i n g s t r i c t l y on t o p o l o g i c a l c l a s s i f i c a t i o n , c i r c u i t and c e l l u l a r networks appear q u i t e s i m i l i a r ( f i g u r e 1.2c and 1.2d). In order to d i s t i n g u i s h between the two we must know e i t h e r something about t h e i r cause ( g e n e r a t i v e process) or something concerning t h e i r e f f e c t ( t h e i r f u n c t i o n ) . Thus f u r t h e r c l a s s i f i c a t i o n i s needed. N a t u r a l vs. S y n t h e t i c As Haggett uses d i m e n s i o n a l i t y to c l a s s i f y the p l a n a r and non-planar networks, so can process be employed to c l a s s i f y networks a c c o r d i n g to t h e i r o r i g i n s . As a very general c l a s s i f i c a t i o n , and one that has str o n g r o o t s i n geography, networks can be d i v i d e d i n t o those that are a f u n c t i o n of some n a t u r a l p r o c e s s , and those that are s y n t h e t i c (man-made)(figure 1.3). Among c o u n t l e s s examples, two such n a t u r a l l y generated networks are stream n e t w o r k s 2 3 ( t r e e s ) and i c e wedge p o l y g o n s 2 * ( c e l l u l a r networks). The s y n t h e t i c world of networks a l s o has an abundance of examples. Some common r e p r e s e n t a t i v e s of t h i s 2 3 R.E. Horton, " E r o s i o n a l development of streams and t h e i r drainage b a s i n s : h y d r o p h y s i c a l approach t o q u a n t i t a t i v e morphology," B u l l e t i n of the G e o l o g i c a l  S o c i e t y of America, V o l 56 (1945) pp.275-370. 2 9 J . Ross Mackay, "Pingos of the Tuktoyaktuk P e n i n s u l a Area, Northwest T e r r i t o r i e s , " Geographie Physique e t Q u a t e r n a i r e , Vol.XXXIII, No.1 (1979) pp.3-61. 13 NETWORK CLASSIFICATION I I Network a n a l y s i s S p a t i a l Dimension: P a t t e r n Type: planar point area (from f i g u r e 1.1) path tree c i r c u i t c e l l ( t r a n s p o r t a t i o n ) O r i g i n : s y n t h e t i c (man-made) n a t u r a l ( p h y s i c a l ) Following: B.N.Boots,"Some models of the random s u b d i v i s i o n of space",Geografiska Annaler, Vol.55B, (1973), pps34^487 Figure 1.3 14 group are t r a n s p o r t a t i o n n e t w o r k s 2 5 , ( c i r c u i t s ) and s e r v i c e areas i n c e n t r a l p l a c e s t u d i e s ( c e l l s ) 2 6 . K2.2 Morphology v s . F u n c t i o n a l i t y T urning again t o the t o p o l o g i c a l problems of d i s t i n g u i s h i n g the c i r c u i t from the c e l l , we f i n d t h a t another c l a s s i f i c a t i o n i s needed. We c o u l d at some time be e m p i r i c a l l y s t u d y i n g a man-made network s t r u c t u r e , yet because of incomplete knowledge about i t s o r i g i n or f u n c t i o n , we may not be a b l e t o a c c u r a t e l y l a b e l t h i s network a c i r c u i t or a c e l l . Knowledge about i t s f u n c t i o n s must be added to i n f o r m a t i o n about i t s morphology before the c i r c u i t or c e l l can be i d e n t i f i e d . Thus, f u n c t i o n , l i k e process and d i m e n s i o n a l i t y , can be used as a method of c l a s s i f y i n g n e t w o r k s 2 7 ( f i g u r e 1.4). In t h i s t h e s i s the term 'morphology' denotes the geometric s t r u c t u r e of networks: the term ' f u n c t i o n a l i t y ' denotes t h e i r non-geometric c h a r a c t e r i s t i c s . The geometry of networks can be measured u s i n g exact m e t r i c s which d e a l with parameters of the d e n s i t y , d i s t a n c e and d i r e c t i o n of 2 5 W.L. G a r r i s o n and D.F. Marble, "A prolegomenon to the f o r e c a s t i n g of t r a n s p o r t a t i o n development," T r a n s p o r t a t i o n Centre, Northwestern U n i v e r s i t y , Research  Report No.4 (196BT! 2 6 G e t i s and Boots, Models of S p a t i a l Processes (1978). 2 7 C. Werner "The r o l e of topology and geometry i n o p t i o n a l network d e s i g n , " Papers of the Regional Science  A s s o c i a t i o n , Vol.XXI (1967) p176. 15 NETWORK CLASSIFICATION I I I Network A n a l y s i s S p a t i a l Dimension: planar P a t t e r n Type: point area (from f i g u r e 1.1) path tree c i r c u i t c e l l ( t r a n s p o r t a t i o n ) O r i g i n : Geometric Approach: s y n t h e t i c (man-made) t morphology (geometric) n a t u r a l ( p h y s i c a l ) f u n c t i o n a l i t y (non-geometric) Figure 1.4 16 such network v a r i a b l e s as p o i n t s and l i n e s . Measurement i n the non-geometric world however, i s more d i f f i c u l t , as v a r i a b l e s are not as narrowly d e f i n e d . T h i s does not suggest however, that one world i s more v a l u a b l e than the ot h e r . E m p i r i c a l study, i f aimed at e x p l a n a t i o n and p r e d i c t i o n , i d e n t i f y i n g the exact nature of a network, should i n c l u d e a n a l y s i s of both morphology and f u n c t i o n a l i t y . I f the i n f l u e n c e of morphology or geometry of a network i s known, i t i s e a s i e r to i s o l a t e the non-geometric f e a t u r e s 2 8 . Although the form-process dichotomy e x i s t s i n both the non-geometric and geometric worlds, t h i s d i s s e r t a t i o n d e a l s with the l a t t e r or more s p e c i f i c a l l y , the morphology of s y n t h e t i c c i r c u i t networks. _.3 Related L i t e r a t u r e Networks and t h e i r s t r u c t u r e have been s t u d i e d i n many d i s c i p l i n e s s i n c e the t o p i c was i n t r o d u c e d by Konig i n 1936 2 9. The t o p o l o g i c a l nature of a network lends i t s e l f to m u l t i - d i s c i p l i n a r y use. In the e a r l y stages of network a n a l y s i s , academic d i s c i p l i n e s exchanged both ideas and jargon about c i r c u i t networks, geography being no 2 8 G e t i s and Boots, Models of S p a t i a l Processes (1978). 2 9 Peter Haggett, L o c a t i o n a l A n a l y s i s i n Human Geography, (Toronto: MacMillan Co., 19657"! 17 e x c e p t i o n . A map i s a r e p r e s e n t a t i o n on a plane s u r f a c e of any r e g i o n , such as the e a r t h ' s s u r f a c e . 3 0 A graphic r e p r e s e n t a t i o n of a network may be c o n s i d e r e d a s p e c i a l case of a map. Since the map i s a fundamental t o o l of the geographer, the adoption of network a n a l y s i s i n t h i s d i s c i p l i n e spread r a p i d l y among both n a t u r a l and s o c i a l s c i e n t i s t s . As a r e s u l t , geography possesses i t s own l i m i t e d though ever expanding body of l i t e r a t u r e on network a n a l y s i s . P h y s i c a l geographers f i r s t reduced r i v e r channels to t h e i r most elemental form, a t r e e n e t w o r k 3 1 . E a r l y a b s t r a c t i o n s of r i v e r s and t h e i r t r i b u t a r i e s c o n c e n t r a t e d on r e v e a l i n g the t o p o l o g i c a l s t r u c t u r e of both paths and t r e e s ( S h r e v e 3 2 , Woldenberg 3 3, Smart 3*, and W a r n t z 3 5 ) . Although data problems a s s o c i a t e d with e x t r a c t i n g a c curate channel networks from maps l e d to a s h i f t toward f i e l d 3 0 Funk and Wagnalls, Standard C o l l e g e D i c t i o n a r y , (Toronto: F i t z h e n r y and Whiteside L t d . , 1975), p825. 3 1 Horton, E r o s i o n a l development of streams, 1945. 3 2 R.L. Shreve " I n f i n i t e t o p o l o g i c a l l y random channel networks," J o u r n a l of Geology, Vol.75, No.1 (1967) pp.178-186. 3 3 M.J. Woldenberg, "Geography and p r o p e r t i e s of s u r f a c e s , " Harvard Papers i n T h e o r e t i c a l Geography, Vol.13, (1967) pp.1-36. 3 * J.S. Smart, "The t o p o l o g i c a l p r o p e r t i e s of channel networks," IBM Research, RC 2310, No.11312 (1968). 3 5 W i l l i a m Warntz, "A note on stream o r d e r i n g and contour mapping," Harvard Papers i n T h e o r e t i c a l Geography, Vol.18, (1968) pp.1-30. 18 s t u d i e s of p r o c e s s 3 6 , much of the e a r l i e r l i t e r a t u r e c o n c e n t r a t e d on morphology r a t h e r than f u n c t i o n . More r e c e n t l y , geographers s t u d y i n g the p h y s i c a l landscape have used Haggett's c e l l c l a s s i f i c a t i o n of networks to d i s s e c t a r e a s . The morphology of r i v e r channels has been i n v e s t i g a t e d by a b s t r a c t i n g t h e i r b a s i n s i n t o c e l l u l a r n e t w o r k s 3 7 . In a d d i t i o n , i c e wedge polygons have been s t u d i e d i n the same c o n t e x t 3 8 . S e v e r a l w r i t e r s have a p p l i e d the study of c e l l s to human a c t i v i t i e s . Woldenberg and Berry have presented c e n t r a l p l a c e h i n t e r l a n d s as c e l l s 3 9 . S e v e r a l other examples occur i n work undertaken by Boots and G e t i s * 0 . There i s one c l a s s of networks i n Haggett's paradigm 3 6 R.L. Shreve, " S t a t i s t i c a l law of stream numbers," J o u r n a l of Geology, Vol.74, No.1 (1966) ppl7-37. L.B. Leopold and W.B. Langbein, "The concept of entropy i n landscape e v o l u t i o n , " U n i t e d S t a t e s G e o l o g i c a l Survey, P r o f e s s i o n a l Papers (19627^ 3 7 M.J. Woldenberg, " S p a t i a l order i n f l u v i a l systems: Horton's laws d e r i v e d from mixed hexagonal h i e r a r c h i e s of drainage b a s i n s " , B u l l e t i n of the G e o l o g i c a l S o c i e t y of  America, Vol.80,(1969),pp.97-112. Werner, The r o l e of topology, (1967). 3 8 A.H. Lachenbruch, "Mechanics of thermal c o n t r a c t i o n c r a c k s and ice-wedge polygons i n permafrost", G e o l o g i c a l  S o c i e t y of America, S p e c i a l Papers, Vol.70,(1962). 3 9 M.J. Woldenberg and B.L.Berry, " R i v e r s and c e n t r a l p l a c e s : analogous systems?", J o u r n a l of Regional Science, Vol.7, No.2., (1967), pp129-139. 4 0 B.N. Boots, "Patterns of urban s e t t l e m e n t s r e v i s i t e d " , P r o f e s s i o n a l Geographer, Vol.27, No.4 (1975), pp.426-31. G e t i s and Boots, Models of S p a t i a l Processes, 1978. 19 whose l i t e r a t u r e remains t o be d i s c u s s e d , and t h a t c l a s s r e p r e s e n t s the area of t h i s d i s s e r t a t i o n . As p r e v i o u s l y mentioned, c i r c u i t networks may m o r p h o l o g i c a l l y resemble t h e i r c e l l u l a r c o u n t e r p a r t s found o f t e n i n a n a t u r a l s e t t i n g , but they are predominantly s y n t h e t i c i n o r i g i n . As a r e s u l t , almost a l l the l i t e r a t u r e i n v o l v i n g c i r c u i t networks i s based i n human geography. Many d i v e r s e phenomena i n the man-made world can be represented as c i r c u i t networks. Human geographers study t r a n s p o r t systems which move people, goods or i n f o r m a t i o n * 1 . As with Haggett's c l a s s i f i c a t i o n system (and i n keeping with the a d d i t i o n a l c l a s s i f i c a t i o n i n f i g u r e 1.4) there have been two d i s t i n c t approaches t o the study of t r a n s p o r t systems as c i r c u i t s : the m o r p h o l o g i c a l , and the f u n c t i o n a l . Since Ullman's c l a s s i c papers on " s p a t i a l i n t e r a c t i o n " and "the r o l e of t r a n s p o r t a t i o n " * 2 , much g e o g r a p h i c a l c i r c u i t network l i t e r a t u r e has concerned i t s e l f with flows. As the Z e i t g e i s t i n t r a n s p o r t a t i o n geography s h i f t e d from the ideographic to the nomothetic, the f u n c t i o n a l approach from j u s t a simple examination of the s p a t i a l s t r u c t u r e of 9 1 Peter Haggett, A . D . C l i f f and A.Frey, L o c a t i o n a l A n a l y s i s i n Human Geography (London: A r n o l d , 1977). * 2 E.L. Ullman, "The r o l e of t r a n s p o r t a t i o n and the b a s i s f o r i n t e r a c t i o n , " i n W i l l i a m L. Thomas (ed.), Man's Role i n Changing the Face of the E a r t h (Chicago: U n i v e r s i t y of Chicago Press, 1956) pp.862-880. 20 e m p i r i c a l flows ( p a t t e r n s of commodity flow from o r i g i n to d e s t i n a t i o n ) * 3 , to the i n v e s t i g a t i o n of p o t e n t i a l flows generated by a t h e o r e t i c a l p r o c e s s * * . The development of analog models (modelling p o t e n t i a l i n t e r a c t i o n ) generated a vast l i t e r a t u r e i n s p a t i a l i n t e r a c t i o n and flow o p t i m i z a t i o n , of which the t r a n s p o r t a t i o n model i s the most famous* 5 . Since t h i s d i s s e r t a t i o n focuses on the geometric p r o p e r t i e s of c i r c u i t s , the examination of the l i t e r a t u r e w i l l conclude i n the area of c i r c u i t network morphology. With Ullman's concept of movement at hand, t r a n s p o r t a t i o n geographers s t a r t e d to borrow and develop r i g o r o u s techniques which accomplished more than j u s t g a t h e r i n g f a c t s about c i r c u i t networks. T h i s approach i n v o l v i n g techniques became known as the "Northwestern Approach"* 6, as many of the f i r s t papers on the subject were produced at * 3 M.J. W i l l s , "Linear and n o n - l i n e a r e s t i m a t o r s of the 0-D m a t r i x , " unpublished Ph.d d i s s e r t a t i o n (Vancouver: Department of Geography, The U n i v e r s i t y of B r i t i s h Columbia, 1978) ** W i l l i a m Warntz, "A note on s u r f a c e s and paths and a p p l i c a t i o n s to g e o g r a p h i c a l problems," Michigan  I n t e r - u n i v e r s i t y Community of Mathematical Geographers, D i s s c u s s i o n Paper No. 6 (Ann Arbor, Michigan" 1965). W i l l i a m Warntz, "The topology of socio-economic t e r r a i n and s p a t i a l flows," Papers of the Regional Science  A s s o c i a t i o n , Vol.17, (1966) pp.47-61. * 5 Alan J . S c o t t , C o m b i n a t o r i a l programming, s p a t i a l  a n a l y s i s and p l a n n i n g (London: Methuen, 1971). J.C. Lowe and S.Moryadas, The Geography of Movement, (Boston: Houghton M i f f l i n Co., 1975T! * 6 P.J. Rimmer, " R e d i r e c t i o n s i n t r a n s p o r t a t i o n geography," Progress i n Human Geography, Vol.2, No.1 (1978) pp.76-100. 21 that s c h o o l . * 7 E a r l y work on c i r c u i t network morphology focussed on a c c e s s i b i l i t y * 8 , nodal ( p o i n t ) a n a l y s i s * 9 , and simple s t r u c t u r a l a n a l y s i s . 5 0 These p i o n e e r i n g attempts to d e s c r i b e the form of c i r c u i t networks used simple t o p o l o g i c a l i n d i c e s to i l l u s t r a t e p o i n t and l i n e c h a r a c t e r i s t i c s . However, they d i d l i t t l e to e x p l a i n , r e c o g n i z e or r e v e a l i n t e r n a l p a t t e r n s . Continued r e s e a r c h r e v e a l e d the inadequacies of these i n d i c e s f o r any s o p h i s t i c a t e d a n a l y s i s . 5 1 They were regarded as poor d i s c r i m i n a t o r s f o r a n a l y z i n g isomorphic g r a p h s . 5 2 * 7 W.L. G a r r i s o n , " C o n n e c t i v i t y of the i n t e r s t a t e highway system," Papers and Proceedings of the Regional Science  A s s o c i a t i o n , Vol.6, (1960) pp.121-137. K.J. Kansky, S t r u c t u r e s of T r a n s p o r t a t i o n Networks, Department of Geography, Research Papers, No.84 (Chicago: U n i v e r s i t y of Chicago Press, 1963). G a r r i s o n and Marble, A prolegomenon t o the f o r e c a s t i n g , (1965). * 8 G a r r i s o n , C o n n e c t i v i t y of the i n t e r s t a t e , (1960). * 9 J.D. Nystuen, and M.F.Dacey, "A graph theory i n t e r p r e t a t i o n of nodal r e g i o n s , " Papers and Proceedings  of the Regional Science A s s o c i a t i o n , Vol77 (1961) pp.29-42. 5 0 Kansky, S t r u c t u r e s of T r a n s p o r t a t i o n (1963). G a r r i s o n and Marble, A prolegomenon to the f o r e c a s t i n g , (1965). 5 1 John D. Radke, " S t o c h a s t i c models i n c i r c u i t network growth," Unpublished Master of A r t s t h e s i s (Waterloo, O n t a r i o : Department of Geography, W i l f r i d L a u r i e r U n i v e r s i t y , 1977) G.A. James, A . D . C l i f f , P.Haggett and J.K.Ord, "Some d i s c r e t e d i s t r i b u t i o n s of graphs with a p p l i c a t i o n s t o r e g i o n a l t r a n s p o r t networks," G e o g r a f i s k a Annaler, Vol.52B (1970) pp.14-21. D.C. F u r n e l l , "Methods of measuring the n o d a l i t y of p l a c e s on a t r a n s p o r t a t i o n network - an assessment based on s t u d i e s of the Uganda road system," P e r c e p t i o n and  N o d a l i t y , Department of Geography, Makerere U n i v e r s i t y O c c a s i o n a l Paper,No.15 (1970) pp.26-43. 5 2 James e t a l , Some d i s c r e t e d i s t r i b u t i o n s (1970). 22 In the two decades that f o l l o w e d , the l i t e r a t u r e r e f l e c t e d many attempts at improving the techniques which d e s c r i b e d form. Dacey f o r example progressed from work on nodal a n a l y s i s 5 3 t o an a n a l y s i s of the e n t i r e p a t t e r n of p o i n t s . Dacey not o n l y i n c o r p o r a t e d new m e t r i c s based on d e n s i t y and d i s t a n c e , but a l s o o r i g i n a t e d attempts at d e f i n i n g process i n map p a t t e r n s 5 * . In t h e i r quest to understand the m o r p h o l o g i c a l s t r u c t u r e of c i r c u i t s , those i n 'simple s t r u c t u r a l a n a l y s i s ' f o l l o w e d Dacey's work and i n c o r p o r a t e d d e n s i t y and d i s t a n c e m e t r i c s i n t h e i r search f o r both form and p r o c e s s . Gauthier , f o r example, weighted the l i n k s i n h i s c i r c u i t networks a c c o r d i n g to both d i s t a n c e and t r a n s p o r t c o s t s i n an attempt to d e s c r i b e form more a c c u r a t e l y . 5 5 E a r l y experiments by a mathematician, G i l b e r t 5 6 , to e x p l a i n process were repeated, a l b e i t i n a very a b s t r a c t attempt, by Brown. 5 7 Although Brown c o n s i d e r e d h i s s i m u l a t i o n model to be a p r e d i c t i v e t o o l i n epidemiology, 5 3 Nystuen and Dacey, A graph theory i n t e r p r e t a t i o n (1961). 5 * M i c h a e l Dacey, " E v a l u a t i o n of the Poisson approximation to measures of the random p a t t e r n i n the square," G e o g r a p h i c a l A n a l y s i s , V o l . 7 , No.4 (1975) pp.361-367. 5 5 H. Gauthier, " T r a n s p o r t a t i o n and the growth of the Sao Paulo economy," J o u r n a l of Regional Science, Vol.8, No.1 (1968) pp.77-94. 5 6 E.N. G i l b e r t , "Random plane networks," SIAM J o u r n a l of  A p p l i e d Mathematics, V o l . 9 , (1961) pp.533-543. 5 7 L.A. Brown, "Models f o r s p a t i a l d i f f u s i o n r e s e a r c h , " O f f i c e of Naval Research, Geography Branch, TASK 389-140, T e c h n i c a l Report, No.3 (1965). 23 he d i d not apply i t t o any e m p i r i c a l r e s e a r c h . The a p p l i c a t i o n of models attempting t o r e v e a l process was not seen u n t i l the e a r l y 1970's, when s e v e r a l papers u s i n g s i m u l a t i o n to p r e d i c t i n t e r a c t i o n , and thus the c r e a t i o n of c i r c u i t s , appeared i n the l i t e r a t u r e . The b a s i s of many of these attempts to simulate process l a y w i t h i n the concept of ' p o t e n t i a l ' m o d e l l i n g which was developed by W a r n t z 5 8 i n 1961. T h i s m o d e l l i n g concept was a p p l i e d s p e c i f i c a l l y to the f i e l d of t r a n s p o r t a t i o n through work on paths and f l o w s 5 9 . With the development of ' p o t e n t i a l ' and ' i n t e r a c t i o n ' m o d e l l i n g , w r i t e r s began to answer q u e s t i o n s concerning process i n those networks c l a s s i f i e d as c i r c u i t s . F o l l o w i n g Warntz's work on r i d g e l i n e s 6 0 , K o l a r s and M a l i n 6 1 p r e d i c t e d r i d g e s of p o p u l a t i o n between major c i t i e s u s i ng a g r a v i t y model to p r e d i c t i n t e r a c t i o n between the c e n t r e s . B l a c k 6 2 a l s o used a Warntz type ' p o t e n t i a l ' model 5 8 W i l l i a m Warntz, " T r a n s - A t l a n t i c paths and p r e s s u r e p a t t e r n s , " Geographical Review, Vol.51, No.2 (1961) pp.187-212. 5 9 Warntz, A note on s u r f a c e s and paths (1965). Warntz, The topology of socio-economic (1966). W i l l i a m Warntz, "Global s c i e n c e and the tyranny of space," Papers of the Regional Science  Assoc.,Vol.19,(1967) pp.7-19. 6 0 Warntz, The topology of socio-economic (1966). 6 1 K o l a r s and H.J.Malin, " P o p u l a t i o n and a c c e s s i b i l i t y : an a n a l y s i s of T u r k i s h r a i l r o a d s , " G e o g r a p h i c a l Review, Vol.60, No.2 (1970) pp.229-246. 6 2 W.R. Black, "An i t e r a t i v e model f o r g e n e r a t i n g t r a n s p o r t a t i o n networks," Ge o g r a p h i c a l A n a l y s i s , V o l . 3 , No.3 (1971) pp.283-288. 24 to hypothesize the g e n e r a t i v e process behind l i n e c o n s t r u c t i o n i n c i r c u i t s . To r e c a p i t u l a t e , t h i s examination of the l i t e r a t u r e b r i e f l y p o i n t s out how each of Haggett's c l a s s i f i c a t i o n s of networks has been examined. Research of path and t r e e networks, f o r the most p a r t , has been addressed i n the p h y s i c a l s e c t o r of geography; while c e l l s have been examined by both p h y s i c a l and human geographers a l i k e . C i r c u i t s have been analyzed by human geographers mainly i n the form of t r a n s p o r t a t i o n networks, with e i t h e r a f u n c t i o n a l or mor p h o l o g i c a l approach. Within the morphologic c i r c u i t network l i t e r a t u r e , methodology begins with those who look at form, and ends with those attempting to l i n k form and p r o c e s s 6 3 . Attempts to d e s c r i b e form were at f i r s t , s t r i c t l y t o p o l o g i c a l , but l a t e r s h i f t e d to d e n s i t y and d i s t a n c e m e t r i c s a f t e r s e v e r a l c r i t i q u e s p o i n t e d out t o p o l o g i c a l weaknesses 6 0. J_.4_ P a t t e r n R e c o g n i t i o n Before a n a l y s i s can begin, some of the terms found i n the p a t t e r n r e c o g n i t i o n l i t e r a t u r e need to be d e f i n e d and explaned. " P a t t e r n r e c o g n i t i o n c o n s i s t s e s s e n t i a l l y of 6 3 Radke, S t o c h a s t i c models (1977). 6 * James et a l , Some d i s c r e t e d i s t r i b u t i o n s (1970). 25 e x t r a c t i n g i n f o r m a t i o n from an o b j e c t ( f e a t u r e e x t r a c t i o n ) , and subsequently making d e c i s i o n s about a course of a c t i o n to be taken ( i d e n t i f i c a t i o n , c l a s s i f i c a t i o n and p a t t e r n d e s c r i p t i o n ) " 6 5 . To recognize a p a t t e r n one has to i d e n t i f y c h a r a c t e r i s t i c s about i t s s p a t i a l s t r u c t u r e . Although the terms ' c h a r a c t e r i z e ' and ' s p a t i a l s t r u c t u r e ' have been p r e v i o u s l y i n t r o d u c e d , more e x t e n s i v e d e f i n i t i o n s are warranted. To c h a r a c t e r i z e i s to d e s c r i b e , i n numerical form, some phenomenon which r e v e a l s s p a t i a l p r o p e r t i e s of a p a r t i c u l a r p a t t e r n , or perhaps a c i r c u i t network. For example, a s e r i e s of numbers may be used to s t o r e s p a t i a l i n f o r m a t i o n formerly represented as a map. In t h i s i n s t a n c e , s p a t i a l s t r u c t u r e can f u r t h e r be d e f i n e d as the geometric form, or geometry, of a geographic s i t u a t i o n . In the geographic l i t e r a t u r e there have been two b a s i c approaches to r e c o g n i z i n g or c h a r a c t e r i z i n g shape i n p a t t e r n s . I f we r e t u r n to a m o d i f i c a t i o n of Haggett's paradigm, we can i d e n t i f y the branching of these two approaches ( f i g u r e 1.5). The e x t e r n a l , or ' g l o b a l ' , approach to c h a r a c t e r i z i n g 6 5 G.T. T o u s s a i n t , " P a t t e r n r e c o g n i t i o n and g e o m e t r i c a l complexity," Proceedings of 5th I n t e r n a t i o n a l Conference  on P a t t e r n R e c o g n i t i o n , December (1980). 26 NETWORK CLASSIFICATION IV Network A n a l y s i s 1 S p a t i a l Dimension: non-planar planar Pa t t e r n Type: point area (from f i g u r e 1.1) path tree c i r c u i t c e l l ( t r a n s p o r t a t i o n ) O r i g i n : s y n t h e t i c (man-made) n a t u r a l ( p h y s i c a l ) Geometric Approach: morphology (geometric) f u n c t i o n a l i t y (non-geometric) Pa t t e r n Recognition, S t r u c t u r a l C h a r a c t e r i z a t i o n : i n t e r n a l ( l i n k - b y - l i n k ) e x t e r n a l (global) F i g u r e 1.5 27 s p a t i a l s t r u c t u r e i n v o l v e s e x t r a c t i n g i n f o r m a t i o n about the c h a r a c t e r i s t i c s of the e n t i r e p a t t e r n using a boundary. In the case of the 'standard d e v i a t i o n a l e l l i p s e ' , the d i s p e r s i o n of the e n t i r e p a t t e r n about i t s c e n t r e i s being m easured 6 6. Convex h u l l s have a l s o been used to measure the shape of a p a t t e r n . However, the boundary used i s the outer o n e 6 7 . A recent e f f o r t to s e n s i t i z e the convex h u l l generates 'alpha s h a p e s ' 6 8 , which appear ' g l o b a l ' a t f i r s t , but do r e v e a l some i n t e r n a l s t r u c t u r e of p a t t e r n s . T h i s leads us to an a l t e r n a t i v e approach f o r c h a r a c t e r i z i n g s t r u c t u r e , namely the i n t e r n a l , l o c a l i z e d or neighbourhood approach. The i n t e r n a l approach c o n c e n t r a t e s on the l o c a l i z e d , or neighbourhood, s t r u c t u r e of elements w i t h i n a p a t t e r n . Although l o c a l s t r u c t u r e i s c a l c u l a t e d , i t i s g e n e r a l l y aggregated t o an index form which r e p r e s e n t s the e n t i r e p a t t e r n . T h i s i s done i n order to c l a s s i f y the p a t t e r n a c c o r d i n g to an aggregated d i s t r i b u t i o n of i n t e r n a l c h a r a c t e r i s t i c s . 6 6 J.W. Raine, "Summarizing p o i n t p a t t e r n s with the standard d e v i a t i o n a l e l l i p s e " , Area, Vol.10, No.5 (1978) pp.328-33. R.S. Y u i l l , "The standard d e v i a t i o n a l e l l i p s e ; an updated t o o l f o r s p a t i a l d e s c r i p t i o n " , G e o q r a f i s k a  Annaler, Vol.53B, (1971) pp.28-39. 6 7 T o u s s a i n t , P a t t e r n r e c o g n i t i o n and g e o m e t r i c a l (1980). 6 8 H. Edelsbrunner, D . G . K i r k p a t r i c k and R . S e i d e l , "On the shape of a set of p o i n t s i n the plane,"IEEE T r a n s a c t i o n s  on Information T h e o r y , ( f o r t h coming). 28 In the l i t e r a t u r e , p o i n t p a t t e r n s have been i n t e r n a l l y c h a r a c t e r i z e d by a nearest neighbour s t a t i s t i c which uses d e n s i t y or d i s t a n c e m e t r i c s 6 9 . S e v e r a l attempts at c i r c u i t network c h a r a c t e r i z a t i o n on a l o c a l s c a l e e x i s t , but these are mainly found i n the l i t e r a t u r e a d d r e s s i n g nodal a n a l y s i s i n t r a n s p o r t a t i o n n e t w o r k s 7 0 . As i n the p o i n t p a t t e r n l i t e r a t u r e , most of these attempts employ s t r i c t l y d e n s i t y and d i s t a n c e m e t r i c s . K 5 Research O b j e c t i v e s F o l l o w i n g a m o d i f i c a t i o n of Haggett's paradigm ( f i g u r e 1 . 5 ) the r e s e a r c h uses some geometric c h a r a c t e r i s t i c s of i n t e r n a l s p a t i a l s t r u c t u r e to examine the morphology of s y n t h e t i c c i r c u i t networks. Since t h i s r e s e a r c h i s concerned with geometric c h a r a c t e r i s t i c s of c i r c u i t networks, and s i n c e such c h a r a c t e r i s t i c s are common to a l l types of networks, i t i s reasonable to assume that the approach and methodology developed here are u n i v e r s a l i n nature and thus t h e i r a p p l i c a t i o n i s not s o l e l y r e s t r i c t e d t o the d i s c i p l i n e of geography. 6 9 Tavlor, Quantitative Methods i n Geography ( ^ 7 7 ) . Getis and Boots, HodelTKsMl^|™=£5g£&' l 9 7 8 ' Vol.59, No\3^T969) pp.417-440. 29 T h i s t h e s i s attempts to recognize p a t t e r n at an i n t e r n a l , l o c a l i z e d l e v e l i n c i r c u i t n e t w o r k s 7 1 . In order to pursue t h i s g o a l , a t w o - f o l d methodology i s i n t r o d u c e d . T h i s i n v o l v e s f i r s t l y , the use of a t h e o r e t i c a l p r o c e s s 7 2 to generate a bench mark, or y a r d s t i c k , to which d e s c r i p t i o n s of form can be o r i e n t e d ; and secondly, the l i n k - b y - l i n k examination of c i r c u i t networks determining each l i n k ' s r e l a t i o n s h i p to the bench mark. F i r s t l y , i n keeping with the form-process dichotomy c a t a l o g u e d i n recent l i t e r a t u r e , t h i s t h e s i s uses the 'process-model' a p p r o a c h 7 3 to generate a t h e o r e t i c a l bench mark. The 'spacing' l i t e r a t u r e uses the t h e o r e t i c a l 'Poisson' as a process to generate a bench mark from which to i d e n t i f y p o i n t p a t t e r n s ; and the 'shaping' l i t e r a t u r e uses c e n t r a l p l a c e theory ( C h r i s t a l l e r i a n hexagonal s u r f a c e s ) to measure d i s t o r t i o n or v a r i a t i o n i n g l o b a l shapes. 7* T h i s t h e s i s uses a s e r i e s of t h e o r e t i c a l l y 7 1 K.J. T i n k l e r , " C h a r a c t e r i z i n g graphs of networks t h a t a l l have the same l o c a l s t r u c t u r e , " Presented a t the A s s o c i a t i o n of American Geographers 73rd Annual Meeting, New Orleans (1978). 7 2 The p r o c e s s takes i n t o account t h a t i n t e r v e n i n g p o i n t s or bodies i n f l u e n c e the s p a t i a l i n t e r a c t i o n between two p o i n t s and thus a f f e c t s t h e i r n e i g h b o u r l i n e s s and l i k e l i h o o d of being l i n k e d . T h e r e f o r e , when d e a l i n g w i t h the absence of other l i n k c r i t e r i a , the 'gravity-model' concept severes as a d i s c r i m i n a t o r of neighbours. 7 3 Barry N. Boots, and Arthur G e t i s , " P r o b a b i l i t y model approach to map p a t t e r n a n a l y s i s , " Progress i n Human  Geography, V o l . 1 , No.2 (1977) pp.264-287. 7 * Two examples of g l o b a l shape are the Standard D e v i a t i o n a l E l l i p s e and the Convex H u l l . 30 generated graphs as a bench mark, to c h a r a c t e r i z e the i n t e r n a l s t r u c t u r e of c i r c u i t networks. Chapter 3 c o n t a i n s a comprehensive d e s c r i p t i o n of the graphs composing the bench mark i n t h i s t h e s i s . B r i e f l y , they have a continuous range from a completely connected graph (CCG), t o a very rudimentary graph (RG) with few p o i n t s connected. The u n d e r l y i n g t h e o r e t i c a l g e n e r a t i v e process of each graph composing the bench mark i n v o l v e s l i n k i n g two p o i n t s , i n an e m p i r i c a l graph under study, i f a search space between them c o n t a i n s no other p o i n t s from the same g r a p h . 7 5 The search space can be a l t e r e d to c r e a t e a continuous range of search spaces which can then be used to generate a spectrum of graphs ranging from the CCG to the RG. For the completely connected graph, the search space of two p o i n t s i s c h a r a c t e r i z e d by a s t r a i g h t l i n e drawn between them. For the rudimentary graph, the search space i s c h a r a c t e r i z e d by a l i n e drawn between two p o i n t s and the e n t i r e space p e r p e n d i c u l a r to and on e i t h e r s i d e of the l i n e . The r e s t of the search spaces f a l l w i t h i n the CCG and RG bounds. Two of these t h e o r e t i c a l l y generated graphs used i n the bench mark are known i n the l i t e r a t u r e , the ' R e l a t i v e Neighborhood Graph' and the ' G a b r i e l G r a p h ' . 7 6 7 5 In other words, neighbourly p o i n t s have a high l i k e l i h o o d of being l i n k e d when a l a r g e empty search space i s p o s s i b l e . On the other hand, i n t e r v e n i n g p o i n t s cause a p a i r of p o i n t s being examined to become l e s s n e i g h b o u r l y and have a low l i k e l i h o o d of being l i n k e d . 7 6 T o u s s a i n t , G.T., P a t t e r n r e c o g n i t i o n and g e o m e t r i c a l , 31 The second phase of the methodology i n v o l v e s l i n k - b y - l i n k examination of an e m p i r i c a l network, comparing each e x i s t i n g l i n k to a s e r i e s of t h e o r e t i c a l l y generated graphs from the spectrum of graphs which make up the bench mark i n the f i r s t phase of the methodology. E m p i r i c a l l i n k s which correspond to those which would f i r s t appear i n a very rudimentary graph of the bench mark would have a very h i g h l i k e l i h o o d of o c c u r r i n g . T h i s h i g h l i k e l i h o o d e x i s t s as a r e s u l t of the t h e o r e t i c a l g e n e r a t i v e process used to generate the search space f o r each l i n k . The concept of the search space can be p a r a l l e l e d with the concept behind the Newtonian g r a v i t y m o d e l . 7 7 In the Newtonian g r a v i t y model, the a t t r a c t i o n of one mass to another i s a f u n c t i o n of both t h e i r masses and t h e i r p r o x i m i t y with respect to each o t h e r . As the d i s t a n c e s e p a r a t i n g the two masses decreases, the a t t r a c t i o n between them i n c r e a s e s . Likewise, as the d i s t a n c e between the two masses i n c r e a s e s , t h e i r a t t r a c t i o n to each other decreases. S i m i l a r i l y , as the p r o x i m i t y of p o i n t s t o each l i n k being examined i n an e m p i r i c a l network decreases, the search space needed t o observe a p o i n t i n c r e a s e s and the l i k e l i h o o d of the l i n k o c c u r r i n g i n c r e a s e s because the p o t e n t i a l i n t e r a c t i o n between the two l i n k end p o i n t s i s g r e a t e r than with any other p o i n t s . 1980. 7 7 P.J. T a y l o r , "Distance decay i n s p a t i a l i n t e r a c t i o n s " , CATMOG S e r i e s (1975). 32 E m p i r i c a l l i n k s which correspond t o t h e o r e t i c a l l y generated l i n k s which would f i r s t appear i n a completely connected graph of the bench mark, would have a very low l i k e l i h o o d of o c c u r r i n g , as they would appear t o possess redundant q u a l i t i e s . On the other hand, l i n k s which would appear i n the RG end of the spectrum would have a high l i k e l i h o o d of occurance. The r e s u l t of such a method i s an e m p i r i c a l c i r c u i t network w i t h a mosaic of weighted l i n k s , each corresponding to some t h e o r e t i c a l l y generated l i n k s t r u c t u r e . I t i s argued that t h i s p r o v i d e s a u s e f u l a b s o l u t e comparison of l i n k s w i t h i n and between networks, as w e l l as a t o o l f o r o v e r a l l p a t t e r n r e c o g n i t i o n . 6 Summary of Chapter j_ The need to develop theory which can a i d i n the r e c o g n i t i o n of s p a t i a l s t r u c t u r e i n c i r c u i t networks i s the m o t i v a t i o n behind t h i s t h e s i s . A s c i e n t i f i c approach i s taken i n an attempt to l i n k the form of e m p i r i c a l c i r c u i t networks with a t h e o r e t i c a l g e n e r a t i v e p r o c e s s . The i m p l i c a t i o n s of such an approach are t w o - f o l d : i ) the t h e o r e t i c a l g e n e r a t i v e process p r o v i d e s a good bench mark to which e m p i r i c a l s p a t i a l s t r u c t u r e can be compared. T h i s comparison a l l o w s a more g e n e r a l i z e d d e s c r i p t i o n of form, and c r e a t e s a medium i n which inter-network comparison can be made between two separate e m p i r i c a l 33 networks; and i i ) the second advantage hinges on the f a c t t h a t i n the form-process examination techniques, the c i r c u i t network's l i n k s are i n d i v i d u a l l y compared to the bench mark. T h i s i n t e r n a l l i n k - b y - l i n k approach allows comparisons w i t h i n the l i n k s t r u c t u r e of the e m p i r i c a l network and thus an intra-network examination of the network's p a t t e r n . Such comparison a i d s i n r e v e a l i n g trends w i t h i n the l i n k s t r u c t u r e of a p a r t i c u l a r e m p i r i c a l c i r c u i t network. Haggett's paradigm of network c l a s s i f i c a t i o n i s adopted and m o d i f i e d t o d e l i n e a t e the type of networks addressed i n t h i s d i s s e r t a t i o n . A review of the l i t e r a t u r e s e t s the stage upon which t h i s t h e s i s u n f o l d s , at f i r s t b r i e f l y examining the a n a l y s i s of networks i n geography i n g e n e r a l . T h i s i s f o l l o w e d by a review of the l i t e r a t u r e d e a l i n g with c i r c u i t networks i n geography which represent t r a n s p o r t a t i o n networks. A f i n a l m o d i f i c a t i o n to Haggett's paradigm i s undertaken to d e l i n e a t e the l e v e l of p a t t e r n r e c o g n i t i o n i n v e s t i g a t e d i n t h i s r e s e a r c h . A g l o b a l , or e x t e r n a l approach i s examined and c o n t r a s t e d to the i n t e r n a l , or l o c a l i z e d examination of network l i n k s used i n t h i s t h e s i s . F i n a l l y , the main o b j e c t i v e of the r e s e a r c h , to r e c o g n i z e p a t t e r n s a t an i n t e r n a l , l o c a l i z e d l e v e l i n 34 c i r c u i t networks, i s made e x p l i c i t . In order to accomplish t h i s objective, a two-fold methodology i s introduced and b r i e f l y explained. Further detailed examination of the methodology i s reserved for Chapter 3. 35 Chapter 2: ANALYTICAL FORUM 2 .J_ I n t r o d u c t i o n T h i s chapter w i l l develop a working typology f o r the t h e s i s . Whenever r e s e a r c h of t h i s k i nd i s undertaken, there i s always an immediate quest f o r a t h e o r e t i c a l framework t o p r o v i d e an adequate base or forum f o r a n a l y s i s and understanding. In geography and e s p e c i a l l y i n t r a n s p o r t a t i o n , many s t u d i e s have not focused on fundamental c h a r a c t e r i s t i c s such as geometric s t r u c t u r e . They have d e a l t with q u e s t i o n s about i n d i v i d u a l road c h a r a c t e r i s t i c s , r a t h e r than attempt a view of the e n t i r e system. There does e x i s t however, a growing body of l i t e r a t u r e that adopts d e f i n i t i o n s which f i l t e r out' r e a l world 'noise' by p r e s e n t i n g c i r c u i t networks as models or geometric a b s t r a c t s of r e a l i t y . The present study adopts these d e f i n i t i o n s . 36 Although there i s no g e n e r a l theory of movement i n geography, models are seen as good b u i l d i n g blocks f o r theory. In t h i s r e s e a r c h , t r a n s p o r t a t i o n ( c i r c u i t ) networks w i l l be presented as analog models i n order to reach a l e v e l of a b s t r a c t i o n where some t h e o r e t i c a l g e n e r a l i z a t i o n s may be made 1. 2.2 Network A n a l y s i s The term network i s not new to the l i t e r a t u r e , with some c l a s s i c s t u d i e s d a t i n g back to the 19th C e n t u r y 2 . The f i r s t comprehensive treatment of network topology was p u b l i s h e d by Kansky i n 1963 3. As argued i n the f i r s t c hapter, network a n a l y s i s i s of common i n t e r e s t to both human and p h y s i c a l geographers', but d i d not become widely entrenched i n the l i t e r a t u r e u n t i l the l a t e 1950's and e a r l y 1960's 5. Kansky*s work has been the most c i t e d , and 1 As p r e v i o u s l y mentioned, t h i s l e v e l of a b s t r a c t i o n can a l s o t r a n s f e r to d e s c r i p t o r s of form, the a b i l i t y to u n i v e r s a l l y c h a r a c t e r i z e . 2 Peter Haggett and R.J.Chorley, Network A n a l y s i s i n  Geography, (London: Edward A r n o l d L t d . , 1969) p i 2 1 . 3 K.J. Kansky, S t r u c t u r e s of T r a n s p o r t a t i o n Networks, Department of Geography, Research Papers No.84. (Chicago: U n i v e r s i t y of Chicago Press, 1963). * Haggett and C h o r l e y , Network A n a l y s i s i n Geography ( 1969). R.E. Horton, " E r o s i o n a l development of streams and t h e i r drainage b a s i n s : h y d r o p h y s i c a l approach to q u a n t i t a t i v e morphology," B u l l e t i n of the G e o l o g i c a l  S o c i e t y of America, Vol.56, (1945) pp.275-370. W.L. G a r r i s o n , " C o n n e c t i v i t y of the i n t e r s t a t e highway system," Papers and proceedings of the Regional Science  Assoc., V o l . 6 , (1960) pp.121-137. D.L. Huff, "A t o p o g r a p h i c a l model of consumer space s much of the terminology found i n the geographic l i t e r a t u r e has grown from h i s book. A network i s a r e a l world o b j e c t and can be c o n s i d e r e d a system of i n t e r l a c i n g c u r v e s . 6 For geographers, Kansky d e f i n e s a network as a set of geographic elements i n t e r c o n n e c t e d i n t o a system by a number of r e l a t i o n s h i p s 7 . The three fundamental c h a r a c t e r i s t i c s of t r a n s p o r t a t i o n networks each occupy a unique geographic l o c a t i o n : o r i g i n , route and d e s t i n a t i o n . The elements of a t r a n s p o r t a t i o n network are s y n t h e t i c (man-made) and are l o c a t e d on the p h y s i c a l landscape i n geometric p a t t e r n s . Sometimes however, the elements can d e v i a t e from the t a n g i b l e o b j e c t s such as roadways to the i n t a n g i b l e or impalpable such as a i r l i n e r o u t e s . Analog models however, can account f o r i n t a n g i b l e a r t e r i e s which have a s i m i l a r r e p r e s e n t a t i o n to the t a n g i b l e . Network a n a l y s i s i s an examination of a complete network, i t s elements, and t h e i r r e l a t i o n s h i p s . In the pas t , geographers have commonly represented networks i n two ways. The f i r s t , a map, can summarize many network p r e f e r e n c e s , " Papers and proceedings of the Regional  Science Assoc., Vol.6, (1960) pp.159-173. J.D. Nystuen and M.F. Dacey, "A graph theory i n t e r p r e t a t i o n of nodal r e g i o n s , " Papers and Proceedings of  the Regional Science A s s o c i a t i o n , Vol.7,(1961) pp.29-42. Kansky, S t r u c t u r e s of T r a n s p o r t a t i o n (1963). 6 A graph i s c o n s i d e r e d the r e p r e s e n t a t i o n of a r e a l world network. 7 Kansky, S t r u c t u r e s of T r a n s p o r t a t i o n , 1 9 6 3 . 38 c h a r a c t e r i s t i c s but o f t e n proves too i n f l e x i b l e t o permit f u n c t i o n a l a n a l y s i s of a network. A second form of network r e p r e s e n t a t i o n i s a matrix, i n which the rows and columns represent i n d i v i d u a l elements, and the e n t r i e s i n the body of the matrix represent the r e l a t i o n s h i p between the elements. T h i s t h e s i s d e a l s p r i m a r i l y with c i r c u i t networks represented as a graph whose p o i n t elements 8 are embedded i n a plane; t h e r e f o r e , matrix r e p r e s e n t a t i o n i s not d i s c u s s e d . 9 A symbolic n o t a t i o n i s common to the analog model (the graph) and a i d s p r e c i s i o n i n the d i s c u s s i o n of network c h a r a c t e r i s t i c s . T h i s symbolic language decreases the ambiguity so o f t e n found i n d e s c r i p t i v e language. Geographers can a p p r e c i a t e the n e c e s s i t y of such a language; maps as s e t s of symbolic elements are probably the o l d e s t models of p h y s i c a l f e a t u r e s l o c a t e d on the ea r t h ' s s u r f a c e . 2.3 T h e o r e t i c a l Concepts of the Graph S e v e r a l textbooks d i s c u s s the analog model, the graph, 8 P o i n t elements are d i s c u s s e d on the f o l l o w i n g page. 9 Examples of networks represented as mat r i c e s are q u i t e common and can be found i n most t e x t s a d d r e s s i n g graph the o r y . R.G. Busacker and T.G. Saaty, F i n i t e Graphs and Networks, (Toronto: McGraw-Hill Inc., 1965). Frank Harary, Graph Theory, (Reading: Addison-Wesley, 1969). 39 and i t s symbolic l a n g u a g e 1 0 . In t h i s s e c t i o n terms used i n t h i s study are d e s c r i b e d with d e f i n i t i o n s that are c l o s e l y a l i g n e d with those i n the major textbooks. The mathematical concept, the graph, has become a widely used t o o l i n geography. A graph can be co n s i d e r e d analogous t o , or a s p e c i a l c a s e 1 1 of a map. Graph theory, a branch of c o m b i n a t o r i a l topology, p r o v i d e s the a p p r o p r i a t e symoblic language and framework f o r the c h a r a c t e r i z a t i o n and a n a l y s i s of the geometric s t r u c t u r e of networks. Although maps, which represent i n v i s u a l form data gathered from o r i g i n a l surveys, have been with us f o r hundreds of yea r s , the i n t r o d u c t i o n of graph theory to geography i s r e c e n t . In t r a n s p o r t a t i o n , graph theory was f i r s t i n t r o d u c e d as a framework f o r a n a l y s i s by G a r r i s o n 1 2 i n a paper on "The c o n n e c t i v i t y of the i n t e r s t a t e highway system i n the Un i t e d S t a t e s " and H u f f 1 3 i n a paper "A t o p o g r a p h i c a l ( s i c ) model of consumer space p r e f e r e n c e s " . Geography has borrowed techniques from neighbouring d i s c i p l i n e s f o r q u i t e some time and Graph Theory i s no e x c e p t i o n . With t h i s 'new' framework came a new set of 1 0 Haggett and Chorley, Network A n a l y s i s (1965). Harary, Graph Theory (1969) 1 1 A map i s c o n s i d e r e d a two dimensional a b s t r a c t i o n of a three dimensional world. 1 2 G a r r i s o n , C o n n e c t i v i t y of the i n t e r s t a t e (1960). 1 3 Huff, A t o p o g r a p h i c a l model (1960). 40 terms rooted mainly i n mathematics and e n g i n e e r i n g . U n f o r t u n a t e l y , as with most r e l a t i v e l y new techniques, a standard terminology i s l a c k i n g , t h e r e f o r e a b r i e f review of some common graph t h e o r e t i c concepts i s warranted here. A graph i s composed of a set of V v e r t i c e s (sometimes known as nodes) which can represent p o i n t s i n space, and a set of E l i n k s which are edges connecting d i s t i n c t p a i r s of v e r t i c e s . An edge i s another term f r e q u e n t l y used to represent a l i n k . Such a graph i s u s u a l l y denoted G(V;E) and i s g e n e r a l l y represented by a diagram ( f i g u r e 2.1). Since i n t h i s t h e s i s the v e r t i c e s are embedded i n a plane, they represent s p e c i f i c geographic l o c a t i o n s i n space. The p a t t e r n r e c o g n i t i o n scheme developed i n Chapter 3 takes advantage of t h i s c h a r a c t e r i s t i c of embedded gr a p h s . 1 * V(G) i s u s u a l l y denoted as the v e r t e x - s e t , and E(G) the l i n k or edge-set of G. The order of G or the number of elements of V(G) i s represented by n, while the number of elements i n E(G) i s denoted by m, that i s : G(n,m). A l i n k or edge {Vj,Vj} i s u s u a l l y r e presented by e j j where Vj and Vj are v e r t i c e s of V(G). Although phenomena i n t h i s t h e s i s are c o n s i d e r e d embedded i n a plane, the techniques developed here can extend to other dimensions and measurements of d i s t a n c e . 41 POINTS AND LINKS IN GRAPH G(V;E) G(n,m) = G ( 5 , 6 ) F i g u r e 2.1 ADJACENT AND TOPOLOGICAL NEIGHBOURS 42 Adjacency I f e i j i s a l i n k i n E(G), then e i s s a i d to j o i n and Vj and these v e r t i c e s are adjacent ( f i g u r e 2.2). Here, v i i s a l s o s a i d to be a t o p o l o g i c a l neighbour of Vj and e i s i n c i d e n t t o V\ and V j . A graph i n which each vertex i s adjacent t o a l l others i s termed a complete graph ( f i g u r e 2.3) . A complete graph ( f o r n£5) i s c o n s i d e r e d non-planar as l i n k c r o s s i n g s do not n e c e s s a r i l y form v e r t i c e s i n the graph. Valency L i n k s or edges i n a graph are c o n s i d e r e d adjacent when two l i n k s i n E(G) share a common vertex i n V(G) ( f i g u r e 2.4) . In t h i s case, the v e r t e x V, i s i n c i d e n t to both l i n k s and i s s a i d t o have a valency or degree of two, denoted by P(V,)=2. A v e r t e x with a P(V)=0 i s c a l l e d an i s o l a t e d v e r t e x while a P(V)=1 denotes an end-vertex. I f a l l V(G) have the same P(V), then G i s s a i d t o be a r e g u l a r  graph or p - v a l e n t graph ( f i g u r e 2.5). An O-Valent graph i s c a l l e d a n u l l graph (one where V(G)=G and E(G)=#) and i s u s u a l l y r e f e r r e d t o as a p o i n t graph or p o i n t p a t t e r n ( f i g u r e 2.6). When V(G)=1 and E(G)=0 the graph i s denoted t r i v i a l . A 3-valent graph i s u s u a l l y termed a t r i v a l e n t  graph. 43 COMPLETE GRAPH G(n,m) = G(5,10) Figure 2 . 3 ADJACENT LINKS OR EDGES V-V_ i s incident to e_j and e ^ Valency of V_ = P(Vi) = 2 P(Vj) = 1 denoted an end point P(V n) = 0 denoted an is o l a t e d point G(n,m) = G ( 4 , 2 ) Figure 2 . 4 44 REGULAR OR P-VALENT GRAPH P ( V i , V j , V k ) = 2 G(n,m) = G(3,3) F i g u r e 2.5 NULL OR O-VALENT GRAPH # V k P ( V i , V j , V k ) = 0 G(n,m) = G(3,0) Commonly a P o i n t P a t t e r n F i g u r e 2.6 k 45 Paths and C i r c u i t s A sequence of l i n k s {e 0,e,,e 2,...,Vr} i s c a l l e d a walk from V 0 to Vr. I f the l i n k s are s h a r p l y d e f i n e d , 1 5 the walk i s c a l l e d a t r a i l ; and i f both the l i n k s and v e r t i c e s are s h a r p l y d e f i n e d , the t r a i l i s denoted as a p a t h ( f i g u r e 2.7). The l e n g t h of a path can be measured i n s e v e r a l ways. The most common i s t o p o l o g i c a l l e n g t h where each l i n k i s given a value of one and the l e n g t h between V 0 and V 3 i n path {V 0,...,Vr}, i s t h r e e . A second approach, f a m i l i a r to geographers, i n v o l v e s the use of e u c l i d e a n d i s t a n c e 1 6 as a framework f o r measuring path l e n g t h . Here, the graph i s embedded i n e u c l i d e a n space and the length between V 0 and V 3 i n a path {V 0,...,Vr} i s some u n i t of e u c l i d e a n d i s t a n c e or the sum of the l e n g t h of each l i n k between V 0 and V 3 ( f i g u r e 2.8). If V 0=Vr and {V 0,V,,...,Vr} i s a path, then the walk i s l a b e l l e d a c i r c u i t , sometimes known as a c y c l e . A fundamental c y c l e e x i s t s when i t s elements bound a c e l l which c o n t a i n s no l i n k s or v e r t i c e s ( f i g u r e 2.9). A c i r c u i t of t o p o l o g i c a l l e n g t h three i s c a l l e d a t r i a n g l e . 1 5 The term 'sharply d e f i n e d ' denotes elements that are c l e a r l y d e f i n e d and r e c o g n i z a b l y not the same. 1 6 Other spaces can be used, however, i n t h i s t h e s i s measurement i s addressed i n e u c l i d e a n space. 46 A PATH v 3 e i . V 0 « ' Vl^-Qj- / \ e 3 e t • v r V 2 1 • ' LENGTH |(V 0 to V 3) = (ei+e 2+e 3) = 3 where: e ± = 1 r TOTAL = S e± = r i= l Figure 2.7 EUCLI DEAN PATH WITH WEIGHTED LENGTHS Vi v 3 V 0 e i = 16 e 3 = 2 5 / l = 20 e 2=21^ •Vr V 2 \ • LENGTH i (V 0 to v 3 ) = (ei+e 2+e 3) = 62 whe re: ei = 16 e 2 = 21 e 3 = 25 Figure 2.8 47 A CIRCUIT v 2 v 3 -WHEN V 0=V r and {V 0,Vi,...V r} i s a path, a c i r c u i t or 1 cycle e x i s t s . V 0=V r - In t h i s instance a fundamental cycle e x i s t s . Vi A -A c i r c u i t with topo-l o g i c a l length = 3 V 0 i s a t r i a n g l e . Figure 2.9 A PLANE GRAPH ^—FACE 1/1 > Figure 2.10 48 Often c i r c u i t graphs are embedded i n or i l l u s t r a t e d on a planar s u r f a c e without any i n t e r s e c t i n g l i n k s and are denoted plane graphs ( f i g u r e 2.10). A contiguous area of a plane which i s bounded by a fundamental c y c l e of an embedded plane graph i s c a l l e d a f a c e . C o n n e c t i v i t y A connected graph i s one th a t has at l e a s t one path between every p a i r of v e r t i c e s . When a connected graph c o n t a i n s no c y c l e s i t i s known as a t r e e ( f i g u r e 2.11). When a disc o n n e c t e d or non-connected graph c o n t a i n s no c y c l e s i t i s known as a set of t r e e s and termed a f o r e s t or a c y c l i c graph ( f i g u r e 2.12). A graph G,(V;E) i s a subgraph of graph G 2(V;E) i f i t s elements EtG,) and V(G,) are a l s o elements of G 2(V;E) and where Gi(n,m) £ G 2(n,m). I f G 2 i s a connected graph and H i s a subgraph of G 2, and i f V(G 2)=V(H), then H i s a spanning subgraph of G 2. I f H c o n t a i n s no c i r c u i t s then H i s a spanning t r e e of G 2. I f the d i s t a n c e ( t o t a l d i s t a n c e between a l l p o i n t s ) w i t h i n H i s minimized, then H becomes the minimum spanning t r e e MST(G 2) ( f i g u r e 2.13). 49 A FOREST OR ACYCLIC GRAPH F i g u r e 2.12 5 0 Figure 2.13 2.4 Map P a t t e r n s Geographers have always been i n t e r e s t e d i n map p a t t e r n s . Some have been concerned with the development of techniques to d e s c r i b e and summarize map p a t t e r n s , thus f a c i l i t a t i n g t h e i r comparison. Others have been i n t e r e s t e d i n map p a t t e r n s f o r a n a l y t i c a l purposes, to i d e n t i f y the process r e s p o n s i b l e f o r the p a r t i c u l a r form of a phenomenon 1 7. Geographers have approached the area of p a t t e r n r e c o g n i t i o n i n three b a s i c ways. A l l c o n t a i n some form of a b s t r a c t i n g r e a l i t y i n t o symbols, the " r e s u l t of t h e o r e t i c a l knowledge which we b r i n g to bear on the problem being s t u d i e d . " 1 8 These symbols are recognized as p o s s e s s i n g c e r t a i n p r o p e r t i e s , among which d i m e n s i o n a l i t y p l a y s an important r o l e i n c l a s s i f i c a t i o n . Thus we have three types of p a t t e r n s p r e v i o u s l y c l a s s i f i e d by H a g g e t t 1 9 , ... p o i n t , l i n e and area p a t t e r n s . P o i n t s are without dimension, l i n e s have one dimension and areas have two dimensions. A c i t y can be i l l u s t r a t e d on a map as a p o i n t , a road i s mapped as a l i n e and a r e g i o n i s a b s t r a c t e d as an a r e a . 1 7 Barry N. Boots and Arthur G e t i s , " P r o b a b i l i t y model approach to map p a t t e r n a n a l y s i s , " P r o g r e s s i n Human  Geography, V o l . 1 , No.2 (1977) pp.264-280. 1 8 A r t h u r G e t i s and Barry N.Boots, Models of S p a t i a l  Processes (Cambridge: Cambridge U n i v e r s i t y Press, 1978). 1 9 Peter Haggett, L o c a t i o n a l A n a l y s i s i n Human Geography (Toronto: MacMillan Co.,1965). 52 2.5 P o i n t P a t t e r n A n a l y s i s Two d i s t i n c t approaches have evolved to d e a l with the problems of p o i n t p a t t e r n r e c o g n i t i o n . The f i r s t , the 'quadrat a p p r o a c h ' 2 0 uses a methodology based on d e n s i t y ; the second, the 'nearest neighbour approach', r e l i e s on e u c l i d e a n d i s t a n c e m e t r i c s . Recently t h e r e has been i n t r o d u c e d an a l t e r n a t i v e approach which d e a l s with the p r o p e r t i e s of the set of Delaunay t r i a n g l e s of a p o i n t p a t t e r n 2 1 . The s t r a t e g y f o r seeking p a t t e r n s i n quadrat a n a l y s i s i s to sample the d e n s i t y or frequency of p o i n t s at d i f f e r e n t l o c a t i o n s . To do t h i s , a g r i d i s super-imposed on a set of p o i n t s i n space, u s u a l l y embedded i n a plane ( f i g u r e 2.14), and the number of p o i n t s i n each quadrat i s then recorded. The r e s u l t i s a frequency d i s t r i b u t i o n of d e n s i t y values f o r the quadrats c o n t a i n e d w i t h i n the p o i n t p a t t e r n . T h i s frequency d i s t r i b u t i o n can be compared t o the frequency d i s t r i b u t i o n of some t h e o r e t i c a l l y generated p a t t e r n (bench mark) such as the Poisson, to determine i f the p a t t e r n i s d i s p e r s e d ( r e g u l a r ) random or c l u s t e r e d . The second approach to P o i n t P a t t e r n A n a l y s i s , the 2 0 M i c h a e l F. Dacey, "The geometry of c e n t r a l p l a c e theory", G e o g r a f i s k a Annaler, Vol.47B, (1965) pp.111-124. 2 1 G e t i s and Boots, Models of S p a t i a l Processes (1978). 53 QUADRAT ANALYSIS OF A POINT PATTERN A B C • ••• • • • • • • • • • • • • • • Quadrat | Frequency of j p o i n t s AA | 5 AB | 2 AC | 4 BA | 0 BB j 5 BC | 2 CA | 1 CB | 1 CC 3 s:= 23 = n - where n = # of p o i n t s i n the p a t t e r n . F i g u r e 2.14 54 nearest neighbour approach, exchanges the no t i o n of p o i n t s per u n i t area ( d e n s i t y ) f o r i t s r e c i p r o c a l , area per p o i n t ( d i s t a n c e s p a c i n g ) . T h i s method i s q u i t e simple and i n v o l v e s measuring the e u c l i d e a n d i s t a n c e ' r 0 ' between every p o i n t and i t s nearest neighbour i n the p a t t e r n ( f i g u r e 2.15). The mean of a l l these e u c l i d e a n nearest neighbour (ENN) d i s t a n c e s produces a value ' r 0 ' which can be compared to a standard i n order to determine the s p a t i a l c h a r a c t e r i s t i c s of the set of p o i n t s . The standard or bench mark used i n most i n s t a n c e s i s the mean nearest neighbour d i s t a n c e of a p o i n t p a t t e r n which has been generated by u s i n g the Poisson p r o c e s s . T h i s i s sometimes denoted a 'random' p o i n t p a t t e r n . The expected mean ENN d i s t a n c e f o r t h i s t h e o r e t i c a l l y generated p a t t e r n i s g iven by: ' f e ' = 1.0/fc.O/X) where X = n/a where n = number p o i n t s i n the p a t t e r n a = area of the p a t t e r n . 2 2 An 'R' s t a t i s t i c i s generated, (R = f 0 / f e ), which measures the amount of divergence between the observed p o i n t p a t t e r n ' s mean ENN d i s t a n c e and t h a t of the bench mark, the t h e o r e t i c a l l y generated Poisson. T h i s 'R' 2 2 P.J. T a y l o r , Q u a n t i t a t i v e Methods i n Geography (Boston: Houghton M i f f l i n Company, 1977). 55 EUCLIDEAN NEAREST NEIGHBOUR MEASUREMENTS - where rQ = mean ENN di s t a n c e , d. = the ENN distance between two p o i n t s , n = the number of points i n the pat t e r n . = 2.0 Figure 2.15 56 s t a t i s t i c ranges from 0.0 to 2.149, where the former i s a t o t a l l y c l u s t e r e d p a t t e r n of p o i n t s , a l l the p o i n t s being i n one l o c a t i o n , and the l a t t e r i s a r e g u l a r or d i s p e r s e d p a t t e r n . A v a l u e of 1.0 would r e v e a l that the mean ENN d i s t a n c e f o r the observed p a t t e r n was equal to that of the t h e o r e t i c a l l y generated Poisson p a t t e r n 2 3 . The most recent attempt at p o i n t p a t t e r n r e c o g n i t i o n , the Delaunay t r i a n g u l a t i o n approach 2*, i n v o l v e s shape. U n l i k e the quadrat and ENN approaches, the DT approach i s ' d e n s i t y independent'. The ' d e n s i t y - f r e e ' p r o p e r t i e s of the Delaunay T r i a n g l e s 2 5 a l l o w the observed d i s t r i b u t i o n of a ngles w i t h i n the t r i a n g l e s t o be compared without b i a s t o a d i s t r i b u t i o n of angles generated by a Poisson process ( f i g u r e 2 . 1 6 ) 2 6 . However once the Poisson Model i s r e j e c t e d due t o l a c k of c o r r e l a t i o n between the observed and expected, u n l i k e the 'quadrat' and 'nearest neighbour' approaches, one cannot s p e c u l a t e about the nature of the p o i n t p a t t e r n . T h i s i n a b i l i t y to p r e d i c t i s a f u n c t i o n of the s t a t e of the development of r e s e a r c h i n t h i s a r e a 2 7 S t i l l the DT approach to measuring angles i s noteworthy 2 3 I b i d . 2 4 Barry N. Boots, "Delaunay t r i a n g l e s : an a l t e r n a t i v e approach t o p o i n t p a t t e r n a n a l y s i s , " Proceedings of the  Assoc i a t i o n of American Geographers, Vol.6, TT974) pp.26-29. 2 5 An e x p l a n a t i o n of Delaunay T r i a n g l e s i s given i n Chapter 3. 2 6 The C h r i s t a l l e r i a n hexagonal s t r u c t u r e can a l s o be used as a bench mark f o r comparison. 2 7 G e t i s and Boots, Models of S p a t i a l Processes (1978). 57 X = 0 . 0 0 2 X = 0 . 0 0 5 Figure 2.16 Measuring Angles i n Delaunay Triangles. [ where X = density ] 58 here because the method fo l l o w e d i n Chapter 3 i s a l s o d e n s i t y independent. There have been other approaches to p o i n t p a t t e r n r e c o g n i t i o n but many of them have proved t o be vacuous. However, one mentioned i n the p r e v i o u s chapter and worth expanding upon i s the Standard D e v i a t i o n a l E l l i p s e . There have been s e v e r a l attempts at shaping a p a t t e r n of p o i n t s , and those with t h e i r r o o t s i n c e n t r o g r a p h i c a l r e s e a r c h have proven the most s u c c e s s f u l . L e f e v e r 2 8 proposed the Standard D e v i a t i o n a l E l l i p s e which measures d i s p e r s i o n about the c e n t r e of the p o i n t p a t t e r n . A l e a s t squares t e c h n i q u e 2 9 i s adopted to determine the spread of p o i n t s about a major and minor a x i s , a l l o w i n g an e l l i p s e to be generated that bounds the p o i n t p a t t e r n . 3 0 F i g u r e 2.17 i l l u s t r a t e s both the Standard D e v i a t i o n a l E l l i p s e and the Convex H u l l mentioned e a r l i e r . M a r k 3 1 used a bounding e l l i p s e t o measure o v e r a l l shape of a p a t t e r n of mountain peaks. S e v e r a l o t h e r s have used e l l i p s e s t o d e s c r i b e shape: S i m o n s 3 2 , while o b s e r v i n g d i s t o r t i o n s of r e t a i l 2 8 D.W. L e f e v e r , "Measuring geographic c o n c e n t r a t i o n by means of the Standard D e v i a t i o n a l E l l i p s e , " T h e American  J o u r n a l of S o c i o l o g y , Vol.XXXII, No.1 (1926) pp.88-94. 2 9 S e v e r a l s t u d i e s have used h e u r i s t i c s i n the past but exact s o l u t i o n s do e x i s t . 3 0 In c o n t r a s t , the convex h u l l o n l y uses the outer p o i n t s to generate a boundary s t r u c t u r e . 3 1 D. Mark, " T o p o l o g i c a l randomness of geomorphic s u r f a c e s " , Department of Geography, Simon F r a s e r U n i v e r s i t y , Ph.d. t h e s i s (unpublished)(1977). 3 2 P.L. Simons, "Measuring the shape d i s t o r t i o n s of r e t a i l market areas", G e o g r a p h i c a l A n a l y s i s , V o l . 7 , No.4 59 STANDARD DEVIATIONAL ELLIPSE CONVEX HULL F i g u r e 2 . 1 7 6 0 market areas; Y u i l l 3 3 , updating the standard d e v i a t i o n a l e l l i p s e as a t o o l f o r d e s c r i p t i o n ; and R a i n e 3 ' , d i s c u s s i n g a h e u r i s t i c a l g o r i t h m to generate the e l l i p s e . However, one l i m i t a t i o n t o t h i s ' g l o b a l ' approach i s that i t l a c k s the a b i l i t y t o measure ' i n t e r n a l ' shape and i s not s e n s i t i v e enough to be used beyond comparing g l o b a l shapes of p o i n t p a t t e r n b o u n d a r i e s . 3 5 2.6 L i n e P a t t e r n A n a l y s i s When two p o i n t s i n a p o i n t p a t t e r n are l i n k e d by an edge, another dimension i s added and the p o i n t p a t t e r n takes on the s p a t i a l c h a r a c t e r i s t i c s of a l i n e p a t t e r n . The a n a l y s i s of such a p a t t e r n has become commonly known i n the l i t e r a t u r e as Network A n a l y s i s . Within t h i s g e n e r a l c l a s s i f i c a t i o n , work has been c o n t r i b u t e d by both p h y s i c a l and human geographers. Approaches to l i n e p a t t e r n a n a l y s i s have focussed on methodologies which expose p r o p e r t i e s of the a c t u a l l i n k s themselves, with l i t t l e a t t e n t i o n being given to the (1975) pp.331-40. 3 3 R.S. Y u i l l , "The standard d e v i a t i o n a l e l l i p s e ; an updated t o o l f o r s p a t i a l d e s c r i p t i o n " , G e o g r a f i s k a Annaler, Vol.53B, (1971) pp.28-39. 3 * J.W. Raine, "Summarizing p o i n t p a t t e r n s with the standard d e v i a t i o n a l e l l i p s e " , Area, Vol.10, No.5 (1978) pp.328-33. 3 5 J.D. Radke,"Bounding c l u s t e r s i n s p a t i a l p o i n t p a t t e r n s " , Presented at the Canadian A s s o c i a t i o n of Geographers Annual Meeting, Montreal (1980). 61 surrounding space. A s u b - c l a s s i f i c a t i o n , known as T o p o l o g i c a l A n a l y s i s 3 6 , i s a p e r f e c t example of t h i s approach. Here, p h y s i c a l geographers s t u d y i n g branching ( t r e e networks) i n streams co n c e n t r a t e on o r d e r i n g stream channels. As i n s i m i l i a r approaches i n p o i n t p a t t e r n a n a l y s i s , the observed o r d e r i n g d i s t r i b u t i o n s are compared to some bench mark, u s u a l l y an expected random d i s t r i b u t i o n of stream o r d e r s 3 7 . Human geographers a l s o adopt the t o p o l o g i c a l approach to d e s c r i b e the form of the l i n k s t r u c t u r e i n t r a n s p o r t a t i o n ( c i r c u i t ) networks. Most attempts concentrate on both the c h a r a c t e r i s t i c s of the l i n k s themselves and the t o p o l o g i c s t r u c t u r e of the p o i n t s . As s t a t e d i n the p r e v i o u s chapter, three s u b - c l a s s i f i c a t i o n s of t h i s a n a l y s i s have s u r f a c e d : nodal, a c c e s s i b i l i t y , and simple s t r u c t u r a l  a n a l y s i s . A l l of these analyses which do i n c l u d e c h a r a c t e r i s t i c s of the p o i n t s t r u c t u r e , mainly d e a l with the m a n i p u l a t i o n of p o i n t s and l i n e s t o r e v e a l some u n d e r l y i n g l i n k s t r u c t u r e 3 8 . 3 6 Haggett and Chorley, Network A n a l y s i s i n Geography (1969) p23. 3 7 R.L. Shreve, " S t a t i s t i c a l law of stream numbers," J o u r n a l of Geology, Vol.74, (1966) pp.17-37. 3 8 G.A. James, A.D. C l i f f , P. Haggett and J.K. Ord, "Some d i s c r e t e d i s t r i b u t i o n s of graphs with a p p l i c a t i o n s to r e g i o n a l t r a n s p o r t networks," G e o g r a f i s k a Annaler, Vol.52B, (1970) pp.14-21. D.C. F u r n e l l , "Methods of measuring the n o d a l i t y of p l a c e s on a t r a n s p o r t a t i o n network - an assessment based on s t u d i e s of the Uganda road system," P e r c e p t i o n and  N o d a l i t y , Department of Geography, Makerere U n i v e r s i t y 62 Approaches to a n a l y z i n g l i n e p a t t e r n s are q u i t e s i m i l a r to those that analyze p o i n t p a t t e r n s . The chronology of metric development i n l i n e a n a l y s i s l i k e p o i n t a n a l y s i s , has moved from d e n s i t y through d i s t a n c e to measure d i r e c t i o n . T h i s change of m e t r i c s u s u a l l y r e p r e s e n t s a s h i f t from the r e c o g n i t i o n of space to t h a t of shape. However, most approaches i n t r a n s p o r t a t i o n ( c i r c u i t networks) using d i r e c t i o n a l m e t r i c s , analyze the d i r e c t i o n of flows along l i n k s that are a l r e a d y f i x e d , and are not concerned with the shape of a network. Geographers working on problems i n the p h y s i c a l world use d i r e c t i o n a l m e t r i c s t o i n d i c a t e more than j u s t the flow of water along a given l i n k or stream channel. U n l i k e human l i n e networks, stream networks are governed by the law of g r a v i t y and thus the t r e e graphs which re p r e s e n t t h e i r s t r u c t u r e are ' d i r e c t e d ' . D i r e c t i o n m e t r i c s are used by p h y s i c a l geographers to measure the j u n c t i o n angles of t r i b u t a r i e s so t h a t the o r i e n t a t i o n of drainage networks can be l i n k e d with c h a r a c t e r i s t i c s about i t s b a s i n . T h i s methodology a l l o w s f o r the d e s c r i p t i o n of i n t e r n a l morphologic shape i n t r e e n e t w o r k s 3 9 . Although t h i s d i s s e r t a t i o n uses a d i f f e r e n t c o nceptual approach and t e c h n i c a l methodology, i t addresses a s i m i l a r problem of shape measurement i n c i r c u i t networks. O c c a s s i o n a l Paper, No.15 (1970) pp.26-43. 3 9 Haggett and Chorley, Network A n a l y s i s i n Geography (1969), p99. 63 2.7 Area P a t t e r n A n a l y s i s Area p a t t e r n s e x i s t when the p o i n t s i n a p a t t e r n are l i n k e d by l i n e s which a c t as b a r r i e r s between areas. These b a r r i e r s d e l i n e a t e space r e s u l t i n g i n p a t t e r n s commonly c l a s s i f i e d as c e l l u l a r networks. The approaches used to examine c e l l p a t t e r n s are q u i t e s i m i l a r to those used to recognize p o i n t and l i n e p a t t e r n s . Since the c e n t r o i d * 0 of a c e l l can be c o n s i d e r e d the d u a l * 1 of i t s b a r r i e r s , methodologies used i n p o i n t p a t t e r n r e c o g n i t i o n can be e a s i l y adapted to examine c e l l s . In a d d i t i o n , the f a c t that l i n e and c e l l p a t t e r n s are made up of s i m i l i a r elements ( p o i n t s and l i n e s ) o f t e n allows the j o i n t a p p l i c a t i o n of r e p r e s e n t a t i v e methodology. Point and l i n e p a t t e r n a n a l y s i s addresses p o i n t s and l i n e s , while c e l l p a t t e r n r e c o g n i t i o n focuses more d i r e c t l y on the measurement of area w i t h i n the c e l l . T h e r e f o r e the m e t r i c s which use d e n s i t y , d i s t a n c e and d i r e c t i o n as a medium f o r r e c o g n i t i o n must address t h i s a d d i t i o n a l element of s t r u c t u r e . The terms space and shape then take on a d d i t i o n a l meaning as they r e f e r to polygons i n t h i s *° The ' c e n t r o i d ' of a c e l l i s i t s c e n t r e of g r a v i t y . * 1 The 'dual' always bears a constant mathematical r e l a t i o n s h i p to the o r i g i n a l or p r i m a l . In t h i s case the c e n t r o i d bears a mathematical r e l t i o n s h i p to the c e l l s b a r r i e r s . 64 i n s t a n c e , r a t h e r than s t r i c t l y p o i n t s and l i n e s . Much of the r e s e a r c h i n area p a t t e r n r e c o g n i t i o n has used the Poisson and C h r i s t a l l e r i a n s u r f a c e s as bench marks f o r e m p i r i c a l r e c o g n i t i o n * 2 . The development of an approach and/or methodology to recognize s p a t i a l s t r u c t u r e i n any c l a s s of networks has t r a d i t i o n a l l y i n f l u e n c e d p a t t e r n r e c o g n i t i o n i n the other c l a s s e s . 2.8 Planar D i m e n s i o n a l i t y One of the main themes i n Geography i s the study of the d i s t r i b u t i o n of phenomena on the s u r f a c e of the e a r t h . If we were to study the e a r t h i n the ' g l o b a l ' context, we would have to d e a l with i t s ' s p h e r i c a l ' nature, and the space most a p p r o p r i a t e t o work i n would be 'Riemann' s p a c e * 3 . Most geographic s t u d i e s however, are more l o c a l i z e d than g l o b a l , and f o r s i m p l i c i t y , d e a l with a space tangent to a p a r t i c u l a r l o c a t i o n on the e a r t h ' s s u r f a c e ( f i g u r e 2.18). In t h i s space, phenomena are assumed to be embedded on a f l a t or plane s u r f a c e and space i s e u c l i d e a n . A graph * 2 G e t i s and Boots, Models of S p a t i a l Processes (1978). * 3 In -'Riemann' space, the s h o r t e s t d i s t a n c e i s not a s t r a i g h t l i n e but a curved one and t h e r e f o r e i s more a p p l i c a b l e when stu d y i n g the s p h e r i c a l e a r t h . A.W. Goodwin, G.D.Vannatta and H.P. Fawcett, Geometry: A U n i f i e d Course (Columbus: C h a r l e s E. M e r r i l l Books, Inc., 1961). 65 PLANE TANGENT TO THE EARTH'S SURFACE 66 r e p r e s e n t i n g a network i n e u c l i d e a n space would be c o n s i d e r e d a plane graph i f the i n t e r s e c t i o n of i t s l i n e s o c c u r r e d only at i t s p o i n t s . Conversely, i f l i n e s i n t e r s e c t e d at l o c a t i o n s other than those of p o i n t s , the embedded graph would be non-plane. In almost a l l s t u d i e s of stream channel networks, the r e s u l t a n t t r e e graphs are p l a n a r . However c i r c u i t graphs r e p r e s e n t i n g t r a n s p o r t a t i o n networks can be non-planar. For i n s t a n c e , a i r l i n e networks are f o r the most pa r t t h r e e - d i m e n s i o n a l , and some freeway, subway and r a i l networks are non-planar as w e l l . G e n e r a l l y however, the m a j o r i t y of ground t r a n s p o r t a t i o n networks are pl a n a r when a b s t r a c t e d to graphic form. T h i s study u n f o l d s i n e u c l i d e a n space and addresses both pl a n a r and non-planar graphs. 2.9 Summary of Chapter 2 The i n t e n t i o n of t h i s chapter was to c r e a t e a forum f o r t h i s t h e s i s . The f i e l d of Network A n a l y s i s as i t stands i n geography was b r i e f l y examined and a typology of graph t h e o r e t i c concepts commonly used i n the l i t e r a t u r e was presented. Another look at the l i t e r a t u r e from which t h i s study emerged was made by a d d r e s s i n g the approaches to a n a l y z i n g p a t t e r n morphology i n d i f f e r e n t c l a s s e s of networks. S e v e r a l a d d i t i o n s were made to the l i t e r a t u r e 67 review i n the f i r s t c hapter, of the space w i t h i n the c l a r i f i e d . F i n a l l y , framework the of d i m e n s i o n a l i t y t h i s study was Keeping w i t h i n the forum d e l i n e a t e d i n t h i s chapter, the subsequent c h a p t e r s w i l l develop an approach and methodology which attempt to add to the r e c o g n i t i o n of p a t t e r n s i n c i r c u i t networks. F i n a l l y , some e m p i r i c a l examples w i l l be examined using the techniques developed i n t h i s t h e s i s . A d i s c u s s i o n of the impact of t h i s study i n the l i t e r a t u r e w i l l conclude t h i s t h e s i s . 68 Chapter 3: THE APPROACH TO PATTERN RECOGNITION _._ I n t r o d u c t i o n The p r e v i o u s chapter o u t l i n e d a forum, e x p l o r e d typology and examined some e x i s t i n g approaches and methodologies f o r r e c o g n i z i n g morphologic s t r u c t u r e i n networks. T h i s chapter presents an a l t e r n a t e approach to p a t t e r n r e c o g n i t i o n i n c i r c u i t networks. The proposed approach has a two p a r t methodology. The f i r s t p a r t of the methodology uses a t h e o r e t i c a l p rocess t o generate an expected spectrum of graphs or bench marks, while the second phase of the methodology compares the l i n k s t r u c t u r e of an observed c i r c u i t graph to those of the t h e o r e t i c a l bench mark. The g e n e r a t i o n of t h e o r e t i c a l bench marks f o r comparing and examining e m p i r i c a l examples i s needed i n c i r c u i t network morphology. As p r e v i o u s l y mentioned, there a l r e a d y 69 e x i s t some schemes f o r d e s c r i b i n g the s p a t i a l d i s t r i b u t i o n of e m p i r i c a l p o i n t p a t t e r n s embedded i n a plane. Most of these i n v o l v e comparing e m p i r i c a l p a t t e r n s to those generated using a 'Poisson' p r o c e s s 1 . In a d d i t i o n , shape measured i n e m p i r i c a l p o i n t p a t t e r n s has been compared to t h e o r e t i c a l bench marks d e r i v e d from c e n t r a l p l a c e t h e o r y 2 . S e v e r a l t h e o r e t i c a l bench marks have a l s o been d e r i v e d f o r e v a l u a t i o n and comparison purposes, i n work by G e t i s and B o o t s 3 on the c l a s s of c e l l u l a r networks. The bench mark developed here i s new i n t h a t i t a p p l i e s d i r e c t l y to c i r c u i t networks, something that does not e x i s t i n the l i t e r a t u r e . I t i s a l s o much more comprehensive than the p r e v i o u s l y mentioned bench marks and spans a spectrum of graph s t r u c t u r e s r a t h e r than being simply a d i s c r e t e s t r u c t u r e . In t h i s study, the bench mark i s a spectrum of c i r c u i t graph s t r u c t u r e s generated u s i n g a s p e c i f i c u n d e r l y i n g t h e o r e t i c a l p r o c e s s . L i k e a l l g e n e r a t i v e processes, the one used here i n c l u d e s s e v e r a l assumptions which must be made e x p l i c i t . The process i n v o l v e s e x t r a c t i n g the f i x e d set of p o i n t s on an i s o t r o p i c plane, V(G 0)*» i n a graph 1 P.J. T a y l o r , Q u a n t i t a t i v e Methods i n Geography, Boston: Houghton M i f f l i n Company, 1977. 2 For example the Standard D e v i a t i o n a l E l l i p s e . 3 A r t h u r G e t i s and Barry N. Boots, Models of S p a t i a l  P rocesses, (Cambridge: Cambridge U n i v e r s i t y P r e s s , 1978) 4 The s u b s c r i p t ' 0 ' denotes the elements are from an observed or e m p i r i c a l graph and the s u b s c r i p t '£' r e p r e s e n t s the elements are from an expected or 70 being examined, G 0 ( V ; E ) , and g e n e r a t i n g a t h e o r e t i c a l l i n k s t r u c t u r e E(G£), f o r them. In t h i s study the e m p i r i c a l graph i s c o n s i d e r e d to be on an i s o t r o p i c plane. Since the f i x e d set of p o i n t s V(G 0) i s used, the e m p i r i c a l graph s t r u c t u r e i s being observed at one i n s t a n t , t h u s a l l p o i n t s are assumed to be synchronous. L i k e a l l t h e o r e t i c a l work, assumptions made to gain e f f i c i e n c y i n g e n e r a l i z a t i o n impose l i m i t a t i o n s to s p e c i f i c a p p l i c a t i o n . S ince e m p i r i c a l networks may develop asynchronously, as more i n f o r m a t i o n i s determined about a network's present and f u t u r e development, assumptions used i n the g e n e r a t i v e process can be t a i l o r e d to c r e a t e a bench mark f o r more s p e c i f i c a p p l i c a t i o n . 5 Since the development of the network i s assumed to be synchronous, the l i n k between a p a i r of p o i n t s i n V(G 0) i s independent of a l l other l i n k s i n E ( G 0 ) . The e v a l u a t i o n of the e m p i r i c a l l i n k s t r u c t u r e i s a l s o a l i n k - b y - l i n k e v a l u a t i o n . Each l i n k i s i n d i v i d u a l l y compared to the spectrum of t h e o r e t i c a l l y generated graphs. I t i s argued that the observed graph G 0(V;E) i s a subgraph of a completely connected graph CCG 0(V;E), with a p o i n t set V ( G 0 ) . The spectrum of t h e o r e t i c a l l y generated graphs used as a bench mark i s a l s o a subgraph of CCG 0(V;E) with a t h e o r e t i c a l l y generated graph. 5 T h i s t h e s i s i s concerned with the morphology of a network s t r u c t u r e , t h e r e f o r e the e m p i r i c a l p o i n t l o c a t i o n s serve as a u s e f u l constant i n the development of a t h e o r e t i c a l l y d e r i v e d bench mark. 71 p o i n t set V ( G 0 ) and a l i n k set E(G£), where E(G£) £ E(CCG). T h i s new l i n k set i s generated when the u n d e r l y i n g assumptions of the bench mark are imposed on the observed p o i n t s t r u c t u r e V ( G 0 ) . As a r e s u l t , a l i n k - b y - l i n k comparison between E(G„) and the spectrum of i t h e o r e t i c a l l y generated graphs w i l l a llow the d e l i n e a t i o n of each member of E ( G 0 ) ' s l o c a t i o n i n the "spectrum of graphs ranging from the CCG 0(V;E) to some rudimentary graph s t r u c t u r e , RG 0(V;E). A t h e o r e t i c a l l y generated l i n k s t r u c t u r e such as E(G£) can be c o n s i d e r e d a type of s k e l e t o n . T h i s s k e l e t o n s t r u c t u r e f i x e s a new t o p o l o g i c a l neighbourhood to the p o i n t set V ( G 0 ) , c r e a t i n g a new d i s t r i b u t i o n of l i n k s . Before the spectrum of s k e l e t o n s or graph s t r u c t u r e s i s examined i n d e t a i l , a d e s c r i p t i o n of the general nature of s k e l e t o n s i s necessary. 3.2 Skeletons We commonly r e f e r t o a s k e l e t o n as the bone s t r u c t u r e or frame around which a body i s b u i l t . More f o r m a l l y , a s k e l e t o n i s a sup p o r t i n g framework or type of n u c l e u s 6 . In the s u b - d i s c i p l i n e of s p a t i a l a n a l y s i s , there have been two 6 Webster's T h i r d New I n t e r n a t i o n a l D i c t i o n a r y , P . B . G o v e ( e d i t o r ) , ( S p r i n g f i e l d : G.&C. Merriam Co.,1971). 72 fundamental approaches t o the development of graphs r e f e r r e d t o as s k e l e t o n s . These s k e l e t o n s , l i k e those of l i v i n g organisms, r e f e r t o e i t h e r an endoskeleton ( i n n e r ) or exoskeleton ( e x t e r n a l ) . Although not always r e f e r r e d to by name, the exoskeleton has been the most common form of s k e l e t o n observed i n graph theory. Two examples mentioned e a r l i e r are the Convex H u l l and Standard D e v i a t i o n a l E l l i p s e 7 . There appear to be two c l a s s e s of endoskeletons observed i n graph theory, each c h a r a c t e r i z e d by i t s method of c o n s t r u c t i o n . One c l a s s , Blum's Medial A x i s F u n c t i o n 8 , r e p r e s e n t s the inner s k e l e t o n of a set of edges which form an outershape or boundary. Form a l l y , t h i s f u n c t i o n i s d e f i n e d as the set of couples (c, T) where c i s the ce n t r e of a maximal empty c i r c l e or d i s c and T i s the r a d i u s of th a t d i s c . These d i s c s are bounded by th r e e or more p o i n t s i n the o r i g i n a l set and, a f t e r the o r i g i n a l set i s completely segregated by d i s c s , a scheme t o j o i n a l l the newly generated d i s c c e n t r e s i s implemented. F i g u r e 3.1 i s an example of a Medial A x i s F u n c t i o n endo-skeleton. The second c l a s s of endoskeletons i s not generated by 7 I t i s i n t e r e s t i n g t o note that Alpha-shapes can be co n s i d e r e d both an endo and exo s k e l e t o n . 8 H. Blum, " B i o l o g i c a l shape and v i s u a l Science (part 1)", J o u r n a l of T h e o r e t i c a l B i o l o g y , Vol.38, No.2 (1973) pp.205-287. 73 Figure 3.1 Medial Axis Function Endo-skeleton. c l u s t e r s Figure 3.2 L i n k i n g V(G) Endo-skeleton. 74 l i n k i n g a new set of p o i n t s w i t h i n some space, such as the l i n k i n g of the set of a l l c's i n Blum's Media l Axis F u n c t i o n . Rather t h i s c l a s s i s d i s t i n g u i s h e d by an u n d e r l y i n g g e n e r a t i v e process which, given a s e t of assumptions, 9 l i n k s a l l the e x i s t i n g p o i n t s i n the graph to form a s k e l e t o n . When a pl a n a r set of p o i n t s , V(G), appears c l u s t e r e d i n a graph, i t i s sometimes important not to separate p o i n t s of the same c l u s t e r . One s o l u t i o n i s to c r e a t e an a l g o r i t h m which assumes near p o i n t s 1 0 are of the same c l u s t e r , and thus generate l i n e s , E(G), between the near p o i n t s to c r e a t e an endoskeleton of V(G) ( f i g u r e 3 . 2 ) 1 1 . Other i n s t a n c e s a r i s e when a f i n a l graph which makes some p e r c e p t u a l l y meaningful sense of a p a t t e r n of p o i n t s i s d e s i r e d . T h e r e f o r e an a l g o r i t h m with some other l i n k c r i t e r i a must be developed and a r e p r e s e n t a t i v e s k e l e t o n s t r u c t u r e g e n e r a t e d 1 2 . Although there appears to be an i n f i n i t e set of assumptions and processes which c o u l d 9 In most i n s t a n c e s the assumptions i n v o l v e l i n k i n g p o i n t s t h a t are neighbourly or assumed t o i n t e r a c t ( i e . the 'gravity-model' concept d i s c u s s e d e a r l i e r ) . 1 0 The term 'near p o i n t s ' i m p l i e s that p o i n t s c l o s e i n p r o x i m i t y to one another are of the same c l u s t e r . The a c t u a l d i s t a n c e which determines whether or not p o i n t s are from the same c l u s t e r i s deci d e d i n the development of the a l g o r i t h m . 1 1 C T . • Zahn, " G r a p h - t h e o r e t i c a l methods f o r d e t e c t i n g and d e s c r i b i n g g e s t a l t c l u s t e r s " , IEEE Trans. Computers, Vol.C-20, January (1971) pp.68-86. 1 2 B. Rosenberg and D.J. Landgridge, "A computational view of p e r c e p t i o n " , P e r c e p t i o n , V o l . 2, (1973) pp.415-424. 75 generate t h i s type of endoskeleton, t h i s t h e s i s w i l l d e a l with a spectrum of s k e l e t o n s which c o n s i d e r neighbours of p o i n t s to be measured i n e u c l i d e a n d i s t a n c e . 3.3 A Known Family of Planar Skeletons A f a m i l y of pl a n a r graphs a l r e a d y p r e s e n t i n the l i t e r a t u r e , c o n t a i n s the Minimum Spanning Tree (MST, d e f i n e d i n Chapter 2) and the Delaunay T r i a n g u l a t i o n (DT). The MST(G) of a set of p o i n t s V(G) i s the t r e e graph formed by j o i n i n g a l l the p o i n t s i n V(G) such that the sum of eu c l i d e a n l i n e l e ngths i s minimized ( f i g u r e 3.3). The DT or l o c a l l y e quiangular t r i a n g u l a t i o n of a set of p o i n t s V(G), i s a s p e c i a l case of a f a m i l y of t r i a n g u l a t i o n s 1 3 ( f i g u r e 3.4). A p o i n t set i s t r i a n g u l a t e d when s t r a i g h t l i n e segments whose end p o i n t s are i n V(G), are introduced so that as many t r i a n g l e s as p o s s i b l e are c r e a t e d w i t h i n the Convex H u l l of a set of p o i n t s without c r o s s i n g l i n e s . The DT i s the graph dual of the Voronoi Diagram (VD). A Voronoi diagram of a set of p o i n t s V(G), p a r t i t i o n s a space or plane P i n t o d i s j o i n t regions or polygons, such that each element x of a polygon P i , as s i g n e d to a p a r t i c u l a r p o i n t V^, i s c l o s e r ( i n e u c l i d e a n d i s t a n c e ) to 1 3 G e t i s and Boots, Models of S p a t i a l Processes, 1978. 76 MST(V;E) F i g u r e 3.3 Minimum S p a n n i n g T r e e o f p o i n t s e t V ( G ) . t h a t p o i n t than any other p o i n t i n V ( G ) 1 * ( f i g u r e 3.5). P i = {x| d(x, v;) < d(x, v j ) V i 9t,} (3.1) where d = e u c l i d e a n d i s t a n c e and, X = a l l elements i n P In geography Voronoi diagrams are commonly r e f e r r e d to as Thiessen p o l y g o n s 1 5 . Voronoi neighbours are two p o i n t s i n a Voronoi diagram which share a common l i n e or edge of t h e i r r e s p e c t i v e polygons. An edge i n the DT i s formed by j o i n i n g two p o i n t s i n V(G) which are Voronoi neighbours. Two other known members of the fa m i l y of p l a n a r graphs i n c l u d i n g the MST and the DT, are the R e l a t i v e  Neighbourhood G r a p h 1 6 and the G a b r i e l Graph ( G G ) 1 7 . The R e l a t i v e Neighbourhood Graph (RNG) i s a ' s u p e r g r a p h ' 1 8 of the MST and a 'subgraph' of the G a b r i e l Graph and the Delaunay T r i a n g u l a t i o n . The G a b r i e l Graph i s a l s o a 'subgraph' of the Delaunay T r i a n g u l a t i o n . 1 9 1 0 T o u s s a i n t , G.T., " P a t t e r n R e c o g n i t i o n and Geometrical Complexity", Proceedings of 5th I n t e r n a t i o n a l Conference  on P a t t e r n R e c o g n i t i o n , December 1980. 1 5 G e t i s and Boots, Models of S p a t i a l P rocesses, 1978. 1 6 G.T. T o u s s a i n t and R. Menard, "Fast a l g o r i t h m s f o r computing the p l a n a r r e l a t i v e neighbourhood graph", Proceedings 5th Symposium on Operations Research, Koln, August, (1980). 1 7 D.W.- Matula and R.R. S o k a l , " P r o p e r t i e s of G a b r i e l graphs r e l e v a n t to geographic v a r i a t i o n r e s e a r c h and the c l u s t e r i n g of p o i n t s i n the p l a n e " . Geographical  A n a l y s i s , V o l . 12, No.3 ( J u l y 1980) pp.205-222. 1 8 I f G,(V;E) i s a subgraph of G 2(V;E) then G 2(V;E) i s a supergraph of G,(V;E). 78 Figure 3 .5 Voronoi Diagram of. point set V(G). 79 D e f i n i t i o n of the G a b r i e l Graph Two p o i n t s V\ and V j , from some set of plana r p o i n t s V(G) = {V, ,V2 ,V3 , v ; , V j , . . . ,VTJ} , are G a b r i e l neighbours i f d 2 ( v ; , v ;> < d 2 ( v ; , v « ) + d 2 ( v j , v * ) (3.2) V K=1121•••ri/ and K * \ , \ where d ( V j , V j ) denotes e u c l i d e a n d i s t a n c e from V, to V j . Between every V\ and Vj i n V(G) that are G a b r i e l neighbours, a l i n k e\\ i s c o n s t r u c t e d . Thus the set of a l l ei j generated i s the G a b r i e l graph GG(V;E) of the p o i n t set V(G). G e o m e t r i c a l l y , e\\ i s a G a b r i e l graph l i n k when i t s end p o i n t s , V\ and Vj are end p o i n t s of the diameter of an empty d i s c whose r a d i u s T i s : T = d ( v j , V j ) (3.3) 2.0 T h i s d i s c d e f i n e s the mutual neighbourhood or ' c i r c l e of i n f l u e n c e ' of Vj and V j 2 0 ( f i g u r e 3 .6) . When a l l 'mutual Graphs i n t h i s f a m i l y are d i s c r e t e t r a n s f o r m a t i o n s of the DT. To u s s a i n t , P a t t e r n r e c o g n i t i o n and g e o m e t r i c a l complexity, 1980. 80 Two p o i n t s V\ and V\ a r e G a b r i e l n e i g h b o u r s i f , a nd o n l y i f , t h e c i r c l e b e t w e e n them, w i t h d i a m e t e r 2^ i s empty. F i g u r e 3 .6 G a b r i e l G r a p h C o n s t r u c t i o n . GG(V;E) F i g u r e 3 .7 G a b r i e l G r a p h o f p o i n t s e t V ( G ) . 81 neighbourhoods' between a l l p a i r s of p o i n t s have been determined, the r e s u l t a n t graph i s the G a b r i e l graph ( f i g u r e 3 .7) . Where 'mutual neighbourhoods' are generated using the G a b r i e l graph, the R e l a t i v e Neighbourhood graph i s based on the n o t i o n of ' r e l a t i v e l y c l o s e ' n e i g h b o u r s 2 1 i n a g e o g r a p h i c a l c o n t e x t . The R e l a t i v e Neighbourhood graph i s seen as "an improvement to the MST i n s o l v i n g the problem of e x t r a c t i n g the p e r c e p t u a l l y r e l e v a n t s t r u c t u r e from a dot p a t t e r n " 2 2 . D e f i n i t i o n of the R e l a t i v e Neighbourhood Graph Using the same planar p o i n t set V(G) above, two p o i n t s are ' r e l a t i v e l y c l o s e ' i f , d ( v ; , v j ) ^ M A x{d ( v ; , v « ),d ( v j , V K ) } (3.4) V K=,, 2r...i1 where K * \ , \ 2 3 Between every v\ and V] i n V(G) that are ' R e l a t i v e neighbours', a l i n k e j j i s c o n s t r u c t e d . Thus the set of 2 1 P .M. Lankford, " R e g i o n a l i z a t i o n : theory and a l t e r n a t i v e a l g o r i t h m s " , G eographical A n a l y s i s , V o l . 1, No. 2, (1969> pp.196-212. 2 2 G.T. T o u s s a i n t , "The r e l a t i v e neighbourhood graph of a f i n i t e p l a n a r s e t " . P a t t e r n R e c o g n i t i o n , V o l . 12, No. 4 (1980) p267. 2 3 Lankford, R e g i o n a l i z a t i o n theory and a l t e r n a t i v e a l g o r i t h m s , 1969. 82 a l l e j j generated i s the R e l a t i v e Neighbourhood graph RNG(V;E) of p o i n t set V(G). G e o m e t r i c a l l y , e j j i s a R e l a t i v e Neighbourhood graph l i n k when i t s end p o i n t s , v j and Vj l i e on the a r c s d e f i n i n g t h e i r 'lune' which i s empty. The 'lune' of two p o i n t s Vj and Vj i s the i n t e r i o r of the re g i o n formed by the i n t e r s e c t i o n of two pl a n a r c i r c l e s of r a d i u s d j j , f o r the RNG, one i s centered at Vj and the other at Vj ( f i g u r e 3.8). When a l l the ' r e l a t i v e neighbours' of a l l the p o i n t s in the graph V(G) have been determined, the r e s u l t a n t graph i s the RNG ( f i g u r e 3.9). 3.4 Proposed Methodology i ) Development of the Bench Mark The spectrum of sk e l e t o n s proposed as the bench mark f o r comparing e m p i r i c a l networks has s i m i l a r i t i e s t o the f a m i l y of d i s c r e t e t r a n s f o r m a t i o n graphs c o n t a i n i n g the MST, RNG, GG and the DT. Both the G a b r i e l graph and the R e l a t i v e Neighbourhood graph are members of t h i s spectrum but the Delaunay T r i a n g l e and the Minimum Spanning Tree are not, except i n degenerate cases. The GG and RNG are d e f i n e d i n terms of neighbourhoods. 83 The 'lune' of V. and V . i s the region 1 J between v . i i T 1 v . T 1 two a r c s , not i n c l u d i n g the a r c s . . Figure 3.8 R e l a t i v e Neighbourhood Graph Construction. RNG(V;E) Figure 3.9 R e l a t i v e Neighbourhood Graph of point set V(G). 84 T h i s can a l s o be used to generate each member of the new spectrum of s k e l e t o n s . The RNG 'lune' s e a r c h i n g method i s m o d i f i e d t o generate a continuous t r a n s f o r m a t i o n and thus range of search 'lunes', each 'lune' corresponding to a member of the spectrum. L i k e the GG and the RNG, other bench mark members are generated when the search 'lunes', between a l l p a i r s of p o i n t s i n V ( G 0 ) r are r e p l a c e d with l i n k s when they are v o i d of other members of V ( G 0 ) . The c o l l e c t i o n of these l i n k s forms the set of l i n k s E£(G) i n the bench mark member s k e l e t o n . Each s k e l e t o n i s c h a r a c t e r i z e d by the search space used to formulate i t s l i n k s t r u c t u r e . The s k e l e t o n s i n the bench mark form a spectrum which ranges from the CCG to some rudimentary graph RG. Since each s k e l e t o n corresponds to a p a r t i c u l a r search space, the search spaces a l s o form a continuous range. For two p o i n t s Vj and Vj from a network understudy, the search spaces can range from an area d e f i n e d by a l i n e between two p o i n t s ( t h i s area c o r r e s p o n d i n g to the CCG s k e l e t o n ) , to an area which r e p r e s e n t s a c o r r i d o r between the two p o i n t s t h a t s t r e t c h e s to i n f i n i t y and i s p e r p e n d i c u l a r to the CCG search space ( t h i s area corresponds to the RG s k e l e t o n and i s d e s c r i b e d i n d e t a i l l a t e r ) . The r a d i u s R of each p l a n a r c i r c l e t h a t c o n s t r u c t s the lune between two p o i n t s , h e l p s determine the lune's shape 85 and s i z e . The r a d i u s of the p l a n a r c i r c l e s t h a t make up the lune between two RNG neighbours i s twice t h a t of the r a d i u s of the plan a r c i r c l e that makes up the c i r c l e of i n f l u e n c e between two G a b r i e l neighbours. T h e r e f o r e : • i f R = r f o r the GG •then R = 2T f o r the RNG (3.5) •where T = r a d i u s of GG ' d i s c ' •and R = r a d i u s of RNG 'lune' A m u l t i p l e of T w i l l a l t e r the lune between two neighbours and can serve as a value which generates and c h a r a c t e r i z e s each s k e l e t o n i n the spectrum composing the bench mark. T h i s value i s denoted 0. When 0 = 1.0, the GG of a p o i n t set V(G) w i l l be c o n s t r u c t e d . The RNG i s generated when 0 = 2.0. Thus: R = flfd(v; ,Vj )1 f o r 0£ 1.0 (3.6) L 2.0 J Besides the r a d i u s , the c e n t r e p o i n t s of the plan a r c i r c l e s are a l s o needed i n order to complete the ge n e r a t i o n of l u n e s . By d e f i n i t i o n , and Vj must always l i e on the a r c s d e f i n i n g t h e i r lune ( f i g u r e 3.8). As the value of beta i s v a r i e d to generate new member s k e l e t o n s of the bench mark, the r a d i i of the p l a n a r c i r c l e s d e f i n i n g the lune's a r c s are a l t e r e d . As the r a d i u s of the a r c s p a s s i n g through the p o i n t s changes, the c e n t r e s of the plan a r 86 c i r c l e s d e f i n i n g the a r c s must a l s o change. For 0 ^ 1 , the c e n t r e s of the a r c s or c i r c l e s are l o c a t e d a l o n g a s t r a i g h t l i n e which passes through and extends on e i t h e r s i d e of the two neighbours being examined, Vj and V j . T h i s l i n e i s d e f i n e d as: y j = m x j + b (3.7) where b = y i n t e r c e p t and m = slope of the l i n e (see f i g u r e 3.10). The c e n t r e f o r the arc l y i n g on Vj i s denoted Cj and i s d e f i n e d : C. = i (X..Y.) X. > X 1 c Y > Y Y = mX + b and i c X. > X 1 c Y. < Y 1 c i f m > 0 i f m < 0 ( 3 . 8 ) where X = c X. + X. Y.+ Y. Y.- Y. - i Y = — i i-t and m = — i i . 2 . 0 X.- X. i J 2 . 0 87 J V. V Si v . c. 1 [y = mx + by where distance d(V ,V.) = T, c J and d(Vj,Cj) = R Figure 3.10 Construction l i n e f o r the centres of the 'lune' a r c s , [where /? > 1 ] 88 The c e n t r e f o r the a r c l y i n g on Vj i s denoted Cj and i s d e f i n e d : X. < X c i f m > 0 C. = (X.,Y.) Y = mX + b and Y. < Y J C J ( 3 . 9 ) X. <X 1 Y. > Y i f m < 0 c with d(c;,v;> = pt = d(c;,v;) For the two known members of the spectrum of s k e l e t o n s ( f i g u r e 3.11) the f o l l o w i n g i s t r u e : • f o r the GG, R = T and the c e n t r e of the c i r c l e of i n f l u e n c e i s , C\ = C\ = (Xc,Yc) • f o r the RNG, R = 2T and the c e n t r e of the a r c s a r e , c; = v j and c; = v; For the rudimentary graph RG, the search space i s c h a r a c t e r i z e d by two a r c s with a c u r v a t u r e approaching 0 and t h e r e f o r e the two a r c s forming the 'lune' must approach s t r a i g h t l i n e s . In order f o r these a r c s to approach s t r a i g h t l i n e s , the r a d i i of the pl a n a r c i r c l e s d e f i n i n g them must be R = <*> I t i s impossible t o generate a 'lune' between two p o i n t s 89 where distance d(V ,V.) = T , and d (V . C .) = R /? = — C "| T Figure 3.11 'Lune' Construction for /? > 1. 90 Vj and Vj with an area s m a l l e r than the c i r c l e which generates the GG (when 0 = 1.0), i f the two a r c s forming the 'lune' are c e n t e r e d on the l i n e d e f i n e d by yj = mxj+b. T h e r e f o r e , a technique which employs both Vj and V j , and d i v i d e s the remaining range of search space w i t h i n the GG's c i r c l e search space t o generate the remaining s k e l e t o n s i n the spectrum composing the bench mark (from the GG to the CCG) i s developed. 'Lunes' can be c o n s t r u c t e d which form a continuous range of search spaces from a l i n e (the CCG's search space) to a c i r c l e (the search space of the GG) and employing both Vj and Vj i n t h e i r c o n s t r u c t i o n . These 'lunes' however, have to be r o t a t e d 90° from the 'lunes' which form the continuous search spaces which generate the s k e l e t o n spectrum from the RG to the GG. As p r e v i o u s l y s t a t e d ; f o r the RG, R = » and the a r c s d e f i n i n g the 'lune' of the RG approach s t r a i g h t l i n e s , one pa s s i n g through Vj and the other through V j . I f R = 0 0 f o r a r c s c o n s t r u c t i n g 'lunes' when the lunes are r o t a t e d 90°, the r e s u l t a n t a r c s as befo r e approach s t r a i g h t c u r v e s . Since Vj and Vj have t o l i e on the edge of the lune c o n s t r u c t i n g t h e i r search space, f o r the ' r o t a t e d lunes' when R = <*> , the search space i s a s t r a i g h t curve which l i e s between Vj and Vj and serves to generate the CCG. For the ' r o t a t e d lunes', the search spaces " can be made continuous by v a r y i n g the value of R from R = 1.0, f o r a c i r c l e ( corresponding t o the GG) 91 to a l i n e where R = °° (corresponding t o the CCG). When 0 £ 1.0, R ranges from T to °° and the r e s u l t a n t s k e l e t o n s span from the GG to the RG. S i m i l a r l y , when the search 'lunes' are r o t a t e d 90°, R ranges from T to » and the r e s u l t a n t s k e l e t o n s span from the GG to the CCG. To c o n t i n u o u s l y represent the spectrum of s k e l e t o n s composing the bench mark, when the search 'lunes' are r o t a t e d , the value of 0 i s represented as 0 = ''VR. Then (3.6) becomes: R = 1-°/0 r d ( v ; , v ; ) l (3.10) L 2.0 J f o r 0 . 0 * 0 * 1 . 0 Theref o r e the value of 0 ranges from ' • ° / 0 0 to 1.0 to 0 0 ( t a b l e 3.1) When 0 l i e s between 0 and 1, the c e n t r e s of the a r c s that d e l i n e a t e the search space of the ' r o t a t e d lune' occur on a new l i n e which i s p e r p e n d i c u l a r to the l i n e v e c t o r or l i n k e j j , with end p o i n t s Vj and V j . T h i s new l i n e ( f i g u r e 3.12) i s d e f i n e d as: y = m'x + b' (3.11) Since v j and Vj must always l i e on the a r c s d e f i n i n g t h e i r lune, Vj and Vj become the i n t e r s e c t i o n p o i n t s of t h i s new s e r i e s of r o t a t e d lunes ( f i g u r e 3.13). Again, as 0 v a r i e s , the r a d i u s of the a r c s v a r i e s and so must the c e n t r e s . T h e r e f o r e the c e n t r e s of the new a r c s are 92 Table 3.1 BENCH MARK PROPERTIES Value of 0 Search space Value of R Skeleton 1 oo 1 lune oo r | RG | 1 2.0 | lune 2r | RNG | 1 1.0 | lune r | GG | 1 -j—i.o | r o t a t e d lune r | GG | I — =0.0 | oo r o t a t e d lune OO •£ 1 CCG | 93 ^ [ y = m'x+b' ] V. V 1 c 90 \ J [y= mx+b P C I J ' where distance \ d(V jV.) = T , c' 1 5 and d(V.,C!) = R l l Figure.3.12 Rotated Construction l i n e f o r the centres of the 'lune' a r c s . [where 0 < /3<1 ] 94 .[y= m'x+b' ] C! 1 since the search space i s r o t a t e d , (3 ' s value i s considered R ' • i i where distance d(V ,V.) c 1 1 0.5 0,33 0.83 0 r , and d{V±iCL) = R Figure 3.13 'Lune' Construction f o r 0< /? <1 95 def i n e d : C = i (X^Y.) X. > X i c Y. > Y Y = m' X + b' and 1 c-c 0 X. > X 1 c Y. < Y 1 c i f m' > 0 i f m' < 0 ( 3 . 1 2 ) and C! = j (X. ,Y.) J J m'X + b' c and X. < X J c Y . < Y J c. X. < X J = Y. > Y J c i f m' > 0 i f m1 < 0 ( 3 . 1 3 ) with d(C;,v;> = ( 1 . ° / 0 ) r = d(C^,Vj) The Bench Mark and i t s P r o p e r t i e s When 0 £ 1, two p o i n t s Vj and Vj are G0(V;E) neighbours i f , 0r <: MAX{d(Cj,V K),d(Cj,V K)} V K= 1 f 2,...,Tj,and * * j , j (3.14) When 0 ranges from 0 to I , two p o i n t s Vj and Vj are G0(V;E) neighbours i f , (V/3)r^MAX{d(c; fVfc) rd(c; fVfc)}V K= , , 2 ,... , r?,and K * j , j (3.15) 96 The new graph and member of the bench mark generated i n t h i s t h e s i s i s o b t a i n e d by c o n s t r u c t i n g an edge or l i n k between Vj and Vj f o r a l l j , j = \ , 2,...,n; j * j , i f Vj and Vj are neighbours. G e o m e t r i c a l l y , Vj and Vj are G0(V;E) neighbours i f t h e i r lune of i n f l u e n c e does not c o n t a i n any other p o i n t s of V(G). As a r e s u l t of the process used to c o n s t r u c t the bench mark of s k e l e t o n s , the completely connected graph (CCG) h o l d s the p o s i t i o n at the upper bound of the spectrum and and some rudimentary s t r u c t u r e (RG), holds the p o s i t i o n at the lower end of the spectrum. Therefore the former d i s c r e t e f a m i l y , MST c RNG c GG C DT i s r e p l a c e d by a spectrum RG c RNG C GG C CCG. P r o p e r t i e s of the Bench Mark The t h e o r e t i c a l bench mark used i n t h i s t h e s i s i s the spectrum of graphs which i s generated when the u n d e r l y i n g assumptions, d i s c u s s e d i n the p r e v i o u s s e c t i o n , are a p p l i e d t o an observed p o i n t s e t , V ( G 0 ) . In t h i s i n s t a n c e , an expected l i n k s t r u c t u r e E(G£), i s generated which forms an endoskeleton of the observed p l a n a r c i r c u i t network's p o i n t s t r u c t u r e . The r e s u l t a n t graph, G£(V;E) i s expected i f on 97 each p a i r of neighbours Vj and Vj t h e i r lune, generated with a constant 0 v a l u e , i s empty. If a p l a n a r graph G 0(V;E) e x i s t s with the c o o r d i n a t e s of V(G 0) being X{xj} and Y{y,,y 2,...,yj,... , y f } then G 0(V;E) = RG(V;E) = RNG(V;E) = GG(V;E) = CCG(V;E) ( f i g u r e 3.14). However, t h i s i s a s p e c i a l case and most p o i n t p a t t e r n s r e v e a l q u i t e d i f f e r e n t l i n k s t r u c t u r e s . For example, given a set of p o i n t s V ( G 0 ) , that are generated using a Poisson process, i t can be i l l u s t r a t e d t h a t graph members from the bench mark of graphs d i f f e r c o n s i d e r a b l y . From f i g u r e 3.15 i t can be seen t h a t : RG(V;E) C RNG(V;E) C GG(V;E) C CCG(V;E). The MST, d e f i n e d i n Chapter 2, i s formed when the t o t a l e u c l i d e a n d i s t a n c e between a l l p o i n t s i s minimized f o r a spanning t r e e graph of some p o i n t set V(G). In the rudimentary graph (RG) two p o i n t s , Vj and V j , are l i n k e d i f and only i f no other p o i n t s l i e i n a ' c o r r i d o r ' which i s l o c a t e d between them. Thus a l i n k i n the rudimentary graph spans the minimum e u c l i d e a n d i s t a n c e p o s s i b l e to l i n k one of the two p o i n t s , Vj or Vj to the r e s t of the graph when ge n e r a t i n g the MST. T h e r e f o r e , the RG C MST. One of the most d i f f i c u l t problems that face s p a t i a l a n a l y s t s , and f o r t h a t matter many other r e s e a r c h e r s , i s the problem of s c a l e dependence. O f t e n , while generating 98 MST = RNG = GG = DT Figure 3.14 Degenerative Graph. 9 9 100 s t r u c t u r e s used f o r comparative purposes or a p p l y i n g d e s c r i p t i v e techniques i n p a t t e r n r e c o g n i t i o n , s c a l e i s i n f l u e n t i a l and can c r e a t e severe l i m i t a t i o n s . The t h e o r e t i c a l g e n e r a t i v e process developed i n t h i s t h e s i s to c o n s t r u c t the bench mark, possesses s t r u c t u r a l i n v a r i a n c e at v a r y i n g s c a l e s . Since the 'lune' search space i s a f u n c t i o n of the d i s t a n c e between the two p o i n t s being observed, as the s c a l e changes so does the d i s t a n c e and thus the s i z e of the search space. T h e r e f o r e a given p o i n t set with d e n s i t y X [V(GX)], generates a l i n k s t r u c t u r e E(GX) which i s congruent to a l i n k s t r u c t u r e E(GX') formed from a p o i n t set V(GX'). F i g u r e 3.16 i l l u s t r a t e s t h i s . One of the most obvious advantages of such a property i s the u n i v e r s a l a p p l i c a b i l i t y of the methodology developed f o r comparison of c i r c u i t networks of v a r y i n g s c a l e s . Since 0 = 1.0 generates the GG which i s a subgraph of the p l a n a r DT, i t i s easy to prove t h a t s k e l e t o n s generated i n the bench mark spectrum with v a l u e s of 0 £ 1.0 are p l a n a r . I t i s p o s s i b l e however, f o r v a l u e s of 0 that are s l i g h t l y l e s s than 1.0, to generate non-planar l i n k s i n a s k e l e t o n . T h i s property i s a f u n c t i o n of the 'lune' search space technique employed to generate the spectrum and i s i l l u s t r a t e d i n f i g u r e 3.17. 2 9 In some of the e m p i r i c a l p a t t e r n s s t u d i e d to date, 0 values f o r s p e c i f i c l i n k s i n the DT of a p o i n t set were as low as 0.00020. 101 0 = 2 \ = 0.046 • • • • • • • • • • • • V(G X) RNGA(V;E) 0 = 2 x' = 0.062 • • • • A \ • • • • • • • • V(GX<) RNGAKV;E) Figure 3.16 S t r u c t u r a l Invariance of the Bench Mark at varying s c a l e s , [where \ =• den s i t y ] 102 Figure 3.17 Forming a non-planar l i n k [ (3 ^  1]. 103 In Chapter 1, d i s c u s s i n g methods of i n t e r n a l shape c h a r a c t e r i z a t i o n , r e s e a r c h was mentioned which generated and e x p l o r e d a - s h a p e s . 2 5 The present d i s s e r t a t i o n , although i t i s concerned with i n t e r n a l s t r u c t u r a l c h a r a c t e r i z a t i o n , f o l l o w s the re s e a r c h on a-shapes and possesses some p a r a l l e l p r o p e r t i e s . The n o t i o n of the a-shape of a f i n i t e set of p o i n t s , l e t us say V(G), f o r a r b i t r a r y r e a l a, can be p a r a l l e l e d with the n o t i o n of the 'endo' or '0'-skeleton of a f i n i t e set of p o i n t s f o r a r b i t r a r y r e a l 0. In both i n s t a n c e s the v e r t i c e s i n V(G), which are embedded i n a plane, p l a y a key r o l e i n the genera t i o n of the l i n k s t r u c t u r e that d e f i n e s the a-shape or 0-skeleton. These v e r t i c e s , i n the case of a-shapes, become a-neighbours, which are used t o generate the a-shape of set V(G), when an a - h u l l i s generated f o r V(G). The a - h u l l i s d e f i n e d as the i n t e r s e c t i o n of a l l c l o s e d complements of ' d i s c s ' with r a d i i 1/a (where, - co 0 0 ) that c o n t a i n a l l the p o i n t s of V(G). These ' d i s c s ' generate search spaces which are c o n c e p t u a l l y s i m i l a r t o the 'lune' search spaces f o r the /^-skeletons. P o i n t s Vj and Vj are a-neighbours i f they l i e on the same ' d i s c ' a r c used i n c o n s t r u c t i n g the a - h u l l . 2 6 Appendix A 2 5 H. Edelsbrunner, D . G . K i r k p a t r i c k and R . S e i d e l , "On the shape of a set of p o i n t s i n the plane," IEEE T r a n s a c t i o n s  on Information Theory, ( f o r t h coming). 2 6 Edelsbrunner et a l , On the shape of a set of p o i n t s i n the plane, ( f o r t h coming). 104 c o n t a i n s i l l u s t r a t i o n s of a-shapes as w e l l as 0-skeletons of a p o i n t set V(G). In the present r e s e a r c h , the 0-skeletons make up a spectrum of sk e l e t o n s which i s generated by v a r y i n g the value of 0 and thus the 'lune' search space. S i m i l a r l y , the ' d i s c ' search space can be a l t e r e d by changing the value of a and a spectrum of a - h u l l s ensues. A l a r g e value of a tends t o produce "a rat h e r crude shape of the p o i n t s " and s m a l l e r v a l u e s of a " r e v e a l more d e t a i l " 2 7 , while an a of - - generates a p o i n t p a t t e r n . S i m i l a r l y , s m a l l 0 v a l u e s y i e l d r a t h e r complex s k e l e t o n s with much d e t a i l (the CCG an extreme case when 0=0.0) and l a r g e 0 v a l u e s generate r a t h e r crude s k e l e t o n s that are g e n e r a l l y d i s c o n n e c t e d graphs (such as the RG when 0= <*> ). U n l i k e the a-shapes, there i s only a p o s s i b i l i t y of a p o i n t p a t t e r n o c c u r r i n g i n 0-skeletons and then only when 0 i s very l a r g e . F i n a l l y , i t i s w e l l known by now t h a t ; MST Q RNG c GG c DT. 2 8 In t h i s t h e s i s i t i s shown t h a t , RG £ MST and i t i s t r i v i a l t h a t , DT c CCG. In the gene r a l case the GG (where 0=1.0) and the RNG (where 0=2.0) are members of the spectrum of 0-skeletons but the MST and the DT are not (except i n degenerate c a s e s ) . I t i s now known that the 2 7 Edelsbrunner et a l , On the shape of a set of p o i n t s i n the plane, ( f o r t h coming) , p l 1 . 2 8 T o u s s a i n t , P a t t e r n r e c o g n i t i o n and g e o m e t r i c a l complexity, 1980. 105 a-shape [of a p o i n t set V(G)] c DT but t h a t i n the gen e r a l case; the DT, GG, RNG, and the MST are not members of the f a m i l y of a - s h a p e s . 2 9 I t i s t r i v i a l that the a-shape [of a p o i n t set V(G)] c CCG but t h a t both the RG and the CCG are not members of the f a m i l y of a-shapes, except i n degenerate cases. i i ) R e c o g n i t i o n Scheme of the E m p i r i c a l Link S t r u c t u r e The second and f i n a l phase of the methodology i n v o l v e s the comparison of the e m p i r i c a l l i n k s t r u c t u r e E(G 0) to a s e r i e s of t h e o r e t i c a l l y generated graphs from the spectrum of s k e l e t o n s introduced i n the p r e v i o u s phase. S p e c i f i c a l l y , a l i n k - b y - l i n k examination i s undertaken ob s e r v i n g each element of E ( G 0 ) , determining i n which s k e l e t o n G0(V;E) of the bench mark i t would f i r s t appear, a s s i g n i n g the corresponding 0 v a l u e to i t . A l l G 0(V;E) are subgraphs of CCG 0(V;E). Ther e f o r e a s s i g n i n g 0 v a l u e s t o a l l elements of E ( G 0 ) all o w s t h e i r p l a c e i n the s k e l e t o n spectrum to be l o c a t e d a c c u r a t e l y . The 0 value behaves l i k e a p r o b a b i l i t y and i s u s e f u l i n the e v a l u a t i o n of each l i n k i n E ( G 0 ) . I f a l i n k i s a s s i g n e d the 0 value which approaches » i t has a h i g h l i k e l i h o o d 2 9 Edelsbrunner et a l , On the shape of a s e t of p o i n t s i n the plane, ( f o r t h coming). 106 of e x i s t i n g as i t corresponds c l o s e l y to the RG(V;E) end of the spectrum. On the other hand a value of 0 which approaches 0 would mean a l i n k had a very low l i k e l i h o o d of o c c u r r i n g as i t corresponds to a l i n k found only i n the CCG(V;E) end of the spectrum. The graphic r e s u l t i s a mosaic of valued l i n k s which a l l o w s the r e c o g n i t i o n of l i n k p a t t e r n w i t h i n a now known spectrum of s k e l e t o n s with a t h e o r e t i c a l base ( f i g u r e 3.18). L i n k s that do not e x i s t but that make up the complement of those l i n k s t h a t are a s s o c i a t e d with h i g h 0 v a l u e s , are examined as w e l l . The p a r a l l e l with the g r a v i t y model concept exp l o r e d e a r l i e r i n t h i s t h e s i s d i r e c t s c o n s i d e r a t i o n that these n o n - e x i s t i n g l i n k s are seen as l i n k s t h a t have a high l i k e l i h o o d of o c c u r r i n g yet they d i d not. Examination of these n o n - e x i s t i n g l i n k s should prove v a l u a b l e i n e m p i r i c a l r e s e a r c h as p a t t e r n s can be d e t e c t e d which not only s t i m u l a t e more i n t e l l i g e n t q u e s t i o n s to be asked concerning the network's development, they a l s o may a i d i n the f o r m u l a t i o n of b e t t e r hypotheses concerning the e m p i r i c a l network's g e n e r a t i o n . Steps of the A l g o r i t h m The f o l l o w i n g a l g o r i t h m embodies the l i n k - b y - l i n k 107 Figure 3.18 Mosaic of (3 value l i n k s i n an observed c i r c u i t graph. 108 r e c o g n i t i o n scheme: For each l i n k e j j i n E(G 0) connecting p o i n t s Vj and perform the f o l l o w i n g : STEP 1 By d e f i n i t i o n G 0(V;E) i s a subgraph of CCG(V;E) with E ( G 0) Q E(CCG) and V(G 0) = V(CCG). F u r t h e r d e f i n i t i o n of the bench mark d e s c r i b e d i n Phase i ) of the methodology r e v e a l s V(RG) = V(G 0) V(CCG) and E(RG) c E(G 0) Q E(CCG). T h e r e f o r e the f i r s t s tep of the a l g o r i t h m i n v o l v e s e x t r a c t i n g from G 0(V;E) the set V(G 0) of 17 p l a n a r p o i n t s : V(G 0) - {V, ,V2 , ... ,Vi , V j , . . . , V T ? } ( f i g u r e 3.19). STEP 2 Since the RG(V;E) i s the lower l i m i t of the bench mark, any p o i n t s from the V(G 0) that are not i n e j j ' s search space f o r o b t a i n i n g the RG(V;E) can be e l i m i n a t e d . For the RG(V;E), e j j ' s search space i s a ' c o r r i d o r ' of a l l the space that l i e s p e r p e n d i c u l a r t o a s t r a i g h t l i n e c o n s t r u c t e d from Vj to Vj ( f i g u r e 3.20). T h i s ' c o r r i d o r ' i s bounded by two p a r a l l e l l i n e s , through p o i n t Vj and through V j , p e r p e n d i c u l a r t o ej j . i ) The equation of a l i n e p e r p e n d i c u l a r t o e,, and on p o i n t Vj i s : Cj = -(Axj + Byj) where A = x j - x j (3.16) and B = y j - y j i i ) The equation of a l i n e p e r p e n d i c u l a r to e j j and on p o i n t Vj i s : 109 110 Figure 3.20 Co r r i d o r search space f o r V. and V.. \ # \ V J [C.=-(Axi+By. ) ] X V \ 1 A. • • _[C.=-<Ax j +Ey.)] Figure 3.21 V(COR) with a l l other points omitted. I l l Cj = -(Axj + ByJ) (3.17) P o i n t s from the set V ( G 0 ) , such as V K , are i n c l u d e d i n e j j ' s search ' c o r r i d o r ' , forming a new p o i n t set V ( C O R ) i f : where K*,,2,•••fm, and K ± j , j and i f Cj < C K < Cj when Cj < Cj or Cj < C K < Cj when Cj < Cj Thus: V(COR) = { V,, V 2, V j , V j , . . . , Vm }. A l l other p o i n t s from set V(G 0) are e l i m i n a t e d at t h i s stage ( f i g u r e 3.21). 'Lunes' form the search space f o r the c o n s t r u c t i o n of the endoskeletons that comprise the bench mark. At one end of the spectrum, a lune formed by two a r c s with r a d i u s °° and whose c e n t r e s l i e on a lune p a s s i n g through Vj and V j , make up the ' c o r r i d o r ' search space of the RG(V;E). By d e f i n i t i o n , the lune c o n s t r u c t i o n method changes when the search space becomes a c i r c l e . The search space of the GG(V;E) whose ce n t r e i s : from (3.8) Vc(Xc,Yc) = VcfXj+Xj , Yj+Yj] (3.19) and from (3.3) T = / ( x j - x c ) 2 + ( y j - y c ) 2 (3.20) As a r e s u l t , the p o i n t set V(COR) can be d i v i d e d i n t o two c l a s s e s . For a l l p o i n t s i n V(COR), measure the d i s t a n c e d« from Vt to V K , where K * ,i2 r • • ' > m and K ^ i , j • C K = - ( A X K + ByK) (3.18) STEP 3 (see f i g u r e 3.22) 112 Figure 3.22 D i v i s i o n of V(COR) search space. search //X space ///, d(V k,V c) < r \ V/F \ V/// c x // • Figure 3.23 Search space when /J < 1. Figure 3.24 Search space when 0 >1. 113 6K = / ( X C - X K ) 2 + ( V C - V K ) 2 (3.21 ) u n t i l any 6K < r, then proceed to STEP 4a ( f i g u r e 3.23). I f no d* < r, then proceed t o STEP 4b ( f i g u r e 3.24). STEP 4a F i n d the c e n t r e s of the a r c s c o n s t r u c t i n g the l a r g e s t empty ' r o t a t e d lune', where V j , Vj and V K a l l l i e on an a r c of the 'lune', and where i f 21 • • • »m and «*j,j ( f i g u r e 3.25). In accomplishing t h i s we know from (3.12) and (3.13) that C, and Cj l i e on a l i n e d e f i n e d as: yc = m'xc + b' (3.22) Since m' i s p e r p e n d i c u l a r to m i n (3.7), m ' = - i . o / m (3.23) If V j , Vj and V K a l l l i e on an arc of the r o t a t e d lune, then the l a r g e r d i s t a n c e of e i t h e r d(C^, V K ) or d ( C j ' , V K ) ensures that r e s p e c t i v e l y Cj or Cj l i e s on a l i n e which i s a p e r p e n d i c u l a r b i s e c t o r of c h o r d ( V j , V K ) 3 0 ( f i g u r e 3.26). The slope of the c h o r d ( V j , V K ) i s : ( Y K - Y J ) m; = (3.24) ( X K - X J ) T h e r e f o r e the p e r p e n d i c u l a r b i s e c t o r i s d e f i n e d by the equation: Ya = mjXa + b'2 (3.25) where m'2 = - ' • % ) , Xa = ( X J + X K ) , Ya = ( Y ; + Y K ) . 2.0 2.0 Thus the c o o r d i n a t e s of e i t h e r C, or C j ' a r e : (b'a - b') . Xca = (m' - mj) (3.26) Yea = b'2 + mjXca A 'chord' i s a l i n e j o i n i n g any two p o i n t s on the circumference of a c i r c l e . In t h i s i n s t a n c e i t i s the l i n e j o i n i n g Vj and V j . 114 [y = m'x +b'] L J c c J V V a * 9° C! 1 [y i= mJx-^+bJ] [y = m'x +b' ] J a 2 a 2 / V V . i / -jL-. c J [y c= mxc+b] - where chord(V. ,V. ) = e., , and R = d(V.,C. i ' k i k ' i ' l Figure 3.26 Location of c! [/?<!] 115 and r a d i u s R of a r c s forming the lune i s : R = / ( X i - X c a ) 2 + ( Y j - Y c a ) 2 (3.27) STEP 4b F i n d the c e n t r e s of the two a r c s c o n s t r u c t i n g the l a r g e s t empty lune, where Vj l i e s on the arc with c e n t r e C j , Vj l i e s on the arc with c e n t r e Cj and V K l i e s on one of the two a r c s , where K * ,,2,...,m and ' " ' j f j ( f i g u r e 3.27). In accomplishing t h i s we know from (3.8) and (3.9) that Cj and Cj l i e on a l i n e d e f i n e d as: yj = mxj + b (3.28) If Vj and V K l i e on the same a r c , then Cj l i e s on a l i n e which i s a p e r p e n d i c u l a r b i s e c t o r of c h o r d ( V j , V K ) ( f i g u r e 3.28). The slope of chord(Vj ,V K) i s : ( Y K - Y J ) m3 = (3.29) ( X K - X J ) and the p e r p e n d i c u l a r b i s e c t o r i s d e f i n e d by the e q u a t i o n : Y 0 = ba + mjXo (3.30) ,n ( X - + X J ( Y - + Y J where m1 = — , x = — — , Y = — - — 3 m3 0 2.0 ° 2.0 Thus the c o o r d i n a t e s of Cj a r e : (b! - b) X = — and Y = b! + ml X (3.31) co , , , co 3 3 co (m - m^ ) and r a d i u s R of a r c with c e n t r e Cj i s : R. = / ( X . - X.. )2 + (Y s - Y^ )2 (3.32) CO 1 CO I f Vj and V K l i e on the same a r c , then Cj l i e s on a l i n e which i s a p e r p e n d i c u l a r b i s e c t o r of chord(Vj,VK) ( f i g u r e 3.29). The slope of 116 Figure 3.27 In search o f C i [ |3 i_ 1 ] . 117 ^-[y.= m 3x i +b 3 ] -where chord (V^V^) = e i k , and R = d( V ± ,C±) Figure 3.28 Location of C [ /J>1]. C . V. V V . 1/ [ y = m; x +b; ] 1 [ V [ y - mx+b ] \ / X;Cyj= = m x .+b 4 J 4 ] -where chord(V.,V J = e., , and R = d(C ., J V Figure 3.29 Location of C . [ 0> 1 ] . 118 (Y - Y.) chord(Vj,V«) i s : m = — - i— ( 3 . 3 3 ) 4 (X - X.) k J and the p e r p e n d i c u l a r b i s e c t o r i s d e f i n e d by the e q u a t i o n : Y = b' + m'X ( 3 .34 ) r 4 4 r i n ( X - + X t } ( Y - + Y i , ) where m1 = — , X = —i — and Y = — * — . 4 m , r r, n r '4 ' 2 . 0 2 . 0 Thus the c o o r d i n a t e s of Cj a r e : (b'-b) x _ —2 and Y = b' + m'X ( 3 . 3 5 ) cr , , > cr 4 4 cr (m-m,) 4 and r a d i u s R of arc with c e n t r e Cj i s : _ _ R . = / ( X . - X ) l + (Y.- Y T ( 3 .36 ) J v j cr j cr Choose the g r e a t e r value of Rj and Rj and i t becomes the r a d i u s R of a r c s that form the l a r g e s t empty lune between p o i n t s Vj and V j . STEP 5 The value of 0 a s s i g n e d to the l i n k e j j i s then c a l c u l a t e d . From the r e s t r i c t i o n s imposed i n STEP 3, when the lune i s a s s o c i a t e d with the range of endoskeletons from the GG(V;E) to the RG(V;E), 0 ranges from 1 t o - r e s p e c t i v e l y . T h e r e f o r e i f STEP 4b was performed, the value of 0 i s : from (3.6) 0 = — (3.37) r When the lune i s a s s o c i a t e d with the range of endoskeletons from the CCG(V;E) t o the GG(V;E), 0 ranges from 0 to 1 r e s p e c t i v e l y . T h e r e f o r e i f STEP 4a was preformed, the value of 0 i s : from (3.10) 0 = - J - (3.38) The r e s u l t of a p p l y i n g STEPS 1 through 5 to 119 a l l l i n k s i n G 0(V;E) i s a weighted graph, G0(V;E), with 0 v a l u e s a s s i g n e d to each member of E(G0) ( f i g u r e 3.30). The advantages of t h i s method a r e : i ) The set of p o i n t s V(G 0) to be searched f o r each e j j i s reduced to only those which can be i n the c o n s t r u c t i o n of the graph. i i ) The set of p o i n t s not e l i m i n a t e d V(COR), i s f u r t h e r d i v i d e d i n t o two c a t e g o r i e s to again reduce s e a r c h i n g space before two d i f f e r e n t 'lune' c o n s t r u c t i o n s are a p p l i e d . 3.5 Summary of Chapter 3 The approach and methodology at the heart of t h i s d i s s e r t a t i o n , was d i s c u s s e d i n t h i s c h a p ter. For c l a r i f i c a t i o n , the methodology was d i v i d e d i n t o two s e c t i o n s . The f i r s t p a r t d i s c u s s e d the value of bench marks and i n t r o d u c e d a spectrum of graphs used as the bench mark developed i n t h i s study. Secondly, t h i s chapter presented a method of comparing the observed l i n k s t r u c t u r e E(G 0) of a graph G 0(V;E) to l i n k s t r u c t u r e s expected, given the presence of the u n d e r l y i n g assumptions of the bench mark. 120 G^CVjE) Figure 3.30 Observed graph with /3 values assigned to each l i n k . 121 In s h o r t , the methodology addresses i n t e r n a l r e c o g n i t i o n of l i n k p a t t e r n s i n c i r c u i t networks. S p e c i f i c a l l y , a spectrum of endoskeletons i s used t o generate a t h e o r e t i c a l bench mark to which observed networks can be compared. 122 Chapter 4: EMPIRICAL ILLUSTRATION 4._ I n t r o d u c t i o n The p r e v i o u s Chapter i n t r o d u c e d an approach that c o n t a i n s a two p a r t methodology f o r r e c o g n i z i n g p a t t e r n s i n c i r c u i t networks. The f i r s t p a r t of the methodology i n v o l v e s the generation of a t h e o r e t i c a l spectrum of s k e l e t o n s used as a bench mark, while the second p a r t d e s c r i b e s the method of comparing an observed network to the t h e o r e t i c a l bench mark. T h i s chapter i l l u s t r a t e s the a p p l i c a t i o n of such an approach to e m p i r i c a l c i r c u i t networks, keeping i n mind that l i k e a l l t h e o r e t i c a l work, there are l i m i t a t i o n s t o s p e c i f i c a p p l i c a t i o n . I t must be r e c o g n i z e d however, that given a p r i o r i knowledge about e m p i r i c a l networks, t a i l o r i n g of the bench mark f o r s p e c i f i c a p p l i c a t i o n s can take p l a c e and thus c o u l d enhance the r e s u l t s o b t a i n e d i n t h i s c h a p t e r . 123 In keeping with the methodology presented i n Chapter 3, a l i n k - b y - l i n k examination of an observed c i r c u i t network i s undertaken. The r e s u l t , as i l l u s t r a t e d i n f i g u r e 3.30, uncovers a p a t t e r n generated by a s s i g n i n g 0 values to the observed l i n k s t r u c t u r e i n the network. The continuous v a l u e s of 0 along a range from 0 to « are a f u n c t i o n of the examination procedure which generates 0. F i g u r e 3.30 c l e a r l y r e v e a l s a value f o r each l i n k but more imp o r t a n t l y , a p o s s i b i l i t y of trends among the l i n k s and thus p a t t e r n s may be observed. The l i n k 0 v a l u e s , besides p r o v i n g to be a good v i s u a l source of data, a l s o p r o v i d e a source of data which can be aggregated i n s e v e r a l ways to d e t e c t p a t t e r n s . In t h i s c h apter, two such aggregation methods are employed which a i d i n the r e c o g n i t i o n of p a t t e r n s that may appear hidden. The f i r s t method i n v o l v e s an i n d u c t i v e approach which examines groups of l i n k s with s i m i l a r 0 v a l u e s to those t h a t are s o l e l y a s s o c i a t e d with s k e l e t o n s a t e i t h e r end of the bench mark spectrum. C h a r a c t e r i z i n g the s t r u c t u r e of these groups, denoted ' l i n k t h r e s h o l d s ' 1 , can l e a d to the r e c o g n i t i o n of p a t t e r n s i n the c i r c u i t network which may have otherwise gone undetected. 1 The term ' l i n k t h r e s h o l d s ' i s d e f i n e d i n d e t a i l i n the f o l l o w i n g s e c t i o n . 124 F i n a l l y , when s p a t i a l p a t t e r n s are not apparent, a second method can be adopted to search f o r some p a t t e r n i n the 0 value d i s t r i b u t i o n of the network. T h i s method of obs e r v i n g 0 value d i s t r i b u t i o n s 2 , u n l i k e the f i r s t method, i s based on a ded u c t i v e approach which examines and compares d i s t r i b u t i o n s of 0 v a l u e s between a l r e a d y d e l i n e a t e d s e c t o r s of a network. Rather than search s i m i l a r 0 values to d e l i n e a t e areas of i n t e r e s t , t h i s second method al l o w s the examination of s i m i l a r i t i e s i n 0 value d i s t r i b u t i o n s between s e c t o r s . 4.2 Link Thresholds I t i s c l e a r t h at a p a t t e r n can be r e v e a l e d by implementing the l i n k - b y - l i n k examination from Chapter 3 on an observed graph G 0 ( V ; E ) . However, trends are not always obvious and f u r t h e r examination and e v a l u a t i o n of the network i s needed. Keeping t h i s i n mind, i t i s of i n t e r e s t to observe the l i n k s i n a graph G 0(V;E) t h a t : i ) e x i s t and are not expected to have a high l i k e l i h o o d of o c c u r r e n c e 3 , and i i ) those l i n k s i n a given graph that do not occur but would have been expected given the d i s t r i b u t i o n of the T h i s method of o b s e r v i n g 0 value d i s t r i b u t i o n s i s d i s c u s s e d i n d e t a i l i n a l a t e r s e c t i o n of t h i s chapter where i t i s employed. These are l i n k s with low 0 v a l u e s and given the p a r a l l e l to the g r a v i t y concept i n Chapter 1, they would tend t o e x i s t o n l y when the graph possesses a gr e a t d e a l of c o n n e c t i v i t y . 125 p o i n t set V ( G 0 ) . The a l t e r n a t e l i n k s t r u c t u r e c o u l d r e v e a l some tren d s i n p a t t e r n not uncovered by the observed l i n k s t r u c t u r e w i t h 0 v a l u e s . As a r e s u l t of the spectrum of 0 v a l u e s , i t i s uncommon to f i n d two e m p i r i c a l l i n k s a s s o c i a t e d with the same endoskeleton i n the bench mark. The exception i s a r e g u l a r p o i n t p a t t e r n or those l i n k s a s s o c i a t e d with the RG. However, 0 v a l u e s that are c l o s e i n value can be e x t r a c t e d and a new s p a t i a l d i s t r i b u t i o n of l i n k s can be generated. These new s p a t i a l d i s t r i b u t i o n s of l i n k s with s i m i l a r 0 values generate a l t e r n a t e p a t t e r n s denoted ' l i n k t h r e s h o l d s ' . " These ' l i n k t h r e s h o l d s ' are important t o det e c t and observe f o r two reasons. Two e m p i r i c a l networks which may appear d i s s i m i l a r i n s t r u c t u r e 5 , c o u l d c o n t a i n s i m i l a r ' l i n k t h r e s h o l d ' p a t t e r n s . 6 Secondly, areas of s i m i l a r l i n k s t r u c t u r e are areas of i n t e r e s t and i t can be deduced that they d i f f e r somewhat from the r e s t of the network. In the e m p i r i c a l networks examined i n t h i s c hapter, * These ' t h r e s h o l d s ' are the va l u e s of 0 which correspond t o both the upper and lower l i m i t s of the bench mark. 5 T h i s c o u l d be due to v a r i a t i o n s i n the o v e r a l l number of l i n k s or the range of 0 value d i s t r i b u t i o n s . 6 I t i s p o s s i b l e t h a t two e m p i r i c a l networks c o u l d have s i m i l a r l i n k g e n e r a t i o n r e s t r i c t i o n s , yet appear q u i t e d i f f e r e n t i n s t r u c t u r e due to v a r y i n g stages of development ( i e . age of the network). Examination of t h r e s h o l d p a t t e r n s can over come such o b s e r v a t i o n d i f f i c u l t i e s . 126 t h r e s h o l d s are observed f o r both: i ) l i n k s t h at e x i s t with low 0 v a l u e s , and i i ) l i n k s t h at do not e x i s t but are members of the s k e l e t o n s from the t h e o r e t i c a l bench mark and possess high 0 v a l u e s . 4._ Some H y p o t h e t i c a l Networks The C h r i s t a l l e r i a n hexagonal l i n k s t r u c t u r e , now common in the g e o g r a p h i c a l l i t e r a t u r e , proves to be an i n t e r e s t i n g example f o r a n a l y s i s . Since the p o i n t set V(G 0) i n the C h r i s t a l l e r i a n graph G 0(V;E) i s a r e g u l a r l a t t i c e , the 0 values f o r the l i n k s j o i n i n g them remain f a i r l y even or r e g u l a r as w e l l . F i g u r e 4.1 i l l u s t r a t e s the hexagonal s t r u c t u r e with i d e n t i c a l 0 v a l u e s approaching °° a s s i g n e d to each l i n k . Thus the C h r i s t a l l e r i a n l i n k s t r u c t u r e i s the RG 0(V;E) of the p o i n t set V ( G 0 ) . Another i d e a l i z e d s t r u c t u r e i s that which can l i n k together a square l a t t i c e of p o i n t s such as those i n f i g u r e 4.2. L i k e the hexagonal s t r u c t u r e , when analyzed u s i n g the methodology i n t r o d u c e d i n t h i s t h e s i s , i t i s observed that the l i n k s t r u c t u r e i s that of the RG 0(V;E) of the p o i n t set V(G 0) ( f i g u r e 4.3). However, a l l r e g u l a r l i n k s t r u c t u r e s which connect r e g u l a r p o i n t l a t t i c e s , are not a l l RG's of the p o i n t l a t t i c e . A h i g h l y r e g u l a r p a t t e r n e d l i n k s t r u c t u r e on a r e g u l a r p o i n t l a t t i c e does r e v e a l a r e g u l a r or even d i s t r i b u t i o n of 0 v a l u e s a s s o c i a t e d with the l i n k s . 127 0 » oo f o r a l l l i n k s i n E(G) Figure 4.1 Link /? Values of a Regular Hexagonal Network. [ RG(V;E) of point set V(G) ] 128 Figure 4.2' Regular Point P a t t e r n [square l a t t i c e ] > 1 > 1 1 1 p 1 -• O O -> oo t ' 1 • i > 1 -> oo 1 1 > 1 p ( i3 - oo f o r a l l l i n k s i n E(G) Figure 4.3 Link 0 Values of a Regular Square Network. [ RG(V;E) of point set V(G) ] 129 F i g u r e 4.4 i s an example of a t r i a n g u l a r p o i n t l a t t i c e with a very r e g u l a r p a t t e r n e d l i n k s t r u c t u r e . As a r e s u l t , the 0 v a l u e s a s s i g n e d to each of the l i n k s are i d e n t i c a l . T h e r e f o r e , r e g u l a r networks have r e g u l a r 0 value d i s t r i b u t i o n s . F i n a l l y , a h y p o t h e t i c a l l i n k s t r u c t u r e i s generated to demonstrate a change i n s t r u c t u r e w i t h i n a map p a t t e r n . Using a Poisson process, a set of p o i n t s i s generated, V ( G T ) of a c i r c u i t graph G T ( V ; E ) ( f i g u r e 4.5). The l i n k set E ( G T ) however, i s generated using two v a r y i n g methods which produce a planar l i n k s e t . Those p o i n t s on the l e f t h a l f of the p a t t e r n are connected u s i n g a process attempting to l i n k neighbours, while those on the r i g h t are generated using a s t o c h a s t i c p r o c e s s . As a r e s u l t , the 0 v a l u e s from f i g u r e 4.6 v i s u a l l y i n d i c a t e the v a r i a t i o n i n p a t t e r n between the two s i d e s . There appears to be a c e r t a i n amount of homogeneity w i t h i n the l e f t s i d e of the map p a t t e r n with most of the 0 v a l u e s £ 2.0. To f u r t h e r examine the l i n k s t r u c t u r e of the h y p o t h e t i c a l l y generated network, ' l i n k t h r e s h o l d s ' are observed f o r both i ) e x i s t i n g l i n k s with low 0 v a l u e s and i i ) n on-existant l i n k s that would possess h i g h 0 v a l u e s i f they were pres e n t . i ) F i g u r e 4.7a i l l u s t r a t e s the e x i s t i n g l i n k s with the lowest 10% of the 0 v a l u e s and f i g u r e 4.7b r e p r e s e n t s those 130 2.0 2.0 / \ / \ 2.0\ \_/ 2.0 \ y \ 2.0/ P = 2 f o r a l l l i n k s i n E(G) F i g u r e 4.4 L i n k 0 V a l u e s o f a R e g u l a r T r i a n g u l a r N e t w o r k . [ RNG(V;E) o f p o i n t s e t V(G) ] 131 Figure 4.5 Planar C i r c u i t Graph of a Hypothetical Network. 1 3 2 Figure 4.6 Link 0 Values of the Hypothetical Network. 133 a) lowest 1 0 % of 0 Values 1 • > \ b) lowest 2 0 7 o of 0 Values Figure 4.7 'Link Thresholds' of the Hypothetical Network. [existing links with low (3 values] 1 3 4 p o s s e s s i n g the lowest 20%. In both i n s t a n c e s , the l i n k s w ith lowest 0 values are l o c a t e d on the r i g h t s i d e of the h y p o t h e t i c a l l y generated network. T h i s was expected as the network was purposely generated to i l l u s t r a t e the use of r e c o g n i t i o n schema on p a t t e r n s with d i s t i n c t v a r i a t i o n s , i i ) The ' l i n k t h r e s h o l d s ' that do not occur i n the observed graph G T ( V ; E ) , r e v e a l i n t e r e s t i n g p a t t e r n s and can be s e p a r a t e l y graphed. F i g u r e 4.8a-d i l l u s t r a t e s those l i n k s that do not appear i n f i g u r e 4 .5, the h y p o t h e t i c a l l y generated c i r c u i t graph G T ( V ; E ) , yet are elements of t h e o r e t i c a l l y generated 0-skeletons of elements of t h e o r e t i c a l l y generated 0-skeletons of p o i n t set V ( G r ) . In t h i s i n s t a n c e a r b i t r a r y 0-skeletons are chosen to observe the ' l i n k s t h a t do not occur yet are e xpected. 7 Two s t r u c t u r a l c h a r a c t e r i s t i c s of the h y p o t h e t i c a l graph G r ( V ; E ) are exposed a p p l y i n g t h i s r e c o g n i t i o n method. When 0 —• co no 'missing l i n k s ' o c c u r r e d , t h e r e f o r e R G T ( V ; E ) 9 G T ( V ; E ) . TWO d i f f e r e n t graphs with d i s t i n c t t h r e s h o l d s make up G T ( V ; E ) s i n c e t h e r e are no 'missing l i n k s ' on the l e f t s i d e of the p a t t e r n , yet s e v e r a l 'missing l i n k s ' on the r i g h t (when 0*5). The abundance of those 'missing l i n k s ' on the r i g h t i l l u s t r a t e s the homogeneity of the r i g h t h a l f of the map p a t t e r n suggesting the l a c k of near 7 The advantage of using 0-skeletons as t h r e s h o l d l i m i t s i s that comparisons between d i f f e r e n t network ' l i n k t h r e s h o l d s ' can occur i f d e s i r e d . 135 \ / / a) 0= 100 ' / / / \ ^ / b) =20 t/ / / c) 0 =5 V • ' / d) 0=2 \y F i g u r e 4 . 8 'Link Thresholds' of the H y p o t h e t i c a l Network. [ /?-skeleton l i n k s m i s s i n g from the observed graph G T ( V ; E ) ] 136 neighbour l i n k i n g and i n d i c a t i n g some other generation scheme. T h i s example was h y p o t h e t i c a l l y developed to show d i s t i n c t p a t t e r n v a r i a t i o n and i t proves u s e f u l here i n i l l u s t r a t i n g the ' l i n k t h r e s h o l d ' scheme f o r r e c o g n i z i n g p a t t e r n s . 4.4 D e l i n e a t i o n of the Sample Space The implementation of the methodology on e m p i r i c a l data i n v o l v e s s e l e c t i n g some c i r c u i t networks to be used as observed c i r c u i t graphs. Since most examples of c i r c u i t networks i n human geography are t r a n s p o r t a t i o n networks, the observed pla n a r graphs s e l e c t e d f o r examination are a b s t r a c t e d from road networks. Three road networks are chosen, a l l l o c a t e d i n western Canada and a l l p o s s e s s i n g d i s s i m i l a r p o i n t p a t t e r n s . Topography i s i n f l u e n t i a l i n the development of town s i t e s and t h e i r c o nnecting road networks. To i n s u r e examples with v a r i a t i o n i n both p o i n t and l i n k s t r u c t u r e , three d i f f e r e n t topographies are c o n s i d e r e d 8 . The e m p i r i c a l road networks are s e l e c t e d from: S a l t s p r i n g I s l a n d , the pr o v i n c e of B r i t i s h Columbia and the p r o v i n c e of Saskatchewan. I t should be noted that i t i s not the i n t e n t i n t h i s t h e s i s to d i s c u s s the e f f e c t of topography on the un d e r l y i n g g e n e r a t i v e processes of e m p i r i c a l network development. 137 In a d d i t i o n , a non-planar c i r c u i t network i s examined which r e p r e s e n t s the major 9 a i r l i n e network i n Canada. T h i s example i s much d i f f e r e n t from the preceeding examples as l i n k s can i n t e r s e c t a t more than j u s t v e r t e x l o c a t i o n s . 4.5 Recognizing P a t t e r n s i n E m p i r i c a l Networks S a l t s p r i n g I s l a n d The f i r s t e m p i r i c a l example examined i s the road network on S a l t s p r i n g I s l a n d , B r i t i s h Columbia. Due to the lack of paved roads on S a l t s p r i n g I s l a n d , secondary as w e l l as g r a v e l roads are c o n s i d e r e d as p a r t of the I s l a n d ' s t r a n s p o r t a t i o n network. To c r e a t e an observed graph, the road network i s transformed t o a plana r c i r c u i t graph Gp(V;E) ( f i g u r e 4.9). The l i n k s E(Gp) i n the graph represent the roads i n the t r a n s p o r t network and the p o i n t s V(Gp) represent the i n t e r s e c t i o n s of the roads. Observing s i m i l a r 0 valu e s i n f i g u r e 4.10 r e v e a l s some trends i n the l i n k p a t t e r n of S a l t s p r i n g ' s road network. 9 The 'major' a i r l i n e network i n Canada i s d e f i n e d here as the network used by the two domestic a i r c a r r i e r s as w e l l as the four r e g i o n a l c a r r i e r s . 138 139 Figure 4.10 Link /3 Values of the S a l t s p r i n g I s l a n d Network. 140 Very few l i n k s s o l e l y a s s o c i a t e d w i t h the RGp(V;E) from S a l t s p r i n g ' s p o i n t set V(Gp) are present, and those t h a t are tend t o occur on l i n k s c o n n e c t i n g o u t l y i n g p o i n t s . As w e l l , t h e r e are few l a r g e v a l u e s of 0 a s s o c i a t e d with l i n k s , i n d i c a t i n g that connected p o i n t s do not appear to be i s o l a t e d from o t h e r s . S i m i l a r i l y , few l i n k s with very low P values e x i s t f o r S a l t s p r i n g , i n d i c a t i n g that few redundant l i n k s or l i n k s s o l e l y a s s o c i a t e d with the CCGp(V;E) occur i n the s y s t e m . 1 0 Examining the remaining l i n k s r e v e a l s a l a r g e number of /3 values which are c l o s e to va l u e s a s s o c i a t e d with the RNG and GG. T h i s suggests, as Lankford d e f i n e s the RNG 1 1, th a t ' r e l a t i v e l y c l o s e * neighbours i n the network are j o i n e d . T h i s i s not unexpected i n a t r a n s p o r t a t i o n network such as S a l t s p r i n g ' s , as the c o s t of b u i l d i n g a l i n k i s extremely expensive and the network can be c o n s i d e r e d a r e l a t i v e l y underdeveloped system. T h e r e f o r e , a spanning s t r u c t u r e that l i n k s c l o s e neighbours i s common under these c o n d i t i o n s and appears t o g a i n some r e c o g n i t i o n here, r a t h e r than some p a t t e r n c l o s e l y a s s o c i a t e d with the CCGp(V;E). These are l i n k s t h a t would l i n k two p o i n t s Vj and V,' even though many other p o i n t s , from a set V(G), e x i s t e d i n t h e i r 'lune' search space. P.M. Lankford, " R e g i o n a l i z a t i o n : theory and a l t e r n a t i v e a l g o r i t h m s " , G e o g r a p h i c a l A n a l y s i s , V o l . 1, No. 2, (1969) ppsl96-212. 141 When the ' l i n k t h r e s h o l d ' technique i s a p p l i e d to the e m p i r i c a l networks, i t i s more d i f f i c u l t to o b t a i n d i s t i n c t p a t t e r n s such as those observed i n the h y p o t h e t i c a l graph. F i g u r e 4.11a-b re p r e s e n t s the e x i s t i n g l i n k s with the lowest 10% and 20% of the 0 v a l u e s , r e s p e c t i v e l y . In both i n s t a n c e s a unique p a t t e r n r e s u l t s , with the d i r e c t i o n of l i n k s f o l l o w i n g the northwest to southeast spread of the i s l a n d . The r e c o g n i t i o n of such a unique t h r e s h o l d p a t t e r n can o b v i o u s l y d i r e c t the q u e s t i o n s of r e s e a r c h e r s concerned with the g e n e r a t i o n of such an e m p i r i c a l network. F i g u r e 4.12a-d i l l u s t r a t e s the 0-skeleton l i n k s m i s s i n g from the observed graph Gp(V;E). Here, l i t t l e homogeneity appears to e x i s t i n the p a t t e r n s of non-existent l i n k s , the 'missing l i n k s ' appearing to be evenly d i s t r i b u t e d throughout the graph, save f o r a small c l u s t e r of 'missing l i n k s ' i n the c e n t r e . F i v e of the 'missing l i n k s ' from f i g u r e 4.12d can be e a s i l y e x p l a i n e d s i n c e they c r o s s water. B r i t i s h Columbia The B r i t i s h Columbia road network i s another example of a p l a n a r c i r c u i t network whose shape i s governed to some extent by topography. U n l i k e S a l t s p r i n g I s l a n d however, the major roadways w i t h i n B r i t i s h Columbia are s t r o n g l y i n f l u e n c e d by the mountainous t e r r a i n r a t h e r than some 142 a) lowest 10% of j3 Values b) lowest 207c of /? Values Figure 4.11 'Link Thresholds' of the Saltspring Island Network. [existing links with low 0 values] 143 It 1, 'I a) 0 + b) 0 =10 c) 0 = 5 d) 0 =2 Figure 4.12 'Link Thresholds' of the S a l t s p r i n g I s l a n d Network, [0-skeleton l i n k s missing from the observed graph G p ( V ; E ) ] 144 bounding body of water. As a r e s u l t , a f a i r l y unusual major road p a t t e r n r e s u l t s . As the a n a l y s i s of the B r i t i s h Columbia network u n f o l d s , the major road network i s a b s t r a c t e d to form the observed c i r c u i t graph G 0(V;E) ( f i g u r e 4.13). In t h i s a b s t r a c t i o n , the l i n k s E (G 0) represent the major roads and the p o i n t set V(G 0) represents c i t i e s and towns, rather than i n t e r s e c t i o n s as i n the S a l t s p r i n g I s l a n d example. Observation of l i k e 0 v a l u e s i n the B r i t i s h Columbia example ( f i g u r e 4.14), l i k e S a l t s p r i n g I s l a n d , r e v e a l s few l i n k s s o l e l y a s s o c i a t e d with the RG 0(V;E) of the p o i n t set V ( G 0 ) . U n l i k e the S a l t s p r i n g example, s e v e r a l l i n k s with r e l a t i v e l y l a r g e 0 values do e x i s t and are mainly a s s o c i a t e d with o u t l y i n g or i s o l a t e d p o i n t s i n the p a t t e r n . Few l i n k s that are a s s o c i a t e d with the h i g h l y connected end of the bench mark spectrum are present, the few that are and worth mention are those t h a t l i n k the top pa r t of the network with the bottom. F i n a l l y , few l i n k s with 0 v a l u e s s i m i l a r to the RNG are observed and i t i s probable that l i n k s between ' r e l a t i v e l y c l o s e ' neighbours i n the i n t e r i o r of B r i t i s h Columbia are impeded due to t o p o g r a p h i c a l c o n s t r a i n t s . When the ' l i n k t h r e s h o l d ' technique i s a p p l i e d t o the B r i t i s h Columbia network, i t i s even more d i f f i c u l t to 145 Figure 4.13 Planar C i r c u i t Graph of the B r i t i s h Columbia Major Road Network. 146 147 o b t a i n any o v e r a l l r e c o g n i z a b l e p a t t e r n . As the t h r e s h o l d i s expanded from 10% i n f i g u r e 4.15a to 20% i n f i g u r e 4.15b, the emphasis on the F r a s e r V a l l e y area as the haven f o r low 0 value l i n k s s h i f t s t o the i n t e r i o r . F i g u r e 4.l6a-d r e p r e s e n t s the 'missing l i n k s ' from the observed graph G 0(V;E) of B r i t i s h Columbia. No o v e r a l l r e c o g n i z a b l e p a t t e r n e x i s t s f o r a l l four ' l i n k t h r e s h o l d s ' . However, when i n d i v i d u a l m i s s i n g l i n k s are examined, i t i s observed that many of them span mountain ranges and thus are absent from the e m p i r i c a l network. Saskatchewan The f i n a l p l a n a r example chosen to i l l u s t r a t e the approach and implement the methodology, i s the major road network i n the Province of Saskatchewan. U n l i k e the S a l t s p r i n g I s l a n d and B r i t i s h Columbia networks, the Saskatchewan road network i s not h e a v i l y c o n s t r a i n e d by topography as i t i s b u i l t on a f a i r l y homogeneous s u r f a c e . T h e r e f o r e other f o r c e s , such as socio-economic c o n s t r a i n t s , are more i n f l u e n t i a l on the p a t t e r n of development r e s u l t i n g i n a very d i f f e r e n t road network s t r u c t u r e than those p r e v i o u s l y examined. The observed c i r c u i t graph, Ga>(V;E), a b s t r a c t e d from the 148 a) lowest 1 0 7 o of P Values 1 ^,„,,.......J . b ) lowest 2 0 7 o f of 0 Values Figure 4 . 1 5 'Link Thresholds' of the B r i t i s h Columbia Network. [existing links with low 0 values] 1 4 9 f H /§ a) iff -» oo / 1 b) /?=10 c ) /?=5 ^ f ' d) 0=2 Figure 4.16 'Link Thresholds' of the B r i t i s h Columbia Network. [ /?-skeleton links missing from the observed graph G 0(V;E)] 150 Saskatchewan road network c o n s i s t s of a set of p o i n t s V ( G_0 r e p r e s e n t i n g settlements and a set of l i n k s E ( G C J ) denoting t h e i r c o n necting roadways ( f i g u r e 4.17). U n l i k e the p r e v i o u s examples, the Saskatchewan c i r c u i t network appears evenly spaced and g e n e r a l l y more connected as a whole. F i g u r e 4.18 i l l u s t r a t e s the 0 values of each l i n k i n the Saskatchewan road network. In c o n t r a s t to the B r i t i s h Columbia network, r e l a t i v e l y few l i n k s with 0 a s s o c i a t e d s o l e l y with the R G _ > ( V ; E ) member of the bench mark e x i s t . Many of the l i n k s have v a l u e s a s s o c i a t e d with the R N G C J ( V ; E ) and u n l i k e both the B.C. and S a l t s p r i n g networks, many l i n k s have very small 0 v a l u e s . F u r t h e r a n a l y s i s , which i n v o l v e s the ' l i n k t h r e s h o l d * technique, r e v e a l s a unique p a t t e r n f o r both the lowest 10% and 20% 0 value t h r e s h o l d s f o r the e x i s t i n g l i n k s i n G _ i ( V ; E ) . In g e n e r a l , o b s e r v a t i o n of f i g u r e 4.l9a-b r e v e a l s the t r a n s p o r t a t i o n network i s r e l a t i v e l y w e l l developed w i t h many l i n k s spanning i n an east-west b i a s and a s s o c i a t e d with the h i g h l y connected endoskeletons i n the t h e o r e t i c a l bench mark. In p a r t i c u l a r , the east-west b i a s i s c o n c e n t r a t e d i n the southern h a l f of the network. The 0-skeleton l i n k s t h a t do not occur i n the observed graph G w ( V ; E ) , a l s o r e v e a l a unique p a t t e r n . U n l i k e the S a l t s p r i n g and B r i t i s h Columbia networks, a l l the l i n k s 151 152 Figure 4.18 Link /? Values of the Saskatchewan Network. 153 a) l o w e s t 107c o f 0 V a l u e s b) lowest 207o of 0 Values Figure 4.19 'Link Thresholds' of the Saskatchewan Network, [ e x i s t i n g l i n k s w i t h low R v a l u e s ] 154 from the RGa>(V;E) are present i n the Saskatchewan network. F u r t h e r , from f i g u r e 4.20a-d i t i s observed t h a t o v e r a l l t h e r e are few 'missing l i n k s ' i n the c e n t r a l to north c e n t r a l p a r t of the p r o v i n c e . As w e l l , those 'missing l i n k s ' t h a t occur i n f i g u r e 4.20, appear to span i n a north-south d i r e c t i o n . Major Canadian A i r l i n e Network The f i n a l example chosen i s an example of a non-planar c i r c u i t network. T h i s network i s the major Canadian a i r l i n e network, i n c l u d i n g both n a t i o n a l a i r l i n e s as w e l l as the four r e g i o n a l Canadian a i r c a r r i e r s . The observed c i r c u i t graph Go(V;E), a b s t r a c t e d from the major a i r l i n e s c h e d u l i n g c h a r t s , c o n s i s t s of a set of p o i n t s V(Go) r e p r e s e n t i n g a i r p o r t s and a set of l i n k s E(Ga) denoting t h e i r c o n n e c t i n g routes ( f i g u r e 2.21). In c o n t r a s t to the planar examples, the a i r l i n e network has a h i g h degree of c o n n e c t i v i t y with many of the routes a s s o c i a t e d with the low 0 value l i n k s spanning i n an east-west d i r e c t i o n . As a r e s u l t of the h i g h c o n c e n t r a t i o n of l i n k s , a f i g u r e i l l u s t r a t i n g the 0 v a l u e s of the l i n k s i n t h i s network would prove d i f f i c u l t to read v i s u a l l y and i s thus omitted. 155 a) 0=20 c) /?=7.5 / / b) 0=10 I / / / \ / / d) 0=5 Figure 4.20 'Link Thresholds' of the Saskatchewan Network. [ 0-skeleton links missing from the observed graph GJV;E)] 156 Figure 4.21 Non-planar C i r c u i t Graph of the Canadian Major A i r l i n e Network. 157 The ' l i n k t h r e s h o l d s ' of e x i s t i n g l i n k s f o r the 10% and 20% lowest 0 v a l u e s i n Go(V;E) are i l l u s t r a t e d i n f i g u r e 4.22a-b. G e n e r a l l y , the low 0 value l i n k s span long d i s t a n c e s i n an east-west d i r e c t i o n . T h i s however, i s not s u r p r i s i n g as s e v e r a l l i n k s i n the major Canadian a i r l i n e network tend to l i n k the major c i t i e s east to west. The 0-skeleton l i n k s that do not occur i n the observed graph Go(V;E) are a l s o determined and i l l u s t r a t e d i n f i g u r e 4.23a-d. I t i s observed that l i k e the S a l t s p r i n g and B r i t i s h Columbia networks, 'missing l i n k s ' from the RGa(V;E) occur. As w e l l , many of the 'missing l i n k s ' i n f i g u r e 4.23d are op p o s i t e i n c h a r a c t e r i s t i c to those i n f i g u r e 4.22 as they span short d i s t a n c e s i n a north-south d i r e c t i o n . 4.6 Observing _ Value D i s t r i b u t i o n s Often any form of s p a t i a l p a t t e r n may appear non - e x i s t e n t when ob s e r v i n g c i r c u i t graphs. In p a r t i c u l a r , s p a t i a l trends i n 0 v a l u e s may prove d i f f i c u l t to re c o g n i z e , t h e r e f o r e techniques of a n a l y z i n g the d i s t r i b u t i o n of 0 v a l u e s i n a sample space may expose some p r e v i o u s l y hidden p a t t e r n s . D e s c r i p t i v e as w e l l as i n f e r e n t i a l s t a t i s t i c s can be 158 i l N a) l o w e s t 107o o f /3 V a l u e s N 159 b) /? =40 HI I \ d) 0=5 y l 23 'Link Thresholds' of the Canadian Maior A i r l i n e Network. [ /?-skeleton links missing from the observed graph G f f(V;E)] 160 used to examine the 0 value d i s t r i b u t i o n s t o determine whether or not v a r i a t i o n occurs between s e c t o r s of the c i r c u i t network. These s e c t o r s c o u l d r e p r e s e n t regions w i t h i n a c i r c u i t network and thus t h e i r d e l i n e a t i o n c o u l d be e m p i r i c a l l y motivated. However, i n t h i s r e s e a r c h no a p r i o r i knowledge i s assumed and s e c t o r s are formed by d i v i d i n g the map p a t t e r n , c o n t a i n i n g the c i r c u i t network, i n t o q u adrats. These quadrats are s i m i l i a r to those employed i n the p o i n t p a t t e r n l i t e r a t u r e d i s c u s s e d i n Chapter 2. Appendix B c o n t a i n s the quadrat d i v i s i o n s f o r the p l a n a r c i r c u i t networks examined i n t h i s c h a p ter. Within each quadrat, the d i s p e r s i o n of the d i s t r i b u t i o n of 0 v a l u e s i s expressed as the c o e f f i c i e n t of v a r i a t i o n V. V = — (4.1) X where S_= the standard d e v i a t i o n and X = mean of the d i s t r i b u t i o n . D i s t r i b u t i o n s with a high degree of homogeneity possess c o e f f i c i e n t s of v a r i a t i o n which approach 0. Thus quadrats found with low values of V, c o n t a i n l i n k s with s i m i l i a r 0 v a l u e s . 1 2 Since the 0 ranges, 0 to 1 and 1 to °° , are determined by d i f f e r e n t lune search methods, 0 c o n s i s t s of two s e t s of r a t i o d a ta. T h e r e f o r e , p a t t e r n s i n the d i s t r i b u t i o n of 0 v a l u e s are sought f o r both ranges (0 to 1 and 1 to *> ) as merging the two s e t s of data would v i o l a t e the assumptions of the s t a t i s t i c a l t e s t s . 161 Table 4.1 c o n t a i n s the 0 value c o e f f i c i e n t s of v a r i a t i o n f o r the p l a n a r c i r c u i t networks under study. Extreme d i s p e r s i o n i s found i n a l l quadrats f o r 0 ranges 1 t o co and a l t h o u g h V i s r e l a t i v e l y s m a l l e r f o r 0 ranges 0 to 1, the o n l y quadrat that appears to possess some homogeneity i s quadrat 2 i n the S a l t s p r i n g I s l a n d n e t w o r k . 1 3 Since l i t t l e homogeneity e x i s t s w i t h i n each quadrat, another method of a n a l y s i s can be adopted to look f o r p a t t e r n s i n the d i s t r i b u t i o n of 0 v a l u e s . The degree of f i t between the 0 v a l u e d i s t r i b u t i o n s of two quadrats can be measured using a Kolmogorov-Smirnov (K-S) two-sample t e s t . The K-S two-sample t e s t i s a t e s t of whether two independent samples have been drawn from p o p u l a t i o n s with the same d i s t r i b u t i o n . 1 * The r e s u l t s of the K-S t e s t i n d i c a t e t hat no s i g n i f i c a n t d i f f e r e n c e between the quadrats d i s t r i b u t i o n of 0 v a l u e s e x i s t e d when the quadrats sampled were from the same e m p i r i c a l c i r c u i t network. T h i s was not unexpected f o r both the S a l t s p r i n g and Saskatchewan networks as the quadrats appeared evenly balanced. The B r i t i s h Columbia network's l a c k of d i f f e r e n c e may have been due to the Although no t e s t f o r s i g n i f i c a n c e l e v e l s e x i s t s f o r V, s i m u l a t i o n s have shown th a t v a l u e s of V < 0.3 tend toward homogeneity. S . S i e g e l , Nonparametric S t a t i s t i c s , (Toronto: McGraw-Hill Book Company, 1956) p127. 162 Table 4 . 1 COEFFICIENT OF VARIATION ( f o r planar networks) C i r c u i t Network Quadrat 1 2 3 4 H y p o t h e t i c a l 1 - - 1 --- — . 1 ___ S a l t s p r i n g I s l a n d 1 o . 4 3 | 0 . 2 0 | — - 1 — B r i t i s h Columbia 1 o . 3 5 | 0 . 6 6 | 0 . 7 0 | Saskatchewan 1 o . 5 0 | 0 . 3 6 | 0 . 5 5 | 0 . 4 6 0 range Hypoth e t i c a l 1 4 . 2 5 | 3 . 3 4 | -- ! -— 1 S a l t s p r i n g I s l a n d 1 3 . 4 4 | 3 . 4 2 | -- -— 1 B r i t i s h Columbia 1 1 . 3 4 | 0 . 8 2 | 1 • 3 1 | 1 • 6 3 | Saskatchewan I 5 • 4 1 | 2 . 4 8 | 2 . 7 9 | 1 . 1 2 | Q range 1 — * - o o 163 method of d e l i n e a t i n g the quadrats as at f i r s t glance, the Fr a s e r V a l l e y area appeared to have a d i f f e r e n t d i s t r i b u t i o n of 0 v a l u e s than the r e s t of the network. A d i f f e r e n c e between the 0 value d i s t r i b u t i o n s (ranging from 1 t o °° ) of the two quadrats from the h y p o t h e t i c a l l y generated c i r c u i t network i s r e v e a l e d at a .05 l e v e l of s i g n i f i c a n c e . T h i s however, i s not unexpected as quadrat 2 was m i s s i n g many of the l i n k s a s s o c i a t e d with the 0£1.O (from f i g u r e 4.6). The methods e l a b o r a t e d here, that analyze the d i s t r i b u t i o n of 0 v a l u e s i n a sample space,are only two of s e v e r a l a v a i l a b l e techniques that a i d i n aggregation and summarization of d a t a . T h e i r i l l u s t r a t i o n here shows that 0 v a l u e s can be e a s i l y aggregated i n attempts to recognize v a r i a t i o n s i n t h e i r d i s t r i b u t i o n w i t h i n the c i r c u i t network i t s e l f or between d i f f e r e n t s p a t i a l s e c t o r s of the network. 4.7 Summary of Chapter 4 To summarize, i t i s the i n t e n t of t h i s chapter to i l l u s t r a t e the proposed approach and implement the methodology developed i n the p r e v i o u s chapter. Some i d e a l h y p o t h e t i c a l p l a n a r c i r c u i t networks were f i r s t examined to i l l u s t r a t e extreme cases with equal 0 v a l u e s . These are 164 f o l l o w e d by an example where purp o s e l y generated, d i s t i n c t l i n k p o i n t s e t . 0 v a l u e s d i s c l o s e p a t t e r n s w i t h i n the two same A f t e r these examples i l l u s t r a t i n g the use of the 0 v a l u e s i n c o n t r o l l e d c o n d i t i o n s , three p l a n a r c i r c u i t ( t r a n s p o r t a t i o n ) networks, each with a v a r y i n g s p a t i a l p a t t e r n , are a b s t r a c t e d from e m p i r i c a l road networks. As w e l l , the non-planar major a i r l i n e network of Canada i s a b s t r a c t e d from s c h e d u l i n g c h a r t s . The 0 values are d e r i v e d f o r each l i n k and the r e s u l t a n t graphs are examined, n o t i n g any obvious s p a t i a l trends i n p a t t e r n . Often trends are not e a s i l y d e t e c t e d and other means of a n a l y z i n g the graphs are sought. Although i t i s c o n c e i v a b l e that many a n a l y t i c a l a l t e r n a t i v e s e x i s t , one such attempt, the ' l i n k t h r e s h o l d ' method, i s i l l u s t r a t e d . In t h i s i n s t a n c e , low 0 v a l u e d l i n k s t h a t e x i s t are aggregated and examined to determine whether they r e v e a l any areas of i n t e r e s t i n the network. As w e l l ' l i n k t h r e s h o l d ' l i m i t s are generated using s e v e r a l a r b i t r a r i l y h i g h 0 value s k e l e t o n s c o n s i d e r e d s p e c i a l members of the graph spectrum used as the bench mark. Any high 0 value l i n k s of the observed p o i n t set that do not appear i n the observed l i n k s t r u c t u r e are noted. These mi s s i n g high 0 value l i n k s can r e v e a l p a t t e r n s that might have otherwise gone unno t i c e d . 165 F i n a l l y , i n f a i r l y complex networks i t i s sometimes d i f f i c u l t to v i s u a l l y r e c o g n i z e s p a t i a l trends and an a l t e r n a t i v e a n a l y s i s that determines v a r i a t i o n s i n 0 v a l u e s over a sample space can prove u s e f u l . T h e r e f o r e d i s t r i b u t i o n s of 0 values i n v a r y i n g s e c t o r s of the map p a t t e r n are determined. 166 Chapter 5: SUMMARY 5.1 Overview The opening chapter i n t r o d u c e d the main t o p i c of concern i n t h i s d i s s e r t a t i o n : c i r c u i t networks. Since i t appears that there are a v a r i e t y of approaches to s t u d y i n g c i r c u i t networks, the m o t i v a t i o n f o r the one used i n t h i s t h e s i s (the study of the morphology or geometric s p a t i a l s t r u c t u r e ) was j u s t i f i e d with a b r i e f d i s c u s s i o n of form, f u n c t i o n and process r e a l i z a t i o n s i n geography. The i m p l i c a t i o n s of such an approach were then d i s c u s s e d , with two urgent needs i n c i r c u i t network r e c o g n i t i o n addressed. These needs are , f i r s t , a method of form c h a r a c t e r i z a t i o n f o r i n t e r n a l s t r u c t u r e ; and second, the development of a t h e o r e t i c a l bench mark from which to e v a l u a t e and compare e m p i r i c a l networks. Although the 167 methodology does not attempt to e x p l a i n an e m p i r i c a l map p a t t e r n , comparisons made to a t h e o r e t i c a l l y generated bench mark allow b e t t e r comparison between e m p i r i c a l networks and as w e l l may a i d i n attempts to b e t t e r hypothesize process i n the ' r e a l ' world. The f i r s t chapter continued with a formal d e f i n i t i o n of the term ' c i r c u i t ' , along with a d e s c r i p t i o n of how i t i s c l a s s i f i e d with other networks i n geography. Haggett's paradigm ( f i g u r e 1.1) was used as a s t a r t i n g p o i n t , and the c l a s s i f i c a t i o n s of networks were f i l t e r e d u n t i l the c l a s s of c i r c u i t s under study i n t h i s d i s s e r t a t i o n was d e l i n e a t e d 1 . A l i t e r a t u r e review, c o n t a i n i n g network s t u d i e s i n geography as a whole, was i n c l u d e d i n the f i r s t chapter. T h i s review d i s c u s s e d examples of t r e e and c e l l u l a r networks, and then con c e n t r a t e d on those p e r t i n e n t s t u d i e s which l i n k process and form i n c i r c u i t morphology. Furthermore, two approaches i n the l i t e r a t u r e which attempted to c h a r a c t e r i z e form, were a l s o d i s c u s s e d . These two approaches i n v o l v e d the a p p l i c a t i o n of d e n s i t y and d i s t a n c e m e t r i c s to d e s c r i b e the spacing of p a t t e r n s , and the examination of element d i r e c t i o n s to d e t a i l p a t t e r n shape. 1 The c l a s s of c i r c u i t s under examination are s y n t h e t i c networks. 168 The chapter continued by d i s c u s s i n g the concept of p a t t e r n r e c o g n i t i o n and the two b a s i c approaches to i t ( e x t e r n a l and i n t e r n a l ) adopted by geographers. T h i s l e d to the o b j e c t i v e s of the r e s e a r c h s t a t e d as an attempt to reco g n i z e p a t t e r n s at an i n t e r n a l , or l o c a l , l e v e l i n c i r c u i t networks. To accomplish t h i s task a twofold methodology was i n t r o d u c e d which generated a t h e o r e t i c a l bench mark f o r the comparison of observed networks and c h a r a c t e r i z e d i n t e r n a l s t r u c t u r e . S ince the f i e l d of c i r c u i t network a n a l y s i s has been e x p l o r e d i n s e v e r a l d i s c i p l i n e s , a set of d e f i n i t i o n s preceded by a set of sometimes synonymous terms e x i s t s . T h e r e f o r e an e x t e n s i v e symbolism common to the study of graphs was presented i n the second chapter t o d e f i n e the set of terms used i n t h i s d i s s e r t a t i o n . D iscussed, as w e l l , were s e v e r a l recent approaches taken to the study of p o i n t , l i n e and area p a t t e r n s . The methodologies and measuring techniques i n these approaches t o map p a t t e r n a n a l y s i s paved the way f o r the methodology proposed i n the chapter which f o l l o w e d . A t h e o r e t i c a l g e n e r a t i v e process was used t o c r e a t e the f a m i l y of c i r c u i t graphs i n t r o d u c e d i n the t h i r d chapter as the bench mark employed i n t h i s t h e s i s . Such a bench mark has not been developed i n p r e v i o u s s t u d i e s of c i r c u i t network morphology, but bench marks do e x i s t i n the 169 a n a l y s i s of both p o i n t s and c e l l s . Furthermore, a l o c a l i z e d or l i n k - b y - l i n k examination technique was developed t h a t compared each l i n k i n an e m p i r i c a l c i r c u i t network to the t h e o r e t i c a l l y generated bench mark. The r e s u l t i s a c i r c u i t network with a mosaic of weighted l i n k s , each corresponding to one member (/3-skeleton) of the bench mark. T h i s p r o v i d e s a means of comparing l i n k s w i t h i n and between c i r c u i t networks i n a quest to uncover p a t t e r n s . F i n a l l y , the approach and methodology to c i r c u i t p a t t e r n r e c o g n i t i o n presented i n t h i s d i s s e r t a t i o n were i l l u s t r a t e d by examining a h y p o t h e t i c a l l y generated network as w e l l as four r e a l world examples of c i r c u i t networks i n Chapter 4. Since the t h e o r e t i c a l approach developed i n t h i s t h e s i s possesses a methodology based on s t r i c t assumptions, d i r e c t a p p l i c a t i o n of the methodology,in i t s present form, to e m p i r i c a l networks possesses l i m i t a t i o n s . Assumptions can c e r t a i n l y be t a i l o r e d f o r s p e c i f i c a p p l i c a t i o n thus making the r e s u l t s more e m p i r i c a l l y o r i e n t e d . The study has covered s u b s t a n t i a l ground i n p r e s e n t i n g a base f o r a more v i g o r o u s and f l o u r i s h i n g approach to examining c i r c u i t network morphology. T h i s study i s a beginning, and expansion of the approach and methodology developed h e r e i n i s p o s s i b l e . Such a d d i t i o n a l r e s e a r c h w i l l be d i s c l o s e d i n the next s e c t i o n . 170 5.2 Developments Beyond t h i s Study There are s e v e r a l developments that can be viewed as n a t u r a l e x t e n s i o n s of t h i s study. The present r e s e a r c h possesses some s t r i c t assumptions regarding the t h e o r e t i c a l g e n e r a t i v e process used i n c r e a t i n g the spectrum of s k e l e t o n s composing the bench mark. R e l a x i n g some of these assumptions reduces the g e n e r a l nature of the bench mark and a l l o w s i t to be t a i l o r e d f o r s p e c i f i c e m p i r i c a l use. Two areas where m o d i f i c a t i o n s seem promising i n v o l v e assumptions r e g a r d i n g time and space. The e m p i r i c a l graph s t r u c t u r e s are p r e s e n t l y observed at one i n s t a n t i n time and t h e i r development i s thus assumed to be synchronous. T h e r e f o r e the set of p o i n t s V(G 0) used to generate the s k e l e t o n s or members of the bench mark remains f i x e d . However, many e m p i r i c a l networks develop asynchronously, with some p o i n t s and l i n k s e x p e r i e n c i n g e a r l y g e n e r a t i o n while others are generated l a t e r . The p o i n t s and l i n k s t h a t experience e a r l y b i r t h o f t e n have an e f f e c t on those p o i n t s and l i n k s which f o l l o w . T h e r e f o r e to assume equal i n f l u e n c e of the p o i n t s and l i n k s i n the g e n e r a t i o n of the bench mark, can be r e s t r i c t i v e . Future r e s e a r c h i n t h i s area c o u l d i n v o l v e a m o d i f i c a t i o n to the e x i s t i n g assumption of synchronous development. Such a m o d i f i c a t i o n would a l l o w those p o i n t s 171 and l i n k s i n the e m p i r i c a l network t h a t were generated f i r s t , to have a stronger i n f l u e n c e i n the generation of the bench mark. The t h e o r e t i c a l g e n e r a t i v e process of the bench mark c o u l d i n c l u d e weights a s s i g n e d to each p o i n t and l i n k that are a f u n c t i o n of the time at which they f i r s t appeared i n the g e n e r a t i o n of the e m p i r i c a l network. Such a m o d i f i c a t i o n would allow the i n c l u s i o n of a temporal dimension i n t o the spectrum of s k e l e t o n s making up the bench mark. Another e x t e n s i o n to the present r e s e a r c h a l s o i n v o l v e s r e l a x i n g some assumptions re g a r d i n g the bench mark gene r a t i o n scheme. I n i t i a l l y , the e m p i r i c a l c i r c u i t network i s assumed to be on an i s o t r o p i c plane. T h e r e f o r e , the i n f l u e n c e of a l l the elements of p o i n t set V(G 0) on each other i s a f u n c t i o n of only the e u c l i d e a n d i s t a n c e s e p a r a t i n g them. The space which r e a l world c i r c u i t networks occupy i s seldom i s o t r o p i c . Therefore another m o d i f i c a t i o n to the bench mark's t h e o r e t i c a l g e n e r a t i v e p r o c e s s , t h i s one i n v o l v i n g s p a t i a l i n f l u e n c e , i s seen as a f u r t h e r way to t a i l o r the bench mark to address e m p i r i c a l r e s e a r c h . T h i s m o d i f i c a t i o n c o u l d e n t a i l adding weights to each l i n k i n the bench mark of s k e l e t o n s . Such weights c o u l d represent the ' f r i c t i o n of d i s t a n c e ' 2 and c o u l d be a f u n c t i o n of a 172 combination of c r i t e r i a such as; the a c t u a l d i s t a n c e of a l i n k (that i s a road i n a road network), the c o s t and the time taken t o t r a v e l between two p o i n t s i n a network. T h e r e f o r e the 0 valu e s a s s i g n e d t o generate a l i n k i n each bench mark s k e l e t o n , would be a f u n c t i o n of not only the s i z e of the 'lune' search space but a l s o the ' f r i c t i o n of  d i s t a n c e ' between each p a i r of p o i n t s i n V ( G 0 ) . A m o d i f i c a t i o n such as t h i s would allow the i n c l u s i o n of s p a t i a l c o n s t r a i n t s , which are e m p i r i c a l l y induced, i n the ge n e r a t i o n of the spectrum of s k e l e t o n s used as a bench mark. 5.3 A l t e r n a t i v e Approaches Before t h i s d i s s e r t a t i o n draws to a c l o s e , i t i s necessary t h a t a few comments be made concerning a l t e r n a t i v e approaches to the study of c i r c u i t networks. There e x i s t s an absence of theory i n the study of c i r c u i t n e tworks 3. T h e r e f o r e , as theory advances, the adoption of a l t e r n a t i v e approaches w i l l most l i k e l y prove advantageous. For i n s t a n c e , s e v e r a l of the approaches that e x i s t i n other areas of s p a t i a l a n a l y s i s c o u l d be m o d i f i e d to analyze c i r c u i t graphs as w e l l . In p a r t i c u l a r , some of the 2 J.C. Lowe and S.Moryadas, The Geography of Movement, (Boston: Houghton M i f f l i n Co., 1975T7 3 K.J. T i n k l e r , "Graph Theory",Progress i n Human  Geography, V o l . 3 , No.1 (1979) pps85-116. 173 approaches to c e l l u l a r networks presented by G e t i s and Boots' c o u l d prove v a l u a b l e i n g e n e r a t i n g s e q u e n t i a l c i r c u i t networks modifying s t r u c t u r e i n each time frame. In Chapter 2, i n t e r n a l as w e l l as e x t e r n a l approaches to p a t t e r n r e c o g n i t i o n were d i s c u s s e d . No adequate d e s c r i p t i v e m etric that addresses a continuous range of form, from i n t e r n a l to e x t e r n a l , e x i s t s . Future r e s e a r c h i n d e v eloping the l i n k - b y - l i n k sampling technique, to cover s e v e r a l order neighbours, may prove to be a promising s o l u t i o n . F i n a l l y , once the geometry of a network has been c h a r a c t e r i z e d , the next step i s to examine i t s non-geometric, or f u n c t i o n a l , c h a r a c t e r i s t i c s . In the same in s t a n c e , advances made i n the world of s y n t h e t i c network r e s e a r c h (as i n the present study) can p o s s i b l y be a p p l i e d t o n a t u r a l network r e s e a r c h i n attempts to l i n k form and process i n p h y s i c a l geography. 5.4 C o n c l u s i o n I t i s important to mention the impact of t h i s study upon the f i e l d of c i r c u i t network a n a l y s i s . I t i s a primary * A.Getis and B.N.Boots, Models of S p a t i a l Processes, Cambridge: Cambridge U n i v e r s i t y P r e s s , 1978. 174 quest of academics to work toward a ge n e r a l theory of understanding. T h i s d i s s e r t a t i o n i n t r o d u c e s an approach which p r o v i d e s a beginning from which theory can be generated. Such theory a i d s i n our d e s i r e to understand both the geometric and non-geometric p r o p e r t i e s i n r e a l world networks. With such an approach i n hand, and with a stro n g d e s i r e to e x p l a i n , p o s s i b i l i t i e s f o r rese a r c h l e a d i n g to a more complete understanding of c i r c u i t networks appear promising. 175 BIBLIOGRAPHY Black, W.R., "An i t e r a t i v e model f o r ge n e r a t i n g t r a n s p o r t a t i o n networks", Geographical A n a l y s i s , Vol.3,No.3, 1971, pp283-288. B l a u t , J.M., "Space and Process", The P r o f e s s i o n a l  Geographer, Vol.13,No.1, 1961, pp1-7. Blum, H., " B i o l o g i c a l shape and v i s u a l Science (part 1)", J o u r n a l of T h e o r e t i c a l B i o l o g y , Vol.38, No.2 (1973) pps205-287. Boots, B.N., "Some models of the random s u b d i v i s i o n of space", G e o g r a f i s k a Annaler, Vol.55B, 1973. Boots, B.N., "Delaunay t r i a n g l e s : an a l t e r n a t i v e approach to p o i n t p a t t e r n a n a l y s i s , " Proceedings of the  A s s o c i a t i o n of American Geographers, V o l . 6 , (1974) Boots, B.N., "Patterns of urban settlements r e v i s i t e d " , P r o f e s s i o n a l Geographer, Vol.27,No.4, 1975, pp426-43l. Boots, B.N., and A . G e t i s , " P r o b a b i l i t y model approach to map p a t t e r n a n a l y s i s " , Progress i n Human Geography, V o l . 1 , No.2, 1977, pps264-87. Boots, B.N., "Comments on Using E i g e n f u n c t i o n s to Measure S t r u c t u r a l P r o p e r t i e s of Geographic Networks", Environment and Pl a n n i n g , Vol.14, No.8, 1982. Brown, L.A., "Models f o r s p a t i a l d i f f u s i o n r e s e a r c h " , O f f i c e of Naval Research, Geography Branch, TASK  389-140, T e c h n i c a l Report, No.3, 1965. Bunge, W.,Theoretical Geography, Lund S t u d i e s i n Geography, S e r i e s C, No.1, Second E d i t i o n , 1966. Burghaut, A., "The o r i g i n and the development of the road network of the Niagara P e n i n s u l a , O n t a r i o , 1770-1851", Annals of the AAG, Vol.59,1969,pp417-440. Busacker, R.G.,and T.G. Saaty, F i n i t e Graphs and  Networks, Toronto: McGraw-Hill Inc., 1965. Curry, L.,"The Random S p a t i a l Economy: An E x p l o r a t i o n i n Settlement Theory", Annals of the AAG, Vol.54,No.1, 1964, pp138-46. Dacey, M.F., "The geometry of c e n t r a l p l a c e theory", G e o g r a f i s k a Annaler, Vol.47B, 1965, pps111-124. 176 Dacey, M.F.,"A P r o b a b i l i t y Model of C e n t r a l P l a c e L o c a t i o n s " , Annals of the AAG, Vol.56,No.3, 1966, pp549-68. Dacey, M.F., " E v a l u a t i o n of the Poisson approximation to measures of the random p a t t e r n i n the square", Geographical A n a l y s i s , Vol.7,No.4, 1975, pp361-367. Edelsbrunner, H., D . G . K i r k p a t r i c k and R . S e i d e l , "On the shape of a set of p o i n t s i n the plane", IEEE  T r a n s a c t i o n s on Information Theory ( f o r t h coming). Eichenbaum, J . and S. Gale, "Form, F u n c t i o n , and Process: A M e t h o d o l o g i c a l I n q u i r y " , Economic  Geography, Vol.47, No.4, 1971, pp525-44. Funk, and Wagnalls, Standard C o l l e g e D i c t i o n a r y , Toronto: F i t z h e n r y and Whiteside L t d . , 1975, p825. F u r n e l l , D.C., "Methods of measuring the n o d a l i t y of p l a c e s on a t r a n s p o r t a t i o n network - an assessment based on s t u d i e s of the Uganda road system". P e r c e p t i o n and N o d a l i t y , Department of Geography, Makerere U n i v e r s i t y O c c a s s i o n a l Paper,No.15,1970,pp26-43. G a r r i s o n , W.L., " C o n n e c t i v i t y of the i n t e r s t a t e highway system", Papers and Proceedings of the Regional  Science Assoc., Vol.6, 1960, pp121-137. G a r r i s o n , W.L. and D.F. Marble, "A prolegomenon to the f o r e c a s t i n g of t r a n s p o r t a t i o n development", T r a n s p o r t a t i o n Centre, Northwestern U n i v e r s i t y , Research Report4, 1965. Gauthier, H., " T r a n s p o r t a t i o n and the growth of the Sao Paulo economy", J o u r n a l of Regional S c i e n c e , Vol.8,No.1, 1968, pp77-94. G e t i s , A. and B.N.Boots, Models of S p a t i a l Processes, Cambridge: Cambridge U n i v e r s i t y Press, 1978. G i l b e r t , E.N., "Random plane networks", SIAM J o u r n a l of  A p p l i e d Mathematics, Vol.9, 1961, pp533-543. G i l b e r t , G.N.,"Convexity of H i l l Tops",Journal of  Geology, Vol.17, 1969, pp344-50. Goodwin, A.W., G.D.Vannatta and H.P. Fawcett, Geometry: A U n i f i e d Course Columbus: C h a r l e s E. M e r r i l l Books, Inc., 1961. 177 Hagerstrand, T.,"Innovation D i f f u s i o n as a S p a t i a l Process", T r a n s l a t e d by A.Pred, Chicago: U n i v e r s i t y of Chicago Press,1967. Haggett, P., L o c a t i o n a l A n a l y s i s i n Human Geography, Toronto: MacMillan Co., 1965. Haggett, P.and R.J.Chorley, Network A n a l y s i s i n  Geography, London: Edward A r n o l d Ltd.,1969. Haggett, P., A . D . C l i f f and A.Frey, L o c a t i o n a l A n a l y s i s i n  Human Geography, London: A r n o l d , 1977. Harary, F., Graph Theory, Reading: Addison-Wesley, 1969. Horton, R . E . , " E r o s i o n a l development of streams and t h e i r drainage b a s i n s : h y d r o p h y s i c a l approach to q u a n t i t a t i v e morphology", B u l l e t i n of the G e o l o g i c a l  S o c i e t y of America, V o l 56, 1945, pp275-370. Huff, D.L., "A t o p o g r a p h i c a l model of consumer space p r e f e r e n c e s , " Papers and proceedings of the Regional  Science Assoc., Vol.6, 1960, pps159-173. James, G.A., A . D . C l i f f , P.Haggett and J.K.Ord, "Some d i s c r e t e d i s t r i b u t i o n s of graphs with a p p l i c a t i o n s t o r e g i o n a l t r a n s p o r t networks", G e o g r a f i s k a Annaler, Vol.52B, 1970, pp14-21. Kansky, K.J., S t r u c t u r e s of T r a n s p o r t a t i o n Networks, U n i v e r s i t y of Chicago: Department of Geography, Research Papers, No.84, 1963. K o l a r s , J . and H.J.Malin, " P o p u l a t i o n and a c c e s s i b i l i t y : an a n a l y s i s of T u r k i s h r a i l r o a d s " , G e ographical  Review, Vol.60,No.2, 1970, pp229-246. Lachenbruch, A.H., "Mechanics of thermal c o n t r a c t i o n c r a c k s and ice-wedge polygons i n permafrost", G e o l o g i c a l S o c i e t y of America, S p e c i a l Papers, Vol.70,1962. Lankford, P.M., " R e g i o n a l i z a t i o n : theory and a l t e r n a t i v e a l g o r i t h m s " , Geographical A n a l y s i s , V o l . 1 , No.2, 1969, PPS196-212. L e f e v e r , D.W., "Measuring geographic c o n c e n t r a t i o n by means of the Standard D e v i a t i o n a l E l l i p s e , " T h e  American J o u r n a l of S o c i o l o g y , Vol.XXXII,No.1, 1926, pps88-94. Leopold, L.B. and W.B. Langbein, "The concept of entropy i n landscape e v o l u t i o n " , U n i t e d S t a t e s  G e o l o g i c a l Survey, P r o f e s s i o n a l Papers, 1962. 178 Lowe, J.C. and S.Moryadas, The Geography of Movement, Boston: Houghton M i f f l i n Co., 1975. Mackay, J . Ross, "Pingos of the Tuktoyaktuk P e n i n s u l a Area, Northwest T e r r i t o r i e s " , Geographie Physique et Q u a t e r n a i r e , Vol.XXXIII, No.1, 1979, pp3-61. Matula, D.W. and R.R. S o k a l , " P r o p e r t i e s of G a b r i e l graphs r e l e v a n t t o geographic v a r i a t i o n r e s e a r c h and the c l u s t e r i n g of p o i n t s i n the plane", G e o g r a p h i c a l  A n a l y s i s , Vol.12,No.3, J u l y 1980, pps205-222. Mark, D . , " T o p o l o g i c a l randomness of Geomorphic s u r f a c e s " , Department of Geography, Simon F r a s e r U n i v e r s i t y , Ph.d. t h e s i s (unpublished)1977. Nystuen, J.D., and M.F.Dacey, "A graph theory i n t e r p r e t a t i o n of nodal r e g i o n s " , Papers and  Proceedings of the Regional Science Assoc., V o l . 7 , 1961, pp29-42. Radke, J.D., " S t o c h a s t i c models i n c i r c u i t network growth", Department of Geography, W i l f r i d L a u r i e r U n i v e r s i t y , Master's T h e s i s , (unpublished) 1977. Radke, J.D., "Bounding c l u s t e r s i n s p a t i a l p o i n t p a t t e r n s " , Presented at the annual Canadian Assoc. of Geographers meetings, Montreal, 1980. Raine, J.W., "Summarizing p o i n t p a t t e r n s with the Standard D e v i a t i o n a l E l l i p s e " , Area,Vol.10,No.5,1978,pp328-333. Rimmer, P.J., " R e d i r e c t i o n s i n t r a n s p o r t a t i o n geography", Progress i n Human Geography,Vol.2,No.1,1978,pp76-100. Rosenberg, B. and D.J. Landgridge, "A computational view of p e r c e p t i o n " , P e r c e p t i o n , Vol.2, 1973, pps4l5-424. Schaefer, F .K.,"Exceptionalism i n Geography: A M e t h o d o l o g i c a l Examination", Annuals of the AAG, Vol.43,No.3, 1953, pp226~49. S c o t t , A.J., C o m b i n a t o r i a l programming, s p a t i a l a n a l y s i s  and p l a n n i n g , London: Methuen, 1971. Shreve, R.L., " S t a t i s t i c a l law of stream numbers", J o u r n a l of Geology, Vol.74,No.1, 1966, pp17-37. Shreve, R.L., " I n f i n i t e t o p o l o g i c a l l y random channel networks", J o u r n a l of Geology, Vol.75,No.1, 1967, pp178-l86. 179 S i e g e l , S., Nonparametric S t a t i s t i c s , Toronto: McGraw-Hill Book Company, 1956, p127. Simons, P.L., "Measuring the shape d i s t o r t i o n s of r e t a i l market areas", G e o g r a p h i c a l Analysis,Vol.7,No.4, 1975, pp33l-340. Smart, J.S., "The t o p o l o g i c a l p r o p e r t i e s of channel networks", IBM Research, RC 2310, No.11312, 1968. T a y l o r , P.J., "Distance decay i n s p a t i a l i n t e r a c t i o n s " , CATMOG S e r i e s (1975). T a y l o r , P.J., Q u a n t i t a t i v e Methods i n Geography, Boston: Houghton M i f f l i n Company, 1977. T i n k l e r , K.J., " C h a r a c t e r i z i n g graphs of networks that a l l have the same l o c a l s t r u c t u r e , " Presented a t the A s s o c i a t i o n of American Geographers 73rd Annual Meeting, New Orl e a n s , 1978. T i n k l e r , K.J.,"Graph Theory", Progress i n Human  Geography, Vol.3, No.1, 1979, pps85-1l6. T o u s s a i n t , G.T., "The r e l a t i v e neighbourhood graph of a f i n i t e planar s e t " , P a t t e r n R e c o g n i t i o n , Vol.12,No.4, 1980. T o u s s a i n t , G.T. and R. Menard, "Fast a l g o r i t h m s f o r computing the plan a r r e l a t i v e neighbourhood graph", Proceedings 5th Symposium on Operations Research, Koln, August, 1980. To u s s a i n t , G.T., "P a t t e r n r e c o g n i t i o n and ge o m e t r i c a l complexity", Proceedings of 5th I n t e r n a t i o n a l  Conference on P a t t e r n R e c o g n i t i o n , December, 1980. Ullman, E.L., "The r o l e of t r a n s p o r t a t i o n and the b a s i s f o r i n t e r a c t i o n " , i n W i l l i a m L. Thomas (ed.), Man's  Role i n Changing the Face of the E a r t h , Chicago: U n i v e r s i t y of Chicago Press, 1956, pp862-880. Warntz, W., " T r a n s - A t l a n t i c paths and pressure p a t t e r n s " , The Geographical Review, Vol.51,No.2, 1961, pp187-212. Warntz, W., "A note on s u r f a c e s and paths and a p p l i c a t i o n s to g e o g r a p h i c a l problems", Ann Arbor, Michigan: Michigan I n t e r - u n i v e r s i t y Community of  Mathematical Geographers, D i s s c u s s i o n Paper No. 6, 1965. Warntz, W.,"The topology of socio-economic t e r r a i n and s p a t i a l flows", Papers of the Regional Science  A s s o c i a t i o n . Vol.17, 1966, pp47-61. 180 Warntz, W., "Global s c i e n c e and the tyranny of space", Papers of the Regional Science  Assoc.,Vol.19,I967,pp7-19. Warntz, W., "A note on stream o r d e r i n g and contour mapping", Harvard Papers i n T h e o r e t i c a l Geography, Vol.18, 1968, pp1-30. W i l l s , M.J., "Linear and n o n - l i n e a r e s t i m a t o r s of the 0-D matrix", Department of Geography, The U n i v e r s i t y of B r i t i s h Columbia, Ph.d. t h e s i s (unpublished) 1978. Woldenberg, M.J., "Geography and p r o p e r t i e s of s u r f a c e s " , Harvard Papers i n T h e o r e t i c a l Geography, Vol.13^ 1967, ppl-36. Woldenberg, M.J. and B.L.Berry, "R i v e r s and c e n t r a l p l a c e s : analogous systems?". J o u r n a l of Regional  Sc i e n c e , Vol.7, No.2., 1967, pp129-139. Woldenberg, M.J., " S p a t i a l order i n f l u v i a l systems: Horton's laws d e r i v e d from mixed hexagonal h i e r a r c h i e s of drainage b a s i n s " , B u l l e t i n of the G e o l o g i c a l  S o c i e t y of America, Vol.80,1969,pp97-112. Websters' T h i r d New I n t e r n a t i o n a l D i c t i o n a r y , P .B.Gove(edTtor), S p r i n g f i e l d : G.& C. Merriam Co.,1971. Werner, C.,"The r o l e of topology and geometry i n o p t i o n a l network de s i g n " , Papers of the Regional Science  Assoc., Vol.XXI,1976,p176. Y u i l l , R.S., "The Standard D e v i a t i o n a l E l l i p s e ; an updated t o o l f o r s p a t i a l d e s c r i p t i o n " , G e o g r a f i s k a  Annaler,Vol.53B,1971,pp28-39. Zahn, C.T., " G r a p h - t h e o r e t i c a l methods f o r d e t e c t i n g and d e s c r i b i n g g e s t a l t c l u s t e r s " , IEEE Trans. Computers, Vol.C-20, January 1971, pps68-86. 181 APPENDIX A negative a-shape 3-skeleton 182 APPENDIX B Quadrat Divisions of the Hypothetical C i r c u i t Network. 183 Quadrat 1 Quadrat Divisions of the Saltspring Island Road Network. 184 Quadrat 1 Quadrat 3 Quadrat 2 Quadrat 4 Quadrat Divisions of the B r i t i s h Columbia Major Road Network. 185 Quadrat 1 Quadrat 3 Quadrat 2 Qua drat "4" Quadrat D i v i s i o n s of the Saskatchewan Major Road Network. 186 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0095874/manifest

Comment

Related Items