Trees are fundamental structures in computer science, being widely used in modeling and representing different types of data in numerous computer applications. In many cases, properties of objects being modeled are stored as weights or labels on the nodes of trees. Thus researchers have studied the preprocessing of weighted trees in which each node is assigned a weight, in order to support various path queries, for which a certain function over the weights of the nodes along a given query path in the tree is computed [3, 14, 22, 26]. In this thesis, we consider the problem of supporting several various path queries over a tree on n weighted nodes, where the weights are drawn from a set of σ distinct values. One query we support is the path median query, which asks for the median weight on a path between two given nodes. For this and the more general path selection query, we present a linear space data structure that answers queries in O(lg σ) time under the word RAM model. This greatly improves previous results on the same problem, as previous data structures achieving O(lg n) query time use O(n lg^2 n) space, and previous linear space data structures require O(n^ε) time to answer a query for any positive constant ε [26]. We also consider the path counting query and the path reporting query, where a path counting query asks for the number of nodes on a query path whose weights are in a query range, and a path reporting query requires to report these nodes. Our linear space data structure supports path counting queries with O(lg σ) query time. This matches the result of Chazelle [14] when σ is close to n, and has better performance when σ is significantly smaller than n. The same data structure can also support path reporting queries in O(lg σ + occ lg σ) time, where occ is the size of output. In addition, we present a data structure that answers path reporting queries in O(lg σ + occ lg lg σ) time, using O(n lg lg σ) words of space. These are the first data structures that answer path reporting queries.

Trees are fundamental structures in computer science, being widely used in modeling and representing different types of data in numerous computer applications. In many cases, properties of objects being modeled are stored as weights or labels on the nodes of trees. Thus researchers have studied the preprocessing of weighted trees in which each node is assigned a weight, in order to support various path queries, for which a certain function over the weights of the nodes along a given query path in the tree is computed [3, 14, 22, 26]. In this thesis, we consider the problem of supporting several various path queries over a tree on n weighted nodes, where the weights are drawn from a set of σ distinct values. One query we support is the path median query, which asks for the median weight on a path between two given nodes. For this and the more general path selection query, we present a linear space data structure that answers queries in O(lg σ) time under the word RAM model. This greatly improves previous results on the same problem, as previous data structures achieving O(lg n) query time use O(n lg^2 n) space, and previous linear space data structures require O(n^ε) time to answer a query for any positive constant ε [26]. We also consider the path counting query and the path reporting query, where a path counting query asks for the number of nodes on a query path whose weights are in a query range, and a path reporting query requires to report these nodes. Our linear space data structure supports path counting queries with O(lg σ) query time. This matches the result of Chazelle [14] when σ is close to n, and has better performance when σ is significantly smaller than n. The same data structure can also support path reporting queries in O(lg σ + occ lg σ) time, where occ is the size of output. In addition, we present a data structure that answers path reporting queries in O(lg σ + occ lg lg σ) time, using O(n lg lg σ) words of space. These are the first data structures that answer path reporting queries.

As planted forests mature and are clearfelled in patches, second rotation tree crops (restocks) become available to black grouse, a species of conservation concern in the UK. Currently, only a limited amount is known about the resources provided by this habitat to black grouse and their broods. The aims of this study therefore, were to investigate the recovery of field-layer vegetation and the invertebrate population from restock through to canopy closure of planted trees, assess the duration of habitat availability and food resources to black grouse, and understand how forest management could improve provision. Changes to the abundance of predators resulting from habitat management were also considered. The comparative habitat quality of restocks was assessed in a wider landscape context. Field-layer vegetation in 72 restocks in two afforested areas in the north-east and the south-west of the Scottish Highlands was surveyed. On average, only 60% of ground in restocks was re-planted with second rotation trees, with the remainder left unplanted. Initial vegetation recovery was generally impeded by timber harvest residues (mainly brash), which comprised up to 50% of total ground cover two years after restock. Increased cover of heather Calluna vulgaris, often an important component of black grouse habitat, and decreased brash cover were recorded in areas of restocks where first-rotation timber was removed by cable-winch (compared with harvester and forwarder removal) and in planted areas (compared with areas left unplanted). Bilberry Vaccinium myrtillus and cotton grass Eriophorum spp. occurrence was recorded infrequently irrespective of restock age or management. Heather generally dominated the field-layer six years after restock, reaching a height and density reported to be suitable for black grouse nesting and brood cover in other studies. The onset of tree canopy closure as early as eight years suggests that suitable black grouse habitat availability in restocks is likely to be severely limited in duration. Brash removal, or break-up and re-distribution of the brash layer, positively affected the recovery of field-layer vegetation species potentially of use to black grouse. Extending the fallow period prior to restock resulted in an extended period of suitable habitat available to black grouse prior to canopy closure. However, habitat created by extending the fallow period also attracted a higher number of mammalian predators of black grouse. In the longer term, areas of restocks left unplanted should provide a valuable open-ground resource after canopy closure of the planted crop, although results suggest that management to prevent encroachment of naturally regenerating non-native trees is likely to be necessary. Invertebrate taxa selected by chicks in previous black grouse studies were available in all ages of restock studied. Taxa abundance differed as restocks aged and field-layer vegetation developed, although contrasting habitat preferences of taxa meant that each was affected differently by restock management. No single forest management method positively increased abundance of all taxa. Abundance of Lepidoptera larvae, a key food item for black grouse chicks, was positively related to dwarf shrub cover. An extended fallow period prior to restock should prolong increased larvae availability to chicks. Provision of preferred field-layer vegetation habitat and invertebrate abundance in restocks was comparable to habitat surrounding leks - areas likely to be occupied and utilised by black grouse. Restocks had a comparatively low occurrence of key plant species, including bilberry Vaccinium myrtillus and cotton grass Eriophorum spp. Cover of the dwarf shrub bog myrtle Myrica gale, positively associated with Lepidoptera larvae abundance in habitat surrounding leks, was absent from restocks. The abundance of other invertebrate taxa considered was similar between leks and restocks. Study findings are discussed with reference to black grouse conservation and commercial forestry systems in Europe. Management recommendations to improve habitat for black grouse in second rotation planted forests in Britain are provided.

Submitted by Lucas Jamiro Barbosa (eng.lucasjb@gmail.com) on 2018-02-21T18:50:52Z No. of bitstreams: 1 barbosa_lj_me_prud.pdf: 5180173 bytes, checksum: 561a235397d5860ed83f8776cc40f6a4 (MD5) / Approved for entry into archive by ALESSANDRA KUBA OSHIRO ASSUNÇÃO (alessandra@fct.unesp.br) on 2018-02-21T19:37:41Z (GMT) No. of bitstreams: 1 barbosa_lj_me_prud.pdf: 5180173 bytes, checksum: 561a235397d5860ed83f8776cc40f6a4 (MD5) / Made available in DSpace on 2018-02-21T19:37:41Z (GMT). No. of bitstreams: 1 barbosa_lj_me_prud.pdf: 5180173 bytes, checksum: 561a235397d5860ed83f8776cc40f6a4 (MD5) Previous issue date: 2017-04-28 / Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) / O Sensoriamento Remoto tem-se mostrado, nos últimos anos, uma excelente ferramenta na aquisição de informações da cobertura da Terra. Dentre os diversos sensores remotos, o sistema de aquisição de dados por varredura LASER (Light Amplification by Stimulated Emission of Radiation) se apresenta como uma ferramenta poderosa na coleta de informações tridimensionais. A tecnologia lidar (Light Detection And Ranging), quando a bordo de aeronaves, pode ser denominada como Airborne Laser Scanning (ALS), diferente dos sistemas aerofotogramétricos de imageamento tradicionais, permite coletar, simultaneamente, pontos com coordenadas 3D sobre copas de árvores, bem como o terreno abaixo dela, em função da capacidade de registro de múltiplos retornos e da divergência do pulso. Por esta razão, esta tecnologia tem sido utilizada em diversas aplicações florestais, como manejo e recuperação florestal, silvicultura, exploração madeireira, dentre outras. Diversas pesquisas têm mostrado a possibilidade de utilização dos dados lidar na extração e delimitação de indivíduos arbóreos e, portanto, na estimativa de variáveis dendrométricas. Desta forma, o desenvolvimento de técnicas que proporcionem a automatização no delineamento das copas das árvores e na estimativa destas informações é de grande interesse. Contudo, grande parte das pesquisas relacionadas à detecção de árvores, delimitação de copa e estimativa de algumas variáveis são desenvolvidas considerando cenários homogêneos e específicos, onde a vegetação é caracterizada pela presença de árvores coníferas e/ou deciduais, ou florestas de exploração madeireira. Portanto, o objetivo desta pesquisa foi a implementação e avaliação de uma técnica que permita detectar indivíduos arbóreos e aglomerados, considerando um cenário urbano heterogêneo e complexo; e, destes indivíduos, estimar variáveis dendrométricas como área da copa; altura da árvore; e raio médio da copa. A metodologia proposta é realizada em três etapas e se baseia no uso do método de crescimento de regiões, aplicado à nuvem de pontos originais, ordenados quanto à altura. Além disso, são usados polígonos convexos visando a extração de indivíduos arbóreos e aglomerados. Para isso, são utilizados três parâmetros: distância mínima, buffer e perímetro comum. Foram realizados experimentos considerando dados reais e cenários diferentes em uma área urbana, para diferentes conjuntos de parâmetros utilizados no processo de delimitação das copas. Os mesmos foram avaliados quanto a acurácia temática, completeza e F-Score, calculados em função de referências obtidas de forma manual. Na delimitação de indivíduos arbóreos e aglomerados, simultaneamente, o maior valor de F-Score foi de 54% e na delimitação de indivíduos e aglomerados, em separado, o melhor resultado obtido foi 74% e 39%, respectivamente. Embora melhorias possam ser feitas visando aumentar estes indicadores, principalmente para aglomerados, pode-se considerar que o método proposto tem potencial de aplicação, sobretudo quando se tem por objetivo a extração de árvores individuais em ambiente urbano. / Remote Sensing has shown to be, in the last years, an excellent way of acquiring Earth’s surface data. Among all remote sensors, the system of data acquisition by LASER (Light Amplification by Stimulated Emission of Radiation) scanning has been presented as a powerful tool for three-dimensional information collection. lidar (Light Detection And Ranging) technology, when onboard of airplanes can be named Airborne Laser Scanning (ALS) and, differently from traditional photogrammetric techniques, allows the collection of simultaneously 3D points over tree crowns, as well as the ground underneath it, due to the recording capacity of multiple echoes arising from the divergence of the pulse. For this reason, this technology has been used in many different forest applications, as management and forest recovery, forestry, logging and others. Some researchers have shown the possibility of using lidar data on tree extraction and crown delineation and, therefore, on the estimation of their dendrometric variables. In this way, the development of techniques that can provide the automation of tree crowns delineation and estimation of this information has increased. However, most of the researches performed ever related to tree detection, canopy delineation and estimation of some dendrometric variables are developed considering homogeneous and specific scenarios where the vegetation is characterized by the presence of coniferous and/or deciduous trees. For this purpose, the objective of this research was the implementation and evaluation of a technique capable of detecting individual trees and clumps, considering a heterogeneous urban scenario. Additionally, from those individual trees some dendrometric variables such as crown area; tree height and average crown radius were estimated. Experiments were conducted considering different study areas in an urban environment varying the parameters used in the crown delineation process. Those experiments were evaluated in terms of thematic accuracy, completeness and F-Score, computed based on reference values obtained manually. When the simultaneous delimitation of arboreal individuals and agglomerates was performed the best F-Score was 54%. For independent processing, the best result was 74% and 39%, respectively, for individuals and agglomerates. Although improvements can be performed aiming to improve those indicators, mainly to clumps, it is possible to consider that the proposed method has potential, especially when the objective is the extraction of individual trees in an urban environment.