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.

Submitted by isabela.moljf@hotmail.com (isabela.moljf@hotmail.com) on 2017-07-26T12:43:15Z No. of bitstreams: 1 joaopaulopecanhanavarrodeoliveira.pdf: 20245819 bytes, checksum: 0b6a88d7e0946052431cdb43acc011c3 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-08-08T18:35:21Z (GMT) No. of bitstreams: 1 joaopaulopecanhanavarrodeoliveira.pdf: 20245819 bytes, checksum: 0b6a88d7e0946052431cdb43acc011c3 (MD5) / Made available in DSpace on 2017-08-08T18:35:21Z (GMT). No. of bitstreams: 1 joaopaulopecanhanavarrodeoliveira.pdf: 20245819 bytes, checksum: 0b6a88d7e0946052431cdb43acc011c3 (MD5) Previous issue date: 2012-08-30 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A aproximação de superfícies contínuas através de malhas poligonais é importante em várias áreas do conhecimento. Esse tipo de malha é empregado em aplicações como simulações computacionais de engenharia e física, modelagem geométrica e animações. Os modelos de entrada muitas vezes apresentam baixa qualidade, seja na distribuição de seus elementos ou no alinhamento e forma dos polígonos. Neste trabalho é apresentado um método para recobertura de malhas triangulares dado um comprimento de aresta m. A malha de entrada é uma superfície triangular de variedade-2 com topologia e geometria arbitrária, com ou sem borda. Definido o comprimento de aresta alvo m, o algoritmo remove e insere vértices de acordo com um critério, ajustando a quantidade necessária de elementos que o objeto deve conter. Após esta etapa, o modelo entra em uma fase de relaxamento global utilizando uma variação do operador discreto de Laplace-Beltrami, que na formulação aqui proposta utiliza os k primeiros vizinhos de cada vértice, ao contrário da definição clássica que usa apenas os vizinhos mais próximos. Isto é feito de maneira iterativa até que se esgote o número máximo de iterações fornecido no início do processo. Ao final, tem-se uma malha com comprimento de aresta próximo a m e com baixo desvio padrão, i.e., vértices uniformemente distribuídos sobre o modelo; seus triângulos também tendem a ser equiláteros. Os resultados do remalhamento se mostraram quantitativamente satisfatórios, com baixo desvio padrão do comprimento das arestas. O espaço dual pode ser utilizado para geração de malhas trivalentes, compostas majoritariamente por hexágonos em superfícies de baixa curvatura. / The approximation of continuous surfaces by polygonal meshes is very important in several areas. In recent years we have seen the use of this kind of mesh in various industrial applications such as computer simulations, geometric modeling and animation. Often, the input models have poor quality, i.e., bad elements distribution and inconsistent polygon shape. One important feature of poligonal surfaces is vertex distribution and sometimes it is necessary to control the vertices distance with an uniform edge lentgh. This work presents a method for triangular remeshing given a target edge length m. The input is a 2-manifold triangular surface with arbitrary geometry and topology. The proposed algorithm removes and inserts vertices adjusting the amount of necessary elements. Then, the model enters in a global relaxation process using a variation of Laplace-Beltrami discrete operator, which uses the k nearest neighbors of each vertex. This is done in an iteratively fashion until the algorithm reaches the maximum iteration number. At the end, one have a grid with edge length near to m and low standard deviation (vertices uniformly distributed). The triangles also presents good connectivity and high isotropy; the results shown that our remeshing scheme quantitatively improved the mesh quality. The dual space of the final triangular surface can be used for trivalent remeshing. These models are important for physical simulations of nano-carbon surfaces and we dedicated a chapter of our work to discuss this subject.

Orientadores: Pedro Jussieu de Rezende, Flávio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T08:56:08Z (GMT). No. of bitstreams: 1 Sasaki_AndersonToshiyuki_M.pdf: 1449279 bytes, checksum: 851c64c64afd4605cbfb4946ed5f97a4 (MD5) Previous issue date: 2014 / Resumo: No problema de cobertura mínima por conjuntos (MSC - Minimum Set Cover), são dados um conjunto L de objetos e uma coleção R de conjuntos e deseja-se encontrar uma sub-coleção S de R que seja uma cobertura de L de custo mínimo, ou seja, L está contido na união de todo os conjuntos R de S com a soma dos custos dos conjuntos R de S sendo mínima. Entre as variantes desse problema, existem aquelas advindas de configurações geométricas, em que tanto os elementos de L quanto os conjuntos contidos em R são objetos geométricos. Como tais problemas são, em geral, NP-difíceis, se P ? NP, não é possível encontrar algoritmos exatos de tempo polinomial para os mesmos. Assim, torna-se interessante a busca por algoritmos aproximados eficientes para obtenção de soluções com garantia de qualidade. Nesta dissertação, estudamos diferentes versões do problema de cobertura mínima por discos (MDC ¿ Minimum Disk Cover), em que o conjunto R é um conjunto de discos, e o objetivo é projetar algoritmos aproximados. Tais versões do problema estão relacionadas com a solução de problemas práticos, como o posicionamento de estações-base em projeto de redes sem fio ou de dispositivos em redes de sensores. Para o caso em que o conjunto de objetos geométricos L é constituído de um único segmento de reta no plano, apresentamos um FPTAS. Para outra versão mais geral, na qual o conjunto de objetos geométricos é dado por um sistema de inequações polinomiais algébricas, propomos um algoritmo aproximado, o qual demonstramos ser um PTAS / Abstract: The Minimum Set Cover problem (MSC) can be described as: given a set L of elements and a collection of sets R, find a subcollection S of R that is a minimum-cost covering for L, i.e., L is contained in the union of the sets R in S, and the sum of the costs of the sets R in S is minimum. Among the variants of this problem, there are those that arise from a geometric configuration in which both the elements of L and the sets contained in R are geometric objects. As such problems are, in general, NP-hard, if P ? NP, it is impossible to find polynomial-time exact algorithms for them. Thus, the use of efficient approximation algorithms to find high quality solutions becomes a good approach. In this dissertation, we study different versions of the Minimum Disk Cover problem (MDC), in which the sets in R are disks, and we seek to develop approximation algorithms. These versions are related to practical problems, such as base station positioning problem for wireless network design and placement of devices in a sensor network. For the case in which the set of geometric objects to be covered is given by a single line segment, we present an FPTAS. For a more general case, where the set of geometric objects is given by a system of algebraic polynomial inequalities, we propose an approximation algorithm which we prove to be a PTAS / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientadores: Cid Carvalho de Souza, Pedro Jussieu de Rezende / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T16:57:43Z (GMT). No. of bitstreams: 1 Tozoni_DaviColli_M.pdf: 4212278 bytes, checksum: afb91e202a72e28729ff14334901884f (MD5) Previous issue date: 2014 / Resumo: Nesta dissertação, apresentamos nossa pesquisa sobre o Problema da Galeria de Arte (AGP), um dos problemas mais estudados em Geometria Computacional. O AGP, que é um problema NP-difícil, consiste em encontrar o número mínimo de guardas suficiente para garantir a cobertura visual de uma galeria de arte representada por um polígono. Na versão do problema tratada neste trabalho, usualmente chamada de Problema da Galeria de Arte com Guardas-Ponto, os guardas podem ser posicionados em qualquer lugar do polígono e o objetivo é cobrir toda a região, que pode ou não conter buracos. Nós estudamos como aplicar conceitos e algoritmos de Geometria Computacional, bem como Técnicas de Programação Inteira, com a finalidade de resolver o AGP de forma exata. Este trabalho culminou na criação de um novo algoritmo para o AGP, cuja ideia é gerar, de forma iterativa, limitantes superiores e inferiores para o problema através da resolução de versões discretizadas do AGP, que são reduzidas a instâncias do Problema de Cobertura de Conjuntos. O algoritmo foi implementado e testado em mais de 2800 instâncias, de diferentes tamanhos e classes. A técnica foi capaz de resolver, em minutos, mais de 90% de todas as instâncias consideradas, incluindo polígonos com milhares de vértices, e ampliou em muito o conjunto de casos para os quais são conhecidas soluções exatas. Até onde sabemos, apesar do extensivo estudo do AGP nas últimas quatro décadas, nenhum outro algoritmo demonstrou a capacidade de resolver o AGP de forma tão eficaz como a técnica aqui descrita / Abstract: In this dissertation, we present our research on the Art Gallery Problem (AGP), one of the most investigated problems in Computational Geometry. The AGP, which is a known NP-hard problem, consists in finding the minimum number of guards sufficient to ensure the visibility coverage of an art gallery represented as a polygon. In the version of the problem treated in this work, usually called Art Gallery Problem with Point Guards, the guards can be placed anywhere in the polygon and the objective is to cover the whole region, which may or not have holes. We studied how to apply Computational Geometry concepts and algorithms as well as Integer Programming techniques in order to solve the AGP to optimality. This work culminated in the creation of a new algorithm for the AGP, whose idea is to iteratively generate upper and lower bounds for the problem through the resolution of discretized versions of the AGP, which are reduced to instances of the Set Cover Problem. The algorithm was implemented and tested on more than 2800 instances of different sizes and classes of polygons. The technique was able to solve in minutes more than 90% of all instances considered, including polygons with thousands of vertices, greatly increasing the set of instances for which exact solutions are known. To the best of our knowledge, in spite of the extensive study of the AGP in the last four decades, no other algorithm has shown the ability to solve the AGP as effectively as the one described here / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Hélio Pedrini / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-21T23:01:00Z (GMT). No. of bitstreams: 1 Fazanaro_DaltonIeda_M.pdf: 17180414 bytes, checksum: 024cc06fef1c6ac030cce29037783fd1 (MD5) Previous issue date: 2013 / Resumo: Inicialmente centralizadas na solução de problemas científicos em Dinâmica dos Fluidos, as interfaces evolutivas, com o advento da modelagem mais eficiente e robusta provida pelo método Level Set, expandiram os seus limites originais de aplicabilidade, proporcionando uma nova frente de pesquisa para os campos dos mais diversos, com destaque à Ciência da Computação. Especificamente à área de Processamento de Imagens, os trabalhos até então apresentados, relacionando o Level Set à reconstrução de superfícies tridimensionais, concentram-se na reconstrução a partir de uma nuvem de dados dispersos no espaço; a abordagem baseada em fatias planas paralelas e transversais ao objeto a ser reconstruído evidencia-se ainda incipiente. Esse cenário fomenta, portanto, uma análise da viabilidade do Level Set para a reconstrução de superfícies tridimensionais. Fundamentando-se nessa constatação, a dissertação propõe-se a oferecer uma metodologia que agregue, simultaneamente, as idéias comprovadamente eficientes já publicadas sobre a aproximação em questão e as propostas para contornar as limitações inerentes ao método ainda não satisfatoriamente tratadas, em particular a suavização excessiva de características finas dos contornos em evolução sob o Level Set. Relativamente a esse ponto, o emprego da variante Particle Level Set é sugerido como uma possível solução, por sua intrínseca capacidade comprovada para a conservação de massa ou volume de fronteiras dinâmicas traduzirem-se, presumivelmente, em um controle ao problema destacado. Ao final, conjuntos de dados sintéticos e reais são utilizados para avaliar a metodologia de reconstrução de superfícies tridimensionais apresentada qualitativamente / Abstract: Evolving interfaces were initially focused on solutions to scientific problems in Fluid Dynamics. With the advent of the more efficient and robust modeling provided by Level Set method, their original boundaries of applicability were extended, offering a new front of research to the more diverse fields, especially to Computer Science. Specifically to Image Processing area, the works published until then, relating Level Set to tridimensional surface reconstruction, centered themselves on reconstruction from a data cloud dispersed in space; the approach based on parallel planar slices transversal to the object to be reconstructed is still incipient. Therefore, this scenario foments a feasibility analysis of Level Set to the reconstruction of tridimensional surfaces. Basing on this fact, this dissertation proposes to offer a methodology that simultaneously integrates the proved efficient ideas already published about such approximation and the proposals to process the inherent limitations of the method not satisfactorily treated yet, in particular the excessive smoothing of fine characteristics of contours evolving under Level Set. In relation to this, the application of the variant Particle Level Set is suggested as a possible solution, for its intrinsic proved capability to preserve mass or volume of dynamic fronts manifests itself, presumably, into a control of the stressed problem. At the end, synthetic and real data sets are used to evaluate the presented tridimensional surface reconstruction methodology qualitatively / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Submitted by Reginaldo Soares de Freitas (reginaldo.freitas@ufv.br) on 2018-06-06T18:51:26Z No. of bitstreams: 1 texto completo.pdf: 10760567 bytes, checksum: e11aa8ab3d3f98f215de81a9ce967fcc (MD5) / Approved for entry into archive by Reginaldo Soares de Freitas (reginaldo.freitas@ufv.br) on 2018-06-06T18:51:49Z (GMT) No. of bitstreams: 1 texto completo.pdf: 10760567 bytes, checksum: e11aa8ab3d3f98f215de81a9ce967fcc (MD5) / Approved for entry into archive by Reginaldo Soares de Freitas (reginaldo.freitas@ufv.br) on 2018-06-06T18:52:00Z (GMT) No. of bitstreams: 1 texto completo.pdf: 10760567 bytes, checksum: e11aa8ab3d3f98f215de81a9ce967fcc (MD5) / Made available in DSpace on 2018-06-06T18:52:08Z (GMT). No. of bitstreams: 1 texto completo.pdf: 10760567 bytes, checksum: e11aa8ab3d3f98f215de81a9ce967fcc (MD5) Previous issue date: 2017-11 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This thesis presents an exact parallel algorithm for computing the intersection be- tween two 3D triangular meshes, as used in CAD/CAM (Computer Aided De- sign/Computer Aided Manufacturing), CFD (Computational Fluid Dynamics), GIS (Geographical Information Science) and additive manufacturing (also known as 3D Printing). Geometric software packages occasionally fail to compute the correct result because of the algorithm implementation complexity (that usually needs to handle several special cases) and of precision problems caused by floating point arithmetic. A failure in an intersection computation algorithm may propagate to any software using the algorithm as a subroutine. As datasets get bigger (and the chances of failure in an inexact algorithm increase), exact algorithms become even more important. While other methods for exactly intersecting meshes exist, their performance makes them non-suitable for applications where the fast processing of big geometric models is important (such as interactive CAD systems). The key to obtain robustness and performance is a combination of 5 separate techniques: • Multiple precision rational numbers, to exactly represent the coordinates of the objects and completely eliminate roundoff errors during the computations. • Simulation of Simplicity, a symbolic perturbation technique, to ensure that all geometric degeneracies (special cases) are properly handled. • Simple data representations and local information, to simplify the correct pro- cessing of the data and make the algorithm more parallelizable. • A uniform grid, to efficiently index the data, and accelerate some of the steps of the algorithm such as testing pairs of triangles for intersection or locating points in the mesh. / Só foram apresentados título e resumo em inglês.

[pt] A confiabilidade dos dados coletados diretamente ao longo do caminho de poços de petróleo é maior que a confiabilidade de dados sísmicos e, por isto, os primeiros podem ser utilizados para ajustar o volume de aquisição sísmica. Este trabalho propõe um ajuste dos volumes de amplitudes sísmicas através de uma algoritmo de três passos. O primeiro passo é a identificação de feições comuns através de um algoritmo de reconhecimento de padrões. O segundo passo consiste em gerar e otimizar uma malha alinhada às feições de interesse do dado sísmico voluméletrico através de um novo algoritmo baseado em processamento de imagens e inteligência computacional. E o terceiro e último passo é a realização de uma deformação volumétrica pontoa- ponto usando interpolação por funções de base radial para registrar o volume sísmico aos poços. A dissertação apresenta ainda resultados de implementações 2D e 3D dos algoritmos propostos de forma a permitir algumas conclusões e sugestões para trabalhos futuros. / [en] Data acquired directly from borehole are more reliable than seismic data, and then, the first can be used to adjust the second. This work proposes the correction of a volume of seismic amplitudes through a three step algorithm. The first step is the identification of common features in both sets using a pattern recognition algorithm. The second step consists of the generation and the optimization of a mesh aligned with the features in the volumetric data using a new algorithm based on image processing and computational intelligence. The last step is the seismic-to-well registration using a point-to-point volumetric deformation achieved by a radial basis function interpolation. The dissertation also presents some results from 2D and 3D implementations allowing conclusions and suggestions for future work.

Orientadores: Cid Carvalho de Souza, Pedro Jussieu de Rezende / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-26T19:18:58Z (GMT). No. of bitstreams: 1 Crepaldi_BrunoEspinosa_M.pdf: 13275684 bytes, checksum: aa236e6a56dd7ed5507276017c51b8fb (MD5) Previous issue date: 2014 / Resumo: Considerado uma variação do problema da galeria de arte, o problema do posicionamento de antenas trata do posicionamento do menor número de antenas requerido para determinar se uma pessoa está dentro ou fora da galeria. Uma antena propaga uma chave única dentro de um ângulo específico de transmissão, de modo que o conjunto de chaves recebidas em um dado ponto do plano seja suficiente para decidir se ele pertence ou não ao polígono que representa a galeria. Para verificar esta propriedade de localização, uma fórmula Booleana deve ser produzida junto com o posicionamento de antenas. Dizemos que as antenas estão em posição natural se elas estão localizadas nos vértices ou nas arestas do polígono e transmitindo sinal no ângulo formado pelos lados deste último no ponto onde a antena está posicionada. O problema do posicionamento natural de antenas é NP-difícil. Nesta dissertação, apresentamos um algoritmo exato para resolvê-lo. Para tanto, propomos um modelo inicial de programação linear inteira para o problema que, ao ser computado por um resolvedor comercial, se mostrou capaz de encontrar soluções ótimas de instâncias correspondentes a polígonos com algumas dezenas de vértices. Em seguida, através de estudos de propriedades geométricas, são introduzidas várias melhorias no modelo matemático e também na forma de computá-lo. Como consequência desta pesquisa, desenvolvemos um algoritmo iterativo baseado em programação linear inteira com o qual conseguimos solucionar o problema para instâncias consideravelmente maiores. A eficiência do nosso algoritmo é certificada por resultados experimentais que compreendem as soluções ótimas de 720 instâncias de até 1000 vértices, incluindo polígono com buracos, as quais foram calculadas em menos de seis minutos em um computador desktop padrão / Abstract: Considered a variation of the art gallery problem, the wireless localization problem deals with the placement of the smallest number of broadcasting antennas required to determine if someone is inside or outside the gallery. Each antenna propagates a unique key within a certain antenna-specific angle of broadcast, so that the set of keys received at any given point is sufficient to determine whether that point is inside or outside the polygon that represents the gallery. To ascertain this localization property, a Boolean formula must be produced along with the placement of the antennas. We say that the antennas are in natural position if they are located at the vertices or the edges of the polygon and transmitting their signals in the angle formed by the sides of the polygon at the point where the antenna is positioned. The natural wireless localization problem is NP-hard. In this dissertation, we present an exact algorithm to solve it. To this end, we propose an initial integer linear programming model for the problem that, after being computed by a commercial solver, proved to be capable of finding optimal solutions for instances corresponding to polygons with tens of vertices. Then, through studies of geometric properties, several improvements are introduced in the mathematical model and also in the way of computing it. As a result of this research, we develop an iterative algorithm based on integer linear programming with which we can solve the problem for considerably larger instances. The efficiency of our algorithm is certified by experimental results comprising the solutions of 720 instances, including polygon with holes with up to 1000 vertices, in less than six minutes on a standard desktop computer / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientadores: Cid Carvalho de Souza, Pedro Jussieu de Rezende / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-26T19:27:17Z (GMT). No. of bitstreams: 1 Brandt_AlexFernando_M.pdf: 1939918 bytes, checksum: c6d9d34f314830d07dc1e49ad43ab514 (MD5) Previous issue date: 2014 / Resumo: Seja P um conjunto de pontos no plano. O grafo geométrico de P, G(P) = (P, E), é o grafo ponderado completo cujos vértices correspondem aos pontos de P e no qual o custo de uma aresta {i, j} é dado pela distância Euclidiana entre os pontos i e j. Inicialmente, considere um problema genérico em que se quer construir uma rede com boa qualidade de conexão ligando um conjunto de locais representados por pontos no plano. Em muitas aplicações deste tipo, o problema pode ser modelado com o auxílio de um grafo geométrico. Isso ocorre quando, por exemplo, para um par de pontos, a medida de qualidade é definida como a razão entre o comprimento do menor caminho que os conecta na rede projetada e a respectiva distância Euclidiana. Esta razão determina a dilatação daquele par de pontos na rede. Já a dilatação da rede construída em si é dada pela dilatação máxima sobre todos os pares de pontos. Nesta dissertação apresentamos métodos exatos para resolução dos problemas dedicados a encontrar uma árvore geradora ou uma triangulação planar de dilatação mínima, denominados, respectivamente, Problema da Árvore Geradora de Dilatação Mínima (MDSTP) e Problema da Triangulação de Dilatação Mínima (MDTP). Os métodos descritos são compostos principalmente pela formulação, redução e resolução de programas lineares inteiros mistos. A redução do tamanho destes modelos matemáticos é feita explorando-se a geometria dos problemas por meio de rotinas que determinam a presença ou da ausência de certos elementos da formulação em soluções com dilatação menor ou igual ao limitante primal fornecido por uma heurística. A aplicação destas rotinas em uma fase de pré-processamento permite uma redução significativa do tamanho do modelo levando à aceleração do seu tempo de resolução. Com a combinação destas técnicas obteve-se, pela primeira vez, soluções comprovadamente ótimas de instâncias até 20 pontos para o MDSTP e até 70 pontos para o MDTP. Os problemas e suas formulações, bem como suas formas de redução e de resolução, são apresentados em detalhes. Além disso, são feitas análises de desempenho computacional não só dos métodos exatos, mas também de algoritmos propostas por outros autores / Abstract: Let P be a set of points in the plane. The geometric graph of P, G(P) =(P, E), is the complete weighted graph whose vertices correspond to the points of P and in which the cost of an edge {i, j} is given by the Euclidean distance between the points i and j. Initially, consider a general problem where one wants to build a network with good connection quality joining a set of sites represented by points in the plane. In many applications of this kind, the problem can be modeled with the aid of a geometric graph. This occurs when, for example, for a pair of points, the quality measure is defined as the ratio of the length of the shortest path that connects them in the designed network and their Euclidean distance. This ratio determines the dilation of that pair of points in the network. On the other hand, the dilation of the built network itself is given by the maximum dilation over all pair of points. In this dissertation we present exact methods for solving problems dedicated to finding a spanning tree or a planar triangulation of minimum dilation, named, respectively, the Minimum Dilation Spanning Tree Problem (MDSTP) and Minimum Dilation Triangulation Problem (MDTP). The described methods are composed primarily by the formulation, downsizing and resolution of mixed integer linear programs. The downsizing of these mathematical models is done by exploiting the geometry of the problems by means of routines that determine the need of the presence or the absence of certain elements of the formulation in solutions with dilation less than or equal to the primal bound supplied by a heuristic. Applying these routines in a pre-processing phase allows a significant reduction of the model size leading to the acceleration of its resolution time. With the combination of these techniques, for the first time, proven optimal solutions of instances with up to 20 points for the MDSTP and up to 70 points to the MDTP were obtained. The problems and their formulations, as well as ways of reducing and solving them, are presented in detail. Furthermore, analyzes of computational performance not only of the exact methods, but also of algorithms proposed by other authors are made / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientadores: Pedro Jussieu de Rezende, Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-26T19:09:30Z (GMT). No. of bitstreams: 1 Zambon_MauricioJosedeOliveira_M.pdf: 2774684 bytes, checksum: 1d0ed1f5c1ae01b7646e4bffea6a3736 (MD5) Previous issue date: 2014 / Resumo: Nesta dissertação, apresentamos a primeira abordagem algorítmica e os primeiros resultados experimentais da literatura para tratamento do Problema Cromático Discreto da Galeria de Arte (DCAGP). Trata-se de um problema de natureza geométrica que consiste de uma variante do clássico Problema da Galeria de Arte. Neste, deseja-se encontrar um conjunto de guardas com cardinalidade mínima que consiga vigiar toda uma dada galeria. Já no DCAGP temos por objetivo obter um conjunto de observadores que cubra a galeria e que admita uma coloração válida com o menor número de cores. Uma coloração é válida se dois observadores que veem um mesmo ponto recebem cores distintas. Abordamos a resolução deste problema através de duas abordagens: uma exata e uma heurística. Inicialmente, apresentamos uma heurística primal que fornece limitantes superiores de boa qualidade e, em seguida, um modelo de programação linear inteira para resolução exata do DCAGP. Este método foi capaz de resolver todas as instâncias de um extenso conjunto de galerias, representadas por polígonos simples aleatoriamente gerados, de até 2500 vértices, em menos de um minuto. Já num outro conjunto de instâncias onde a representação inclui polígonos com buracos e polígonos fractais de von Koch com até 800 vértices, o método encontrou soluções comprovadamente ótimas para 80% das instâncias em menos de 30 minutos. No contexto dessas soluções, discutimos o uso de lazy-constraints e de técnicas de fortalecimento do modelo, assim como uma breve análise da dificuldade das instâncias. Reportamos ainda resultados da utilização de relaxação Lagrangiana, para obtenção de bons limitantes, principalmente superiores, e também resultados obtidos por meio de uma variação da técnica relax-and-fix. Finalmente, discutimos um processo de branch-and-price para resolução exata do DCAGP / Abstract: In this dissertation, we present the first algorithmic approach and the first experimental results in the literature for solving the Discrete Chromatic Art Gallery Problem (DCAGP). This problem is geometric in nature and consists of a variation of the classic Art Gallery Problem. In the latter, we want to find a minimum cardinality guard set that is able to watch over a given gallery. On the other hand, in the DCAGP, the objective is to find a set of watchers that covers the gallery and admits a valid coloring with a minimum number of colors. A coloring is valid if two watchers that observe a same point are assigned different colors. To solve this problem we apply two approaches: an exact and a heuristic one. Firstly, we present a primal heuristic able to provide good quality upper bounds, and subsequently an integer programming model that yields exact solutions for the DCAGP. This method was able to solve all instances from an extensive set of galleries, represented by randomly generated simple polygons, of up to 2500 vertices, in less than one minute. On another set of instances, where the representation includes polygons with holes and fractal von Koch polygons, with up to 800 vertices, this method found proven optimal solutions for 80% of the instances in less than 30 minutes. In the context of these solutions, we discuss the use of lazy constraints and techniques for strengthening the model, besides a brief analysis of the hardness of the instances. Moreover, we report on results obtained through a Lagrangian relaxation, mainly as a means to obtain good upper bounds, as well as from a variation of the relax-and-fix technique. Lastly, we discuss a branch-and-price process for solving the DCAGP to exactness / Mestrado / Ciência da Computação / Mestre em Ciência da Computação