$3. . . . ”AHA , , , , “Ham, . . . u . ha. "or“...l‘...‘ Bin-vulva. V .. , r . . am... am“... YLV . . . , ‘ _ . 2%, ... L. h adfl‘mr s 3‘ n... .\. .6. v2!!! 1...: .3. y 1!. :Q V. y . AI\.5 . 3.1... 1:; .3! U ”Par?" ‘64 :3... .u: .l 1‘14: 1. finiélfigsmzvnfikau .ummawu. «13% 51‘: 1. 1i 2. ‘u. ; ... ..@¢§.. .$“~.§E~;@%.wm m. .ngmuifimm$.a%¢fi.. . 2 1 v . .5131 |I| || “m * LIBRARY 2 Michigan State 77W f University This is to certify that the dissertation entitled LOGGERS AND FOREST FRAGMENTATION: - BEHAVIORAL AND COMPUTATIONAL I MODELS OF ROAD BUILDING IN THE AMAZON BASIN presented by EUGENIO YATSUDA ARIMA has been accepted towards fulfillment of the requirements for the PhD degree In GEOGRAPHY flfifinf‘ WM Major Professor’ 5 Signature flu? / 1. 2519;“ Date MSU is an Affirmative Action/Equal Opportunity Institution PLACE IN REfURN BOX to remove this checkout from your record. T O AVOID FINES return on or before date due. MAY BE RECALLED with earlier due date if requested. DATE DUE DATE DUE DATE DUE 2/05 e/CI-ncloaxeom'——.mms‘ LOGGERS AND FOREST FRAGMENTATION: BEHAVIORAL AND COMPUTATIONAL MODELS OF ROAD BUILDING IN THE AMAZON BASIN By Eugenio Yatsuda Arima A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Geography 2005 ABSTRACT LOGGERS AND FOREST FRAGMENTATION: BEHAVIORAL AND COMPUTATIONAL MODELS OF ROAD BUILDING IN THE AMAZON BASIN By Eugenio Yatsuda Arima Although a large literature now exists on the drivers of tropical defor- estation, less is known about its spatial manifestation. This is a critical shortcoming in our knowledge base, since the spatial pattern of land cover change, and forest fragmentation in particular, strongly affect biodiversity. The purpose of this dissertation is to consider emergent patterns of road networks, the initial proximate cause of fragmenta- tion in tropical forest frontiers. Specifically, I address the road building processes of loggers, who are very active in the Amazonian landscape. To this end, I develop an explanation of road expansions combining a theoretical model of economic behavior with GIS software in order to mimic the spatial decisions of road builders. I simulate three types of road extensions commonly found in the Amazon basin. The first two types are roads that spur off the initial infrastructure constructed by the government in official settlement areas such as the Transamazon and are related to the fishbone pattern of fragmentation. The third type of roads are the skid trail networks, built to access individual trees. I developed several raster based GIS algorithms to model each type of road. Although my simulation results are only partially successful, they call the attention to the role of multiple agents in the landscape, the importance of legal and institutional constraints on economic behavior, and the power of GIS as a research tool. Copyright by © Eugenio Yatsuda Arima 2005 All Rights Rcscrvcd To Norma, for her unlimited support and love. This degree belongs to her. To my parents and my brother, who always encouraged me to pursue my Ph.D. ACKNOWLEDGMENTS Many people have helped me get this far. First and foremost, I would like to thank my advisor, Bob Walker, who suggested this research tepic and convinced me I could get an interesting dissertation. I also thank him for all the support from the first day I arrived in East Lansing until today. Several people have asked me how to choose an adviser. After this experience, I know the answer: look for someone who is genuinely interested in your success and also someone who you can call friend. My committee also played an important role. Jeffrey Wooldridge, Ashton Short- ridge, and Antoinette Winklerprins were the best instructors I ever had and am thankful for what I learned from their incredible knowledge pool. They also provided important constructive criticism during the whole dissertation process. Stephen Perz, who is also in my committee, and Marcellus Caldas were great part- ners in the field. Many insights, observations, and ideas presented in this dissertation were generated during the many discussions we had. The people of Uruara were always very welcoming to the field work team. In particular, I would like to thank Arnildo and Sérgio Karpinski for the many helpful information provided and the Hotel Amazonas’ owners for their hospitality. Stephen Aldrich provided the official roads’ dataset used in Chapter 2, Cynthia Simmons provided the vector data file used in figure 1.2., and Jimmy Grogan, Franklin Pantoja, Edson Vidal, and Dennis Vale from Imazon provided the dataset used in Chapter 4. Thank you all for sharing data. Bruce Pigozzi suggested many references that were very helpful to contextualize vi my work into the human geographical and locational theory literature. Carlos Souza Jr. from Imazon introduced me to IDL and gave me a four-hour crash course back in 2003. Later, Joe Messina made me practice IDL in his geoprocessing class. Thanks for showing the advantages of this programming language. Richard Groop, chair of the department, and the secretaries Judy Reginek, Sharon Ruggles, and Marylin Bria were always accessible and willing to help me resolve bureaucratic and academic issues. This dissertation was typed in 153% using a macro template, created by Brian J. Olson (Department of Mechanical Engineering at Michigan State University), that adheres to the formatting rules of MSU. In my first three years in graduate school, I was a. research assistant for the project ‘Socio—spatial processes of road extension and forest fragmentation in the Amazon’ funded by the National Science Foundation and for the project ‘A basin—scale econometric model for projecting future Amazonian landscapes’ funded by NASA- LBA. Throughout these years, I also received several small grants for field work and conference participation. I would like to recognize the support from Kenneth Corey, Harm deBlij, and Robert Thomas, whose funds have supported many graduate stu- dents in the Department of Geography. I also received support from the College of Social Sciences, the Center for Latin American and Caribbean Studies (Tinker Field Research Grant), and the Environmental Science & Policy Program at Michigan State University. Finally, I would like to thank all friends for life I made in East Lansing, in par- ticular Cleusa & Eraldo, Martha & Marcellus, Cynthia & Bob, and Steve Aldrich; and the many Brazilian Community Association members who also helped warm up the long and cold winters. Their friendship continuously recharged my batteries and made this journey more pleasant. vii TABLE OF CONTENTS LIST OF TABLES x LIST OF FIGURES xi LIST OF ABBREVIATIONS xiii 1 Introduction 1 1.1 The Environment and Roads in Forest Frontiers ............ 4 1.1.1 Environmental Impacts ...................... 4 1.1.2 Roads and the Social Science Literature ............ 7 1.1.3 Official and Unofficial Roads ................... 10 1.2 Objectives ................................. 15 1.3 Study Area ................................ 16 2 The Evolution of the 'D‘ansportation Network System in the Brazil- ian Amazon and Overall Deforestation Pattern 23 2.1 A Brief History of Transportation in the Amazon ........... 24 2.2 Read Pattern and Deforestation Pattern ................ 41 2.3 The Endogenous Road Debate ...................... 48 3 Modeling Road Patterns 57 3.1 Roads and Land Cover Change ..................... 58 3.1.1 Roads off the Transamazon Highway .............. 59 3.1.2 Loggers and Road Building ................... 61 3.2 A Conceptual Framework for Logging Firm Behavior ......... 62 3.2.1 Indeterminate Roads ....................... 64 3.2.2 Determinate Roads ........................ 68 3.3 Computational Models of Roads ..................... 69 3.3.1 Destination Indeterminate .................... 78 3.3.2 Destination Determinate ..................... 80 3.4 Discussion ................................. 85 4 Modeling Logging Skid Trails 93 4.1 Skid Trails ................................. 97 viii 4.2 All Introduction to Complexity Theory ................. 99 4.3 Graph Theory and the Steiner Tree Problem .............. 103 4.4 Modeling logging skid trails in a. GIS .................. 113 4.5 The Dataset ................................ 123 4.6 Results ................................... 127 4.7 Discussion ................................. 135 5 Conclusions 139 APPENDICES 145 A Field Interviews 145 B IDL Program to Calculate Directional Dependent Slope Least Cost Surfaces 147 C IDL Program to Record the Paths in a raster grid 159 BIBLIOGRAPHY 163 ix 1.1 2.1 2.2 2.3 4.1 LIST OF TABLES Deforestation rates in the Brazilian Amazon (km2 year‘l) ...... 21 Main rivers of the Amazon Basin .................... 25 Evolution of the federal and state road system (km) .......... 37 Evolution of the road system by State (km) .............. 38 Network building cost and processing time spent in each algorithmic solution. .................................. 135 1.1 1.2 1.3 1.4 2.1 2.2 2.3 2.4 2.5 2.6 2.7 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 4.1 4.2 4.3 4.4 4.5 4.6 LIST OF FIGURES Images in this dissertation are presented in color Federal and State Road System in the Brazilian Amazon ....... 13 Unofficial roads in a 100 km buffer along the Transamazon Highway . 14 The Amazon Region ........................... 18 Study areas in Uruara - Para and logging site in Acre, Brazil. . . . . 22 Main Rivers of the Brazilian Amazon Basin .............. 28 Roads (Panel A) and railways (Panel B) in the Brazilian Amazon - 1957 31 Evolution of the road system in the Brazilian Amazon from 1968 to 1993 34 Major network patterns ......................... 43 Deforestation and fragmentation patterns ............... 44 Geometric configuration of the lots along the Transamazon Highway . 46 Existing towns prior to 1957 and the design of the Federal road system 54 Portion of the Transamazon region in Para State. ........... 59 Description of the Horn algorithm used to calculate slopes ...... 76 Perspective view of the Transamazon Highway. Landsat ETM+ image (2000) draped over DEM (SRTM) vertically exaggerated fifteen times. 77 Destination indeterminate simulation ................... 81 Major destination determinate logging roads in Uruara ......... 82 Simulation of destination determinate Transiriri logging road. . . . . 84 Simulated Transtutui' with destination determined at junction of Uruara and Tutui Rivers .......................... 86 Simulated Transtutui with pontos obr'igato'rz'os (mandatory waypoints) included ................................... 87 Euclidean Minimum Steiner, Spanning, and Rectilinear Trees ..... 95 Raster data model ............................ 104 Acyclic and cyclic graphs ......................... 105 Example of a fictitious least cost path between two terminals ..... 107 Ordinary least cost path for a triangle in a raster model ........ 108 I\=‘Iinimum network in a raster model with 3 terminals ......... 110 xi 4.7 Algorithm to generate the least cost convex hull set ........... 117 4.8 Pseudocode for the spanning/ rectilinear tree algorithm ......... 119 4.9 Pseudocode for the 3-terminal Steiner problem ............. 122 4.10 Location of the logging extraction site in Acre State, Brazil. ..... 124 4.11 Area surveyed and sampled points for height measurement ....... 126 4.12 Grid DEM template with surveyed trees’ locations (terminals) . . . . 128 4.13 A - Convex hull and B — Least cost convex hull set. .......... 129 4.14 3D shaded View of the least cost path (in red) from BR-364 to the logging extraction site, vertically exaggerated fifteen times ....... 131 4.15 Ordinary solution to the least cost path. ................ 132 4.16 The ‘spanning tree’ network for 105 terminals and one origin. . . . . 133 4.17 Logging skid trail network using the 3-terminal Steiner algorithm. . . 134 xii BNDES DEM ESRI ETM+ GIS IBAMA IBGE IDL IMAZON INCRA INPE LCCHS MSTaa LMTAP NASA PDA PK: iuN SPVEA SRTM TIN USGS UTM LIST OF ABBREVIATIONS Banco N acienal dc Desenvelvimento Economico e Social Digital Elevation Model Environmental Systems Research Institute Enhanced Thematic Mapper Plus Geographic Information System Institute Brasileiro do Meio Ambiente c dos Recursos Naturais Renovaveis Institute Brasileiro de Geografia e Estatistica Interactive Data Language Institute do Homem e Meio Ambiente da Amazonia Instituto Nacional de Celenizacae e Reforma Agraria Institute N acional de Pesquisas Espaciais Least Cost Convex Hull Set Minimum Steiner Tree (Problem) Multiple Target Access Problem National Aeronautics and Space Administration Plane de Desenvolvimente da Amazenia Plane Integrade dc Colonizaeae Plano de Integraeao Nacional Superintendéneia do Plane dc Valerizaqae Economica da Amazenia Shuttle Radar Topography Mission Triangulated Irregular Network United States Geological Survey Universal Traverse Mercator xiii CHAPTER 1 Introduction Global environmental change resulting from anthrepegenic impacts on land cover and land use is widely recognized as an important issue (Ojima, Galvin, & Turner, 1994). One such change, tropical deforesta- tion, has been of great concern to scientists and the public at large because of its possible effects on climate and biodiversity (Steffen & Tyson, 2001; Jenkins, 2004). A large literature on the issue has emerged in recent decades, and geographers and social scientists have made great strides to understand the factors that motivate humans to clear forested lands in tropical regions (Lambin, Geist, & Lepers, 2003). Although we now know much about the human drivers in this regard, we knew far less about the actual spatial pattern of forest degradation and less. This is a critical shortcoming in our knowledge base given the link between biodiversity and forest fragmentation implied by island biogeegraphy (Whittaker, 1998). Roads and market accessibility more generally have long been rec- ognized as important factors affecting land cover and land use, in both tropical and temperate settings. Indeed, in the Brazilian Amazon nearly 90% of deforestation has occurred within a 100 km buffer of roads built by the federal government (Alves, 2002). The extension of transportation infrastructure into tropical frontiers, especially roads, induces in-migratien, increases agricultural rents, and fosters economic development. As a consequence, land covers are transformed into hu- man artifacts by the urban and agricultural use of land. Although roads appear to be linked to aggregate measures of deforestation, they are also inherently spatial phenomena, and patterns of forest fragmentation are in large part determined by the architecture of the transportation net- work implemented. Thus, understanding how the spatial architecture of a road network emerges is key to gaining insight into fragmentation. Read construction has usually been associated with governmental venture. However, roads built by the private sector, often loggers, have been playing an important role in the dynamics of the frontier expansion in the Amazon, the largest tropical forest remaining in the world (Verissimo et al., 1995). Previous research on the Amazon has yet to systematically document the link between the socioeconomic- spatial processes driving logging road construction and the geometric signature of road networks on landscapes and ecosystems. On the one hand, the ecology and remote sensing literature approaches the issue of roads as a purely spatial phenomenon, and emphasizes the ensuing environmental impacts of habitat fragmentation without attending to the social processes driving road construction in the first place. Social scientists, on the other hand, have only addressed the aggregate impact of road construction on deforestation, a rather blunt measure given the important ecological implications of various spatial geometries of forest fragmentation. As a result, a gap remains between the knowledge bases of ecological and social scientists concerned about links between roads and environmental change. The expansion of the road network in the Brazilian Amazon basin, beyond the initial development highways constructed by Federal and State governments, is mainly driven by the logging sector interacting with both planned and spontaneous colonization. Thus, to understand the processes of fragmentation currently affecting the Amazon basin, it is necessary to understand the road building activities of loggers. My dissertation is aimed specifically at these agents of land-cover change. This research aims to provide (1) insight into logger road building ac- tivities and (2) a simulation approach to predict the spatial outcomes of their economic behavior. The results of this dissertation shed light on the spatial pattern of road building, which has profound implica- tions for biodiversity conservation and sustainable development of the region. This introductory chapter is organized as follows. I first provide an overview of the ecological importance of forest fragmentation patterns to the conservation of biological diversity in tropical forests. Then, I examine the social science literature on the relationship between roads and deforestation. The goal of this literature review is to show that social scientists have not provided an explanation on how forest frag- mentation patterns emerge, which is a critical piece of information to landscape ecologists, and environmental scientists more generally. I conclude by explaining the overall objectives of the dissertation and introducing the study area. 1.1 The Environment and Roads in Forest Fron- tiers 1.1.1 Environmental Impacts The environmental impacts of roads are of particular concern in regions where infrastructure networks are expanding rapidly in areas of high ecological value, such as the Amazon basin (W. F. Laurance, 1998; Schelhas & Greenber, 1996; Reid & Bowles, 1997). Reads can impact biodiversity directly or indirectly. The direct im- pact is related to the physical barrier imposed on the movement of certain species. For example, Laurance et a1. (2004) showed that reads significantly reduced the movement of understory forest-dependent in- sectivorous birds and that certain species tended to avoid edge-affected habitats near roads and road clearings themselves. Another concern for ecologists is the large number of animals killed by traffic. In this re- gard, many studies have been conducted in developed countries, where the road density is very high, to calculate read kills.1 I have not found assessments of animals killed on roads in the Amazon but based on my personal, qualitative observations, the number of reptiles (snakes, lizards), mammals, and birds killed by vehicles is significant. A dead animal in an Amazonian road stretch is a very frequent event to ob- serve, particularly far from large population centers. More important than the direct impacts of roads on tropical forests are the indirect impacts of roads as determinants of the ensuing frag- mentation pattern caused by deforestation. This indirect impact is of most concern to ecologists because of its greater effect on biodiversity. When continuous forested landscapes are converted to non-forest cov- ers, the consequences for biodiversity can be severe. With very few ex- ceptions, tropical rain forest fragmentation leads to local loss of species (Turner, 1996). 1 The number of deer killed annually on roads in the US. ranges from 720,000 to 1.5 million (Forman, 2003). In Montana, Fowle (1990) recorded 205 turtles killed during a four month summer period on a 7.2 km road segment. In Australia. 5.5 million reptiles and frogs are estimated to be killed annually by traffic (Ehmann & Cogger, 1985). Forest fragmentation alters vegetative structure and available habi- tats for many species (Aldrich & Hamrick, 1998; W. F. Laurance, 1998; Scariot, 1999; W. F. Laurance, Perez-Salicrup, et al., 2001). Frag- mentation may modify or even curtail vegetative regeneration (Love- joy et al., 1986) through heightened tree mortality (Ferreira & Lau- rance, 1997; W. F. Laurance et al., 2000) and reduced seedling recruit— ment (Benitez—Malvido, 1998). Such changes result in biomass collapse (W. F. Laurance et al., 1997) and carbon emissions that contribute to global climate change (Gash et al., 1996; Fearnside, 1997). Further, road construction in tropical frontiers can contribute to feedback mech- anisms that catalyze destructive changes in forest ecology. Fragmen- tation raises ground temperatures and reduces precipitation, thereby elevating the risk of drought. This, paired with increased litter fall from dying trees, accentuates the likelihood of fires (Uhl & Kauffman, 1990; Cochrane & Schulze, 1999; Nepstad, Moreira, & Alencar, 1999). Thus, the risk of forest fire is linked to roads and forest fragmentation (Holdsworth & Uhl, 1997; Nepstad et al., 2001). The many ecological impacts of forest fragmentation depend on the size and spatial organization of the fragments themselves. Studies have shown that ( 1) microclimate, soil moisture, wind speed, and luminos- ity, are strongly correlated with distance to fragment boundaries, and that (2) these factors determine the likelihood of tree survival and the presence of animals (Murcia, 1995). This phenomenon is commonly known in the landscape ecology literature as the ‘edge effect.’ Smaller fragments, and those with longer perimeters relative to area, tend to exhibit greater ecological disturbance than large fragments with exten- sive interiors (W. F. Laurance et al., 1997). In a study conducted in forested areas in southern Ghana, Hill (2003) found that large forest fragments contained the greatest number of tree species and the highest proportion of rare tree species. On the other hand, very small fragments lose most of their vertebrate fauna and are floristically completely dif- ferent than an expansive forested landscape (Turner, 1996). Rates of tree deaths can be up to eight times higher in edge than non-edge sites (Ferreira & Laurance, 1997). 1.1.2 Roads and the Social Science Literature Social scientists have helped ecologists understand the drivers of land- scape change, and in the case of the Amazon, the underlying causes of deforestation (Kaimowitz & Angelsen, 1998; Geist & Lambin, 2001). There are by new a multitude of studies that attempt to understand why humans convert forests into non-forested land uses. In the 19803 and early 19903, social scientists implemented statistical and com- putable general equilibrium models to understand why certain countries or regions cut down their forests more rapidly than others. Some of the explanations included economic and population growth and density, exchange rates, interest rates, debt level, political and institutional fac- tors, and density of roads (Allen 81. Barnes, 1985; Rudel, 1989; Deacon, 1994, 1995; Brown & Pearce, 1994; Reis & Guzman, 1994; Cropper, Griffiths, & Mani, 1996). However, such models employ spatially ag— gregated measures of roads and forest loss for municipalities and other administrative units. This leaves us with blunt measures of road net- works and land cover change that contain no information about road network architecture or the spatial geometry of forest fragmentation. In addition, aggregate models generally observe the state of roads and land cover using cross-sectional data, which hinders inferences about landscape dynamics over time. More recently, with the advent of GIS technology, social scientists have implemented the so called ‘spatially explicit model’, which repre- sents an advance beyond models based on aggregate land cover data (Walker, 2004). Typically, spatially explicit models use satellite im- age pixels as units of observation, and estimate the probability of land cover change in pixels with different socioeconomic and locational char- acteristics (Ludeke, Maggie, & Reid, 1990; Bockstael, 1996; Chomitz & Gray, 1996; Nelson & Hellerstein, 1997). The refined spatial reso- lution of the data allows for estimation of the effects of roads on the probability of forest being converted, as well as mapping of modeled probabilities. Spatially explicit models of land cover change reveal sig- nificant road impacts, and maps of modeled probabilities often indicate fragmentation as a result of the road network. Moreover, spatially ex- plicit models using data from multiple points in time have produced estimation results that have been used to project trajectories of future landscape evolution (Mertens & Lambin, 2000). Although spatially explicit models represent a significant advance, they often assume a limited concept of the roles played by roads in land cover change. All roads are presumed to be built by governments in the pursuit of regional development. Hence, all subsequent settlement, forest clearing, and fragmentation is a consequence of this initial infras- tructure. While such a presumption no doubt holds in many instances, it only reflects part of the story, and overlooks the role of other non- government agents in maintaining and especially in extending roads. Indeed, once settlement has occurred in response to the state’s road building efforts, local agents in newly opened regions often take it upon themselves to amplify the road network following initial efforts at land cover change. At the local level, then, road building is both a cause and a consequence of the processes of colonization and development, and not merely an exogenous factor. 1.1.3 Official and Unofficial Roads Despite the potential for ecological damage, the development of trans- portation infrastructure has been viewed as key to efforts at economic development, particularly in developing countries (Vance, 1986; Owen, 1987). Early investment in railroads proved critical to the integration of the US economy, and roads and transportation more generally have often been implemented in advance of demand for transportation ser- vices in frontier areas (Friedmann & Stuckey, 1973). The expansion of road infrastructure in the Brazilian Amazon basin is no exception, and during the 19708 highway construction was a hallmark of state-led de- velopment efforts in the region (Goodland & Irwin, 1975; Mahar, 1979; Smith, 1982). The federal roads built to connect the Amazon region to other parts of Brazil stimulated in—migration by landless families as well as capitalized ranchers, loggers, and mining firms, and by the late 19808, massive deforestation was taking place in the name of re- gional development, a trend that continues today (Mahar, 1988; Hecht & Cockburn, 1989; Skole & Tucker, 1993; Walker, 2004). Government investment in transportation infrastructure is impor- tant to regional development, but it only reflects part of the story, and overlooks the role of private citizens and local agents in maintaining and especially in extending the initial road networks. Indeed, once set- tlement occurred in the Amazon basin, newly arrived individuals, both 10 loggers and colonists, took it upon themselves to extend the federal system in ways suitable to their own specific interests and objectives (Walker, 2003a). One implication is that the mechanisms driving road construction are scale—dependent (Gibson, Ostrom, & Ahn, 2000; Wood & Porro, 2002). On a regional scale, roads are built by governments to improve the accessibility of resource-rich regions for the sake of national development. On the local scale, road building involves the extension of infrastructure by individuals on site seeking to exploit resources for private benefit. For example, logging firms construct new roads when seeking to exploit timber stands made valuable by timber depletion near existing roads, especially if timber prices rise or credit lines be- come available to facilitate infrastructure investments (Walker, 1987; Repetto & Gillis, 1988; Kummer & Turner II, 1994). A second implication of the sequential nature of infrastructure de- velopment in frontier areas is that patterns of fragmentation are likely to be linked to scale and the type of road-building agent active in the landscape. In the Amazon basin, highways constructed by federal and state level agencies involve different methods and materials than read extensions by local agents. Local agents, such as loggers and colonists, pursue different spatial objectives than do state bureaucrats, which af- fects the spatial architecture of the lower order networks they build. In addition, their wide dispersion results in a much more dissected pattern 11 than the one created by the state for development purposes. While the federal system exposes regions to in-migration and land occupation, roads built by private agents are the main proximate cause of fragmen- tation by virtue of their density. Lineal distance of the federal road system, as of 1993, covered 18,177 kilometers, or a density of 0.004 km of road per square kilometer of the Legal Amazonia (Figure 1.1). This stands in sharp contrast with the density of 0.062 km of private road per square kilometer in the study area along the Transamazon Highway between Altamira and Rurepolis (Figure 1.2). Clearly, roads built by local citizens represent a much great proximate threat to the integrity of Amazonian forests than the sparse federal system. Remote sensing scientists have made progress to better understand such lower order, private, unofficial roads. They have been able to clas- sify, identify, and map them using new remote sensing techniques, such as linear spectral mixture models, that improved their ability to detect logging roads from satellite images in several different environments, when compared to visual interpretation and maximum likelihood meth- ods (Souza Jr. & Barreto, 2000; Monteiro, Souza, & Barreto, 2003). Likewise, new sensors and higher spatial resolution satellite images (e. g. IKON OS) can enhance the ability to detect logging roads (Asner et al., 2002; Souza Jr & Roberts, 2005). The emphasis of most of the related remote sensing research literature has been on road signature detection 12 Legend Roads - 1993 — Federal — State Modis 2001 - Land Cover r———I—_I 0 500 1.000 Kilometers Figure 1.1. Federal and State Road System in the Brazilian Amazon and forest degradation assessment. Social scientists have not profited greatly from the advances in remote sensing in efforts to develop theo- retical models or to empirically understand how such roads are built. This brief review of the literature suggests three conclusions that me- tivate my dissertation research. First, the pattern of forest fragmenta- tion is an important piece of information of great interest to landscape ecologists and environmental scientists more generally. The geomet- ric shape of forest patches and their isolation or contiguity, resulting from deforestation processes, is vital to the viability of many plant and 13 Legend — Secondary roads — Transamazon Highway 100 km buffer area ‘J‘fl'l‘l f1) f—T—‘—*—T—'—’_q—I $ 0 25 50 100 Kilometers Figure 1.2. Unofficial roads in a 100 km buffer along the Transamazon Highway Unofficial roads data provided by Simmons (2002) animal populations. Second, roads play an important role in deter- mining overall levels of deforestation and resulting landscape patterns, and third, social scientists, although aware of the causes of deforesta- tion, have not fully explained how deforestation patterns are generated in the first place. Hence, understanding the underlying drivers of for- est fragmentation requires comprehension of the spatial architecture of the road networks that create the geometry of forest fragments. A key objective of the dissertation is to do this for an important class of Ama- 14 zonian roads, namely those built by private citizens, mainly loggers, in frontier settlements. 1.2 Objectives I have two overarching objectives in this dissertation. The first is to provide a theoretical explanation of loggers’ road construction behav- ior. To this end, I borrow from the microeconomic theory of the firm to explain how loggers optimally allocate scarce capital resources to maximize profits in their search for wood. The second objective is op- erational. The theory itself is abstract in the sense that it does not deliver a spatial product. Since I am interested in studying spatial patterns of road networks, I embed the theoretical model in a GIS ap- plication to produce spatial outcomes. Specifically, I modify currently available GIS algorithms to mimic the construction of three different types of logging roads. The dissertation is organized as follows. In the second chapter, I provide a brief description of the evolution of the transportation system in the Brazilian Amazon and the relevant transportation geography and location analysis literature on patterns formed by line segments, or network patterns, and ensuing deforestation patterns. In Chapter 3, I develop a formal theoretical statement of loggers’ road building behavior and simulate the construction of two types of logging roads, which I call destination indeterminate and destination determinate. I also discuss the local political ecology that is relevant to the emergence of roads’ routes. In Chapter 4, I deveIOp a new algorithm to model the construction of a third type of logging road, which I refer to as skid logging trails. Since this algorithm is based on a well known problem in mathematics and computer science, i.e. the Steiner tree problem, I first formally describe the problem using terminology from graph theory applied in a GIS context. Chapter 5 concludes the dissertation by highlighting the major findings and possible future research questions. 1.3 Study Area The Amazon Basin is the largest river basin in the world with an area of approximately 6.4 million km2 extending over the territory of nine coun- tries: Brazil, Peru, Bolivia, Colombia, Ecuador, Venezuela, Guyana, Suriname, and French Guyana. Approximately 63% of the basin, or 4.0 million km2, lies within Brazilian territory (Conservation Interna- tional, 2004)(Figure 1.3). Several geographic terminologies are available to describe the Brazil- ian Amazon. ‘Classic Amazonia’ encompasses the original northern states of Amapa, Acre, Roraima, Rondonia, Amazonas, and Para.2 In 2 Prior to 1953, only Para. Amazonas, and Mato Grosso were states under Brazil’s republic system. From the early colonial years until 1943, Amapa. Rondénia, and Roraima were all part of one of those four states. During World War II, they were dismembered and became territories 16 1953, the Brazilian government created the Superintendéncia do Plano de Valorizacdo Economica da Amazonia (SPVEA) or the Economic Improvement Plan Superintendence, to oversees the application of 3% of total federal taxes over 20 years to develop the north (Mahar, 1978).3 At the same time, a new political nomenclature was implemented to serve the economic development purposes of this plan. The new po- litical entity, known as the ‘Legal Brazilian Amazon’, included all the ‘classic Amazonia’ plus Mato Grosso state north of the parallel 160S, Tocantins north of parallel 13°S, and part of Maranhao west of the 440W meridian.4 All businesses, either industrial or agricultural, lo- cated in states belonging to the Legal Brazilian Amazon were eligible for a series of financial benefits including tax breaks, subsidized credit, and land acquisition on very favorable terms.5 The Legal Amazon ex- tends over 59% of Brazil’s territory or approximately 5.0 million km2 of which 76% was originally forested and the remainder mostly covered by savanna-like vegetation (Lentini, Verissimo, & Sobral, 2003). administered by the federal government. Later, each territory became a state. Rondonia (previously known as Guaporé Territory and later Rondonia Territory) became a state in 1982 and was originally part of Amazonas (northern half) and Mato Grosso (southern half). Amapa and Roraima territories, the latter previously known as Rio Branco Territory, became states in 1988, when a democratically elected congress wrote a new constitution. Acre belonged to Bolivia until 1903. when Brazil gained possession of this territory under the Petropolis Treaty signed between the two countries, and became a state in 1962. 3 Law 1806 from January 6 1953. 4 Mato Grosso belongs to the center-west. region and was part of a larger state that was split into two in 1977: Mato Grosso itself and Mato Grosso do Sul. Tocantins, new incorporated into the northern region, was part of Goias state (center-west region) and was also dismembered in 1988. Maranhao is part of the northeast region. 5 For a good review of those policies and impact on deforestation, development. and social conflict 17 220Eo=¥ com; fill—leJl—li. 1 In con mum o .Eeéaaée . Figure 1.3. The Amazon Region please refer to Mahar (1979) and Schmink and Wood (1984) among others. 18 Unless otherwise specified, I use throughout the dissertation the generic term Amazon or Amazonia to refer to the Legal Brazilian Ama- zon region. This region is the second largest producer of tropical timber in the world, second only to Indonesia, with an annual production of approximately 30 million In3 (Lentini et al., 2003). Brazil as a whole is also extremely rich in biodiversity, much of it concentrated in the Ama- zon and Atlantic forests, with approximately 55,000 angiosperm plant, 428 mammal, 1,622 bird, and 516 amphibian species (Fearnside, 1999). Invertebrates are even more numerous; 1,080 species were found in just four sites near Manaus, capital of the state of Amazonas (Fearnside, 1999). Deforestation rates are also the highest among tropical forested countries. Deforestation peaked in 1994/ 1995 when almost 30,000 km2 were converted. In the subsequent years, rates dropped to 13—18,000 km2 year‘l. However, in the last two years, rates have increased again and been consistently above 23,000 km2 (Table 1.1).6 Mato Grosso, Para, and Rondenia present the highest rates of deforestation. These are also states with a significant logging industry (Lentini et al., 2003). Despite these high annual rates of deforestation, ‘only’ about 17% of the region’s forests have been lost because of the gigantic size of the Amazon (INPE, 2005).7 6 In l\--’Iay 2005. the Brazilian government announced that during the year 2003/2004. 26,130 km2 were deforested in the Amazon, the second highest rate in history. This number was estimated based on satellite in'iagery analysis. 7 Indeed, the Amazon region is not classified as a hot spot for biological conservation by Myers 19 The Brazilian Amazon is a unique setting, with high biodiversity and a rapidly expanding regional economy based on resource exploita- tion. Thus, it constitutes an ideal location to study how logging roads affect spatial patterns of deforestation. I have chosen two localities in the Amazon where I focus my dissertation research. In Chapter 3, I consider destination determinate and destination indeterminate logging roads in the town of Uruara, along the Transamazon Highway in Para state (Figure 1.4). In Chapter 4, I use data collected from a logging ex— traction site in Acre state, located in the western Amazonia, to model skid trails. at al. (2000) because the ecosystem as a whole is not yet in the verge of collapse. 20 Amocmv mazu ”eat—5m 35.5%; .52: :::::emmH .52: Began: enema s; can mass 33. 22: s: 5. a. as amass comma as E. mom...” 3% was on? as; o 5 was seem: a: as“ Ed has SE was as a as :35 8%: as was moss ES some was; as o as 830. some: Sm cam $3 :3 mass on? on. o as. asks ”me: Em. mam Sore. 8% 8% as; one on one mats an? ”a s: as; an? :3. as. as. S mam ass 83: can is was was «.35 so; mm: a an. 38 33a an. as on? say §...S we} 33 a mom; mass eswfi new as 33 $3 8% as. can o as. sass. own? as. as 33 $2.. 33 mm: as 2.. cos 35. one: as. ca. 23 cm; 2.3 Be as oz. own is 5.2 cm... a: 23 83 83. 83 can as oer. 3% En: one one 83 Scam. 8%... 83 cm: 2: as“. She Sea 33 can 2.3 cases 2.3 ones 2...; 8 0% tab» A<>>d<¢ 9% mafia gentler. , :33... .. 290E0=¥ coo; toe-5.213: com - 1957 Figure 2.2. Roads (Panel A) and railways (Panel B) in the Brazilian Amazon 31 tect, control, and maintain Brazil’s large frontier. They believed that Brazilian possession and control of a sparsely populated region such as the Amazon was vulnerable for the take, particularly when countries such as Peru, Bolivia, Colombia, and Venezuela built Andean highways and implemented policies to occupy the Amazonian lowlands in their respective countries (Moran, 1996). The discovery of oil in neighbor- ing countries and the prospect of rich mineral deposits in the Amazon also fueled the fear of territorial disputes. Consequently, the military government implemented policies based on road building construction and subsidized credit to occupy the region. Their motto was integrar para ndo entregar or integrate not to hand over. As such, the Programa de Integragrio Nacional - National Integration Plan (PIN) was imple— mented. In 1967, the government began the construction of a road linking Cuiaba to Porto Velho and to Rio Branco (BR-364), which was completed in 1974 and later asphalted in 1983. A second stretch of BR-364 linking Porto Velho to Acre’s capital, Rio Branco, was opened to traffic in 1975 (Sant’Anna, 1998) and reached Peru’s frontier years later near the western-most point of Brazil. This road connected the whole western portion of the country to the center-south of Brazil, since Cuiaba’. already was connected to Sao Paulo and Brasilia since the early 19603 (Figure 2.3). Three other roads, Porto Velho-Manaus (BR-319), Manaus-Boa 32 Vista (BR-174), and Macapa-Oiapoque (BR-156) were built during this period as well. However, unlike the BR—230 (see below) and BR—364, these roads were not subject to intense colonization. Construction of BR-319 began in 1968 and was finished only in 1976. This road inter- sects the Transamazon at Humaita and is, for commercial transporta- tion purposes, not trafficable beyond this point. BR-174 and BR—156 were clearly built to protect Brazil’s frontier. The first stretch of BR- 174 to be built in 1975 was a 220 km segment linking the capital of Roraima, Rio Branco, to the frontier with Venezuela and to Caracarai, 135 km south or Rio Branco. The longest part linking Caracarai to Manaus was completed in 1977. In total, this road is 1,003 km in ex- tent of which 730 are currently paved (Sant’Anna, 1998). Construction of BR-156 began in the early 19603 but was only completed in 1976 and links the capital of Amapa state, Macapa, to Oiapeque at the French Guiana border. For the first time in Brazil’s history, the country had connection by land from north to south and from east to west. In the beginning of the 19703, the military government tried to bal- ance national security concerns with social goals, namely poverty allevi- ation. After a visit to the severely drought-affected northeastern Brazil, the president at the time, Medici, launched a plan to redistribute lands along roads in the Amazon to small farmers from the northeast and landless farmers from the south. The Plano de Desenvolvimento da 33 cozoeumcoo c. 1 wow. 29m mum .mcouoa wocmucsom 89m fl 2338 93m 3 9.90:..22 oooé com azon from 1968 to 1993 the Brazilian Am Figure 2.3. Evol ution of the road system in 34 Amazonia - Amazon Development Plan (PDA) was implemented with an objective to “bring people without land to a land without people”, to use the famous phrase coined by President Medici. Two major roads were built during this period. The Transamazon Highway (BR-230) that cuts through the middle of the Amazon, in east-west direction, linked the northeast of Brazil to Itaituba in the west (completed in 1972). A second stretch of 1,000 km from Itaituba to Humaita was later completed in 1974 (Mahar, 1978). In total, this road is more than 2,500 km in extent. A second major north-south road (BR-163) with 1,743 km in extent was completed in 1978 and linked Santarém, located at the confluence of the Tapajos and Amazonas rivers, to Cuiaba in the center—south of Brazil (Sant’Anna, 1998). Official settlement plans predominated in two areas: along the Para State portion of the Transamazon and along BR—364 in the state of Rondénia. In those two regions lots of 100 hectares, regularly demar- cated in a grid system, were distributed to small farmers. In 1985 the only currently operational railway was opened. The discovery of the world’s largest iron ore deposit in Serra dos Carajas in 1967 prompted the mining company, which was state owned and later privatized, to build a railway from Carajas to the port of Sao Luis, approximately 1,000 km away. In the 19803 the federal government refrained from building new roads owing to severe budgetary limitations following the so—called sec— ond oil shock sparked by the Iranian Revolution in 1979, the rise in interest rates on international loans, and poor macroeconomic poli- cies, which led to hyperinflation, fiscal deficits, and erosion of public services. From 1980 to 1992, total investment as a percentage of the GDP plummeted from 24% to 14% reflecting Brazil’s meager internal and external savings (Pinheiro, Giambiagi, & Gostkorzewicz, 2000). Nonetheless, several state roads were built as feeder routes linking the hinterland to the federal road system. The resulting pattern was a denser network particularly in the southern and eastern border of Le- gal Amazonia (Para, Maranhao, Tocantins, and Mato Grosso states) and on the northernmost part of Brazil in Roraima state (Figure 2.3). Table 2.2 shows the evolution of both the federal and state road sys- tems.3 In the late 19603 there were only 484 km of state roads in the Amazon compared to the more than 12,000 km of federal roads. In the following decade, the state system was already near 13,000 km while 3 This time series geographical dataset was created as follows by S. Aldrich (Dept. of Geography. Michigan State University). Digital maps of 1993 provided by C. Bohrer (Universidade Federal Fluminense) in Atlas GIS format were imported into ArcGIS. Then each road segment printed on the hard copy roads maps from 1968-1987 were compared with this digital file. Road features that were not present in the hard copy were deleted from the digital file. The remaining linear features in the digital file were saved as the digital version of the hard copies for the respective year. Each road segment. had several attributes including the condition of the road (paved, unpaved, being constructed, bed road, planned, no information, etc.), name of the road, whether the road was state or federal, and other topological information. The original digital maps were in geographic coordinate system. In order to measure the extent of each segment, this map was projected into sinusoidal, which is an equal area projection. Simple GIS commands then calculated the length of each segment used in the analysis. 36 Table 2.2. Evolution of the federal and state road system (km) YEAR Jurisdiction 1968 1975 1985 1993 Federal 12.555 15.495 18.890 18.974 State 484 12,914 33.606 36.688 no data 0 448 21 0 TOTAL 13.039 28.857 52.517 55.663 Obs: these numbers reflect. the official road network but transportation along some segments is not possible during the rainy period. the federal increased by only 3,000 km. In the mid 19803, the state system more than doubled in extent from the previous decade reaching 33,606 km. Meanwhile, the federal system increased by another 3,000 km totaling 18,890 km as of 1985. In the 19903 the federal and state road system remained practically unchanged when compared to the fast growth observed in the previous decades. The federal system had an addition of less than 100 km while 3,000 km were added to the state network. As of 1993, Mato Grosso had by far the largest road network with approximately 20,000 km. Para had 10,000 km of roads followed by Maranhao, Tocantins Roraima, and Rond6nia (Table 2.3). The road network, including both the federal and state systems, was slightly over 55,000 km of which only 28% was paved. 37 was? 5.2 was: 83: his cm? erase :3. 2.2:. $92 Sea was”: 8me 3% mac. :3 m 885 as: as? one...” mm... s a; $3 $3 a . c oases: Rem. we} sue... new 25.». E as a o 2:22.139: was, 9:. m8; 2:. Em c as. c 2.5% ass 23 :3 as a so.” as E we. see Rem Nam. Raw 3. . 83 o as. c geese as: a: a E: s: a as; as 83 mm 33:52.2 e3: E as: .5 meme 8 an e 2% 80 N ea; saw m ”E as a E was c 2.285.: 192mm: D Cor/mom Cacfiwa: D Goa/saw Use/flaw: D Cat/5L Corral: D COZWL meagm 82 £2 £2 £2 m 35$ 33m .3 50?? 1E: 22 E :e_.:;e>m .m.m 03¢? 38 The pattern of transport system development observed in the Ama- zon resembles other patterns observed in other developing countries, which was first studied by Taaffe et a1. (1963). These authors pre- sented a typical sequence of transport development. In the first phase small ports are scattered along the sea cost as a result of colonial con- quest without any connection to the interior. In the second phase, roads or railways departing from the most important ports are built and penetrate the hinterland. The third phase is characterized by the emergence of feeder roads that connect other portions of the interior to the original routes, enlarging the hinterland of the major ports. Even- tually, some cities located in the interior will become centers of trade as important as the original ports. Finally, the Taaffe model predicts the emergence of major paved highways linking the most important centers of commerce. These major routes are also served by airline flights and even railways. The Brazilian Amazon transport system development did not fol- low exactly the Taaffe model. Important centers of commerce in the Amazon, such as Belém and Manaus, emerged almost independently from other large cities in southern Brazil such as 850 Paulo and Rio de J aneiro. For historical reasons (i.e. the rubber boom) and geographi- cal separation, the Amazonian economy was more connected to Europe than to the rest of the country. Indeed, Amazonian international trade, 39 measured as the sum of imports and exports, was larger than the rest of the country during the rubber boom (Barham & Coomes, 1994). After the demise of the rubber economy in 1920 and the rapid industri— alization of the southern part of Brazil, Amazonian cities became eco- nomically peripheral to their southern counterparts. Nonetheless, both Belém and Manaus acquired status as important centers of commerce prior to substantial linkages to the south of the country, or the develop- ment of much of the transportation system (Browder & Godfrey, 1997). Therefore, the expansion of the road system connecting the south to the north cannot be regarded as the construction of ‘penetration roads’ to the hinterland as proposed by Taaffe. Indeed, the construction of roads such as the Belem—Brasilia is more characteristic of the latest phase of the Taaffe model. On the other hand, the roads built to the west, such as the Transamazon, and the Cuiaba-Porto Velho and the north-south Cuiaba-Santarém can be characterized as penetration roads, since the destinations were not, at the time, large centers of trade. Once these major roads were built, then the development of the secondary system, such as the state road system developed in the 19803, follow the Taaffe model. 40 2.2 Road Pattern and Deforestation Pattern The Taaffe model described in the previous section is largely based on inductive historical studies of transport growth in developing coun- tries. Several other studies, conducted by geographers such as Morril, Haggett, and Chorley, have often relied on network theories and meth- ods to explain the development of transportation networks. Hence, it is important to review some of these studies as they relate to network patterns.4 Equally important is to describe how these network patterns translate into deforestation patterns. The study of patterns formed by line segments, or network patterns, has a long history in the natural sciences, particularly in geological and hydrological applications (Strahler, 1952; Howard, 1967). Haggett and Chorley (1969) describe four general network patterns largely de- rived from hydrology: dendritic, parallel, rectangular, and trellis (Fig- ure 2.4).5 The dendritic pattern resembles the hierarchical branching pattern of stream networks commonly found in many places, where the tributaries merge with larger streams at acute angles. The streams 4 For example, Morril (1962, 1963) used Monte Carlo simulations to model the development of settlement over time, the emergence of central places, and transportation network in Sweden. The localization of the network was based on population centers incomes (similar to a gravity model), which were ordered from largest to smallest. The two largest centers were first connected, and then other segments were subsequently added. also following the ‘attraction force’ between centers (Morril, 1965: Chorley & Haggett, 1967). 5 Several metrics and relationships, including length of road or stream segment, order, area served by segment. angle of junction between segments, and flow along segments, were developed by many authors such as Haggett (1967) and Horton (1968). to characterize transportation networks. 41 themselves are not straight but exhibit an irregular, tortuous path. The parallel pattern shows elongated streams that run almost parallel with each other. In the rectangular pattern, streams curve at right an- gles with very few tortuous tributaries. Finally, the trellis pattern is a combination in which major streams show a rectangular pattern while the tributaries Show a dense dendritic pattern. Network analysis was used in physical (description of hydrological networks), economic (rela- tionship and connection between cities), and transportation geography (route optimization) studies.6 Roads and deforestation are closely related in the Brazilian Ama- zon, as discussed in Chapter 1. Not surprisingly, different patterns of roads will lead to different patterns of deforestation and fragmentation. Geist and Lambin (2001) consider deforestation patterns and the pro- cesses that generated them, classifying six types: geometric, corridor, fishbone, diffuse, patchy, and island (Figure 2.5). The geometric pattern is characterized by large, continuous defor- estation areas, usually associated with large-scale clearings for commer— cial agriculture or cattle ranching. The fishbone pattern is characteris- tic of small-holder colonization along the Transamazon Highway and in 6 More recently. network analysis, and graph theory in particular, have been used by ecologists to describe landscape patterns. Cantwell and FOrman (1993) used nodes to represent land cover configurations and edges to represent connectivity between different land covers. They identified at. least eight graphic configurations and studied the connectivity (e.g. number of connections in each node) between different land covers as a measure of interaction between them. The authors point out that such methods can be useful to model landscape function and future changes. 42 17’; Ah: // PARALLEL/ oeuonmc / /\ '\ \ RECTANGU - R Adapted from Howard (1967) Figure 2.4. Major network patterns Rondénia State. The corridor pattern is characterized by deforestation along major axes of transportation, typically long linear road segments. In this case, deforestation occurs within a buffer along the road. The diffuse pattern is characterized by small, discontinuous clearings, usu- ally associated with traditional, subsistence agriculture far from any transportation network (e.g. Indigenous people engaged in shifting cul- tivation). The patchy pattern is found near densely populated areas in which forests are isolated islands surrounded by human modified land 43 covers. Finally, Geist and Lambin (2001) identify a continuous circu- lar clearing pattern surrounding urban areas, which they labeled the ‘island deforestation pattern.” GEOMETRIC CORRIDOR C ,7 0 O D O Q C) O a FISHBONE D D I DIEFUSE o ISLAND Adapted from Geist and Lambin (2001) Figure 2.5. Deforestation and fragmentation patterns As described in Figure 2.6, the design of small-holder colonization 44 projects along the Transamazon followed a standardized geometric pat- tern that was replicated in other parts of the basin, particularly in Rondénia. Lots were regularly demarcated along the main road (BR- 230) and along parallel secondary roads that branched out perpendic- ularly from BR—230 every 5 kilometer to the north and south. These secondary roads were initially constructed by the federal government as access spurs, leading 6-10 km off the federal highway (Simmons, 2004). Colonists were given 100 hectare lots and soon began deforesting to plant annual and perennial crops and pastures. The fragmentation pattern that emerged from the initial settlement geometry resembles a ‘fishbone.’ In other parts of the Amazon, most notably in southern Para State and in Mato Grosso, roads followed a more rectangular pattern with many right angle turns and four-way intersections (Perz et al., 2004). In those two places, colonization projects were handed to private firms that sold large parcels of land to investors in southern Brazil (Schmink & Wood, 1992; Perz et al., 2004). Those parcels, some with more than 100,000 hectares in size, presented a rectilinear geometry. Feeder roads built to access farms farther from the main roads were usually placed on the boundaries of such parcels, forming rectangular patterns. The deforestation pattern that emerged from such a spatial arrangement had a ‘geometric’ characteristic, following Geist and Lambin’s classification. Legend 0 2.5 5 Kilometers I—J—l — Transamazon Hwy D Lots Figure 2.6. Geometric configuration of the lots along the Transamazon Highway Those landowners deforested large, continuous blocks of forests to plant soybeans or pastures to raise cattle. The placement of roads along boundaries is a well studied phe- nomenon in the United States. Two completely different surveying systems were used in the original thirteen colonies east of the Ap- palachians and on lands surveyed after the Land Ordinance of 1785. The first Anglo-European settlers in the United States used the ‘metes 46 and bound’ system (also known as system of warrants and patents) in which surveyors placed boundaries based on physical features such as trees, streams, boulders, and even already existing roads. On the other hand, after the Land Ordinance, which adopted the Township/ Range system, the land was divided into rectangular grids forming townships of six miles on each side, each of which are subdivided into 36 sections. For instance, roads in New England in the early colonial period were highly dependent on the physical geography. For example, many of the towns’ roads and highways in New England converged to sawmills, which were dependent on water power to operate (Cronon, 1983). On the other hand, roads west of the Appalachians often followed a rectilin- ear pattern owing to the flat topography of the Midwest combined with the grid demarcation system. The deforestation and land use pattern that ensued was also different in both regions and is still persistent in the landscape. For example Bain and Brush (2004) were able to recon- struct the original property boundaries in the Gwynns Falls watershed in Baltimore, MD, which was originally surveyed in the 1600-17008, be- cause the original property lines and other physical attributes in rural areas are still imprinted in the landscape. 47 2.3 The Endogenous Road Debate Although my dissertation does not aim at assessing the impact of roads on deforestation or the impact of roads in the landscape, it is important to contextualize the overall discussion about roads in the Amazon. In the recent literature on roads and land cover change the term ‘endogenous roads’ has been frequently used. However, in many cases this term has been used to describe different phenomena. For example, Souza Jr. et al. (2004) use the term endogenous roads to denote these roads built by private agents as opposed to the official roads built by governments. In the econometrics literature, the ‘endogenous roads’ term has a very specific meaning that arises from two different processes. The first case, described by Chomitz and Gray (1996), relates to the correlation between the control variables in a regression and the unobserved er- ror term. Let y, = xifi + p,- be a population model where y could be, for example, a deforested parcel or any land use type, K a vector of explanatory variables, which usually includes a distance to the nearest road variable and a the unobserved error term. The critical assumption to consistently estimate the vector 6 is that E [x’ p] = 0, or that the vec- tor of explanatory variables must be uncorrelated with the unobserved error term. 48 Chomitz and Gray (1996) hypothesized that land would be allocated to its highest use and deforestation would be observed as long as rents from agricultural land uses were higher than rents from forestry, both being greater than or equal to zero. In their model implementation, rent is a function of distance to roads and they call attention to road construction motivated by agricultural development prospects. In par- ticular, roads routed purposefully through areas with better soils can cause the estimation of the partial effect of roads on deforestation to be biased, usually overestimated. If agricultural suitability factors are not controlled for, then the variable roads, which is part of the vector x, would be correlated with the error term )1 (unobserved land qualities) and hence, the partial effects of roads would not be correctly estimated. In order to overcome this problem, the authors included a rich set of variables to control for land quality, including terrain slope, soil wet- ness and pH, available phosphorus, and dummy variables sandy and rocky areas. Nonetheless, the authors suggest that some land quality variables may have not been controlled for, possibly biasing the result. The second case arises from a causality directionality issue. In other words, the population model of interest is actually a system of equations similar to: 49 ya = any]? + X2151 + #21 922 = ai‘Zyil + X2252 + #22 where ya indicates deforestation in a certain place, and 3112, the exis- tence of a road segment and the vectors x1, x2 include other control variables that must not be identical in both equations in order to iden- tify the system. The first equation shows the usual directional causality thoroughly described in the literature: deforestation is a consequence of roads or, the building of roads leads to deforestation. The second equation points to an inverse causal relationship which was not, until recently, much explored in the land cover change literature. Is it possi- ble that deforestation actually precedes the building of roads? In other words, is it possible that roads are a response to development and are actually endogenous to the deforestation process? If this is the case, then usually yl will be correlated with ”(L2 and y2 will be correlated with U1. Therefore, the estimation of the parameters will be biased if we use the usual ordinary least square estimation procedure (Wooldridge, 2002) Clearly, if time series geographic data on deforestation and roads, such as satellite imagery, were available, then causality could possibly be established by looking at whether or not roads precede deforestation in a particular region in the image. The policy implication of this discussion is very important. The question whether roads cause deforestation or not and the ‘magnitude’ of such impact have deep political implications to the environmental protection versus development debate in tropical countries. In recent years, the Brazilian government launched a program named Avanca Brasil with the objective of, among other things, upgrading Brazil’s infrastructure. According to the original plan, 6,245 km of roads in the Amazon are to be renovated and ecologists predict severe conse- quences for the environment, including an increase in forest fires and deforestation rates (Nepstad et al., 2001; W. F. Laurance, Cochrane, et al., 2001). On the other hand, Andersen et al. (2002) claim that paving roads promotes economic growth and even limits clearing, which is a win-win situation, particularly in more populated areas in the Amazon. Their conclusion is based on a panel evaluation of data aggregated at the municipality level. The principal drawback from their work is the lack of a model specification based on theoretical grounds. Instead, they adopted an estimation procedure in which observations considered to be outliers are dropped from the sample. Also, explanatory variables with robust t-statistics under 2.0 are randomly dropped from the estimated model. This procedure is repeated until the model fits some criteria of 51 ‘good’ model. However, the results found by Andersen et a1. (2002) are being contested by new econometric models and estimation methods (Pfaff et al., 2004). Most federal roads seem to be exogenous to deforestation. Figure 2.7 shows population centers identified in the 1957 IBGE maps and the federal roads overlaid.7 Not surprising, the vast majority of the pre—1957 cities were located near rivers. The road routes that emerged are basically lines connecting some of those population centers with very minor deviations, caused possibly because of micro—topography (Figure 2.7). This pattern indicates that there were very few, if any, detours to access areas of high agricultural potential. As such, official roads built by the federal government can be considered exogenous. The most notable examples are the Transamazon (BR-230) and BR- 364 from Cuiaba to western Acre, whose routes seems to be generated by a connect-the—dots exercise. The Cuiaba-Santarém is the only road without any population center in between these two cities. However, according to key informant interviews, there existed a town on the current route in the southern part of Para State, near the border of Mato Grosso State, that is not shown in the IBGE map of 1957 (R. 7 This map was generated as follows. I converted the 1957 pdf maps from IBGE into tiff format and georectified it. Then, I overlaid this map with a 1997 digital map of all urban centers in the Brazilian Amazon obtained from IBGE (1997). Next. I selected all points (urban centers) that also appeared in the 1957 map. I also double checked the name of the cities in the index of the 1957 document to make sure that. all pre-1957 cities were included in the digital dataset. Walker, personal communication). In retrospect, the placement of the federal road system was ulti- mately determined by physical geography. Cities such as Porto Velho, Ariquemes, Itaituba, Altamira, and Maraba became population centers because of physical geographical characteristics of rivers. Ariquemes was a rubber trade village on the margins of J amari River, an impor- tant tributary of the Madeira River that provided access to the rubber- rich interior of this watershed.8 Maraba. also emerged as an important regional trade center because of its location near the confluence of two major rivers, the Tocantins and Araguaia that provided access to an area rich in rubber and brazil nuts (IBGE, 1957; Schmink & Wood, 1992). Porto Velho, Itaituba, and Altamira became population centers because of rapids and waterfalls that interrupted navigability.9 Hence, it was necessary to portage those rapids or transfer products from one boat to another. In other cases, such as Santarém, indigenous villages were already established in strategic locations (confluence of Tapajos and Amazonas rivers) and were later transformed into trading posts by religious and commercial ventures (IBGE, 1957).“) 8 This information was obtained during field trip to Rondénia in 2003, when a team (myself included) interviewed key informants. 9 Porto Velho was created during the It‘ladeira-Mamoré Railway construction. Not surprisingly, it was decided to put the terminus of the railway on a navigable portion of the Madeira river. Key informants told the field team that there was a village upriver from Porto Velho, right below a major waterfall, that lost its importance as a trade center years after the construction of the railway. 10Itaituba. Altamira. and Maraba might also have been indigenous villages prior to colonization but. references I found were not consistent to back up this claim. 1mg . £5.58”. A88. «23.. .223". 8:35 .2000". § 52. . meEo mEExm . ucouo 990E0=¥ coo; Figure 2.7. Existing towns prior to 1957 and the design of the Federal road system 54 In this dissertation, I use the term ‘endogenous roads’ in the context of the econometrics literature, or roads that are built after deforestation occurs or roads purposefully routed to gain access to natural resource (e.g. fertile soils, timber-rich sites, etc.). I will refer to the roads built by the state with the purpose of developing the region as ‘official roads’, either federal or state. Examples of such roads are BR—230 (Transamazon), the BR-OIO (the Belem-Brasilia), PA-150 and, BR-364. Non-official roads’ are those built by local residents, such as loggers, colonists or even local governments, rather than state or federal gov- ernments. These roads are usually built to gain access to land, timber, and other natural resources and are usually endogenous to deforesta- tion. In the case of roads built by the state government, this classifica- tion between endogenous and exogenous is not so clear cut. Anecdotal evidence suggests that some state roads are actually endogenous while others were built to link existing population centers. The official road network explains the general spatial deforestation pattern, which in many cases is related to the hydrological charac- teristics of rivers (i.e. rapids and waterfalls), but ecologists are more concerned about the fragmentation pattern at the finer scale produced by the denser, longer, and intricate non-official network. Hence, this dissertation will focus on non-official roads built by loggers. In the next chapter I provide a theoretical and simulation models of two types of unofficial roads, destination determinate and destination indetermi- nate. In chapter 4, I develop an algorithm to model the third type of unofficial road, skid logging trails. 56 CHAPTER 3 Modeling Road Patterns In the previous chapter I showed that the deforestation pattern is largely associated with the road network pattern. Hence, understanding how the spatial architecture of a road network pattern emerges is key to comprehending forest fragmentation resulting from deforestation. This chapter addresses a specific form of fragmentation in the Brazil- ian Amazon, namely the fishbone pattern, and attempts to develop an explanation based on economic decisions about road-building. Specifi- cally, I use GIS software to mimic the spatial behavior of road builders, and then I attempt to replicate an existing road pattern using the soft- ware. Thus, in this application, I deploy GIS as a tool for understanding forest fragmentation processes, and not for designing optimal road net- works in a normative sense. In essence, the GIS provides the computer- ized thinking to address a process too difficult to resolve with analytical solutions (thita, Krugman, & Venables, 1999; Walker, 2003a). I begin the chapter with a description of the different road types off the main Ttansamazon Highway and the role played by loggers in building such roads. Next, I develop a model of road construction based on the microeconomics of the firm to explain loggers’ road building behavior. This is followed by an explanation of the computational issues involved in the GIS modeling work. Finally, I present and discuss the modeling results. 3.1 Roads and Land Cover Change The modeling focus in this chapter is on the fishbone pattern observed in smallholder colonization areas such as along the Ttansamazonia Highway in Para (Figure 3.1), and also in Rondonia State, but its domain is likely to grow with ongoing government efforts to colonize the region in the interests of land reform by the implementation of pro- jetos de assentament0.1 I focus on Uruara, a town created during the official colonization efforts in the early 19703 through the so-called PIN program (Simmons, 2002). Uruara was part of the Altamira PIC, or Projeto Integrade de Colonizacdo, one of the first official settlements in Amazénia pursuant to development of the federal highway system. 1 A Projeto de Assentamento is a government sanctioned area of small holder colonization that typically fragments the landscape in accordance with early schemes by INCRA, which allowed for 100 hectare holdings (400 x 2500 m) and road spurs to provide access every 5 kilometers. 58 r—T—fi'fifi—I—rfi—I 0 25 50 100 Kilometers Figure 3.1. Portion of the Transamazon region in Para State. 3.1.1 Roads off the Transamazon Highway Colonization in Uruara followed the fishbone pattern described in the previous chapter in which lots were regularly demarcated along the Transamazon and along parallel secondary roads that were initially constructed by the federal government. Visual inspection of satellite imagery as well as field experience es- tablishes that the federal infrastructure was subsequently extended by private interests in the area. In this regard, I have identified three 59 main types of road extensions in my fieldwork. The first comprises simple extensions of the original secondary roads following the govern- mental spur, which I call destination indeterminate roads. Such roads expand relatively slowly and replicate the initial settlement geography. The second type of road I refer to as destination determinate, since it achieves a discernible spatial objective. Two such roads are found in the region, named the Transtutui and the Transiriri because they reach destinations on two rivers in the study area, the Tutui and Iriri, respec- tively. These two roads are longer, better maintained, and more heavily traveled than those without destinations. Both destination indetermi- nate and determinate roads are typically built by well-capitalized log- gers with help from colonists and local government. The third type of roads, referred to as logging skid trails, is a combination of destination determinate roads and the roads we typically associate with a logging operation, i.e. the dense network of logging trails that is built to reach each tree. The GIS model developed to address this third type of roads requires an explanation of graph theory and complexity theory. Ter- rain data must also be obtained in a highly detailed, fine scale. Hence, to facilitate exposition, I will describe destination indeterminate and determinate roads in this chapter and skid trails in Chapter 4. 60 3.1.2 Loggers and Road Building The expansion of the secondary, unofficial network associated with set- tlement roads in the Amazon basin is mainly driven by the logging sector, interacting with both planned and spontaneous colonization. Currently, about 30-40 million In3 of roundwood are extracted on an annual basis in the Brazilian Amazon region, producing 11 million In3 of sawn wood and a gross revenue of US$ 2.5 billion (IBGE, 2003; Lentini et al., 2003).2 These production values translate into an exten- sive spatial impact which is estimated at 9,400 km2 logged in 1996, and 23,400 km:2 in 1999 (Matricardi et al., 2001). In volumetric terms, most extraction is concentrated in the states of Para (40% of total), Mato Grosso (36%), and Rondénia (17%), all of which have experienced dra- matic extensions of their road networks in recent years. Amazonian wood is mainly consumed domestically (86%), while the rest is exported (Smeraldi & Verissimo, 1999). As of 1998, perhaps 2570 sawmill firms were operating in the Brazil- ian Amazon (Lentini et al., 2003), of which 53% were considered small operations processing less than 10 thousand m3 of roundwood annually. Lentini et a1. (2003) estimate that 49% of all roundwood is processed by large, vertically integrated firms that do their own logging. Such 2 Most of the wood exploited is illegal. Of the approximately 11 million m3 exploited, less than 3 million m3 have been authorized by the Brazilian environmental agency, IBAI\“IA(O Liberal Newspaper. January 11, 2004). 61 firms make large investments in sawmill structures, in machinery (cir- cular saws, bandsaws), and in the equipment necessary to cut, extract, and transport the wood to be sawn, which includes skidders, winches, bulldozers, tractors, and trucks (Verissimo et al., 1992, 1995). Along the Transamazon Highway, large integrated firms have been most active in road extensions, particularly for the destination determinate roads that are built quickly and with considerable capital investment. The models I use to replicate road building activity assume road-building by a vertically integrated firm possessing both mobile (e.g, skidders, bulldozers, trucks) and immobile capital, on-site at the sawmill (e.g., saws, buildings). 3.2 A Conceptual Framework for Logging Firm Behavior In this section, I develop a behaviorally-based explanation of the expan- sion of settlement road networks, in particular those in which logging firms play an important role. The approach taken is computational and involves the deployment of GIS to identify ‘optimal’ roads. These are then compared to the actual roads by visual reference to satel- lite images. Road network optimization is not new to operations re— search, but little effort has been made to link the economic behavior 62 of spatial agents such as loggers to the identification of optimal spatial configurations of road networks. The theory of the firm is largely as- patial in this context. For their part, network finding algorithms may neglect financial constraints in a particular setting, or economic con- ditions more generally. Thus, to develop a behaviorally-based theory of road-building and forest fragmentation, it is essential to place the search for optimal pathways within the context of the micro-economic behavior of the firm, which is the purpose of the present section. As discussed, large firms that engage in both wood extraction and processing are presently responsible for a large component of Amazo— nian forest exploitation, and on a per-enterprise basis they exercise far greater forest impact than smaller operations. Thus, I assume only large, vertically integrated firms possess the capital necessary to regu- larly engage in road construction for both indeterminate and determi- nate cases. The model development that follows addresses the decision- making activities of such large, vertically integrated operations, which from this point on will be referred to with the generic term loggers, to be distinguished from the smaller operations that Specialize in tree extraction. In the following two subsections, I develop relevant theory addressing indeterminate and determinate roads individually. The indeterminate case presents a difficult problem, given that destinations are not known. 63 On the other hand, with destinations known, optimization of route selection is transformed into the identification of a least cost path, which is a simpler minimization problem. 3.2.1 Indeterminate Roads In the present context of indeterminate road building and route selec- tion, large integrated logging firms face two optimization problems. The first is profit maximization involving factor allocation between wood ex- traction and processing, subject to financial constraints. The second is spatial and involves identifying the path or paths that provide the greatest volume of roundwood given the quantity of capital allocated to extraction, or mobile capital. The first problem is aspatial in that it requires no geographical information; the solution indicates optimal allocations of roundwood input, labor, and fixed sawmill equipment, or immobile capital. The second problem is spatial because it depends on several forms of geographical information, including location of trees and infrastructure, distance measures, and terrain slopes, and because its solution is spatial, namely a path or paths in two—dimensional space. Profit maximization and the search for optimal pathways require fundamentally different solution approaches. I first consider factor al- location pursuant to profit maximization, an analytical problem, which then constrains the computational spatial problem. Profit maximiza- 64 tion yields the amount of mobile capital as a function of the firm’s financial capability. Mobile capital then constraints the road construc- tion process and its articulation in space. This is the mechanism by which the economic constraints faced by the firm are translated into the formation of a road network in a GIS. I begin with a conventional production problem in which sawmill output is governed by a Cobb- Douglas function: Y=A.K';*:r~3L7 (31) where K1 is the amount of capital used in the sawmill (immobile capi- tal), T is the amount of roundwood input to production, and L is labor input. Y represents marketed sawmill output such as boards, plywood, and veneer. To simplify the exposition, I take the extraction of round- wood (T) as a Cobb-Douglas function depending only on capital, in this case mobile capital (K2): Y=Bwa am where ,u is a random disturbance representing uncertainties regarding the search for wood. Substituting 3.2 into 3.1, defining C E A33 and assuming 0 = 1 (constant returns to scale in roundwood production) the total revenue function is given as: R = pCKf’KngeM’ a, 6,7 > 0 where p is the price of processed timber. The random error )1 is taken to be normally distributed, leading to a multiplicative, lognormally distributed error term exp(afi). Given perfect competition in product and factor markets and independence of the disturbance, the expected total revenue becomes (Feldstein, 1971): E[R] = pCK?K28Lle%-"32” where 0 is E [#2], or the variance of the production function disturbance u. The cost function can be defined as: r(K1+ K2) + wL = F where r is the price of capital, 10 is wage rate, and F is the finan- cial constraint faced by the firm. The firm’s objective is taken to be the maximization of expected revenues subject to this constraint. This model differs from the ‘classical’ firm profit maximization statement, in which firms do not face financial constraints. The present model is con- sistent with the situation observed in many frontier areas where institu- tions (including financial and legal) are not well established (Schneider, 1995). Hence, scarcity of resources available for investment do pose a constraint to the firm. This constrained maximization problem can be 66 solved through the technique of Lagrangian maximization: x31"? A 2 = pcnggLieiW + Mr —- r(K1 + K2) —— wL] where A is the Lagrangian multiplier. The first order conditions are: 6:972 = apCKf_1K'23L7€%320 — Ar = 0 (3.3) 1 .52 = ,apCKOKB—lmeéfi’a — /\r = 0 (3.4) 8K2 1 2 2% = women—left“ — Aw = 0 (3.5) as b—X : F—T(K1+K2)—’LUL=O (3.6) Combining 3.3 and 3.4 yields: 16.9 (1 K1 (3.7) Likewise, combining 3.3 and 3.5, we have: L = 31K, (3.8) aw Equations 3.7 and 3.8 are the usual expansion path for a firm with Cobb-Douglas technology given constant factor prices. By substituting 3.7 and 3.8 into 3.6 and solving initially for K1 and later for K2 and L, 67 the Optimal amount of inputs can be stated as: F KI: a rh+fi+fl 6F K*— 2 rb+fi+fl L._ 7F wm+fi+fl Under constant returns to scale, a + B + 7 = 1, the factor demand functions simplify to the ratio of the technological parameters multi- plied by the constraint and the factor price. Given input prices (r, w) and technological parameters (0, 6,9,7), the logger will devote K 1‘ units of capital to the processing phase and K g to the extraction phase. Note that this factor allocation does not depend on the uncertainty in roundwood production but only on the technological parameters and financial constraint. The result gives the amount of financial capital allocated to labor, and to mobile and to immobile capital. Now that the amount of mobile capital is known, the spatial problem can be addressed, since this is the constraint c that bounds the search in the GIS optimization problem explained in below. 3.2.2 Determinate Roads As discussed, loggers are also actively involved in building destination determinate roads, and in Uruara, two such roads have been built to reach points on two rivers, the Tutui’ and Iriri. From field interviews (see 68 Appendix A), I know that loggers build such roads to get to navigable points on the rivers from where they lead finished products, such as sawnwood, onto ships for transport to markets. As such, the behavioral theory behind the construction of deter- minate roads is much simplified. Suppose a logger currently trans- ports products from sawmill to a distant market, using a pre-existing route. Let associated transport costs be T C1. Also suppose that the current state of operations is profitable, which implies that 7n = R — PC —— T C1 > 0 , where R is the revenue and PC are production costs, both of which are independent of distance. Since the logger has mobile capital available to build new routes, s/ he will search for pos- sible alternative routes to bring products to market. Given imperfect information about all possible routes, s/he will examine a finite set of possible routes i = 2, - - - ,N and will build the route i that maximizes profits or, 7r* = R — PC — TC* , where TC* = min(TC,-). This is necessarily a better option because 7r* > 7n as long as TC" < TCl. Therefore, profit maximization involves identification of the cost mini- mum route. 3.3 Computational Models of Roads The theory presented in the section above is abstract in the sense that no spatial outcome is delivered. Since roads built by loggers are inher- 69 ently spatial entities, I combine the theory with GIS to obtain spatial outcomes. In this section, I first describe the previous studies involv- ing GIS and network optimization relevant to my current application. Then, I explain the dataset used in the modeling effort, followed by a description of the software adaptations I did to model indeterminate roads. At the end of this section, I describe the results for both inde- terminate and determinate roads and the local socio—political ecology involved in determining the choice of road routes. GIS and Road Networks GIS has many applications to transportation and network systems but has not yet been used to model patterns of forest fragmentation based on road building. Consequently, the GIS objective of this dissertation is to develop an algorithm reflecting human behavior that can repli- cate the actual spatial signature of road building. I undertake model construction with a formal conceptualization of human behavior, then I observe the extent to which model outcomes are consistent with the actual roads observed. If the predicted roads are close to the observed roads, I conclude that my model is consistent with the decision-making process that led to the placement of the actual roads. I base my con- clusions largely on visual inspection, given the general lack of accuracy 70 metrics for this particular application.3 Early, pre—GIS approaches to network optimization assume the exis- tence of a road network represented by arcs and nodes, and the direc- tion of permissible flow“ Although an optimal route can be identified using linear programming techniques (Hillier & Lieberman, 1995), the problem of linking multiple points without a prior network is more challenging. Several recent advances in this regard have been made in graph theory and computational science, which refer to this class of problems as Euclidean Steiner tree problems (Ivanov & Tuzhilin, 1994; Warme, 1998; Promel & Steger, 2002), analogous to the multiple tar- get access problem in geography (Dean, 1997; Murray, 1998), which I will discuss in more detail in Chapter 4. A key GIS-based advance enabling the identification of the routes themselves was the Dijkstra algorithm. Finding the least cumulative cost for movement from some arbitrary origin cell to all cells in a grid can be computationally very demanding since there are a great number of possible route combi— nations linking the origin to the other cells. Dijkstra (1959) showed how to compute a cumulative cost surface efficiently by analyzing the neighborhood around the origin and gradually expanding the calcula- 3 Accuracy assessment metrics exist for two dimensional spaces [e.g., Pontius (2000); Walker (2003b)]. This application would require metrics based on one—dimension, to reflect arc intersections. 4 Indeed. routing problems date back to Euler ( 1707-1783) who proved the impossibility of cross- ing all seven bridges of K6nigsberg - Germany. without having to cross any bridge more than once, and Fermat (1601-1665), whose contribution to routing problems will be discussed in Chapter 4. tion until all cells are assigned a least cumulative cost. When the least cumulative cost surface is generated, a direction—to—origin grid is also generated, since each cell traversed in cumulating the least cost is iden- tified. The Dijkstra algorithm provides the optimal solution when there is only one destination point. Tomlin (1990) developed a heuristic solution to the multiple target access problem (MTAP) by applying a version of the cumulative cost surface approach to the identification of logging roads, adapting algo- rithms developed in hydrology. For Tomlin, the cumulative cost surface is an elevation map, and, pursuing the hydrological analogy, trees will be ‘drained’ to the origin by the least cost path. Eventually, the various paths will converge just as water converges to streams. Paths with the highest hauling traffic are then identified as logging roads, just as high- est accumulated flow paths are taken to be streams in the hydrological applications. Although the Tomlin problem is highly relevant to this particular application, its solution is limited in at least three ways. First, the roads identified are arbitrarily defined, since Tomlin necessarily assigns a cut-off based on hauling volume. Second, the solution is not glob- ally optimal because it fails to minimize costs on the basis of access to multiple cells using shared road stretches.5 And third, the Tomlin 5 Tomlin (1990) recognized this problem in his book and dealt with it by artificially decreasing the cost of transportation on the most used road segments. In other words, he 'burned in' the 72 solution identifies potential logging roads, because it is not known if the revenues generated by extraction will cover the costs of road construc- tion, a shortcoming also present in computer science applications. Such solutions may be meaningful in the case of US national forests when government constructs the roads, although presumably some standards of efficiency will emerge over the long-run. My goal is to use GIS soft- ware to define unique road paths that are optimal in the sense that they meet some behavioral object, such as profit maximization or cost minimization, which is what I expect to underpin the road construction process by private individuals such as loggers. Modeling Logging Roads on the Transamazon Highway The two types of roads found in the study area (destination determi- nate and indeterminate) require two different approaches to modeling. When destinations are indeterminate, the solution algorithm necessi- tates a software adaptation of the cumulative cost surface that identifies paths yielding the greatest volume of roundwood; this is because opti- mality requires the greatest amount of extraction per unit cost of road building. On the other hand, the knowledge of a destination, such as potential roads to decrease the cost-elevation grid to assure that, in subsequent iterations, more timber would be transported on fewer road segments. Unfortunately, this procedure works only if we have a relatively rugged cumulative cost surface. If the cost surface has the same traversing cost in all cells (i.e. the 3D representation of the cumulative cost. is a perfect bowl with the origin in the center). the Tomlin solution is a straight line linking each tree to the origin, which is clearly not. a global optimum. 73 with the river roads, greatly simplifies the computational problem, and simply requires parameterization of existing least cost software. Road identification is unique in both cases, and does not require a ‘cut-off.’ Topographic information is critical for assessing the cost of building roads. I obtained terrain data from the Shuttle Radar Topography Mis- sion (SRTM), which were recently generated for the Amazon basin and are available from the USGS web site (USGS, 2004). This space mis- sion, carried out by the Endeavor shuttle on February 2000, contained two radar antennas, one in the main body of the vehicle and another located at the end of a 60 m extended mast. Each antenna emitted and received radar waves to the same portion of the Earth’s surface at a given time. Since the distance between the two antennas was precisely known and held constant throughout the mission, the height of the sur- face could be determined by a method known as interferometry. The data was processed at NASA’S Jet Propulsion Laboratory and gradu- ally released to the public as each continent’s data were processed. For the United States, SRTM data postings are of l-arc second (30 meters) and 3-arc seconds for other areas of the world. NASA made data of the South American continent available for the public in 2002. For all simulations, road-building costs are taken as increasing func- tions of slepe. I defined the friction cost, or the cost of building a road through a cell, as the slope in percentage terms, corresponding 74 to the tangent of the angle. This was calculated with the Horn algo- rithm (Burrough & McDonnell, 1998). Translating slopes into costs is not a simple task in most GIS implementations because each cell has eight slope values, depending on the direction of movement to any of its neighbors. Since only one cost value can be stored in each cell, the Horn algorithm is a convenient way of assigning such value because it calcu- lates a weighted average slope of the eight neighbors to any given cell as exemplified in figure 3.2.6 The kernel moving window, with higher weights (2 or -2) assigned to the closest four neighbors, calculates the change in height values in both :1: and y directions (dz / da: and dz / dy), which then are squared, summed, and taken the square root, according to the example in figure 3.2. The SRTM template grid gave a mean Horn-slope, in percentage values, of 7.7 and standard deviation of 6.9 for the Uruara locale, with values ranging from 0.5 to 112. Assigning such friction values means that it is 200 times more expensive to build a road on a 45° slope (slope value of 100) than on the flattest cell on the grid (0.5). I also incorporated river features into the cost friction grid. Bridg- ing a river is more expensive then simply building roads upland. I converted the third and higher order stream line vectors, as defined by Strahler (1952) and obtained from Institute So’cio-Ambiental (2000), 6 I wrote a program that calculates the least cost path taking into account each cell’s eight slopes and applied to the skid logging trails modeling in Chapter 4. 75 dzldx (17de ”9.92% Kernel “$9399 9" o " ¢¢ o ‘23» .. «33¢ Slope = \/[((5 + 12 + 7) A (3+ 8 + 5))/8l2 + [((5 + s + 3) — (7 + 12 + 5))/8j'2 Figure 3.2. Description of the Horn algorithm used to calculate slopes into a raster, assigning a friction value of 75 to the cells. This value was arbitrarily chosen to be roughly ten times larger than the average slope in the study area.7 Figure 3.3 depicts the tract of the Titansamazon Highway in the study area, reconstructing the topography of the region from the SRTM data. The view is to the east, with Altamira in the distance, and Uruara’. in the foreground. The figure suggests that federal road builders paid some attention to construction costs associated with slope. I now consider the destination indeterminate and determinate roads cases in greater detail, giving a description of the algorithms used as well as the results obtained. I address the destination indeterminate roads first. and follow this with the determinate case. It is essential to 7 I consider it to be equally expensive to traverse a point on a river located either upstream or downstream in the study area. This assumption is reasonable for the rivers in question. For example. the Uruara River requires a substantial bridge far upstream. below the Transamazon Highway. 76 Figure 3.3. Perspective view of the Transamazon Highway. Landsat ETM+ image (2000) draped over DEM (SRTM) vertically exaggerated fifteen times. place the search for optimal pathways within the context of the micro- economic behavior of the firm, which was explained in detail in the previous section. The optimal amount of mobile capital K f resulting from profit maximization constrains the road construction in the GIS algorithm. This is the mechanism by_which I translate the economic constraints faced by the firm into the formation of a road network. In the destination determinate case, the behavioral problem is sim- plified, which facilitates the operational search for optimal pathways. 77 In particular, a destination is assumed to exist, which is part of the firm’s overall strategy to maximize profits. But because the destina- tion has already been identified, loggers presumably will minimize costs in building the roads to go there. Thus, the operational GIS model re- flects only this stage of profit maximization, and as a consequence I can rely on the ArcGis® implementation of the Dijkstra algorithm to identify the minimum cost pathways. 3.3.1 Destination Indeterminate The absence of a specific destination requires software modification to find the optimal road, as well as information on topography (costs) and the distribution of trees (revenues). Because I do not have tree distribution data in my possession, I assume that valuable hardwood is distributed uniformly across the landscape. The algorithm imple- mented in this case identifies road paths in three steps. In the first step for the initial time period, the cumulative cost surface is calculated from the original road network because loggers free ride on existing infrastructure; this is accomplished using the costdistance function in ArcInfo®, which utilizes the Dijkstra algorithm (ESRI, 2002). Let the accumulative costs at a given cell 9,- be described by the function v(g,-). I define a level set ll’> formed by cells 9,- such that 11’ = {9,- : v(g,) = c}, with constant c and N cells. Constant c was made equal to 10,000 units 78 of cost, taken to be the financial constraint on the units of mobile cap- ital depreciable in each iteration period, or year.8 Note that I assume the value of c in the present exposition, as well as in the modeling exer- cise. Nevertheless, c is derivable from the profit maximization problem shown in the logging firm conceptual behavioral model, and is there- fore a function of financial constraints faced by the firm, production technology, and economic conditions more generally. In the second step, the road extension segment is identified as the longest one joining each 9,- 6 IP’ to the original road network, or Road 2 max[L(g,-)] i = 1, - - - ,N, where L is length. The rationale is the assumption that the most efficient use of a fixed quantity of mo- bile capital, or the yearly depreciable amount, is the one that gives the greatest volume of harvestable wood. This is obtainable along the longest path when trees are distributed in a spatially uniform fashion, as assumed. Once the road segment is selected, it is added to the orig- inal road network in step three. The friction grid is then updated, and another cumulative cost surface recalculated, which changes with the additional segment. I repeated the process 60 times to simulate the temporal evolution of the road network. Results of simulations for the destination indeterminate case are given in Figure 3.4, which overlays the modeled paths onto actual roads 8 In reality, since the cumulative cost values are float numbers, I selected the grid cell with values greater than 10.000 and smaller than 10.010. 79 existing in the study area. In all of the figures, the Transamazon High- way and original extent of the settlement roads constructed by govern- ment are given as black lines. The deforested areas are pink in color, and show the actual road extensions that have occurred in the wake of early colonization, which began about thirty years ago. Simulated roads are depicted as yellow line segments. Note that simulation space has been constrained by the protected area of the Araras Indigenous Reserve to the South, shown in light magenta in Figure 3.4.9 3.3.2 Destination Determinate The simulations for the destination indeterminate case reflects a fully developed theoretical model based on profit maximization subject to financial constraints, and which allows for a search over all possible routes for profit maximizing purposes. Nevertheless, key informant in- terviews of loggers suggest that explicitly spatial objectives often highly constrain the route selection process, particularly in the case of longer roads requiring substantial capital investment. The two most impor- tant logging roads in the study area, the so—called Transiriri and the Transtutul', were built in order to reach specific destinations. The Tran- siriri links the TYansamazon Highway and Uruara to the Iriri River in 9 I assigned a friction value of 120 to the cells inside the protected area. This value was chosen because it is slightly above the maximum slope value of 112. Since the friction value was defined as slope in percentage terms. a value of 120 is equivalent to a 50" slope, which effectively makes road construction too costly. 80 mm- Legend -— Original road network — Simulated logging roads 0 15 30 Kilometers Figure 3.4. Destination indeterminate simulation. the south, a major tributary of the Xingu River, while the Transtutul’ provides a link north, to the 'I‘utui River, which ultimately flows to the Amazon River (Figure 3.5). The actual paths of these roads were identified by visual interpretation (RGB 5 / 4/ 3 color composite) of four 1999 Landsat ETM+ images (paths: 226, 227 and rows: 62, 63) and were on—screen digitized at 1:50,000 scale. I consider each of the roads in turn. Although I know from key informants that the final destina- tion of the Transtutul’ is near the convergence of the Tutui’ and Uruara Rivers, I was not able to identify on satellite images the path beyond 81 the digitized segment in figure 3.5. Legend — Road network (20 km) — Major Rivers — Transtutui — Translriri l——_'——fi $ 0 25 50 Kilometers Figure 3.5. Major destination determinate logging roads in Uruara. To replicate the evolution of the so-called Transiriri, I solve for the least cost path from Uruaré. to any segment of the river, including movement along the Transamazon Highway. The costs, as discussed, were calculated using topographic data from the SRTM project and hydrological maps. According to field informants, the area along the Iriri River east of Uruara is susceptible to regular flooding during the rainy season, which imposes a serious cost increment to road builders. Indeed, I was able to identify those areas using 1:100,000 quad sheets 82 MI-654, MI-721, and MI—722 from Institute Brasileiro de Geografia e Estati’stica, or IBGE.10 The results (Figure 3.6) show that the simulated least cost path in yellow diverges from the actual Transiriri, given in blue. The ‘optimal’ path starts directly in the town of Uruara, reaches the end of the official road network, then runs south, contouring the major slope gradients, and reaching the Iriri River four kilometers downstream from the actual destination. As can be observed, the actual path begins 5 km west of Uruara and heads south to the river until it meanders right less than ten kilometers from its destination. Note that in this and the subsequent simulation, the initialized road network in black is set to 20 kilometers rather than six. Both the Transiriri and Transtutui were built after 1980, when many of the settlement roads had already been extended to 20 kilometers in relatively straight lines. The other significant logging road in the region links Uruara to the junction of the Tutui/Uruara Rivers where, according to informants, it ends to the north. The yellow path is very different from the ac- tual route but similar to historical accounts of the original route. The Ti‘anstutui was originally a direct extension of the settlement road start- ing 15 kilometers east of Uruara, as captured by the simulation in figure 3.7; its present-day path begins in the town itself and heads east until 1" I also assigned a value of 120 for the cells inside these potentially floodable areas. 83 Legend Actual Path Road Network (20 km) l——_V—fi $ 0 1O 20 Kilometers Figure 3.6. Simulation of destination determinate 'Ilransiriri logging road. 84 reaching its original route, where it continues north to the river.“I sim— ulate this ‘second best’ solution by incorporating what key informants refer to as pontos obrigato’rios, or necessary points of route passage. I take these to be the actual intersections of the Transtutui with the settlement roads between Uruara and the original one selected for ex- tension to the river. The simulation result given in Figure 3.8 is largely coincident with the actual route, given in blue, with two discrepancies at points A and B. 3.4 Discussion The model applications perform better for the determinate than for the indeterminate case. The simulated indeterminate logging roads are dispersed and fragmented, similar to the dendritic pattern described in Haggett et al. (1977), and begin to show direct extensions of individual settlement roads, as has occurred historically. However, the actual ex- tensions, as can be observed from satellite images, and as substantiated by field interviews, were mostly linear. Evidently, settlers arriving after initial colonization in the early 19703 extended the original spurs lin- early by marking 100 hectare lots (400m x 2500m) identical to the first 1’ This detour from the ‘optimal route’ arose due to a conflict between a colonist, whose lands were on the best route. and the road-builder. who owns one of the two largest sawmills in town. The logger wanted to construct a detour through the colonists lands to avoid a low drainage spot and offered money. The. colonist did not. accept the offer. and the road-builder opted for the present path which originates in town, and traverses two settlement roads to merge with its original, optimal path. Lgend” 7 _ 7 Road network (20 km) Actual Transtutul r—-"‘r—1 $ 0 10 20 Kilometers Figure 3.7. Simulated Transtutui with destination determined at junction of Uruara and Tutui Rivers. settlers, hoping that government would subsequently regularize hold- ings. The settlement road to the north, five kilometers east of Uruara, is illustrative of this process (so-called 175N). According to key infor- mants, the federal government opened the initial spur in 1975. This was followed by subsequent expansions in 1982, 1988, 1994, and 1999, given that colonist demand for land remained high. A local rancher undertook the second expansion in 1982, while municipal government added a nine kilometer addition in 1988. Loggers did not participate in 86 legend7 7 Road network (20 km 3 Actual Transtutui Major rivers lhrmoiaesto - s r__—fi——l $ 0 10 20 Kilometers Figure 3.8. Simulated Transtutui’ with pontos obn‘gato’n'os (mandatory waypoints) included. extending the road until 1994, after it had already reached a distance of 25 kilometers from the Transamazon Highway. As can be observed from the satellite imagery, the road itself shows a reasonably straight path, extending directly from the first opening by the federal government. It can reasonably be assumed that loggers, while not involved in the first three extensions, exploited wood from the newly colonized holdings, in which case they acted as free-riders on the extension process until 1994, about twenty years after the initial opening. This sequencing contrasts 87 with other parts of the world or even other regions in Amazonia, where loggers have often extended roads that were then followed by colonists (Walker, 1987). Expectations of colonists, responsiveness of federal government to land claims, and political relationships between colonists and local gov- ernment appear to have set in motion the linear nature of the expan- sions of destination indeterminate roads, at least out to about thirty kilometers, beyond which loggers enter the picture as the primary road- builders. The implication is that free-riding by loggers has remained possible far beyond the initial construction of the spurs, although even- tually they become responsible for new extensions. Current Brazilian law appears to encourage this by (1) drawing a distinction between the wood resources of loggers and colonists, and by (2) giving loggers two legal ways to access standing timber. In particular, the Brazilian Forestry Code (Law 4771/65) allows log- gers to take timber from natural forests though deforestation (clear cutting) or via forest management (selective logging). The latter ap- proach requires that forest engineers submit a forest management plan to Brazil’s environmental agency, IBAMA, in a highly complex and bureaucratic process that includes on—site visits by enforcement offi- cers and may take several years for approval. This turns out to be quite costly in terms of time and actual resources, so loggers often opt 88 to secure their raw materials from allowable deforestation. In this re- gard, smallholders (S 400 hectares) have fewer legal requirements than largeholders (such as sawmill owners), which facilitates exploitation of their standing timber. Up to fifty percent of a smallholding can be deforested, as compared to twenty percent for large properties.12 In addition, smallholders can legally exploit up to 20 m3ha’1 of timber during the deforestation process without obtaining either a license or permission (Normative Instruction 003 from the Ministry of the Envi- ronment, 10 March 2002). This sharply contrasts with the legal burden on largeholders, who must submit an environmental impact statement to IBAMA prior to obtaining a deforestation permit, which is costly (Barreto, 2002). Largeholders must also prove that they have land title, a simple task for colonists settled by government-sponsored col- onization projects. For reasons such as these, loggers often take their raw material inputs from smallholdings in new colonization sites, such as found in my study area. Evidently, concerns about the regulatory environment together with a growing population of colonists have provided loggers with strong in- centives to help extend the original settlement roads into the emergent fishbone pattern, even if they are not optimal according to the eco- 12 According to the Forestry Code of 1965, both large and small properties were allowed to deforest up to 50%. In 1996, a new regulation lowered this percentage to 20% for large properties but maintained the original percentage for small farmers (Provisory Measure 1511 from 25 July, 1996) 89 nomic model presented here. Of course, if local government bears the road-building costs, and loggers are permitted to take wood off lands allocated to settlement as currently permitted by Brazilian law, the straight extensions will be economically optimal. Simulations for the determinate case, based on straightforward least cost calculations, do appear to have predictive ability for the large sawmill interests intent on substantial expansion of individual roads beyond sanctioned areas of colonization. For the two major logging roads in the study area, the simulations come reasonably close to find- ing the actual routes. This is especially so for the Transtutul', although the routing ultimately changed in the wake of a localized dispute over a detour. Of course, in both cases I introduced a known destination into the search algorithm, namely a river segment. How water access fits into the overall strategy of profit maximization in these specific cases remains an empirical question, although the conceptual framework de- scribed in the previous section states a possible theoretical rationale. In general, the present approaches suffer from three limitations. First, I have stated the models to reflect choices of individual agents act- ing freely in pursuit of purely economic objectives. It appears, however, for the destination indeterminate case that multiple agents, including colonists, loggers, and local government, have been at work in shaping the landscape within both institutional and legal constraints. Thus, 90 the conceptualization of the destination indeterminate process as aris- ing from a single agent acting freely in the absence of social context is incomplete, and does not give rise to the fishbone pattern of forest fragmentation.13 A related shortcoming pertains to my inability to reflect the contin- gent and often unpredictable nature of social and political interactions at ground level in the road construction process. Key informant inter- views indicate that the Transtutui route was strongly influenced by a struggle between a well-capitalized logger, aligned with municipal gov- ernment, and a colonist land-owner. In addition, a secondary struggle emerged when spontaneous colonists attempted to occupy the lands that the logger desired to pass through. The first conflict affected the final route, which detoured considerably from the initial one that was a straightforward extension of the settlement road fifteen kilometers east of Uruara (165N). I do not know the impact of the second conflict, al- though the logger was evidently successful in appropriating these lands and displacing the colonists. As can be observed by reference to figure 3.7, the route deviates considerably from a straight line as it gains dis- tance from the Transamazon Highway. Colonist occupation of distant ‘3 To address certain institutional constraints, such as the inviolability of Indigenous Reserves, I resorted to using a high friction value in the simulations. This has the effect of making passage too costly. in economic terms. Walker (2001) concept1.1alized environmental protection in South Florida in a similar fashion. Moral issues aside, profit maximizers resist. incursions into unused public lands - and appropriation of public resources — if the cost. of doing so. through legal sanction, exceeds the benefit. 91 lands would probably have imposed costly constraints on road con- struction, had they insisted on replication of the settlement geometry closer to the Transamazon Highway. Presumably, the road builder’s de- sire to reach the Tutui River outweighed interest in potential revenues obtainable from colonization. A final limitation is my assumption about the uniform spatial distri- bution of trees, which transforms the longest into the optimal route for the destination indeterminate case. Imposing empirical tree distribu- tions onto the cumulative least cost surface would represent a consider- able improvement, particularly for extensions of fishbone networks far from main highways, in parts of the landscape less-desirable to colonists because of transportation costs.14 1“ Field interviews suggest that such information. particularly at regional scale, could help to shape some of the destination choices made by well-capitalized loggers, like those who opened the Transiriri and Transtutui. Model simulations that fully endogenize such points on the landscape await the incorporation of complete data including tree distributions. 92 CHAPTER 4 Modeling Logging Skid Trails In the previous chapter, I developed a behavioral model to explain the process of road expansion carried out by loggers. I also tried to mimic in a GIS the expansion of settlement roads (destination determinate and indeterminate) in a portion of the Brazilian Amazon near the town of Uruara’. on the Transamazon Highway. In this chapter, I will present a GIS algorithm to model logging skid trails, which are built by loggers to actually reach the trees to be harvested. The GIS model consists of two distinct stages that imitate the actual decision making process of loggers. In the first stage, loggers identity a logging site rich in timber to be extracted and build a main road linking the site to the nearest infrastructure, which is usually a state or federal road. In a GIS, this first stage is accomplished by defining a polygon encompassing the trees to be harvested, which I refer to the least cost convex hull set, and by finding the least cost path between currently existing infrastructure 93 and the logging site polygon. In the second stage, loggers build a network of skid trails connecting each tree to the main road. The GIS objective here is to find the minimum-length (measured by a building cost metric) interconnection of all trees to an origin, from where the timber will be transported to a sawmill. This second stage is equivalent to finding the so—called ‘minimum Steiner tree’ (MST) that connects a set of terminals, which in the present application constitute the trees to be exploited. The MST is an extremely difficult problem to solve. Given N points (or terminals) in a plane (Figure 4.1, panel A), it seems deceptively trivial to find a connected network linking all N points such that this network has minimum length. This apparently easy problem is in- deed very difficult because one is allowed to add nodes in the network. Hence, the difficulty lies on finding how-many extra nodes should be added and where should those nodes be placed in order to minimize the total network (Figure 4.1, panels B and C). Mathematicians and computer scientists have relied on computer algorithms to solve the MST problem (MSTP). But even algorithmic implementations have shown limitations. In fact, there is no known computer algorithm that guarantees a solution in a reasonable amount of time.1 1 Indeed, the MST was not even known to be a finite problem until 1961 when Melzak (1961) showed it was bounded. To my knowledge, the Euclidean Steiner minimum tree with largest number of terminals (2.000) was found by VVarme (1998). 94 .. ' A D . . o "L—fi . ° t. o f L ... o B .a E (Logo—n67 '— 0 Terminals . Added Nodes — Euclidean —— Spanning “—‘V- __ 5599“???” Figure 4.1. Euclidean l\linimum Steiner, Spanning, and Rectilinear Trees Most of the algorithms available to date were developed to find the minimum network in a Euclidean plane (Warme, 1998). Hence, these algorithms minimize the total network length in an Euclidean metric space. In a raster GIS data model, the MST problem differs from the Euclidean metric space in two ways. On the one hand, the MST problem is simplified because the nodes are fixed in a raster model, that is, the number of cells or the extent of the grid is fixed. Hence, one does not have to add extra nodes, although one still has to determine which nodes to choose in order to build the network. On the other hand, the MST problem becomes more difficult in a GIS, when compared to the Euclidean metric, because the objective is to minimize the cost of building the network. As such, terrain characteristics, such as slope, must be taken into account. For example, a minimum network might be tortuous, instead of composed of straight line segments, to avoid high building costs associated with steep slopes. Current GIS minimum path cost algorithms such as Dijkstra’s and Tomlin’s, described in the previous chapter, do not produce minimal networks when the number of terminals is greater than two. Therefore, modifications of current algorithms are necessary to produce better re- sults. Although the algorithms I developed do not produce the minimal possible network either (i.e. the ultimate optimal solution), they do re- turn better results than those advanced by Dijkstra and Tomlin. The chapter is organized as follows. In the first part, I explain the algorithmic GIS implementation in the context of the behavioral profit maximization theory of Chapter 3. Next, I present the Steiner tree problem, adapting graph theory concepts to the GIS environment, and explain the complexity of such optimization problem. I then outline 96 the GIS algorithms I developed to model the building of logging skid trails. Finally, I describe the dataset used in the exercise and the results of the simulations, and I discuss the impact of skid trails on forest fragmentation. 4.1 Skid Trails The behavioral theory behind logging skid trails is similar to the case of determinate roads. From field interviews (see Appendix A), I have learned that the most valuable timber species, such as cedro (Cedrela adorata), ipé (Tabebuz'a 3p.) and mahogany (Swietem'a macrophylla), usually occur in clusters in the landscape. Loggers typically hire ex- perienced surveyors, called mateiros, who are incredibly knowledgeable about timber and possess an acute sense of orientation under closed forests. These surveyors assess the economic potential of certain sites, which can be tens or even hundreds of kilometers away from the nearest infrastructure. The mateiros find trees, mark them on the ground and plot their location on a hardcopy map. In some cases, when openings in the canopy allow, GPS coordinates are also recorded. This informa- tion is then passed on to the logger, who assesses the expected profit of the site. Once s/he is convinced that it is profitable under his/her current capital constraint, s/he will move on to the build road/ trails. Profit, maximization behavior here also implies minimizing road/ trails 97 building costs, since capital allocation decisions between extraction and processing were previously made, and can be considered fixed in the short-run. Key informant interviews also suggest that loggers separate the road building task into two distinct phases. In the first phase, they build a main road to connect the extraction site to the nearest built infrastruc- ture. This phase is similar to the destination determinate case, with the extraction site being the destination. In the second phase, loggers engage in building a series of small skid trails to access the trees to be harvested. Road building cost minimization implies finding a trail network, not a single line segment, linking the main road to multiple terminals, namely the trees to be harvested. Therefore, profit max- imization involves identification of the cost minimum network or the minimum Steiner tree. The GIS approach I developed mimics these two phases. In the first phase, I adapt the concept of convex sets to define the logging site and then link this site to the current infrastructure by the least cost path. In the second stage, I create the minimum cost network to connect each tree and the main road. Before I explain these two algorithms, I first describe the Steiner problem and the GIS challenges to solve it. 98 4.2 An Introduction to Complexity Theory As mentioned above, finding the least cost network in the logging skid trails case is the same as finding the minimum Steiner tree in the build- ing cost metric space. However, this is not a trivial Optimization prob- lem that can be solved numerically or algebraically. Computer scientists classify how hard any optimization problem is by measuring the number of operations or the execution time (also known as time complexity) an algorithm needs to perform to return a solution as a function of the amount 77. of bits of input data. For ex- ample, sorting problems (ascending or descending sorting of numbers or strings) are considered to be easy problems because there exist a1- gorithms that return the ordered list relatively fast (Andersson et al., 1998). Moreover, if a list consists of two elements (n = 2), the cor- rect ordering can be obtained much faster than if a list contains 20, 000 elements. A problem of size n bits of input data is said to be easy if there exists an algorithm that can solve it in n” time, where p is a constant. These easy problems belong to a set labeled P and are said to have polynomial complexity because they can be solved in polynomial time (constant p is the degree of the polynomial term). In other words, easy problems are tractable because there is an algorithm to solve them quickly. Formally, 99 fast algorithms are known to have 0(7),”) complexity. A formal definition of the ‘0’ (big O) notation is provided as follows. We say that a function f is 0(g(n)) if there exist a constant C and an integer N such that I f (72)] < Cg(n) for all n > N. One can think of this statement as “f certainly doesn’t grow at a faster rate than 9” as the size of a given problem increases (Wilf, 1994). The least cost path between two points belongs to the set P because the Dijkstra algorithm can solve it in 0(7),?) time (Greenberg, 2001). A larger superset named nondeterministic polynomial (NP) contains the problems for which a trial solution can be verified in polynomial time. In other words, once presented with a potential solution, there exists an algorithm to verify whether this solution is correct or not in polynomial time. A mathematical analogy can help understand this concept: it is much easier to verify the correctness of a proof of a theorem than actually find the proof itself (Wilf, 1994). A subset of NP, called N P—complete, contains those NP problems for which an algorithmic transformation or reduction in polynomial time can be performed. Sometimes, in order to solve a problem, it is necessary first to transform one problem into another. For example, suppose we want to solve a system of equations such as Ax = b, where A is a non-symmetric matrix. If we pre—multiply both sides by A’, we get A’ Ax = A’b, which is a much easier system to solve because 100 the inverse of a symmetric matrix is easier to obtain. In this example, we basically reduce one problem into another. One characteristic of N P—complete problems is that if any problem were in P then all would also be in P because one could simply reduce, in polynomial time, this problem into another problem that could be solved in polynomial time. I say ‘could’ because, to this day, there is no N P—complete problem known to be in P. In other words, there is no known algorithm to solve any N P-complete problem in polynomial time.2 Finally N P—hard problems are those optimization problems that call an N P—complete problem as a subroutine. Steiner minimum problems are known to be NP—hard (Garey, Graham, & Johnson, 1977), the most difficult class of optimization problems. When exact algorithms exist to solve NP- complete problems, the time complexity grows exponentially (n is the exponent not the base as it is the case of polynomial complex problems) or superexponentially as the size of the problem increases. ‘Hard’ problems can have particular easy instances that can be solved though. These algorithmic complexity classifications are ap- plied to the ‘worse’ possible instance of a given problem or when 72 gets very large. For example, a system of linear equations can be solved using Gauss-Jordan elimination algorithms in 0(n3) time by multiply- ., 2 The possibility the set P is the same as NP (P i NP) is still a famous open problem in computer science and mathematics but. most computer scientists believe NP is a much larger set that contains P or NP (1 P = P (Greenberg 2001). 101 ing, adding, or interchanging matrix rows. Clearly, it is much faster to find the solution if the original system is already similar to an identity matrix (Greenberg, 2001). Despite the nonexistence of a fast algorithm to find a minimum net- work to the Steiner tree problem, approximate solutions exist once ad- equate information is given to the algorithm. Moreover, there are exact solutions for easy instances of the MSTP. In particular, a GIS solution using the Dijkstra algorithm as a subroutine is feasible involving two or three terminals. For the two terminal case, the minimum Steiner tree problem reduces to a simple least cost path between an origin and destination that can be solved in polynomial time using the Dijkstra algorithm.3 For the three-terminal case, the solution can be found with a bit of manipulation. The idea is to find a fourth node 19 and calculate the minimum cost distance from p to the original three terminals. The addition of this ‘extra’ node is crucial for finding a better (cheaper) network. In the next section I will formally describe the Steiner problem and will show two algorithmic approaches to finding an approximate solu- tion in a raster data model. Before this, though, I must first provide several definitions taken from graph theory and apply them to the GIS environment. The notation and definitions were mostly taken from 3 In the case of two points on a plane, the Greeks knew thousands of years ago that the shortest path connecting those two points is a straight. line. 102 chapter 1 of Promel and Steger’s (2002) book. 4.3 Graph Theory and the Steiner Tree Problem A raster is a finite regular lattice where each cell’s center point or node is linked to the adjacent cells’ centers. The nodes are the vertices in graph theory terminology and belong to a set labeled V and the lines linking any two adjacent vertices are the edges in set E (Figure 4.2). Terminals are a subset K of V (K g V), or origins and destinations in transportation geography. A graph G is defined as a pair G (V, E), where E are the edges or the finite set of linked unordered pairs of ver- tices in set V that make up the graph. A weighted graph W is defined as a triple W = [V, E, 7], where the function 7 assigns a nonnegative value (or cost) to each element in E, or 7(E) +—> R20. In raster termi— nology, this function o/(E) is the cost of building or traversing all the edges E that form the paths connecting the vertices V in graph W (see also equation 4.1 below). Two vertices (or nodes) 2),- and vj are adjacent in G if they form an edge or vi, 223- E E. The neighborhood of a vertex v are all nodes u E V such that v, u E E. The number of neighbors of a vertex v is called the degree of U, which is known as the beta index in transportation geography (Haggett & Chorley, 1969), and is denoted by d(v). In a typical raster environment, d(v) for any given cell can be at most eight 103 (queen movement or Moore neighborhood), for cells not located at the border of the grid.4 Figure 4.2 is a representation of a 4 x 5 raster or grid showing the nodes (black dots) at each cell center and the corresponding edges (line segments) linking the cell in the middle to all its neighbors. I I/I\I I —- Edges 0 Set V of nodes or vertices 0 Set K of terminals or origin/destination Figure 4.2. Raster data model A tree is an acyclic connected graph G, that is, between every pair of distinct vertices there is a unique path to them (Figure 4.3). In other words, each terminal can be reached by a single, unique route. Also, a leaf is a vertex of degree one, which makes it a terminal point in a tree, although the converse is not true. The branching points of a tree are all the vertices U such that d(v) 2 3. 5 Given W = [V, E, 7], the minimum Steiner tree for K, where K is 4 In an m x n rectangular grid (m. n > 1), the largest numbers of elements in V and E are easy to determine. V is simply 771 times n and E 2 21:1 p,d(-v,)/2 where p1 = 4 and (1(v1) = 3zp2 = 2 x (m - 2) and (1(122) = 51m = 2 x (n — 2) and (1(193) 2 Exp; = (m — 2) x (n — 2) and d(v4) = 8. The four vertices on the corners (v1 type) of the grid extent have only 3 neighbors: vertices on the border of the grid (v3 and 11;, types) have 5 neighbors. while vertices in the interior of the grid (v4 104 . .\. . . .\./. —— Cyclic graph => not a tree — Acyclic graph or tree 0 Terminals o Branching points of a tree. (1(u) = 3 Figure 4.3. Acyclic and cyclic graphs the set of terminals, is a subgraph S of G (V, E) containing all vertices of K and possibly elements of V as well such that 7(S) is minimum. The cost of a path (or the subgraph) S joining all vertices of K is: 7(3) = 2: 7(6) (4-1) e€E(S) Taking the acyclic graph in figure 4.3 as an example, 7(S) is the sum of the cost of building or traversing five edges e. In a raster environment, the cost (7) of traversing an edge 6 con- necting two adjacent cells’ centers (v1, 212) is given by: type) have eight neighbors. 5 Graph theory terminology applied to a forestry operation is a little confusing because a tree is a connected graph while the trees to be harvested are actually the terminals in graph theory. ‘l—‘C :69 if connected horizontally or vertically 7(6) = (4-2) ELSE; X \/§ if connected diagonally where c1, c2 are the friction costs or the cost of traversing each cell. The least cost network is then simply the cheapest route linking all points in set K, 7(S) = min{7(S’)|S’ are all possible Steiner trees for K in V}. As mentioned above, if K is formed by two elements {190,191}, or an origin and a single destination, then the Steiner tree is formed by seg- ments with degree at most 2, that is, each node is connected to at most two other nodes and the origin and destination terminals are necessar- ily of degree 1 (Figure 4.4). The optimal least cost path can be easily found by applying the Dijkstra algorithm. For reasons to be explained shortly (i.e. adaptation of spanning and rectilinear algorithm), define a new set Q that contains the terminals K and the nodes that make up the least cost path between {k0, 131}. In reference to figure 4.4, this set Q contains five elements (two terminals and three nodes). A spanning minimum tree for K is a subgraph S of C(V, E) such that all terminals K are also the nodes (i.e. no Steiner point is inserted to generate a smaller tree) and 7(S) is minimum (Figure 4.1 panel D). A rectilinear Steiner minimum tree is only interconnected by horizontal or vertical segments. Hence, all intersecting lines form either a 180" or 90" angle (Figure 4.1 panel E). 106 I I “/5. 0 Set K with two terminals Elements of V\K (V not in K) that are part of the solution All vertices in path have d(z:) S 2 Figure 4.4. Example of a. fictitious least cost. path between two terminals Suppose now that K is formed by three elements {k0, k1, k2}. Let 7(S1) be the least cost path associated with graph S1 (one of the sides of a triangle) that links kg to k1 or, 7(51) = 2 7(6’) eIEE(Sl) Likewise, let 7(S2) be the least cost path associated with graph S2 (another side of a triangle) that links k0 to leg. Now, suppose we want to find the least cost path 7(S) associated with the graph S that connects the three vertices in K. Define a graph S’ formed by the union of the two previous graphs S 1 and S2 and let 7(S’) be its associated combined COStZ 107 7(3): 2: 7(6’)+ 2 7(62)- 2 7(6“) (43) e1€E(Sl) e2€E(52) e"e(E(Sl)flE(Sz)) The last term on the right hand side is the cost of the segments 6“ that are part of both graphs 31 and S2 and, therefore, should not be double-counted. In the case of a triangle in plane geometry, this last term is zero because both paths overlay only at point k0. If we apply the current GIS functions, which use the Dijkstra algorithm, to this problem and assuming a homogeneous surface (i.e. same friction cost for all cells), the graph displayed in figure 4.5 is the output solution. IV I 72 . .v. . O S 1 Least cost path from k, to k” 0 52 Least cost path from kg to [co Figure 4.5. Ordinary least cost path for a triangle in a raster model This network is the optimal solution if one wants to minimize the transportation time from points 121 and kg to leg. However, in most applications involving roads, the interest lies on minimizing the building 108 cost (Bunge, 1966). As such, the objective is to find the network with minimum length or, in my GIS application, the minimum length in a building cost metric. It can be shown that there exists a ‘smaller’ or ‘cheaper’ graph S such that the cost of building it is smaller than or equal to the cost of building S’, or 7(S) S 7(S’). When K has three elements, the Steiner tree problem is also known as the Fermat triangle problem, named after the French mathematician who proposed this problem in the 17th century. In a two dimensional Euclidean plane, the three elements of K are the vertices of a triangle and the graph S’ comprises two edges of the triangle such that d(k0) = 2. In raster language, Fermat showed that there exists a point p E V such that: 2 7(2) H Z 700 >+ 2 7(1) p06E(P0) 1) 6E (P1) p2€E( P2) where Z 7(p’) is the least cost path linking the point p to each of the triangle vertices k,- = 0,1,2. The sum of these three least cost paths, 7( S), is the minimal network linking the three vertices in K. The point p is also known as the Fermat or Torricelli point of a triangle (Figure 4.6). If any angle formed by two edges of the triangle is greater than 120° then p is the vertex of such angle, i.e. p E K ;6 otherwise p E V\K (read 6 In this case. the Steiner tree will be the same as the spanning tree. 109 O Terminals Fermat Point (branching point) Figure 4.6. Minimum network in a. raster model with 3 terminals p is a vertex (node) not in the set of terminals). Note that d(p) = 3 if the angles of this triangle are smaller than 120° and the Steiner tree graph will resemble a ‘Y’ with point p located exactly in the intersection of the three lines and the k’ 3 being the endpoints of such lines. In other words, p is a branching point (Figure 4.6). The discussion above shows that the least cost path functions cur- rently available in many GIS software, which use the Dijkstra algo- rithm, can find the minimal network connecting two points, but once more than two points are included in K, the solution may not be op- timal if one is interested in minimizing the total network length. The major challenge in a GIS environment is to find the branching points p ¢ K that make part of the solution to 7(S). It turns out that a series of manipulations using the Dijkstra algo- 110 rithm can also provide the optimal solution to the problem of finding the minimum network linking three points. Suppose we have a raster grid with j = 1, - -- ,N cells. Let gij be the minimum cumulative cost from cell j to the terminal k,- : i = 1,2,3 provided by the Dijsktra algorithm. In other wordS, 9273' is the result of running the Dijkstra algorithm considering each terminal k,- as the source or origin. Then, 3 p=min [29,7], j=1,~- ,N i=1 The paths linking p to the terminals {k0,k1,k2} is the minimum Steiner tree. The proof is almost definitional because p is the smallest sum of the minimum distances (or costs) to the three points. Therefore, the point p is the Fermat point or the branching point of the minimum Steiner tree. Hence, we can find the node (or cell) p by running the Dijkstra algorithm from each k,- separately, summing the three accumulative cost grids and checking for the smallest value in the resulting grid. The minimum network linking the three cells can be calculated backwards from the cell p to the three original terminals (kits) by running the Dijkstra algorithm again but taking the node p as the origin and the three terminals (lei/S) as the destinations. The incorporation of the point p basically transforms the Steiner tree problem into a least cost path problem. As such, the solution basically requires applying the Dijkstra 111 algorithm (at most) four times.7 Geographers have been working on problems similar to this for many years. In fact, a similar approach to the one described above has been used to study the location of firms. These studies data back to 1909 when Alfred Weber published a book on the topic, although some au- thors suggest that Wilhelm Launhardt found the same results much earlier in 1882 (Weber, 1909; Puu, 2003). Indeed, geographers might be familiar with the term ‘Weber triangle’ but completely unaware of the term ‘Fermat point.’ An important group of geographers worked on location and network problem during the so—called quantitative rev- olution in geography in the 1960s and 19708. These works are best summarized in the book “Location analysis in Human Geography”, where Haggett et al. (1977) described several methods designed to tackle the minimal network problem such as the mechanical link-length minimizer, which is also known as Varignon machine, nonlinear opti- mization, and the soap-film method [see Haggett (1967); Haggett et al. (1977) and Morgan (1967) for details on these methods]. Surpris- ingly none of these authors mention either the Fermat problem or the Steiner problem which have a much older history in mathematics. More 7 A similar approach could be used to find the minimum tree connecting four points but ex- periments I did (not shown in this dissertation) suggest the need to calculate seven accumulative least cost surfaces. The number of operations necessary to find a solution seems to increase at least exponentially as the size increase from a two-terminal to a four-terminal problem, which is a characteristic of N P—complete problems. 112 recently, Dean (1997) showed how to calculate the Steiner point in a GIS but he did not provide a rigorous description of his methods or relate his approach to either the Fermat point or the branching point of the Steiner tree, either.8 4.4 Modeling logging skid trails in a GIS The GIS application in this section assumes that the costs of building skid trails are much higher than the cost of transporting logs and hence, the objective of the logger is to minimize building costs, not transporta- tion costs or a combination of both. Indeed, empirical studies in the Amazon have shown that the cost of building these feeder roads are at least four times more expensive than the cost of transporting cut logs (Stone, 1998; Verissimo et al., 1998). I also assume that this is a one- time minimization problem or that there is no dynamics involved in it. In practice, the evolution of the road network is dynamic. According to field informants, loggers usually build roads to exploit timber in one site in a given year and are aware of potencial logging sites nearby for subsequent exploitation in following years. Hence, the Optimal design of roads in a dynamic context might be different than for a one-time exploitation. 8 Dean (1997) did not claim that the path linking the Fermat point to three terminals is the minimum network either. 113 In the previous section I showed that finding the minimum network interconnecting several terminals is a very difficult problem and that exact minimum length networks are possible to obtain in a GIS for the case of two and three terminals. In this section, I will describe the algorithms I developed to emulate the two different phases of the logging extraction process adopted by loggers, namely (1) the definition of the logging site and (2) the construction of a skid trail network cheaper than the solution provided by current GIS algorithms. For this second logging extraction stage, I developed two algorithms that make use of the graph theoretical material presented above. As described in section 4.1, in the first step of the logging extraction process, taken to exploit an area, a logger defines the boundaries of the logging site after a surveyor has identified valuable trees. In a GIS, I define the ‘logging site’ by computing the ‘least cost convex hull set’ (LCCHS) of all trees, presumably identified by a surveyor. A set X is said to be strictly convex if for any pair of points 330, 2:1 E X , the point :1: is also an element of X, where x=Ax0+(1—A)a:1 AE(0,1) In other words, a convex set has the property that all points on a segment, connecting any two points in the set are also in the set. The convex hull is the smallest convex set that contains all elements of a 114 given set. I adapt this definition to the least cost path problem as follows. Suppose we have a set T with n elements, or terminals. Then, a LCCHS is defined as the smallest set containing all elements of T such that all points that are part of the least cost path between any two points t0,t1 E T also lie entirely within this set. Thus, the logging site is taken to be the boundary of the LCCHS, which includes all trees to be harvested. The LCCHS can be determined as follows. First, calculate the least cost path of every element of T to all other elements. Then, the LCCHS boundary is formed by the ‘external edges’ or the paths that enclose all other paths. This process can be computationally very expensive because for a set with n terminals, n—l accumulative least cost surfaces and 22’: n — i paths will have to be calculated. However, least cost paths between points that are located in the middle of the set are very unlikely to be part of the set boundary. Hence, I devised a simpler method that starts by calculating the convex hull of the set T in a Euclidean plane. In a GIS, this is easily accomplished by first creating a triangulated irregular network (TIN),9 and dissolving all internal lines to form a single polygon (Figure 4.7 A). Let the terminals forming the 9 A TIN is a vector data model used to represent continuous surfaces by linked triangles that creates diamond-like facets. These triangles are constructed such that. one vertex of the triangle is connected to its two nearest. neighbors. See Krevelt (1997) for details. vertices of this single polygon be grouped in the set W E T. Next, I calculate the least cost path of each element of IV to all other elements of W and proceed by selecting the ‘external edges’ (Figure 4.7 B). If any terminal t E T\W (read terminal t which is an element of set T but not an element of W) is outside the paths forming the external edge, then this terminal t is moved to set W and the process is repeated until all terminals are on or inside the boundary (Figure 4.7 C). With luck, this process is repeated only a few times. If the number of elements in W is much smaller than those in T, then savings in computational time can be substantial. The resulting boundary is taken to be the LCCHS. Notice that the LCCHS is not always a convex set in the Euclidean geometric sense. With the logging site defined, the logger proceeds to build the main road from the current infrastructure to the logging site. In a GIS, this step is easily accomplished since this is a simple two-terminal problem, where the current infrastructure is the origin and the logging site the destination. Therefore, the application of the Dijkstra algorithm re- turns such minimal cost path between these two terminals. This least cost path is taken to be the main road that provides access to the logging site. In order to recreate the second step in the logging process, I adapted two algorithms to create a ‘better’ network than the solution provided 116 0 Element of set W 0 Element of set T not in W Figure 4.7. Algorithm to generate the least cost convex hull set. by the ordinary least cost path implementations. Better is taken here to be a network with building costs less than the ones provided by the GIS functions. In the first algorithm, I use the ‘spanning and rectilinear tree’ idea to successively form the network. The algorithm works as follows (Figure 4.8). Three data grid inputs are used: the DEM, a binary grid with values set to one if a terminal (tree to be harvested) exists in the cell (Terminals grid), and a grid with the current road infrastructure to where all trees should be brought (Road grid). For this exercise, I take this to be a point (cell) where the LCCHS intersects the main road. Next, I calculate the accumulative cost, using 117 the Dijkstra algorithm, from Road to the nearest (cheapest) terminal. Then, I build the least cost path (skid trail) linking these two points. Finally the Road and Terminals grids are updated, by including this newly built segment and by eliminating the closest terminal that was just reached. This process is repeated until all terminals are reached. This algorithm is a combination of the spanning and rectilinear trees in the Euclidean space metric (Figure 4.1, panels D and E). In a spanning tree, one terminal is connected to its closest neighbor and subsequent connections are allowed only to already connected terminals. In other words, all elements of set K of terminals are also the nodes (set V). On one hand, my algorithm is similar to the spanning tree because it searches the closest neighbor, in the building cost metric, that is then linked by the minimum path. On the other hand, my algorithm allows connection to any portion of the Roads grid, just like rectilinear trees can intersect any portion of a line segment. Using graph theory terminology, the set of nodes that make up the least cost path between two terminals (set Q) is added to the set of terminals K that were already searched (Figure 4.4). Hence, any node in this new set K is a potential branching point for a new skid trail segment in the next iteration. The second algorithm implements the Steiner solution to the three vertices case explained in the graph theory section above. The same 118 #:63— 9:an A W] l DEM ROAD ALC 0 fl Terminals Select To Build path from ROAD to T Update Update Terminals ROAD Repeat Until # Terminals E0 Figure 4.8. Pseudocode for the spanning/rectilinear tree algorithm. 119 inputs used in the spanning tree algorithm are used in this more com- plicated algorithm (Figure 4.9). The algorithm begins by calculating the accumulative least cost from the Road grid (ALC 0). Then, the terminal with the cheapest cost to be reached is selected (To) and a second accumulative least cost from this terminal is calculated (ALC 1). Next, the cheapest terminal to be reached from this first terminal is also selected (T1). If the cost of reaching this terminal T1 from To is greater than the cost of reaching T 0 from Road, than a simple unique path is build from Road to To. Otherwise, the algorithm calculates the Steiner point. To this end, it calculates the accumulative least cost from T1 (ALC 2) and sums the three accumulative costs ALC 0, ALC 1, and ALC 2. The Steiner point (SP) is the smallest value of the sum of these three accumulative grids, as explained in the graph theory section. After this point is selected I calculate another accumulative least cost from this point (ALC 3) and build the skid trails from SP to terminals T 0 and T1 and to the Road grid. Finally, the Road grid is updated to include these built skid trail segments, as well as the Terminals grid whose To and T1 values are changed do zero (since they were already reached). If the Steiner point is the same as one of the vertices, then there will be two segments built from Road to To and from T 0 to T1. Otherwise, three segments will be built departing from the Steiner point to T0, T1, and the Road grid. This process is repeated until all terminals are reached. The resulting network is the logging skid trail network. In the two algorithms described above, the accumulative least cost surface was calculated using a program I wrote in Iterative Data Lan- guage (IDL) that calculates the cumulative least cost by searching each of the eight neighbors separately and choosing the one with the smallest cost (see programs in Appendices B and C). IDL is a powerful matrix oriented computer language that is widely used in remote sensing and visualization applications but has not been used so far, to my knowl- edge, in GIS applications such as this. The algorithm implemented to calculate the accumulative cost surface combines the search for a least accumulative grid using the Dijkstra algorithm with the anisotropic slope information as described by Collischonn and Pillar (2000) and Yu et a1. (2003). Thus, my program overcomes the limitation of as- signing a Horn-average slope to each cell as explained in Chapter 3. No slope information is lost due to averaging and the least cost path direc- tion, which is a function of slope, is assigned more precisely. To simplify the calculations, I assigned the friction value, or the cost of traversing a cell, as the absolute difference in height between two cells, since slope can be calculated as Aheight/Adistance. The cost of traversing one cell to another adjacent cell is then this slope value multiplied by the distance between the two cells (see equation 4.2), which simplifies to 121 DEM EL] ROAD A ll Terminals Select To Repeat Until # Terminals E0 0 I l ALC 1 I Select T1 l N:'°=— mow-mm GreaterThan [ Build path 1 THEN IF costfrom Toto T, from ROAD ’° T0 cost from ROAD to T. ELSE Update Terminals Update ROAD Select SP ALC3 Build paths to T0, T1. ROAD ' Figure 4.9. Pseudocode for the 3-tcrminal Steiner problem difference in height. 4.5 The Dataset A critical piece of information necessary to model logging skid trails is the location of each tree to be harvested. This information was ob- tained for a logging site in Acre State, located in the western part of the Brazilian Amazon (Figure 1.4). This site, with an area of ap- proximately 600 hectares, was part of a mahogany forest management experiment conducted by IMAZON (Institute do Homem e Meio Am- biente da Amazonia) and is approximately 30 km off BR—364 highway (Figure 4.10). This site size is roughly what a logging company would harvest in a year. A typical medium-sized logging firm processes 10,000 m3 of round- wood annually. The area in forest necessary to supply this amount of roundwood depends on the density of commercially valuable trees. Dense forests in Eastern Amazonia contain 20-60 m3 of commercial roundwood (5—10 trees) with an average of approximately 38 m3ha'1 (Verissimo et al., 1992).10 Less productive forests yield 10—20 m3 per hectare (Uhl et al., 1991). Hence, a mid-sized sawmill should exploit each year an area of about 500 ha to obtain raw material for processing. 10In many cases, loggers return to the same site years later to harvest trees that were not previously accepted in the market and the total volume harvested can be above 50 m3ha_l. Legend - 8R6“ - Logglng Slte DEM - SRTM Value ngh : 546 ! Low : 82 r—r—i—rr—“r—i—fififi $ 0 5 10 20 Kilomm Figure 4.10. Location of the logging extraction site in Acre State, Brazil. In this analysis, I used two different sources of elevation data. To simulate the first stage of the logging process, or the least cost path from the existing infrastructure to the logging extraction site, I used SRTM data projected to UTM zone 19 south and the oflicial infrastructure in digital format from IBGE (1997) (Figure 4.10). For the second stage, or the simulation of the skid trail network, I used a much more detailed DEM that I created from field measurements conducted by a team of biologists, foresters, and field assistants. 124 This team ran transects 30—60 m apart in the north south direction and measured the relative altitude, with respect to a zero benchmark located near a read, using clinometers and distance tapes (Figure 4.11).11 These points, with their respective coordinates and height attribute were imported into ArcView®. I used these elevation points to generate a one-meter cell resolution digital elevation model applying the spline or thin plate interpolation method, with 12 points per region for the local approximation. The spline method generates a continuous surface constrained by two conditions. First, the interpolated surface is exact, which means that the surface values and data point values are the same at the data points. Second, the surface must have minimum curvature with a continuous first derivative. This method ensures a smooth (continuous and twice differentiable) interpolated surface and is adequate to represent terrains that do not have abrupt changes in height values (e.g. cliffs) (Burrough & McDonnell, 1998; ESRI, 2002). The location of each tree was recorded with a handheld GPS set to UTM zone 19 south coordinate system. This area is characterized by open forests with many palm trees and openings in the canopy (ACRE, 2000), which facilitates GPS signal reception from satellites and dimin- ishes measurement errors. No accuracy was reported though. The resulting DEM grid was 4731 by 1273 one-meter cells. Since ’1 For a detailed description of methods. please refer to Grogan (2001). on. u 30... 3. u :9: 852. uni—:8 3:33 9222 oooé Figure 4.11. Area surveyed and sampled points for height measurement. the original relative height measurements contained negative values, I shifted all heights by adding 30 meters to each value. Also, in order to capture the point decimal height measurement accuracy and, at the same time, avoid a float data type grid that requires more processing memory, I multiplied all values by 10. The programs I wrote, in par- ticular the three terminals Steiner algorithm, are computationally very demanding. Therefore, in order to diminish the computation time, I clipped a 600 x 600 m area, located on the southwestern corner of the site (Figure 4.11), and increased the size of the grid cell to 3 m, using cubic convolution (ESRI, 2002), resulting in a final template of 200 by 200 cells or a set of 40,000 nodes or vertices.12 In this 36 hectares area, 105 trees were tagged by the field work team. The height range for this DEM used in the analysis was between 82 and 546 tenths of meters (Figure 4.12). 4.6 Results As mentioned, the simulation aims to replicate the decision making process of the whole logging operation, which begins with the definition of the logging extraction site. Figure 4.13 display this first step, which ’2 I could have generated this 3 m resolution DEM directly from the spline interpolation of the height measurements but since the objective of this work is to produce a template on which I can test the algorithms, the indirect approach does not pose a serious problem. l\‘loreover, I became aware of the enormous time spent on processing only later on. after the original DEM was already produced. 127 Legend - Terminals (trees) DEM (3 m resolution) Value BHighzm Low : 82 l_l_l_‘t_l—l Mete rs 0 50 1 00 200 Figure 4.12. Grid DEM template with surveyed trces’ locations (terminals) consists in calculating the least cost convex hull set. The first figure on the left (Panel A) is the first step of such algorithm, Where the convex hull set in a Euclidean plane is generated by dissolving the TIN internal lines. The figure on the right panel (B) is the least cost convex hull set that was generated by running the least cost from each vertex that is element of the convex hull boundary W to all other vertices in W. Once the logging site is defined, the logger builds the main road linking the current infrastructure to the logging site. To this end, I calculated the least cost path from BR-364 to the LCCHS using the 128 «460.. D How :31 5250 D EmEEcob moot. . ozone; 9.20.2 oom one Least cost convex hull set. Figure 4.13. A - Convex hull and B - 129 program I wrote in IDL, which calculates the accumulative least cost surface using the slope information in all eight directions. Since this least cost path calculation uses the SRTM 90 m resolution data and the LCCHS is at 3 In scale, I converted the latter into a 90 m resolution grid. This conversion created a blunt, coarse LCCHS polygon that served as the destination for the least cost path exercise. Ideally, both datasets should be in the same fine scale but detailed elevation information is not available outside the logging site. Figure 4.14 shows a 3D perspective view (to the east) of the resulting least cost path (red line). The path begins in a higher flat plateau, moves in the site direction, gets to a crest and gently descends to a valley. The path continues to follow the lower terrain until it gets to the extraction site. This path is exactly what I expected from the algorithm because the path makes the necessary turns to avoid steep slopes. The second step consists of finding the minimum network of ex- traction skid trails. I first show the ordinary solution provided by the current available software functions, which utilizes the Dijkstra algo- rithm. Figure 4.15 shows that the ordinary solution generates a great number of unnecessary parallel networks and hence, is not a cost-saving network to build. I colored each trail segment by its ‘hauling traffic.’ For example, segments in black are the shared least cost paths to reach 13-105 trees 130 Figure 4.14. 3D shaded view of the least cost path (in red) from BR-364 to the logging extraction site, vertically exaggerated fifteen times. from the origin where the main road and the LCCHS intersects. These colored trails show that if we utilize Tomlin’s approach, the trail in black would be the only clear distinguishable path to select for subse- quent interactions (see footnote 5 in Chapter 4). If the second group of most shared segments of 7—11 trees is selected as well (upper middle- left part of figure in dark red), then Tomlin’s approach fails because these segments are parallel and consequently at least one of them could 131 be eliminated to diminish building costs. Hence, this figure suggests that Tomlin’s approach would generate unnecessary parallel networks, depending on how the hauling traffic cut-off figure is assigned. More- over, even if dark segments are assigned as ‘roads’, it does not eliminate the possibility of generating parallel segments in subsequent iterations (light red, magenta segments). Legend . Terminals (trees) Haul. traffic in segment - 1 - 2 - 2 - 4 - 4 - 7 - 7 - 12 ~ - 12 - 105 Figure 4.15. Ordinary solution to the least cost path. The results of the first algorithm I developed, the adaptation of the spanning and rectilinear trees, are shown in figure 4.16. The origin is 132 the green dot on the central upper part of the grid, where the main road coming from BR-364 intersects with the LCCHS calculated in step 1. The result for the second algorithm, which utilizes the idea of finding the Steiner point between three accumulative least cost surfaces, is presented in Figure 4.17. . Legend . Terminals (trees) 5 -annino Tree Solutlo m Meters 0 50 100 200 Figure 4.16. The ‘spanning tree’ network for 105 terminals and one origin. The results from both algorithms do not differ considerably. Dif— ferences between the networks are difficult to observe visually by com- paring both graphics. In Table 4.1, I present the differences in read 133 Legend . Terminals (trees) - 3-pt Steiner solutlon l—Ll—‘I_l_—7'1 Meters 0 50 100 200 Figure 4.17. Logging skid trail network using the 3—terminal Steiner algorithm. building costs. Indeed, the cost difference between both algorithms is only 25 units or less than one percent improvement with respect to the spanning tree solution. However, the three-point Steiner spent almost 300 minutes of CPU time to return a solution while the spanning tree algorithm spent only 84 minutes, an almost fourfold difference.13 At least for this particular instance of the problem, computing cost for the three—point Steiner algorithm are exorbitant relative to the spanning 13I used a Xeon Pentium 1.5 GHZ with 512 MB of RAM computer to run the programs. 134 Table 4.1. Network building cost and processing time spent in each algorithmic solution. Algorithm Road Cost CPU time (min) Ordinary solution 10969 < 2 Spanning tree solution 3.520 83.64 3—pt Steiner solution 3.495 289.60 tree solution while the building cost saving is only marginal. Both al- gorithms however, return a much better (cheaper) network than the ordinary solution, which costs a total of almost 11,000 units.14 The difference between the ordinary solution and the two algorithms imple- mented here are obvious. 4.7 Discussion As I showed in the results section, the two algorithms I wrote return a much cheaper skid trail network than the solution provided by current GIS functions. However, I do not know how these results compare to the actual skid trail network because data on skid trails are not available. Yet, there are reasons to believe that loggers do not design the network carefully to avoid unnecessary trails. Barreto et a1. (1998) showed that simply tagging the trail path in the forest before tractors actually open the trails reduces the density of trails by 32.6%, when compared to current unplanned operations. In unplanned operations, the team that 1“ I also programmed a function to calculate these costs so that each segment that is used by more than one terminal is not. double counted in the final cost. See equation 4.3. 135 cuts down the trees does not communicate with the team that builds trails and hauls trees to a patio.15 Hence, this second team ‘guesses’ where the fallen trees are by looking for openings in the canopy and obviously are much more prone to build unnecessary trails. In many instances, tractor drivers build trails and reach natural openings in the canopy where no tree are cut down. In other cases, cut trees are simply left behind because drivers are unable to find them. Hence, in this application, my algorithms seems to have a normative use (i.e. how should the trail network be designed) in addition to some predictive capability. These algorithms can also be used to model roads at different scales. For example, instead of defining trees as terminals, I could define log- ging landings (or patios) as terminals and design the road network linking those patios. At an even broader scale, I could define differ- ent logging sites as terminals and use the algorithms to predict the minimum network of main roads connecting different sites. Therefore, these algorithms could be used to predict forest fragmentation caused by roads at many different scales. Fragmentation caused by logging extraction trails is different from the fragmentation caused by the other two types of roads (destination determinate and indeterminate). Although logging operations are very f u . . . 1" Patios are clearings where loggers pile up tree trunks before loading them onto trucks for transport to sawmills. 136 selective and take only 5 to 10 trees per hectare, the extraction process damages many nearby trees. For each tree extracted, 27 others are damaged, and the surrounding canopy is reduced by 40 to 80 percent (Uhl et al., 1997). Such degradation increases forest vulnerability to fire and liana growth (Holdsworth & Uhl, 1997; Gerwing, 2002), which can ultimately lead to a complete change in species composition and in land cover (Cochrane & Schulze, 1999).” On the other hand, the main road linking the current infrastructure to the logging site can be occupied by settlers, just like destination de- terminate and indeterminate roads. Once such example are the roads built by loggers to access mahogany-rich sites in southern Para State, described in Verissimo et a1. (1995). In that area, loggers in search of mahogany-rich sites opened more than 3,000 km of roads into the forests, branching off the state road PA-279 to the north. Colonists rapidly followed loggers and took possession of 50-100 hectares lots along these roads closer to the official infrastructure up to the bor- der of the Apyterewa Indigenous Reserve. However, according to 2000 Landsat ETM+ satellite images (not shown), even the southern portion of the Apyterewa reserve seems to be occupied and deforested. Thus, roads connecting official infrastructure to logging sites can generate fragmentation patterns, caused by subsequent clear-cut deforestation, 16 Intensive log in , such as racticed in Indonesia where 50-120 m3ha‘1 are ex loited, can be S g p I) even more damaging (Curran et al.. 2004). 137 similar to destination determinate roads. 138 CHAPTER 5 Conclusions This dissertation presents a GIS simulation approach that attempts to replicate different types of logging roads that set the pattern for subsequent forest fragmentation caused by deforestation. In Chapter 2, I presented background information about the development of the transportation system in the Amazon and the different patterns of roads and forest fragmentation. I also provided an overview of the role of roads in determining the overall deforestation pattern. I discussed in particular how the federal road network developed and was designed to link pre-existing population centers, which in turn were dependent on geographical characteristics of rivers. I concluded that federal roads can be considered exogenous to deforestation because bureaucrats did not have a clear intention to route the roads towards fertile soils to reap benefits from future agricultural development. In Chapter 3, I attempted to model the fishbone pattern of forest 139 fragmentation as a function of the economic behavior of loggers, key agents of land cover change in the Amazon region. Although my suc- cess was somewhat limited in generating the observed network, several conclusions can be drawn from the analysis that give insight into the ground-level processes at work in the region. In particular, the des- tination indeterminate simulations provide evidence that profit maxi- mization in the interest of wood extraction is probably not the primary driver of forest fragmentation in colonization frontiers. Key informant interviews suggest that, although loggers are involved in extensions of settlement roads in the study area, colonists themselves often take the initiative, and pressure municipal government to act. The objective of property regularization by smallholders is the force behind much of the observed fragmentation, at least in the short- to mid-run period of sev- eral decades following initial colonization. Consequently, the fishbone pattern most likely arises on the basis of multi-agent interactions, in which colonists are dominant, and loggers free-ride on road construc- tion and exploit the extraction loophole in Brazilian law that enables them to buy wood from colonists. My approach is more successful in identifying specific routes for the destination determinate case. The two instances of rapid road extension beyond the boundaries of colonization appear to be consistent with cost minimization by loggers, who seek to reach rivers as part of their 140 overall profit maximization strategy. Understanding this strategy is key to understanding the selection of the destinations, a critical next step to modeling the road extension process in the study area, which is probably of more general significance throughout the basin. Over the long-run, destination determinate roads like the Transtutui and the Transiriri will probably exert substantial influence on the pattern of fragmentation at a regional scale given their economic importance, although in the study area such effects are only incipient. In Chapter 4, I reproduced in a GIS the actual two—stage process of logging as described by field informants. I presented two GIS inno- vations in this chapter. The first is the concept of least cost convex hull set that can be used to define areas encompassing all possible least cost paths between a set of points. This concept was used to define the logging site area. The second innovation were the two algo- rithms developed to calculate networks interconnecting several points in a raster environment. Although the algorithms do not return the ultimate Optimal minimum network, results show that my algorithms do perform much better than current functions available in commercial GIS software that uses the Dijkstra algorithm. Algorithmic improve- ments could be incorporated to decrease the cost of the total network but, as demonstrated by complexity theorists (i.e. NP-complete prob— lem), at very large computational costs. 141 These algorithms could have a normative use to help design skid trails that are less damaging to the forest than current unplanned log- ging operations and hence, could be beneficial to those concerned about sustainable development of the forestry sector. An easy extension of this program would be to include trees that are still small but are valu- able for a second cycle harvest. One could simply increase the ‘friction cost” surrounding these trees so that least cost trail segments would have to detour and avoid damaging those valuable trees. The same could be done for seed trees that should be kept standing to maintain reproductive / regenerative capacity or trees with edible fruits and seeds that are important for animals’ diets. I could also use these algorithms and programs to model, in a positive sense, logging roads in a broader scale by linking different potential logging sites. If some kind of tree density surface grid were available, I could define potential logging sites by assessing their profitability and then connect these sites by a minimum network. As such, I might be able to explain many logging road patterns observed on satellite images throughout the Amazon basin. The conservation community can benefit from the findings of this dissertation as well. This dissertation provides a better understanding of the behavior of actors engaged in road building construction and the results can help policy makers and conservationists better formu- 142 late policies to avoid further landscape fragmentation. In particular, my research showed that once an area is opened for colonization, lo- cal agents take upon themselves to develop the region, even without further governmental support. Local agents, and loggers in particular, have the financial capital and local political support to keep building and improving the initial infrastructure set in place by the government. Hence, the lack of new official investments in infrastructure is not a con- straint for the expansion of the road network. My findings suggest the opposite: governmental institutional presence is necessary in the one hand to provide the infrastructure so badly needed in those areas and, on the other hand, to curb undesirable expansion of the frontier that can have damaging and long lasting consequences to the conservation of biodiversity. Our understanding of the human drivers of deforestation has deep- ened considerably in recent years, but many challenges remain in know- ing how forest clearance is articulated in space. This is an important issue, given that the spatial patterns of clearing strongly affect ecolog- ical processes and conditions and, by implication, biodiversity. While ecologists have paid considerable attention to the environmental im- pacts of forest fragmentation patterns attending the clearance of trop— ical forests, social scientists have not been so quick to provide insight into how the fragmentation patterns arise in the first place. This dis- 143 sertation provided an initial attempt to do so for an old colonization frontier in the Amazon basin. I argue that road building by local agents is the primary proxi- mate cause of the patterns of forest loss, and that loggers together with colonists are the primary lower-order road builders in the Amazon basin. This motivates my focus on loggers as spatial agents, and the use of GIS software to model their spatial decision-making processes. Although my results are only partially successful, they call attention to the role of multiple agents in the landscape, and thereby provide in- sight into a specific form of forest fragmentation observed throughout the basin. Additional work, both theoretical and empirical, is needed to better understand the manner in which these agents interact, and also how specific destinations are chosen as part of a profit maximization strategy. Improving the GIS approach on these grounds could provide powerful methodology for answering spatial questions about the pat- terns of forest loss, so important to the biodiversity issue. Finally, my dissertation showed that the combination of theory, applied field work, and computational GIS can be a powerful combination to understand the social processes that generate patterns in the landscape. 144 APPENDIX A Field Interviews The field interviews were conducted during the period 07-21 July 2004 in Uruara and were part of a larger project supported by NASA’s Large Scale Biosphere and Atmosphere Program (Project: A Basin- Scale Econometric Model for predicting future Amazonian landscapes; PI: Dr. Robert Walker). The field work team applied a formal survey questionnaire, including questions regarding road construction, road’s segments expansions, choice of route, and maintenance. I participated in interviews in seven different travessécs that spur off the Transama- zon. In each travessao, I interviewed three to four colonists. These colonists were selected using the ‘snowball’ sampling approach as fol- lows. In each travessao, I first obtained information about the oldest colonists currently living in the area as well as directions on how to find their lot, by informally chatting with any person I met. I also asked for people that might be knowledgeable about the opening/extension of a particular travessao. Next, I proceeded to interview those subjects that were appointed to be long time residents. Each person interviewed was also asked to suggest other names for further interviews. In the case of the Transtutui, I interviewed the logger that build it and the colonist that participated in the conflict over a detour on his former property. In the case of the Transiriri, I interviewed colonists along the whole stretch of the road as well as old residents in the village at the destination point where a port, used to transport logs in barges, still exists and is currently operational. The information about the two stages of the logging operation in the skid trail case, was obtained from a interview with another logger who is very knowledgeable about road construction since he is specialized in road building. Other interviews that provided contextual information included: IN- CRA’s (Institute for Agrarian Reform) supervisor in Uruara, city coun- cil members, and municipal secretary of infrastructure. 146 APPENDIX B IDL Program to Calculate Directional Dependent Slope Least Cost Surfaces ;********************************t********************************************** ;+ ; NAME: ; LCDEM ; PURPOSE: ; Calculates the accumulative least cost surface and the "back link grid" ; Needs four inputs: a dam grid, a grid determining the origin from which ; the cost will be accumulated and a destination grid. NO FRICTION GRID ; IS USED. SEE FUNCTION ; OUTPUT: ; A structure in which the first element is the accumulative cost grid ; and the second element is the back link grid ; AUTHOR: ; EUGENIO ARIMA ; Imazon & Michigan State University ; CREATED: ; Jan 06 2005 147 ; USAGE: FUNCTION ; IDL> 1cpath = 1cdem(demgrid, origin, destination, csize) ; where ; demgrid is the dem grid ; origin = origin grid ; destination = destination grid ; csize is the cellsize ; MODIFICATION HISTORY: ; Jan 12, 2005: ; Ccost is no longer the whole matrix total sum but an array ; multiplication (faster). ; Jan 18, 2005: ; Include a nodata check ; Feb 14, 2005: ; Include fourth input grid of destination. Program runs until ; the accumulative cost to destination are calculated. All other ; non assigned cells are given a no-value. Saves computation time. ; GENERAL COMMENTS: ; I use the Dijkstra algorithm concept to create this program ; (see Dijkstra 1959). ; The advantage of this program is that you can define your own cost ; functions, i.e. can use for example anisotropic cost surfaces. ; This program is still much slower than ArcInfo costdistance functions ; because of the many IF statements and the loop REPEAT UNTIL. ; This program returns approx. 200 values per second. ; Any suggestion on how to improve the code is welcome... ;titttttt##1##***************#*****tt*********t**********t***************¥*#**** function 1cdem, dem, orig, dest, csize T = SYSTIME(1) csize = csize SourceGrid = temporaryCorig) nDims = size(SourceGrid, /dimensions) 3 ; This program handles the bordering cells a little oddly. ; I create an extra row and column on each side (four) to avoid ; checking whether the cell exist or not. Of course, those ; bordering cells are not included in the processing ; (are assigned a fake ’already searched.’) 148 ndims[0]+2 ndims[1]+2 ;print, ’Number of columns: ’, ncol ncol nrow ;print, ’Number of rows: ’, nrow sg = temporary(make_array(ncol, nrow, /byte, value=0)) ; Plugging the original source grid into the expanded matrix sg[1:ncol-2, 1:nrow-2] - temporary(SourceGrid) SourceGrid = temporary(sg) ; Next, import the dem cost grid file CC = temporary(dem) cgtmp = temporary(make_array(ncol,nrow, /integer)) ; Plug the original dem grid into the expanded matrix cgtmp[1:ncol-2, 1:nrow-2] = temporary(CG) CostGrid = long(cgtmp) ;print, ’Max elevation is: ’, max(CostGrid) ;print, ’Min elevation is: ’, min(CostGrid) ; This is the major change implemented in version 10. ; See bottom of Repeat Until loop. DestGrid = temporary(dest) dg = temporary(make_array(ncol, nrow, /integer)) dg[1:ncol-2, 1:nrow-2] = temporary(DestGrid) DestGrid = temporary(dg) Dest = temporary(where(DestGrid GT 0)) ; see the repeat loop nDest = n,elements(Dest) ;print, ’# of trees is: ’, nDest ;DestArray = make_array(nDest, /byte, value = 1) ooooooooooooooooooooooooooooooooooooooooooooooooooooo noval = where(CostGrid E0 0) ;Print, ’# of novalue data is: ’, n_e1ements(noval) origin = where(SourceGrid GE 1) originl = origin ; Define the matrix of already searched cells JaSearch = make_array(ncol, nrow, /byte, value = 0) JaSearch[origin] = 1 149 ; Set the boarders as already searched JaSearch [0 , t] = 1 JaSearch [* ,0] 1 JaSearch[ncol-1, *] JaSearch[*, nrow-1] II HH ; Set novalue data as already searched if noval NE [-1] then JaSearchfnoval] = 1 ; Define the back link grid BackLink = make_array(ncol, nrow, /integer) ; Define the accumulative cost grid AccumCost = make_array(ncol, nrow, /float, value= -1) AccumCost[origin1] = 0 ; To initialize the program, we first calculate the least ; cost from the origin to the neighborhood of the origin nOrigin = n_elements(origin) ;Print, ’# of origin points: ’, nOrigin ;Print, ” ; Define positions ; For the DEM, I want the difference in height ; Assign -1 relative to central position posO = fltarr(9) posO[4] = 1 p031 = posO posl[3] = -1 p082 = posO pos2[0] = -1 p083 = posO p033[1] = -1 p084 = posO pos4[2] = -1 posS = posO posSIS] = -1 posG = posO p056[8] = -1 p037 = posO pos7[7] = -1 p088 = posO pos8[6] = -1 ; Loop over each cell considered to be the origin for i =0, nOrigin-1 do begin O ’ 150 ; Mask is the 3x3 neighborhood matrix of indexes mask = lon64arr(9) tmp = origin[i]; this is the cell in the middle (positive) tmp1 = origin[i] - 1 tmp2 = origin[i] - ncol - 1 tmp3 = origin[i] - ncol tmp4 = origin[i] - ncol + 1 tmp5 = origin[i] + 1 tmp6 = origin[i] + ncol + 1 tmp7 = origin[i] + ncol + ncol - 1 tmp8 = origin[i] ; This position assignment is very important ; Look at ArcInfo help to understand why. ; Search for costbacklink in grid - Online Help. mask[O] = tmp2 mask[1] = tmp3 mask[2] = tmp4 mask [3] = tmpl mask[4] = tmp mask[5] = tmp5 mask[6] = tmp8 mask[7] = tmp7 mask[8] = tmp6 ; These are the functions that determine the cost of traversing the cells ; You can basically change it to whatever you want. ; Example for the origin: ; ccost1 = transpose(CostGrid[mask]) # posl ; ccost2 = transpose or ; USAGE: FUNCTION ; IDL> trails = allpaths(accumcostgrid, bklinkgrid, destgrid) ; AUTHOR: ; E. Arima ; CREATED: ; Feb 25 2005 ; MODIFICATION HISTORY: ; COMMENTS: ; Need three inputs: accumulative cost grid, back link grid ; and the destination grid ; *********#*******¥***#*******##3####1##**********¥************************* ; First, import destination grid function allpaths, acost, bklink, dest Dest = dest nDims = size(Dest, /dimensions) ncol = ndims[0] nrow = ndimsfl] ; Create the path grid to be filled with ones ; if part of path, otherwise zero ; Path array should be long to accomodate -9999 ; Read the Backlink grid BkLk = bklink ; Read the accumulative cost grid AcCost = acost ; Destinations should be numbered from 1 to N ;DestLab - 1abel_region(Dest, /all-neighbors) ;Dest = DestLab ; For some reason, the label_region command is creating ; many regions (infrastructure) that were supposed to be ; only one. NumTrees = max(Dest) ; number of trees or destinations tree = 1 ; counter Path make_array(ncol, nrow, /Long, value=0) ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo ; Begin Loop While tree LE NumTrees do begin Pathtmp = temporary(make-array(ncol, nrow, /Long, value=0)) DestReg = temporary(where(Dest E0 tree)) ; destination id MinDestCost = temporary(min(AcCost[DestReg])) ; acc. value at destination id PossDest = temporary(where((Dest E0 tree) AND (AcCost E0 MinDestCost[0]))) if MinDestCost[O] E0 0 then begin tree a tree + 1 DestReg = temporary(where(Dest E0 tree)) ; destination id MinDestCost - temporary(min(AcCost[DestReg])) ; acc. value at destination id PossDest = temporary(where((Dest E0 tree) AND (AcCost E0 MinDestCost[0]))) 160 endif ; There might be more than one least possible destinations, ; select the first one TheDest = temporary(PossDestI0]) ; Now, we will select the path from destination ; back to the origin (thats how it works...backwards) ; Create another index variable to loop ind = TheDest ; Now, read the backlink grid value ; Begin loop ; Remember that origin must be assigned a value of zero direction = Bklkfind] repeat begin ;print, ’Current direction :’, direction ;print, ’Current index :’, ind ;print, ’ ’ case direction of 1: Pathtmpfind + 1] = 1 2: Pathtmpfind + ncol + 1] = 1 3: PathtmpEind + ncol] - 1 4: PathtmpEind + ncol - 1] = 1 5: PathtmpIind - 1] = 1 6: PathtmpEind - ncol - 1] = 1 7: PathtmpEind - ncol] = 1 8: PathtmpEind - ncol + 1] = 1 endcase case direction of 1: ind = ind + 1 2: ind = ind + ncol + 1 3: ind = ind + ncol 4: ind = ind + ncol - 1 5: ind = ind - 1 6: ind = ind - ncol - 1 7: ind = ind - ncol 8: ind = ind - ncol + 1 endcase direction = BklkEind] 161 EndRep until (direction E0 0.00) ; Summing the last path to the current ; Number indicates how many trees "use" the path Path Path + Pathtmp tree - tree + 1 ; counter oooooooooooooooooooooooooooooooooooooooooooooooooooo ; End loop Return, Path End 162 BIBLIOGRAPHY ACRE. (2000). Zoneamento ecolo’gico-econémico: recursos naturais e meio ambi- ente - documento final (Tech. Rep). Rio Branco: SECTN‘IA, Coverno do Estado do Acre. Aldrich, P. R., & Hamrick, J. L. (1998). Reproductive dominance of pasture trees in a fragmented tropical forest mosaic. Science, 281, 103-105. Allen, J. C., & Barnes, D. F. (1985). The causes of deforestation in developing countries. Annals of the Association of American Geographers, 75(2), 163-184. Alves, D. (2002). Space-time dynamics of deforestation in Brazilian Amazonia. International Journal of Remote Sensing, 23(14), 2903-2908. Andersen, L. E., Granger, C. W. J., Reis, E., Weinhold, D., & Wunder, S. (2002). The dynamics of deforestation and economic growth in the Brazilian Amazon. Cam- bridge: Cambridge University Press. Andersson, A., Hagerup, T., Nilsson, S., & Raman, R. (1998). Sorting in linear time? Journal of Computer and System Sciences, 57(1), 74-93. Asner, G. P., Keller, M., Pereira, R., & Zweede, J. C. (2002). Remote sensing of selective logging in Amazonia: assessing limitations based on detailed field observa- tions, Landsat ETM+, and textural analysis. Remote Sensing of the Environment, 80, 483-496. Bain, D., & Brush, G. S. (2004). Placing the pieces: reconstructing the original property mosaic in a warrant and patent watershed. Landscape Ecology, 19(8), 843-856. Banco Nacional de Desenvolvimento Economico e Social (BNDES). (1998). Trans- porte na regido Amazoriica (Tech. Rep). Rio de Janeiro: BNDES. Barham, B., 8.: Coomes, O. T. (1994). Reinterpreting the Amazon rubber boom: investment, the state, and dutch disease. Latin American Research Review, 29(2), 73-109. 163 Barreto, P. (2002). Manejo florestal para producdo de madeira na Amazonia: situagdo e perspectivas (Tech. Rep). Brasilia/Belem: World Bank/Imazon. Barreto, P., Amaral, P., Vidal, E., & Uhl, C. (1998). Costs and benefits of forest management for timber production in eastern Amazonia. Forest Ecology and Management, 108(1-2), 9-26. Benitez-Malvido, J. (1998). Impact of forest fragmentation on seedling abundance in a tropical rain forest. Conservation Biology, 12(2), 380-389. Bockstael, N. (1996). Modeling economics and ecology: the importance of a spatial perspective. American Journal of Agricultural Economics, 78, 1168—1180. Browdcr, J ., & Godfrey, B. J. (1997). Rainforest cities: urbanization, development, and globalization of the Brazilian Amazon. New York: Columbia University Press. Brown, K., & Pearce, D. W. (1994). The causes of tropical deforestation: the economic and statistical analysis of factors giving rise to the loss of the tropical forests. Vancouver: UBC Press. Bruno, E. S. (1966). Historia do Brasil. 8510 Paulo: Editora Cultrix. Bunge, W. (1966). Theoretical geography. Royal University of Lund Dept. of Geography; Gleerup. Burrough, P. A., & McDonnell, R. A. (1998). Principles of geographical information systems. Oxford: Oxford University Press. Cantwell, M. D., & Forman, R. T. T. (1993). Landscape graphs: ecological mod- eling with graph theoryto detect configurations common to diverse landscapes. Landscape Ecology, 8(4), 239-255. Chomitz, K., & Gray, D. (1996). Reads, land use, and deforestation: a spatial model applied to Belize. The World Bank Economic Review, 10(3), 487-512. Chorley, R. J ., & Haggett, P. (1967). Models in geography. London,: Methuen; distributed in the USA. by Barnes & Noble. Cochrane, M. A., & Schulze, M. D. (1999). Fire as a recurrent event in tropical forests of the eastern Amazon: effects on forest structure, biomass, and species composition. Biotropica, 31(1), 2—16. Conservation International. (2004). Mapa dos biomas da Ame’r‘ica do Sul. Digital Maps [CDROM]. 164 Collischonn, W., & Pillar, J. V. (2000). A direction dependent least-cost-path algorithm for roads and canals. International Journal of Geographical Information Science, 14 (4), 397-406. Cronon, W. (1983). Changes in the land: indians, colonists, and the ecology of New England. New York: Hill and Wang. Cropper, M., Griffiths, C., & Mani, M. (1996). Roads, population pressures and deforestation in Thailand, 1976-198.9. (Unpublished Manuscript). Curran, L. M., Trigg, S. N., McDonald, A. K., Astiani, D., Hardiono, Y. M., Siregar, P., et a1. (2004). Lowland forest loss in protected areas of Indonesian Borneo. Science, 305’ (5660), 1000-1003. Deacon, R. T. (1994). Deforestation and the rule of law in a cross-section of countries. Land Economics, 70, 414-430. Deacon, R. T. (1995). Assesssing the relationship between government policy and deforestation. Journal of Environmental Economics and Management, 28, 1-18. Dean, D. J. (1997). Finding optimal routes for networks of harvest site access roads using GIS-based techniques. Canadian Journal of Forest Research, 27(1), 11-22. Denevan, W. M. (1996). A bluff model of riverine settlement in prehistoric Ama- zonia. Annals of the Association of American Geographers, 86(4), 654-681. Denevan, W. M. (2001). Cultivated landscapes of native Amazonia and Andes. Oxford: Oxford University Press. Dijkstra, E. W. (1959). A note on two problems in connection with graphs. Numerische Mathematik, 1, 269-271. Ehmann, H., & Cogger, H. G. (1985). Australia’s endangered herpetofauna: a review of criteria and policies. In G. Grigg, R. Shine, & H. Ehmann (Eds), The biology of Australasian frogs and reptiles (p. 435-447). Sydney, Australia: Surrey Beatty and Royal Zoological Society of New South Wales. Erickson, C. L. (2000). An artificial landscape—scale fishery in the Bolivian Amazon. Nature, 408, 190—193. Environmental Systems Research Institute (ESRI) (2002). Ar'cinfo. Online Help. Redlands: ESRI. Fearnside, P. M. (1997). Greenhouse gases from deforestation in Brazilian Amazo- nia: net committed emissions. Climatic Change, 35(3), 321-360. 165 Fearnside, P. M. (1999). Biodiversity as an environmental service in Brazil’s Amazonian forests: risks, value and conservation. Environmental Conservation, 26(4), 305-321. Feldstein, M. S. (1971). Production with uncertain technology: some economic and econometric implications. International Economic Review, 12(1), 27-38. Ferreira, L. V., & Laurance, W. F. (1997). Effects of forest fragmentation on mortality and damage of selected trees in central Amazonia. Conservation Biology, 11, 797-801. Forman, R. T. T. (2003). Road ecology: science and solutions. W'ashiugton, DC: Island Press. Fowle, S. C. (1990). The painted turtle in the Mission Valley on Western Montana. Master’s Thesis, University of Montana. Friedmann, J., & Stuckey, B. (1973). The territorial basis of national transportation planning. In J. S. DeSalvo (Ed), Perspectives on regional transportation planning (p. 141-175). Lexington, MA: D. C. Heath Company. Fujita, M., Krugman, P., & Venables, A. J. (1999). The spatial economy: cities, regions, and international trade. Cambridge: The MIT Press. Garey, M. R., Graham, R. L., & Johnson, D. S. (1977). The complexity of com- puting Steiner minimal trees. SIAM Journal on Applied Mathematics, 32, 835-859. Gash, J. C. H., Nobre, C. A., Roberts, J. M., & Victoria, R. L. (1996). Amazonian deforestation and climate. Chichester: John Wiley and Sons. Geist, H. J., & Lambin, E. F. (Eds). (2001). What drives tropical deforestation? LUCC Report Series No 4. Louvain-la—Neuve: CIACO. Gerwing, J. J. (2002). Degradation of forests through logging and fire in the eastern Brazilian Amazon. Forest Ecology and Management, 157, 131-141. Gibson, C., Ostrom, E., & Ahn, K. T. (2000). The concept of scale and the human dimensions of global change: a survey. Ecological Economics, 32, 217-239. Goodland, R. J. A., & Irwin, H. S. (1975). Amazon jungle: green hell or red desert? An ecological discussion of the environmental impact of the highway construction program in the Amazon Basin. New York: Elsevier Scientific Pub. Goulding, M., Barthem, R., & Ferreira, E. J. G. (2003). The Smithsonian atlas of the Amazon. Washington: Smithsonian Institution Press. 166 Greenberg, H. J. (2001). Mathematical programming glossary supplement: intro- duction to computational complexity. (Unpublished manuscript). Available from: www.cudenver.edu/~ hgreenbe/ Gregan, J. E. (2001). Bigleaf mahogany in SE Pard, Brazil: a life history study with management guidelines for sustained production from natural forests. Ph.D dissertation, School of Forestry and Environmental Studies, Yale. Haggett, P. (1967). An extension of the Horton combinatorial model to regional highway networks. Journal of Regional Science, 7(2), 281-290. Haggett, P., & Chorley, R. J. (1969). Network analysis in geography. London: Edward Arnold. Haggett, P., Cliff, A. D., & Frey, A. E. (1977). Locational analysis in human geography (2d ed). London [England]: E. Arnold. Hecht, S. B., & Cockburn, A. (1989). The fate of the forest: developers, destroyers, and defenders of the Amazon. New York: Verso. Hill, J. L., & Curran, P. J. (2003). Area, shape and isolation of tropical forest frag- ments: effects on tree species diversity and implications for conservation. Journal of Biogeography, 30(9), 1391-1403. Hillier, F. S., & Lieberman, G. J. (1995). Introduction to operations research (6“ ed). New York: McGraw Hill. Holdsworth, A. R., & Uhl, C. (1997). Fire in Amazonian selectively logged rain forest and the potential for fire reduction. Ecological Applications, 7 (2), 713-725. Horton, F. E. (1968). Geographic studies of urban transportation and network analysis. Evanston, Ill.,: Dept. of Geography Northwestern University. Howard, A. D. (1967). Drainage analysis in geologic interpretation: a summation. Bulletin of the American Association of Petroleum Geologists, 51, 2246-2259. Institute Brasileiro de Geografia e Estatistica (IBGE) (1957). Grande regia'o Norte (Vol. XIV). Rio de Janeiro: IBGE. Institute Brasileiro de Geografia e Estatistica (IBGE) (1997). Diagno’stico ambi- ental da Amazonia Legal. IBGE [CDROM]. Rio de Janeiro: IBGE. Institute Brasileiro de Geografia e Estati'stica (IBGE) (2003). Quantidade produzida na silvicultur‘a - 2001. Last accessed: 08/01/03. Available from: wwwsidra.ibgegov.br. 167 Instituto Nacional de Pesquisas Espaciais (INPE). (2005). Monitoramento da floresta Amazénica brasileira por sate’lite - Projeto Prodes. Last Accessed: 20 Jan 2005. Available from: www.0bt.inpe.br/prodes/prodes_1988.2003.htm Institute Sécio—Ambiental (ISA). (2000). Mapas temdticos: hidrografia total. [CDROM]: ISA. Ivanov, A. O., & Tuzhilin, A. A. (1994). Minimal networks: the Steiner problem and its generalizations. Boca Raton: CRC Press, Inc. Jenkins, M. (2003). Propospects for biodiversity. Science, 302(5648), 1175-1177. Kaimowitz, D., & Angelsen, A. (1998, 1998). Economic models of tropical defor- estation - a review. Bogor, Indonesia: CIF OR. Kreveld, M. v. (1997). Digital elevation models and TIN algorithms. In M. v. Kreveld, J. Nievergelt, T. Roos, & P. VVidmayer (Eds), Algorithmic foundations of GIS (p. 1-44). Springer-Verlag. Kummer, D. M., & Turner 11, B. L. (1994). The human causes of deforestation in Southeast Asia. Bioscience, 44 (5), 323-328. Lambin, E. F., Geist, H. J ., & Lepers, E. (2003). Dynamics of land-use and land- cover change in tropical regions. Annual Review of Environment and Resources, 28, 205-241. Laurance, S. G., Stouffer, P. C., & Laurance, W. F. (2004). Effects of roads clearings on movement patterns of understory rainforest birds in Central Amazonia. Conservation Biology, 18(4), 1099-1109. Laurance, W'. F. (1998). Fragments of the forest. Natural History, 107(6), 35-38. Laurance, W. F., Cochrane, M. A., Bergen, S., Fearnside, P. M., Delamonica, P., Barber, C., et a1. (2001). The future of the Brazilian Amazon. Science, 291, 438-439. Laurance, W. F ., Delamonica, P., Laurance, S. G., Vasconcelos, H. L., & Lovejoy, T. E. (2000). Rainforest fragmentation kills big trees. Nature, 404, 836. Laurance, W. F., Laurance, S. G., Ferreira, L. V., Merona, J. M. Rankin-dc, Gas- con, C., & Lovejoy, T. E. (1997). Biomass collapse in Amazonian forest fragments. Science, 278, 1117-1118. Laurance, W. F., Perez-Salicrup, D., Delamonica, P., Fearnside, P. M., D’Angclo, S., Jerozolinski, A., et a1. (2001). Rain forest fragmentation and the structure of Amazonian liana communities. Ecology, 82(1), 105-116. 168 Lentini, M., Verissimo, A., & Sobral, L. (2003). Forest facts in the Brazilian Amazon 2005’. Bele’m, Brazil: IMAZON. Lovejoy, T. E., Bierregaard, R. O., Rylands, A. 8., Malcolm, J. R., Quintela, C. E., Harper, L. H., et a1. (1986). Edge and other effects of isolation on Amazon forest fragments. In M. E. Soul (Ed), Conservation biology: the science of scarcity and diversity (p. 257—285). Sunderland, MA: Sinauer. Ludeke, A. K., Maggie, R. C., & Reid, L. M. (1990). An analysis of anthro- pogenic deforestation using logistic regression and GIS. Journal of Environmental Management, 32, 247—259. Mahar, D. J. (1978). Desenvolvimento econcimico da Amazénia: uma andlise das poli’ticas governarnentais. Relatorio de Pesquisa N" 39 (p. 251-259). Rio de Janeiro: Ipca/Inpes. Mahar, D. J. (1979). Frontier development policy in Brazil: a study of Amazonia. New York: Praeger. Mahar, D. J. (1988). Government policies and deforestation in Brazil’s Amazon region. Washington, DC: World Bank. Matricardi, E., Skole, D., Chomentowski, W. H., & Cochrane, M. A. (2001). Multi- temporal detection of selective logging in the Amazon using remote sensing (Tech. Rep. No. BSRSI/ RA03-01w). Michigan State University: BSRSI. Melzak, Z. A. (1961). On the problem of Steiner. Canadian Mathematical Bulletin, 4, 143-148. Mertens, B., & Lambin, E. F. (2000). Land—cover-change trajectories in Southern Cameroon. Annals of the Association of American Geographers, 90(3), 467-494. Monteiro, A. L., Souza, J., C., & Barreto, P. (2003). Detection of logging in Amazonian transition forests using spectral mixture models. International Journal of Remote Sensing, 24(1), 151-159. Moran, E. (1996). Deforestation in the Brazilian Amazon. In L. E. Sponsel, T. N. Headland, & R. C. Bailey (Eds), Tropical deforestation: the human dimension (p. 149-164). New York: Columbia University Press. Morgan, M. A. (1967). Hardware models in geography. In R. J. Chorley & P. Haggett (Eds), Models in geography (p. 727-774). London: Methuen Co, Ltd., distributed in the US by Barnes & Nobles. Morril, R. L. (1962). Simulation of central place patterns over time. Lund Studies in Geography, Series B, Human Geography, 24, 109-120. 169 Morril, R. L. (1963). The development of spatial distributions of towns in Swe- den: an historical-predictive approach. Annals of the Association of American Geographers, 53(1), 1-14. Morril, R. L. (1965). Migration and the growth of urban setttement. Lund Studies in Geography, Series B, Human Geography, 26, 130-170. Murcia, C. (1995). Edge effects in fragmented forests: implications for conservation. Trends in Ecology and Evolution, 10, 58-62. Murray, A. T. (1998). Route planning for harvest site access. Canadian Journal of Forest Research, 28(7), 1084-1088. Myers, N., Mittermeier, R. A., Mittermeier, C. G., Fonseca, G. A. B., & Kent, J. (2000). Biodiversity hotspots for conservation priorities. Nature, 403, 853-858. Nelson, G., & Hellerstein, D. (1997). Do roads cause deforestation? Using satel- lite images in econometric analysis of land use. American Journal of Agricultural Economics, 79, 80-88. Nepstad, D., Carvalho, G. 0., Barres, A. C., Alencar, A., Capobianco, J. P., Bishop, J ., et al. (2001). Road paving, fire regime feedbacks, and the future of Amazon forests. Forest Ecology and Management, 154(3), 395-407. Nepstad, D., Moreira, A., & Alencar, A. (1999). Flames in the rain forest: origins, impacts, and alternatives to Amazonian fire. Brasilia, Brasil: Programa Piloto para Conservacao das Florestas Tropicais. Ojima, D. S., Galvin, K. A., & Turner, B. L. I. (1994). The global impact of land-use change. Bioscience, 44 (5), 300-304. Owen, W. (1987). Transportation and world development. Baltimore, MD: The Johns Hopkins University Press. Perz, S., Caldas, M., Walker, R. T., Arima, E. Y., & Souza Jr, C. (2004). Social- spatial processes of road building in the Amazon: a comparative analysis of local heterogeneities and implications for forest fragmentation. (Submitted to Conser- vation Biology). Pfaff, A., Reis, E. J., W’alker, R., Laurance, W., Perz, S., Bohrer, C., et al. (2004). Roads and deforestation in the Brazilian Amazon. (Unpublished Manuscript). Pinheiro, A. C., Giambiagi, F ., & Gostkorzewicz, J. (2000). Brazil ’3 macroeconomic performance in the 19903. Rio de Janeiro: BN DES. 170 Pontius Jr., R. G. (2000). Quantification error versus location error in comparison of categorical maps. Photogrammetric Engineering and Remote Sensing, 66(8), 1011-1016. Pr6mel, H. J., & Steger, A. (2002). The Steiner tree problem: a tour through graphs, algorithms, and complexity. Braunschweig/Wiesbadcn: Vieweg. Puu, T. (2003). Mathematical location and land use theory: an introduction (2nd rev. and enl. ed). Berlin; New York: Springer. Raffles, H., & WinklerPrins, A. M. G. A. (2003). Further reflections on Amazonian environmental history: transformations of rivers and streams. Latin American Research Review, 38(3), 165-187. Reid, J. W., & Bowles, I. A. (1997). Reducing the impacts of roads on tropical forests. Environment, 39(8), 10-17. Reis, E., & Guzman, R. (1994). An econometric model of Amazon deforestation. In K. Brown & D. Pearce (Eds), The causes of tropical deforestation (p. 172-191). Vancouver: University of British Columbia Press. Repetto, R., & Gillis, M. (1988). Public policies and the misuse of forest resources. Cambridge: Cambridge University Press. Rudel, T. K. (1989). Population, development, and tropical deforestation: a cross- national study. Rural Sociology, 54, 327-338. Sant’Anna, J. A. (1998, February). Rede ba’sica de transportes da Amazénia (Tech. Rep). Rio de Janeiro: IPEA. Scariot, A. (1999). Forest fragmentation effects on palm diversity in Central Amazonia. Journal of Ecology, 87, 66-76. Schelhas, J ., & Greenber, R. (1996). Forest patches in tropical landscapes. Wash- ington, DC: Island Press. Schmink, M., & Wood, C. H. (1984). Frontier expansion in Amazonia. Gainesville: University of Florida Press. Schmink, M., & Wood, C. H. (1992). Contested frontiers in Amazonia. New York: Columbia University Press. Schneider, R. (1995). Government and the economy on the Amazon frontier. World Bank Environmental Paper NO 11. Washington, DC: The World Bank. 171 Simmons, C. S. (2002). The local articulation of policy conflict: land use, environ- ment, and amerindian rights in eastern Amazonia. The Professional Geographer, 54(2), 241-258. Simmons, C. S. (2004). The polical economy of land conflict in the eastern Brazilian Amazon. Annals of the Association of American Geographers, 94(1), 183-206. Skole, D., & Tucker, C. J. (1993). Tropical deforestation and habitat fragmentation in the Amazon: satellite data from 1978 to 1988. Science, 260, 1905-1910. Smeraldi, R., & Verissimo, A. (1999). Hitting the target: timber consumption in the Brazilian domestic market and promotion of forest certification (Tech. Rep). Amigos da Terra; IMAZON; IMAFLORA. Smith, N. (1982). Rainforest corridors. Berkeley: University of California Press. Souza J r., C., & Barreto, P. (2000). An alternative approach for detecting and mon- itoring selectively logged forests in the Amazon. International Journal of Remote Sensing, 21(1), 173-179. Souza Jr., C., Brandao Jr., A., Anderson, A., & Verissimo, A. (2004). Avangro das estradas endo’genas na Amazénia. Belem: Imazon. Souza Jr, C., & Roberts, D. (2005). Mapping forest degradation in the Amazon region with Ikonos images. International Journal of Remote Sensing, 26, 1-5. Steffen, W., & Tyson, P. (Eds). (2001). Global change and the Earth system: a planet under pressure. Stockholm: IGBP. Stone, S. (1998). Using a geographic information systems for applied policy anal- ysis: the case of logging in the Eastern Amazon. Ecological Economics, 27, 43-61. Strahler, A. N. (1952). Dynamic basis of geomorphology. Geological Society of American Bulletin, 63, 923-938. Taaffe, E. J., Morril, R. L., & Gould, P. R. (1963). Transport expansion in underdeveloped countries: a comparative analysis. Geographical Review, 53(4), 503-529. Tomlin, D. C. (1990). Geographic information systems and cartographic modeling. Englewood Cliffs, NJ: Prentice Hall. Turner, I. M. (1996). Species loss in fragments of tropical rain forest: a review of the evidence. Journal of Applied Ecology, 33(2), 200-209. 172 Uhl, C., Barreto, P., Verissimo, A., Barres, A. C., Amaral, P., Gerwing, J. J ., et al. (1997). An integrated research approach to address natural resource problems in the Brazilian Amazon. Bioscience, 47(3), 160-168. Uhl, C., Vieira, I. C., Verissimo, A., Mattos, M. M., & Brandino, Z. (1991). Social, economic, and ecological consequences of selective logging in an Amazon frontier: the case of Tailandia. Forest Ecology and Management, 46 (3—4), 243-273. Uhl, C., & Kauffman, J. B. (1990). Deforestation, fire susceptibility, and potential tree responses to fire in the Eastern Amazon. Ecology, 71 (2), 437-449. United States Geological Survey (USGS). (2004). SRTM Level 1 {3 are second). Last Accessed: 10 October 2004. Available from: ed- cftp.cr.usgs. gov / pub / data / srtm / South_America / Vance, J. E. (1986). Capturing the horizon: the historical geography of transporta- tion. New York, NY: Harper Row Publishers. Verissimo, A., Barreto, P., Mattos, M., Tarifa, R., & Uhl, C. (1992). Logging impacts and prospects for sustainable forest management in an old Amazon frontier: the case of Paragominas. Forest Ecology and Management, 55, 169-199. Verissimo, A., Barreto, P., Tarifa, R., & Uhl, C. (1995). Extraction of a high- value natural resource in Amazonia: the case of mahogany. Forest Ecology and Management, 72(1), 39-60. Verissimo, A., Souza Jr., C., Stone, 8., & Uhl, C. (1998). Zoning of timber extraction in the Brazilian Amazon. Conservation Biology, 12(1), 128-136. Walker, R. T. (1987). Land use transition and deforestation in developing countries. Geographical Analysis, 19(1), 18-30. Walker, R. T. (2001). Urban sprawl and natural areas encroachment: linking land cover change and economic development in the Florida Everglades. Ecological Economics, 37(3), 357-369. Walker, R. T. (2003a). Mapping process to pattern in the landscape change of the Amazonian frontier. Annals of the Association of American Geographers, 93(2), 376-398. W’alker, R. T. (2003b). Evaluating the performance of spatially explicit models. Photogramrnetric Engineering and Remote Sensing, 69(11), 1271-1278. Walker, R. T. (2004). Theorizing land-cover and land-use change: the case of tropical deforestation. International Regional Science Review, 27, 271-296. 173 Warme, D. M. (1998). Spanning trees in hypergraphs with applications to Steiner trees. Ph.D. dissertation, School of Engineering and Applied Science, University of Virginia. Weber, A. (1909). Reine theorie des standorts. Tiibingen: J.C.B. Mohr (Paul Siebeck). Whittaker, R. J. (1998). Island biogeography: ecology, evolution and conservation. Oxford; New York: Oxford University Press. Wilf, H. S. (1994). Algorithms and complexity (Internet ed). Philadelphia, PA: University of Pennsylvania. Wood, C. H., & Porro, R. (2002). Deforestation and land use in the Amazon. Gainesville: University Press of Florida. Wooldridge, J. (2002). Econometric analysis of cross section and panel data. Cambridge, MA: The MIT Press. Yu, G, Lee, J ., & Munro-Stasiuk, M. J. (2003). Extensions to least-cost path al- gorithms for roadway planning. International Journal of Geographical Information Science, 17(4), 361-376. 174 l l. AAAAAAAAAA lllllll llllllllll 3 1293