Este trabalho aborda dois problemas de geometria computacional: união de círculos e união de (vários) polígonos. Para o problema da união de círculos, os principais algoritmos da literatura são revisados e um algoritmo simples, porém ineficiente, é introduzido. Este algoritmo é então adaptado para resolver o problema da união de polígonos, produzindo um algoritmo que é competitivo com o estado da arte e, dependendo da aplicação, utiliza menos armazenamento. / This work deals with two problems from the field of computational geometry: union of circles and union of (many) polygons. For the union of circles problem, the main algorithms in the literature are revised and a simple, albeit inefficient, algorithm is introduced. This algorithm is then adapted to solve the union of polygons problem, resulting in an algorithm that is competitive with the state of the art and, depending on the application, makes use of less storage.

A classic problem Computational Geometry is finding all euclidean shortest paths in a simple polygon from a given source vertex to every other vertex in the boundary. In this text, we give a detailed description of the Visibility Graph and Shortest Path Tree structures that solve this problem and also present the Shortest Path Map structure that extends the solution to shortest paths to every point inside the polygon. / Um problema clássico em Geometria Computacional é: encontrar todos os caminhos mínimos euclidianos dentro de um polígono simples a partir de um dado vértice fonte para todos os outros vértices da borda. Neste texto, apresentamos detalhadamente as estruturas de Grafo de Visibilidade e Árvore de Caminhos Mínimos que resolvem este problema e descrevemos também a estrutura Mapa de Caminhos Mínimos que estende a solução para todos os pontos contidos dentro do polígono.

Esta tese teve como objetivo estudar problemas cinéticos de clustering, ou seja, problemas de clustering nos quais os objetos se movimentam. O trabalho se concentrou no caso unidimensional, em que os objetos são pontos se movendo na reta real. Diversas variantes desse caso foram abordadas. Em termos do movimento, consideramos o caso em que cada ponto se move com uma velocidade constante num dado intervalo de tempo, o caso em que os pontos se movem arbitrariamente e temos apenas as suas posições em instantes discretos de tempo, o caso em que os pontos se movem com uma velocidade aleatória em que se conhece apenas o valor esperado da velocidade, e o caso em que, dada uma partição do intervalo de tempo, os pontos se movem com velocidades constantes em cada subintervalo. Em termos do tipo de clustering buscado, nos concentramos no caso em que o número de clusters é um dado do problema e consideramos diferentes medidas de qualidade para o clustering. Duas delas são tradicionais para problemas de clustering: a soma dos diâmetros dos clusters e o diâmetro máximo de um cluster. A terceira medida considerada leva em conta a característica cinética do problema, e permite, de uma maneira controlada, que o clustering mude com o tempo. Para cada uma das variantes do problema, são apresentados algoritmos, exatos ou de aproximação, alguns resultados de complexidade obtidos, e questões que ficaram em aberto. / This work aimed to study kinetic problems of clustering, i.e., clustering problems in which the objects are moving. The study focused on the unidimensional case, where the objects are points moving on the real line. Several variants of this case have been discussed. Regarding the movement, we consider the case where each point moves at a constant velocity in a given time interval, the case where the points move arbitrarily and we only know their positions in discrete time instants, the case where the points move at a random velocity in which only the expected value of the velocity is known, and the case where, given a partition of the time interval, the points move at constant velocities in each sub-interval. Regarding the kind of clustering sought, we focused in the case where the number of clusters is part of the input of the problem and we consider different measures of quality for the clustering. Two of them are traditional measures for clustering problems: the sum of the cluster diameters and the maximum diameter of a cluster. The third measure considered takes into account the kinetic characteristic of the problem, and allows, in a controlled manner, that a cluster change along time. For each of the variants of the problem, we present algorithms, exact or approximation, some obtained complexity results, and open questions.

Dois métodos distintos são descritos e implementados. O primeiro método, proposto por Ruppert, possui garantias teóricas de qualidade quando a fronteira do domínio obedece certas restrições. O segundo método, proposto por Persson, possibilita um maior controle na densidade dos elementos que discretizam o domínio. As vantagens, desvantagens e particularidades de cada um dos métodos são descritas e detalhadas / Two distinct methods are described and implemented. The first method, proposed by Ruppert, has theoretical guarantees on the quality of elements when the domain boundaries respect certain restrictions. The second method, proposed by Persson, makes it possible to have greater control over the density of the elements that make up the domain. The advantages, disadvantages and specific points about each method are described and detailed

[pt] O estudo computacional de uniões de bolas possui aplicações em diversas áreas da Matemática. O objetivo principal deste trabalho é propor uma simplificação de união de bolas em R2 através de um movimento que obedece as direções do eixo medial, procurando preservar os grandes elementos geométricos da união de bolas. A desconexão ou não das formas é um aspecto essencial da evolução. Em alguns casos, pode significar uma divisão importante do objeto. Em outros, pode ser indesejada, pois gostaríamos de ter uma versão conexa simplificada da forma. / [en] The computational study of unions of balls has applications in several domains of the Mathematics. The purpose of this dissertation is to propose a simplification of the union of balls in R2 through a movement that obeys the direction of the medial axis in order to simplify it, maintaining the major geometric elements of its shape. The disconnection of the shape is an essential property of the evolution. In some cases, it could mean an important division of the object. In others, it may be undesirable because we would like to have a simplified version connected of this shape.

Malhas simpliciais são utilizadas em várias áreas da Computação Gráfica e Engenharia, como por exemplo, em vizualização, simulação, prototipação, além de outras aplicações. Este tipo de malha é, geralmente, utilizada como aproximações discretas de espaços contínuos, onde eles oferecem representações flexíveis e eficientes. Muito esforço é gasto visando gerar malhas de boa qualidade, porém, em alguns casos as malhas acabam sendo modificadas. Entretanto, este tipo de operação é geralmente custosa e inflexível, o que pode resultar na geraão de malhas bem diferentes das originais. A habilidade de manipular cenas dinâmicas revela-se um dos problemas mais desafiadores da computação gráfica. Este trabalho propõe um método alternativo para atualizar malhas simpliciais que vai além de mudanças geométricas e topológicas. Tal método explora uma das propriedade das Tringulações de Delaunay com Pesos, que permite a usá-las para definir implicitamente as relações de conectividade de uma malha. Ao contrário de manter as informações de conectividade explicitamente, a atual abordagem simplesmente armazena uma coleção de pesos associados a cada vértice. Além disso, criamos um algoritmo para calcular uma Tringulação de Delaunay com Pesos a partir de uma dada triangulação. O algoritmo consiste em uma busca em largura que atribui pesos aos vértices, e uma estratégia de de subdivisão para assegurar que a triangulação reconstruída será correspondente à original. Este método apresenta diversas aplicações e, em particular, permite a criação de um sistema simples de realizar combinação entre triangulações, que será ilustrada com exemplos em 2D e 3D. / Simplicial meshes are used in many fields of Computer Graphics and Engineering, for instance, in visualization, simulation, prototyping, among other applications. This kind of mesh is often used as discrete approximations of continuous spaces, where they offer flexible and efficient representations. Considerable effort is spent in generating good quality meshes, but in some applications the meshes can be modified over time. However, this kind of operation is often very expensive and inflexible, sometimes leading to results very different from the original meshes. The ability to handle dynamic scenes reveals itself as one of the most challenging problems in computer graphics. This work proposes an alternative technique for updating simplicial meshes that undergo geometric and topological changes. It explores the property that a Weighted Delaunay Triangulation (WDT) can be used to implicitly define the connectivity of a mesh. Instead of explicitly maintaining connectivity information, this approach simply keeps a collection of weights associated to each vertex. It consists of an algorithm to compute a WDT from any given triangulation, which relies on a breadth-first traversal to assign weights to vertices, and a subdivision strategy to ensure that the reconstructed triangulation conforms with the original one. This technique has many applications and, in particular, it allows for a very simple method of merging triangulations, which is illustrated with both 2D and 3d examples.

Esta tese teve como objetivo estudar problemas cinéticos de clustering, ou seja, problemas de clustering nos quais os objetos se movimentam. O trabalho se concentrou no caso unidimensional, em que os objetos são pontos se movendo na reta real. Diversas variantes desse caso foram abordadas. Em termos do movimento, consideramos o caso em que cada ponto se move com uma velocidade constante num dado intervalo de tempo, o caso em que os pontos se movem arbitrariamente e temos apenas as suas posições em instantes discretos de tempo, o caso em que os pontos se movem com uma velocidade aleatória em que se conhece apenas o valor esperado da velocidade, e o caso em que, dada uma partição do intervalo de tempo, os pontos se movem com velocidades constantes em cada subintervalo. Em termos do tipo de clustering buscado, nos concentramos no caso em que o número de clusters é um dado do problema e consideramos diferentes medidas de qualidade para o clustering. Duas delas são tradicionais para problemas de clustering: a soma dos diâmetros dos clusters e o diâmetro máximo de um cluster. A terceira medida considerada leva em conta a característica cinética do problema, e permite, de uma maneira controlada, que o clustering mude com o tempo. Para cada uma das variantes do problema, são apresentados algoritmos, exatos ou de aproximação, alguns resultados de complexidade obtidos, e questões que ficaram em aberto. / This work aimed to study kinetic problems of clustering, i.e., clustering problems in which the objects are moving. The study focused on the unidimensional case, where the objects are points moving on the real line. Several variants of this case have been discussed. Regarding the movement, we consider the case where each point moves at a constant velocity in a given time interval, the case where the points move arbitrarily and we only know their positions in discrete time instants, the case where the points move at a random velocity in which only the expected value of the velocity is known, and the case where, given a partition of the time interval, the points move at constant velocities in each sub-interval. Regarding the kind of clustering sought, we focused in the case where the number of clusters is part of the input of the problem and we consider different measures of quality for the clustering. Two of them are traditional measures for clustering problems: the sum of the cluster diameters and the maximum diameter of a cluster. The third measure considered takes into account the kinetic characteristic of the problem, and allows, in a controlled manner, that a cluster change along time. For each of the variants of the problem, we present algorithms, exact or approximation, some obtained complexity results, and open questions.

TEIXEIRA, Daniel Nascimento. Uma técnica de decomposição a priori para geração paralela de malhas bidimensionais. 2014. 95 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2014. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-11T12:51:06Z No. of bitstreams: 1 2014_dis_dnteixeira.pdf: 17919971 bytes, checksum: 092ad12b33cf64a31552e6a839a5a5bc (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-15T12:49:53Z (GMT) No. of bitstreams: 1 2014_dis_dnteixeira.pdf: 17919971 bytes, checksum: 092ad12b33cf64a31552e6a839a5a5bc (MD5) / Made available in DSpace on 2016-07-15T12:49:53Z (GMT). No. of bitstreams: 1 2014_dis_dnteixeira.pdf: 17919971 bytes, checksum: 092ad12b33cf64a31552e6a839a5a5bc (MD5) Previous issue date: 2014 / This work describes a technique of two-dimensional domain decomposition for parallel mesh generation. This technique works for both distributed and shared memory and has the freedom to use any data structure that manages rectangular regions parallel to the axes to decompose the domain given as input, such as a quaternary tree (quadtree) or a binary space decomposition (bsp), for example. Any process of mesh generation that respects the prerequisites established can be used in the subdomains created, for instance, Delaunay or Advancing Front, among others. This technique is called a priori because the mesh on the interface of the subdomains is generated prior to the their internal meshes. The load estimation for each sub-domain in this work is performed with the aid of a refined quadtree, whose level of refinement guides the creation of edges that are defined from the bounderies of only inner cells. This way of estimate load produces results that accurately represent the number of elements to be generated in each subdomain. That contributes to a good partitioning of the domain, making the mesh generation in parallel be significantly faster than the serial generation. Furthermore, the quality of the generated mesh in parallel is qualitatively equivalent to that generated serially within acceptable limits. / Este trabalho descreve uma técnica de decomposição de domínios bidimensionais para geração em paralelo de malhas. Esta técnica funciona tanto para memória distribuída quanto compartilhada, além de permitir que se utilize qualquer estrutura de dados que gere regiões quadrangulares paralelas aos eixos para decompor o domínio dado como entrada. Pode se utilizar por exemplo, uma árvore quaternária (quadtree) ou uma partição binária do espaço (bsp). Além disso, qualquer processo de geração de malha que respeite os pré-requisitos estabelecidos pode ser empregado nos subdomínios criados, como as técnicas de Delaunay ou Avanço de Fronteira, dentre outras. A técnica proposta é dita a priori porque a malha de interface entre os subdomínios é gerada antes das suas malhas internas. A estimativa de carga de processamento associada a cada subdomínio é feita nesse trabalho com a ajuda de uma quadtree refinada, cujo nível de refinamento orienta a criação das arestas que são definidas a partir da discretização das fronteiras das células internas. Essa maneira de estimar carga produz resultados que representam, com boa precisão, o número de elementos a serem gerados em cada subdomínio. Isso contribui para um bom particionamento do domínio, fazendo com que a geração de malha em paralelo seja significativamente mais rápida do que a geração serial. Além disso, a qualidade da malha gerada em paralelo é qualitativamente equivalente àquela gerada serialmente, dentro de limites aceitáveis.

VIEIRA, Rafael Siqueira Telles. Técnicas para geração de malhas de quadriláteros convexos e sua aplicação em reservatórios naturais. 2011. 169 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2011. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-12T15:46:11Z No. of bitstreams: 1 2011_dis_rstvieira.pdf: 3132905 bytes, checksum: e4b5cfff20b3d685dc1674c91df9babc (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-21T15:26:34Z (GMT) No. of bitstreams: 1 2011_dis_rstvieira.pdf: 3132905 bytes, checksum: e4b5cfff20b3d685dc1674c91df9babc (MD5) / Made available in DSpace on 2016-07-21T15:26:34Z (GMT). No. of bitstreams: 1 2011_dis_rstvieira.pdf: 3132905 bytes, checksum: e4b5cfff20b3d685dc1674c91df9babc (MD5) Previous issue date: 2011 / This work describes four methods implemented to achieve a convex quadrilaterization of the two- -dimensional space that may have polygonal lines or holes. Two of these methods, midpoint and ortoquad make use of guide elements, the centroid of a region or the locus of maximum tangent circles inside a geometry, to produce a mesh for the domain. The other two methods, triquad and incremental quadrilatezation use a implicit and explicit triangulation while combining elements in pairs to generate a mesh. All these methods are made through domain decomposition which assure quadrilaterization at the end, since the domain is always partitioned at each iteration. These techniques are compared by a criterion of geometry and topology in order to make clear its advantages and disadvantages and as means of promoting future improvements. The techniques are applied to some samples, including a natural reservoir, in order to view its operation in a real environment or near reality according to the sample used. Also it intends to present throughout this work the requirements, according to the experience with the theme of this author, to develop a technique for quadrilateral mesh generation. / Esta dissertação descreve quatro métodos implementados para realizar uma quadrilaterização convexa do espaço bidimensional que pode conter linhas poligonais ou buracos. Dois destes métodos, ponto médio e ortoquad, utilizam de elementos guia, o baricentro de uma região ou o locus de círculos máximos tangentes e internos a geometria, para produzir uma malha conforme o domínio. Os outros dois, triquad e quadrilaterização incremental, utilizam de uma triangulação explícita e implícita combinando elementos aos pares para realizar a geração da malha. Todas as técnicas são feitas por decomposição de regiões o que garante uma quadrilaterização final, já que o domínio é sempre segmentado a cada iteração. Estas técnicas são comparadas por um critério de geometria e topologia de forma a tornar evidentes suas vantagens e desvantagens assim como promover melhorias futuras. As técnicas são aplicadas a alguns exemplos, incluindo-se um reservatório natural, a fim de exibir seu funcionamento em um ambiente real ou próximo do mesmo, conforme as amostras utilizadas. Também se pretende apresentar ao longo deste trabalho os requisitos necessários, segundo a experiência deste autor com o tema, para o desenvolvimento de uma técnica de geração de malha quadrilateral.

[pt] Este trabalho situa-se numa das linhas de pesquisa da PUC-Rio de projeto de unidades flutuantes tais como, navios e plataformas semi-submersíveis. Nesta linha de pesquisa estão sendo desenvolvidos os programas gráficos MG (Mesh Generator) e o Sstab. O primeiro programa é um modelador geométrico por meio de seções transversais e gerador de malhas para modelos de estruturas flutuantes. O segundo programa é utilizado para a análise de estabilidade estática dos modelos gerados pelo MG. Este trabalho propõe um ambiente integrado de modelagem e de análise estática e dinâmica de estruturas flutuantes. O principal diferencial deste ambiente está no fato de possibilitar a geração automática de variantes de um determinado modelo padrão, a fim de atingir uma configuração desejada, seja no aspecto geométrico ou com relação a sua estabilidade estática. Este ambiente faz uso da linguagem Lua e é possível definir variáveis globais para serem utilizadas como parâmetros de modelagem que extraem, ou modificam, dados como comprimento, largura, altura etc. É possível parametrizar um modelo qualquer, em função de variáveis escolhidas pelo usuário, o que possibilita uma modelagem automática, com a variação de alguns destes parâmetros. Foram ainda desenvolvidas algumas ferramentas auxiliares que facilitam a modelagem de uma estrutura flutuante. Estas ferramentas verificam a consistência topológica de uma malha, gerar uma subdivisão gradativa das curvas cortadas e simplificar as novas malhas geradas. É possível também detectar se o modelo possui simetria num determinado plano e realizar, de forma automática, cortes do modelo final para diferentes calados. / [en] This work is related to the PUC-Rio research area of vessel´s designs such as ships and semi-sub platforms. In this research area two softwares have been developed: MG and Sstab. The first is a geometric modeler based on cross sections and also on a mesh generator; the second is a software for the analysis of static and dynamic stability of MG models. This work proposes an integrated environment for modeling, and static and dynamic analysis of vessels. The main advantage of the proposed environment is that it is possible to obtain automatically variants of a specific model in order to achieve a desired configuration, not only in relation to geometry but also concerning the static stability aspect. This environment uses the Lua programming language and it is possible to define global variables to be used as parameters which retrieve or modify modeling values such as length, width, height, and so on. Any model can be parameterized, as a function of user chosen variables, which allows an automatic modeling with the variation of those parameters. There has been also developed some auxiliary tools which help the modeling of floating structures. Those tools verify the topological consistency of a mesh, generate a gradual subdivision of intersected curves and simplify the new generated meshes. They are also able to detect if the model has symmetry in relation to a certain plane, and sections can be automatically obtained according to different draughts.