Representações computacionais de formas podem ser criadas em ferramentas CAD ou geradas a partir de um objeto físico já existente. Esta última abordagem oferece como vantagens rapidez e fidelidade ao objeto original, que são os aspectos fundamentais em muitas aplicações, como Simulações Numéricas de Equações Diferenciais Parciais e Imagens Médicas. A reconstrução (ou geração de malhas superficiais) a partir de pontos amostrados de uma superfície de um objeto é um problema clássico de representação de formas. Nesta dissertação apresentamos um vasto levantamento bibliográfico deste tipo de reconstrução, classificando e descrevendo os principais trabalhos presentes na literatura. A partir do levantamento bibliográfico, selecionamos um conjunto de algoritmos sobre os quais foram realizadas comparações teóricas e empíricas cujos resultados são apresentados. Para finalizar, apresentamos aplicações de nossas implementações em Simulação Numérica de Equações Diferenciais Parciais e processamento de Imagens / Computational representations of shapes can be developed using CAD applications or created from data acquired from a real physical object. This latter is advantageous with respect to time and fidelity to the original object which are essential to several applications, such as Numerical Simulation of Partial Differential Equations and Medical Imaging. A classical shape representation problem is that of reconstruction (or superficial mesh generation) from points sampled over the surface of an object. In this Master\'s thesis we describe a broad survey of these reconstruction methods. We focus in the classification and characterization of the main algorithms proposed in the literature. From this survey, we selected some algorithms and conducted some theoretical and practical comparisons. We conclude this work describing applications of the algorithms implemented in Numerical Simulations of Differential Partial Equations and Image Processing

La géométrie algorithmique est une discipline en pleine expansion dont l'objet est la conception d'algorithmes résolvant des problèmes géométriques. De tels algorithmes sont très utiles notamment dans l'ingénierie, l'industrie et le multimédia. Pour être performant, il est fréquent qu'un algorithme géométrique utilise des structures de données spécialisées.Nous nous sommes intéressés à une telle structure : le diagramme de Voronoï et avons proposé une généralisation de celui-ci. Ladite généralisation résulte d'une extension du prédicat du disque vide (prédicat propre à toute région de Voronoï) à une union de disques. Nous avons analysé les régions basées sur le prédicat étendu et avons proposé des méthodes pour les calculer par ordinateur.Par ailleurs, nous nous sommes intéressés aux « problèmes de placement de formes », thème récurrent en géométrie algorithmique. Nous avons introduit un formalisme universel pour de tels problèmes et avons, pour la première fois, proposé une méthode de résolution générique, en ce sens qu'elle est apte à résoudre divers problèmes de placement suivant un même algorithme.Nos travaux présentent, d'une part, l'avantage d'élargir le champ d'application de structures de données basées sur Voronoï. D'autre part, ils facilitent de manière générale l'utilisation de la géométrie algorithmique, en unifiant définitions et algorithmes associés aux problèmes de placement de formes. / Computational geometry is an active branch of computer science whose goal is the design of efficient algorithms solving geometric problems. Such algorithms are useful in domains like engineering, industry and multimedia. In order to be efficient, algorithms often use special data structures.In this thesis we focused on such a structure: the Voronoi diagram. We proposed a new generalized diagram. We have proceeded by extending the empty disk predicate (satisfied by every Voronoi region) to an arbitrary union of disks. We have analyzed the new plane regions based on the extended predicate, and we designed algorithms for computing them.Then, we have considered another topic, which is related to the first one: shape placement problems. Such problems have been studied repeatedly by researchers in computational geometry. We introduced new notations along with a global framework for such problems. We proposed, for the first time a generic method, which is able to solve various placement problems using a single algorithm.Thus, our work extend the scope of Voronoi based data structures. It also simplifies the practical usage of placement techniques by unifying the associated definitions and algorithms.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / O presente trabalho propõe analisar metodologias para o cálculo do gradiente em malhas não-estruturadas do tipo Voronoi que são utilizadas no método de Volumes Finitos. Quatro metodologias para o cálculo do gradiente são testadas e comparadas com soluções analíticas. As técnicas utilizadas são: Método do Balanço de Forças, Método do Mínimo Resíduo Quadrático, Método da Média dos Gradientes Projetos e Método da Média dos Gradientes Projetados Corrigidos. Uma análise por série de Taylor também foi feita, e as equações analíticas comparadas com resultados numéricos. Os testes são realizados em malhas cartesianas e malhas triangulares, que em um trabalho anterior apresentaram alguns resultados inconsistentes. A influência do ponto gerador e do ângulo de rotação é analisada. É verificado que a posição do ponto gerador e a metodologia utilizada em cada malha influencia no cálculo do gradiente. Dependendo da malha e da metodologia utilizada, as equações analíticas indicaram que existem erros associados, que prejudicam o cálculo do gradiente. / Presente work propose examine methodologies for calculate gradient using a non-structured mesh of Voronois type, used on finite volume method. Four methodologies for calculate gradient are tested and compared with analytical solutions. The techniques used are: the Forces Balance Method, Minimum Quadratic Residue Method, Average Projected Gradient Method and the Revised Average Projected Method. An analysis using Taylor series was also made, and the analytical equations compared with numerical results. Tests are performed over Cartesian and triangular meshes, second one which in a previous work showed some inconsistent results. The influence of the gerator point displacement and rotation angle is analyzed. It was found that the position of the generator point and the methodology used influences gradient value. Accordingly to the mesh and the methodology used, analytical equations indicates that there are associated errors, which affect gradient value.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / O presente trabalho propõe analisar metodologias para o cálculo do gradiente em malhas não-estruturadas do tipo Voronoi que são utilizadas no método de Volumes Finitos. Quatro metodologias para o cálculo do gradiente são testadas e comparadas com soluções analíticas. As técnicas utilizadas são: Método do Balanço de Forças, Método do Mínimo Resíduo Quadrático, Método da Média dos Gradientes Projetos e Método da Média dos Gradientes Projetados Corrigidos. Uma análise por série de Taylor também foi feita, e as equações analíticas comparadas com resultados numéricos. Os testes são realizados em malhas cartesianas e malhas triangulares, que em um trabalho anterior apresentaram alguns resultados inconsistentes. A influência do ponto gerador e do ângulo de rotação é analisada. É verificado que a posição do ponto gerador e a metodologia utilizada em cada malha influencia no cálculo do gradiente. Dependendo da malha e da metodologia utilizada, as equações analíticas indicaram que existem erros associados, que prejudicam o cálculo do gradiente. / Presente work propose examine methodologies for calculate gradient using a non-structured mesh of Voronois type, used on finite volume method. Four methodologies for calculate gradient are tested and compared with analytical solutions. The techniques used are: the Forces Balance Method, Minimum Quadratic Residue Method, Average Projected Gradient Method and the Revised Average Projected Method. An analysis using Taylor series was also made, and the analytical equations compared with numerical results. Tests are performed over Cartesian and triangular meshes, second one which in a previous work showed some inconsistent results. The influence of the gerator point displacement and rotation angle is analyzed. It was found that the position of the generator point and the methodology used influences gradient value. Accordingly to the mesh and the methodology used, analytical equations indicates that there are associated errors, which affect gradient value.

A poluição atmosférica tornou-se uma das maiores preocupações mundiais para a saúde pública e ambiental. Vários estudos já abordaram o contexto desse tema, no intuito de verificar a associação entre o aumento da incidência de doenças com o aumento da poluição atmosférica, principalmente em cidades onde o tráfego de veículos tem aumentado de forma significante. O controle dessa poluição, normalmente, é realizado através da monitoração da qualidade do ar, por meio de rede de sensores. Esta rede de monitoramento, além de ser utilizada como instrumento de medida de segurança de saúde pública, permite analisar os benefícios propiciados pelas ações de controle dos níveis de poluição do ar e justifica possíveis intervenções em caso de violação dos limiares estabelecidos pela legislação. Os altos custos envolvidos e a dificuldade inerente à logística de implantação e manutenção dos pontos de coleta podem levar a um posicionamento inadequado ou pouco representativo, quando não estudado cuidadosamente. Portanto, uma boa escolha do local de inserção do ponto é indispensável para propiciar uma maior eficiência nesses custos. Os Diagramas de Voronoi Valorados foram utilizados como uma ferramenta para determinar a área de abrangência de cada sensor de poluição atmosférica. Após a realização das simulações, as áreas de abrangência de cada sensor relacionada com seu peso, foram apresentadas de maneira satisfatória / Atmospheric pollutants has become a major world concern for environmental and public health. Several studies have already addressed in this context about theme in order to verify the association between increased incidences of diseases with increased air pollution, mainly in cities where vehicle traffic has increased significantly. The pollution control is usually done by monitoring air quality through the sensor network. This monitoring network, besides being used as a tool for measuring public health safety, allow analyze the benefits gained by efforts to control the levels of air pollution and justify possible actions in case of breach of the thresholds established by legislation. The high costs involved and the difficulty inherent in the logistics of deployment and maintenance of the collection points can lead to an inappropriate placement or unrepresentative, if not carefully studied. Therefore, a good choice of site of insertion point is essential to provide greater efficiency in these costs. In this sense, the use of the weighted diagram Vononoi was used as a tool to determine the coverage area of each pollutant atmospheric sensor. After being realized the simulations, the coverage area of each sensor related with their own weight, were presented in a satisfactory way

Voronoidiagram är en välbeprövad teknik inom många olika områden och är vanligt förekommande inom grafisk texturering men har också förekommit inom stadsgenerering som del av andra tekniker. I denna undersökning har voronoidiagram isolerats från andra erkända tekniker och använts för stadsgenerering. Syftet med arbete var att studera hur olika konfigurationer för voronoidiagram kan användas för att styra diagrammet i syfte att generera en stad med mur. Utseendet för de genererade städerna är baserat på litteratur för medeltida städer. En applikation har skapats för att kunna testa olika konfigurationer. De konfigurationer som har använts inom projektet har utvärderats baserat på deras styrkor och svagheter. Arbetets resultat presenterar utöver utvärdering av konfigurationerna också hypotetiska förändringar och nya infallsvinklar till problemet vilket är intressant för att vidare undersöka för hur voronoidiagram kan användas inom procedurell stadsgenerering.

Representações computacionais de formas podem ser criadas em ferramentas CAD ou geradas a partir de um objeto físico já existente. Esta última abordagem oferece como vantagens rapidez e fidelidade ao objeto original, que são os aspectos fundamentais em muitas aplicações, como Simulações Numéricas de Equações Diferenciais Parciais e Imagens Médicas. A reconstrução (ou geração de malhas superficiais) a partir de pontos amostrados de uma superfície de um objeto é um problema clássico de representação de formas. Nesta dissertação apresentamos um vasto levantamento bibliográfico deste tipo de reconstrução, classificando e descrevendo os principais trabalhos presentes na literatura. A partir do levantamento bibliográfico, selecionamos um conjunto de algoritmos sobre os quais foram realizadas comparações teóricas e empíricas cujos resultados são apresentados. Para finalizar, apresentamos aplicações de nossas implementações em Simulação Numérica de Equações Diferenciais Parciais e processamento de Imagens / Computational representations of shapes can be developed using CAD applications or created from data acquired from a real physical object. This latter is advantageous with respect to time and fidelity to the original object which are essential to several applications, such as Numerical Simulation of Partial Differential Equations and Medical Imaging. A classical shape representation problem is that of reconstruction (or superficial mesh generation) from points sampled over the surface of an object. In this Master\'s thesis we describe a broad survey of these reconstruction methods. We focus in the classification and characterization of the main algorithms proposed in the literature. From this survey, we selected some algorithms and conducted some theoretical and practical comparisons. We conclude this work describing applications of the algorithms implemented in Numerical Simulations of Differential Partial Equations and Image Processing

The thesis apply to reliability problems approach of Voronoi tessellation, typically used in the field of samples designs evaluation and for Monte Carlo samples reweighing. It is shown, this general technique estimation converges to that of Importance Sampling method despite it does not rely on Importance Sampling's auxiliary density. Consequently, reliability analysis could be divided into sampling itself and assessment of simulation results. As an extension of this idea, adaptive statistical sampling using QHull library was attempted.

The thesis deals with aplication of data mining methods for the analysis of two Ni3Si supercells, one with a stable grain boundary and the second one with unstable grain boundary. DOS and COHP curves are examined using selected curve matching methods. The surroundings of the individual atoms are examined by the Voronoi diagram. This information was used to reveal the differences in binding between stable and unstable supercell.

Nous étudions dans cette thèse la génération de maillages anisotropes basée sur la triangulation de Delaunay et le diagramme de Voronoi. Nous considérons tout d'abord les maillages anisotropes localement uniformes, développés par Boissonnat, Wormser et Yvinec. Bien que l'aspect théorique de cette approche soit connu, son utilité pratique n'a été que peu explorée. Une étude empirique exhaustive est présentée et révèle les avantages, mais aussi les inconvénients majeurs de cette méthode. Dans un second temps, nous étudions les diagrammes de Voronoi anisotropes définis par Labelle et Shewchuk. Nous donnons des conditions suffisantes sur un ensemble de points pour que le dual du diagramme soit une triangulation plongée en toute dimension ; un algorithme générant de tels ensembles est conçu. Ce diagramme est utilisé pour concevoir un algorithme qui génère efficacement un maillage anisotrope pour des domaines de dimension intrinsèque faible plongés dans des espaces de dimension large. Notre algorithme est prouvable, mais les résultats sont décevants. Enfin, nous présentons le diagramme de Voronoi Riemannien discret, qui utilise des avancées récentes dans l'estimation de distances géodésiques et dont le calcul est grandement accéléré par l'utilisation d'un graphe anisotrope. Nous donnons des conditions suffisantes pour que notre structure soit combinatoirement équivalente au diagramme de Voronoi Riemannien et que son dual utilisant des simplexes droits mais aussi courbes est une triangulation plongée en toute dimension. Nous obtenons de bien meilleurs résultats que pour nos autres techniques, mais dont l'utilité reste limitée / In this thesis, we study the generation of anisotropic meshes using the concepts of Delaunay triangulations and Voronoi diagrams. We first consider the framework of locally uniform anisotropic meshes introduced by Boissonnat, Wormser and Yvinec. Despite known theoretical guarantees, the practicality of this approach has only been hardly studied. An exhaustive empirical study is presented and reveals the strengths but also the overall impracticality of the method. In a second part, we investigate the anisotropic Voronoi diagram introduced by Labelle and Shewchuk and give conditions on a set of seeds such that the corresponding diagram has a dual that is an embedded triangulation in any dimension; an algorithm to generate such sets is devised. Using the same diagram, we propose an algorithm to generate efficiently anisotropic triangulations of low-dimensional manifolds embedded in high-dimensional spaces. Our algorithm is provable, but produces disappointing results. Finally, we study Riemannian Voronoi diagrams and introduce discrete Riemannian Voronoi diagrams, which employ recent developments in the numerical computation of geodesic distances and whose computation is accelerated through the use of an underlying anisotropic graph structure. We give conditions that guarantee that our discrete structure is combinatorially equivalent to the Riemannian Voronoi diagram and that its dual is an embedded triangulation, using both straight and curved simplices. We obtain significantly better results than with our other methods, but the overall utility of