This thesis is a contribution to a classical problem in computational and combinatorial geometry: the study of the k-sets of a set V of n points in the plane. First we introduce the notion of convex inclusion chain that is an ordering of the points of V such that no point is inside the convex hull of the points that precede it. Every k-set of an initial sub-sequence of the chain is called a k-set of the chain. We prove that the number of these k-sets is an invariant of V and is equal to the number of regions in the order-k Voronoi diagram of V. We then deduce an online algorithm for the construction of the k-sets of the vertices of a simple polygonal line such that every vertex of this line is outside the convex hull of all its preceding vertices on the line. If c is the total number of k-sets built with this algorithm, the complexity of our algorithm is in O(n log n + c log^2k) and is equal, per constructed k-set, to the complexity of the best algorithm known. Afterward, we prove that the classical divide and conquer algorithmic method can be adapted to the construction of the k-sets of V. The algorithm has a complexity of O(n log n + c log^2k log(n/k)), where c is the maximum number of k-sets of a set of n points. We finally prove that the centers of gravity of the k-sets of a convex inclusion chain are the vertices of a triangulation belonging to the family of so-called centroid triangulations. This family notably contains the dual of the order-k Voronoi diagram. We give an algorithm that builds particular centroid triangulations in O(n log n + k(n- k) log^2 k) time, which is more efficient than all the currently known algorithms.

Several examples of nearly optimal transport networks can be found in nature. These networks effectively distribute and drain fluids throughout a medium. Evidence suggests that blood vessels of the circulatory system, airways in the lungs and veins of leaf venations are examples of networks that have evolved to become effective in their tasks while simultaneously being energy efficient. Hence, it does not come as a surprise that recent performance improvements of modern power generating devices occur due to the use of nature-inspired channel architectures. Guided by this observations, in this work, we investigate the application of visually realistic computer-generated leaf venation patterns to a type of photovoltaic device. We solve the flow through the device problem using Computational Fluid Dynamics (CFD) tools. Moreover, we attempt to develop experimentals models. Ultimately, we seek to single out the network properties that affect their performance. / Diversos exemplos de redes de transporte quase ótimas podem ser encontradas na natureza. Essas redes distribuem e coletam fluidos através de um meio. Evidências sugerem que os vasos sanguíneos do sistema circulatório, as vias respiratórias nos pulmões e as veias das venações em folhas são exemplares de redes que evoluiram para se tornarem efetivas em suas tarefas sendo, ao mesmo tempo, eficientes energeticamente. Dessa forma, não chega a ser surpreendente que recentes melhorias de performance em dispositivos de geração de energia modernos ocorrem devido ao uso de arquiteturas de canais inspiradas na natureza. Guiados por estas observações, nesse trabalho, investigamos a aplicação de padrões de venações verossímeis geradas por computador em um tipo de dispositivo fotovoltaico. Resolvemos o problema de escoamento através do dispositivo usando ferramentas de Dinâmica de Fluidos Computacional (CFD). Além disso, procuramos desenvolver modelos experimentais. Em última instância, estamos em busca das propriedades da rede que afetam sua performance.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho apresenta um estudo teórico e numérico sobre os erros que ocorrem nos cálculos de gradientes em malhas não estruturadas constituídas pelo diagrama de Voronoi, malhas estas, formadas também pela triangulação de Delaunay. As malhas adotadas, no trabalho, foram as malhas cartesianas e as malhas triangulares, esta última é gerada pela divisão de um quadrado em dois ou quatro triângulos iguais. Para tal análise, adotamos a escolha de três metodologias distintas para o cálculo dos gradientes: método de Green Gauss, método do Mínimo Resíduo Quadrático e método da Média do Gradiente Projetado Corrigido. O texto se baseia em dois enfoques principais: mostrar que as equações de erros dadas pelos gradientes podem ser semelhantes, porém com sinais opostos, para pontos de cálculos em volumes vizinhos e que a ordem do erro das equações analíticas pode ser melhorada em malhas uniformes quando comparada as não uniformes, nos casos unidimensionais, e quando analisada na face de tais volumes vizinhos nos casos bidimensionais. / This work presents a theoretical and numerical study on the errors that occur in the calculation of gradients on unstructured meshes Voronoi type, these meshes, also formed by Delaunay triangulation. The meshes adopted in the work were cartesian and triangular meshes, the latter is formed by dividing a square in two or four equal triangles. For this analysis, we adopt the choice of three different methodologies for the calculation of gradients: Green Gauss method, weighted least-squares method and mean value of the projected gradients method. The text is based on two main approaches: to show that the equations of errors given by the gradients may be similar, but with opposite signs, for calculation point in opposite volumes. And show that the order of the error of the analytical equations can be improved in uniform mesh when compared to not uniform, the one-dimensional case, and when viewed from the opposite face of such volumes for the two-dimensional case.

[pt] Este trabalho apresenta um método para extração de malhas poligonais adaptativas em multi-resolução, a partir de objetos volumétricos. As principais aplicações da extração de malhas estão ligadas à área médica, dinâmica de fluidos, geociências, meteorologia, dentre outras. Nestas áreas os dados podem ser representados como objetos volumétricos. Nos dados volumétricos as informações estão representadas implicitamente, o que dificulta o processamento direto dos objetos que se encontram representados dentro do volume. A extração da malha visa obter uma representação explícita dos objetos, de modo a viabilizar o processamento dos mesmos. O método apresentado na tese procura extrair a malha a partir de processos de Simplicação e Refinamento. Durante a simplificação é extraída uma representação super amostrada do objeto (na mesma resolução do volume inicial), a qual é simplificada de modo a se obter uma malha base ou malha grossa, em baixa resolução, porém contendo a topologia correta do objeto. A etapa de refinamento utiliza a transformada de distâ ncia para obter uma representação da malha em multi-resolução, ou seja, a cada instante é obtida uma malha de maior resolução que vai se adaptando progressivamente à geometria do objeto. A malha final apresenta uma série de propriedades importantes, como boa razão de aspecto dos triângulos, converge para a superfície do objeto, pode ser aplicada tanto a objetos com borda quanto a objetos sem borda, pode ser aplicada tanto a superfície conexas quanto a não conexas, dentre outras. / [en] This work presents a method for extracting multiresolution adaptive polygonal meshes, from volumetric objects. Main aplications of this work are related to medical area, fluid dynamics, geosciences, metheorology and others. In these areas data may be represented as volumetric objects. Volumetric datasets are implicit representations of objects, so it s very dificult to apply directly any process to these objects. Mesh extraction obtains an explicit representation of the objetc, such that it s easier to process directly the objects. The presented method extracts the mesh from two main processes: Simplification and Refinement. The simplification step extracts a supersampled representation of the object (in the same volume resolution), and simplifies it in such a way to obtain a base mesh (or coarse mesh), in a low resolution, but containing the correct topology of the object. Refinement step uses the distance transform to obtain a multiresolution representation of the mesh, it means that at each instant it s obtained an adaptive higher resolution mesh. The final mesh presents a set of important properties, like good triangle aspect ratio, convergency to the object surface, may be applied as to objects with boundary and as to objects with multiple connected components, among others properties.

The recent technological advances in the field of autonomous vehicles have resulted in a growing impetus for researchers to improve the current framework of mission planning and execution within both the military and civilian contexts. Many recent efforts towards this direction emphasize the importance of replacing the so-called monolithic paradigm, where a mission is planned, monitored, and controlled by a unique global decision maker, with a network centric paradigm, where the same mission related tasks are performed by networks of interacting decision makers (autonomous vehicles). The interest in applications involving teams of autonomous vehicles is expected to significantly grow in the near future as new paradigms for their use are constantly being proposed for a diverse spectrum of real world applications. One promising approach to extend available techniques for addressing problems involving a single autonomous vehicle to those involving teams of autonomous vehicles is to use the concept of Voronoi diagram as a means for reducing the complexity of the multi-vehicle problem. In particular, the Voronoi diagram provides a spatial partition of the environment the team of vehicles operate in, where each element of this partition is associated with a unique vehicle from the team. The partition induces, in turn, a graph abstraction of the operating space that is in a one-to-one correspondence with the network abstraction of the team of autonomous vehicles; a fact that can provide both conceptual and analytical advantages during mission planning and execution. In this dissertation, we propose the use of a new class of Voronoi-like partitioning schemes with respect to state-dependent proximity (pseudo-) metrics rather than the Euclidean distance or other generalized distance functions, which are typically used in the literature. An important nuance here is that, in contrast to the Euclidean distance, state-dependent metrics can succinctly capture system theoretic features of each vehicle from the team (e.g., vehicle kinematics), as well as the environment-vehicle interactions, which are induced, for example, by local winds/currents. We subsequently illustrate how the proposed concept of state-dependent Voronoi-like partition can induce local control schemes for problems involving networks of spatially distributed autonomous vehicles by examining different application scenarios.

We connect the Mimetic Finite Difference method (MFD) with the finite-volume two-point flux scheme (TPFA) for Voronoi meshes. The main effect is reducing the saddle-point system to a much smaller symmetric-positive definite matrix. In addition, the generalization allows MFD to seamlessly integrate with existing porous media modeling technology. The generalization also imparts the monotonicity property of the TPFA method on MFD. The connection is achieved by altering the consistency condition of the velocity bilinear operator. First-order convergence theory is presented as well as numerical results that support the claims. We demonstrate a methodology for using MFD in modeling fluid flow in fractures coupled with a reservoir. The method can be used for nonplanar fractures. We use the method to demonstrate the effects of fracture curvature on single-phase and multi-phase flows. Standard benchmarks are used to demonstrate the accuracy of the method. The approach is coupled with existing reservoir simulation technology. / text

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho apresenta um estudo teórico e numérico sobre os erros que ocorrem nos cálculos de gradientes em malhas não estruturadas constituídas pelo diagrama de Voronoi, malhas estas, formadas também pela triangulação de Delaunay. As malhas adotadas, no trabalho, foram as malhas cartesianas e as malhas triangulares, esta última é gerada pela divisão de um quadrado em dois ou quatro triângulos iguais. Para tal análise, adotamos a escolha de três metodologias distintas para o cálculo dos gradientes: método de Green Gauss, método do Mínimo Resíduo Quadrático e método da Média do Gradiente Projetado Corrigido. O texto se baseia em dois enfoques principais: mostrar que as equações de erros dadas pelos gradientes podem ser semelhantes, porém com sinais opostos, para pontos de cálculos em volumes vizinhos e que a ordem do erro das equações analíticas pode ser melhorada em malhas uniformes quando comparada as não uniformes, nos casos unidimensionais, e quando analisada na face de tais volumes vizinhos nos casos bidimensionais. / This work presents a theoretical and numerical study on the errors that occur in the calculation of gradients on unstructured meshes Voronoi type, these meshes, also formed by Delaunay triangulation. The meshes adopted in the work were cartesian and triangular meshes, the latter is formed by dividing a square in two or four equal triangles. For this analysis, we adopt the choice of three different methodologies for the calculation of gradients: Green Gauss method, weighted least-squares method and mean value of the projected gradients method. The text is based on two main approaches: to show that the equations of errors given by the gradients may be similar, but with opposite signs, for calculation point in opposite volumes. And show that the order of the error of the analytical equations can be improved in uniform mesh when compared to not uniform, the one-dimensional case, and when viewed from the opposite face of such volumes for the two-dimensional case.

Several examples of nearly optimal transport networks can be found in nature. These networks effectively distribute and drain fluids throughout a medium. Evidence suggests that blood vessels of the circulatory system, airways in the lungs and veins of leaf venations are examples of networks that have evolved to become effective in their tasks while simultaneously being energy efficient. Hence, it does not come as a surprise that recent performance improvements of modern power generating devices occur due to the use of nature-inspired channel architectures. Guided by this observations, in this work, we investigate the application of visually realistic computer-generated leaf venation patterns to a type of photovoltaic device. We solve the flow through the device problem using Computational Fluid Dynamics (CFD) tools. Moreover, we attempt to develop experimentals models. Ultimately, we seek to single out the network properties that affect their performance. / Diversos exemplos de redes de transporte quase ótimas podem ser encontradas na natureza. Essas redes distribuem e coletam fluidos através de um meio. Evidências sugerem que os vasos sanguíneos do sistema circulatório, as vias respiratórias nos pulmões e as veias das venações em folhas são exemplares de redes que evoluiram para se tornarem efetivas em suas tarefas sendo, ao mesmo tempo, eficientes energeticamente. Dessa forma, não chega a ser surpreendente que recentes melhorias de performance em dispositivos de geração de energia modernos ocorrem devido ao uso de arquiteturas de canais inspiradas na natureza. Guiados por estas observações, nesse trabalho, investigamos a aplicação de padrões de venações verossímeis geradas por computador em um tipo de dispositivo fotovoltaico. Resolvemos o problema de escoamento através do dispositivo usando ferramentas de Dinâmica de Fluidos Computacional (CFD). Além disso, procuramos desenvolver modelos experimentais. Em última instância, estamos em busca das propriedades da rede que afetam sua performance.

[pt] A otimização topológica tem como objetivo encontrar a distribuição mais eficiente de material (ótima topologia) em uma determinada região, satisfazendo as restrições de projeto estabelecidas pelo usuário. Na abordagem tradicional atribui-se uma variável de projeto, constante, denominada densidade, para cada elemento finito da malha. Dessa forma, a qualidade da representação dos novos contornos da estrutura depende do nível de discretização da malha: quanto maior a quantidade de elementos, mais bem definida será a topologia da estrutura otimizada. No entanto, a utilização de malhas super-refinadas implica em um elevado custo computacional, principalmente na etapa de solução numérica das equações de equilíbrio pelo método dos elementos finitos. Este trabalho propõe uma nova estratégia computacional para o refinamento adaptativo local de malhas utilizando elementos finitos poligonais em domínios bidimensionais arbitrários. A ideia consiste em realizar um refinamento da malha nas regiões de concentração de material, sobretudo nos contornos internos e externos, e um desrefinamento nas regiões de baixa concentração de material, como por exemplo, nos furos internos. Desta forma, é possível obter topologias ótimas, com alta resolução e relativamente baixo custo computacional. Exemplos representativos são apresentados para demonstrar a robustez e a eficiência da metodologia proposta por meio de comparações com resultados obtidos com malhas super-refinadas e mantidas constantes durante todo o processo de otimização topológica. / [en] Topology optimization aims to find the most efficient distribution of material (optimal topology) in a given domain, subjected to design constraints defined by the user. The quality of the new boundary representation depends on the level of mesh refinement: the greater the number of elements in the mesh, the better will be the representation of the optimized structure. However, the use of super refined meshes implies in a high computational cost, especially regarding the numerical solution of the linear systems of equations that arise from the finite element method. This work proposes a new computational strategy for adaptive local mesh refinement using polygonal finite elements in arbitrary two-dimensional domains. The idea is to perform a mesh refinement in regions of material concentration, mostly in inner and outer boundaries, and a mesh derefinement in regions of low material concentration such as the internal holes. Thus, it is possible to obtain optimal topologies with high resolution and relatively low computational cost. Representative examples are presented to demonstrate the robustness and efficiency of the proposed methodology by comparing the results obtained herein with the ones from the literature where super refined meshes are held constant throughout all topology optimization process.

Submitted by JOSIANE SANTOS DE OLIVEIRA (josianeso) on 2017-06-13T15:57:01Z No. of bitstreams: 1 Jonathan Machado_.pdf: 1018280 bytes, checksum: ac428b5c72c1ef24649cb96a3a778512 (MD5) / Made available in DSpace on 2017-06-13T15:57:01Z (GMT). No. of bitstreams: 1 Jonathan Machado_.pdf: 1018280 bytes, checksum: ac428b5c72c1ef24649cb96a3a778512 (MD5) Previous issue date: 2017-03-30 / Nenhuma / Os acidentes de trânsito de veículos são uma das maiores causas de mortes na população jovem mundial, e existe uma tendência ao crescimento no número de casos dos mesmos nos próximos anos. A ocorrência dos acidentes é influenciada por diversos fatores, tais como condições das vias, condições climáticas, fiscalização de leis por órgãos governamentais, dentre outros. Seria interessante conhecer de maneira mais detalhada quais destes fatores detém maior influência. Na internet, existe uma quantidade imensa de dados gerados pelos mais diversos órgãos e empresas, porém grande parte desta informação não é analisada por ninguém, seja por falta de acesso, ou porque os dados não estão estruturados de uma maneira que permita seu entendimento. A disponibilização de dados vem aumentando, seja por conta de políticas de dados abertos implantadas pelo governo ou através de ferramentas colaborativas da web, que possibilitam o registro de informações por parte da população, e que posteriormente disponibilizam seus dados. Este trabalho propõe um método de agrupamento de dados georreferenciados oriundos de diversas fontes, para realização de uma análise estatística utilizando a técnica de Análise de Componentes Principais, que poderá identificar de forma georreferenciada quais características influenciam mais na ocorrência de acidentes de trânsito de veículos. Após a análise, é explorada uma nova metodologia de visualização dos resultados, plotados sobre mapas, que podem servir de auxílio para órgãos do governo e tomadores de decisão que realizam ações para diminuir os acidentes de trânsito. / Traffic accidents of vehicles are one of the biggest causes of deaths in the world's young population, and there is a tendency to increase this number in the next years. The occurrence of accidents is influenced by several factors, such as road conditions, climatic conditions, law enforcement by government agencies, among others. It would be interesting to know in more detail which of these factors has the greatest influence. On the internet, there is an immense amount of data generated by diverse agencies and companies, but much of this information is not analyzed, either because of lack of access, or because the data is not structured in a way that allows its understanding. The availability of data is increasing, either through open data policies implemented by the government, or through collaborative web tools, which make it possible record information by population, and subsequently make their data available. This work proposes a method of grouping georeferenced data from several sources, to perform a statistical analysis using the technique of Principal Components Analysis, which can identify in a georeferenced way which characteristics influence more in the occurrence of traffic acidentes of vehicles. After the analysis, a new methodology for visualizing results, plotted on maps, is explored, which can serve as an aid to government agencies and decision makers who take actions to reduce traffic accidents.