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

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] Os desafios de estudar formas levaram matemáticos a criar abstrações, em particular através da geometria diferencial. Porém, formas simples como cubos não se adequam a ferramentas diferenciáveis. Este trabalho é uma tentativa de usar avanços recentes da análise, no caso a teoria das distribuições, para estender quantidades diferenciáveis a objetos singulares. Como as distribuições generalizam as funções e permitem derivações infinitas, substituição das parametrizações de subvariedades clássicas por distribuições poderia naturalmente generalizar as subvariedades suaves. Isso nos leva a definir D-imersões. Esse trabalho demonstra que essa formulação, de fato, generaliza as imersões suaves. Extensões para outras classes de subvariedades são discutidas através de exemplos e casos particulares. / [en] The challenge of studying shapes has led mathematicians to create powerful abstract concepts, in particular through Differential Geometry. However, differential tools do not apply to simple shapes like cubes. This work is an attempt to use modern advances of the Analysis, namely Distribution Theory, to extend differential quantities to singular objects. Distributions generalize functions, while allowing infinite differentiation. The substitution of classical immersions, which usually serve as submanifold parameterizations, by distributions might thus naturally generalize smooth immersion. This leads to the concept of D-immersion. This work proves that this formulation actually generalizes smooth immersions. Extensions to non-smooth of immersions are discussed through examples and specific cases.

Neste trabalho estudamos problemas relacionados com a busca de pontos e segmentos em janelas retangulares com os lados paralelos aos eixos. É dado um conjunto de segmentos (ou pontos) no plano. Em uma primeira fase estes segmentos são organizados em estruturas de dados de tal forma a tornar buscas por aqueles que estão contidos em janelas retangulares mais eficiente. Na segunda fase são dadas as janelas de maneira online. Várias destas estruturas de dados são baseadas em árvores balanceadas, tais como, árvore limite, árvore de busca com prioridade, árvore de intervalos e árvore de segmentos. Na dissertação mostramos detalhadamente estas estruturas de dados e os algoritmos para resolver este problema para conjuntos de pontos (versão unidimensional do problema) e para segmentos no plano, tanto horizontais e verticais como com qualquer orientação (sem cruzamentos). Os algoritmos são analisados de forma rigorosa quanto ao seu uso de espaço e de tempo. Implementamos também os vários algoritmos estudados, construindo uma biblioteca destas estruturas de dados. Apresentamos, finalmente os resultados de experimentos computacionais com instâncias do problema. / In this work we study problems about point and segment query in rectangular windows whose edges are parallel to the axis. Given a set of segments (or points) in the plane. In a first phase these segments are organized in data structures such that queries for segments in windows are done more efficiently. In the second phase windows are given online. The data structures are balanced trees as range tree, priority search tree, interval tree and segment tree. In this master\'s thesis we show in details data structures and algorithms for solving windowing queries to sets of points (unidimensional version of the problem) and of segments in the plane, as horizontal and vertical as any orientation (without crossings). The algorithms are analysed rigorously regarding their space and time used. We implement the algorithms studied, building a library of these data structures. Finally, we present, the results of computational experiments with instances of the problem.

Submitted by Edisangela Bastos (edisangela@ufpa.br) on 2014-01-13T19:57:26Z No. of bitstreams: 2 license_rdf: 23898 bytes, checksum: e363e809996cf46ada20da1accfcd9c7 (MD5) Dissertacao_DesenvolvimentoMetodologiasAutomaticas.pdf: 1143947 bytes, checksum: 8fc7b7409ff57fceb1ecd680a1020795 (MD5) / Approved for entry into archive by Ana Rosa Silva(arosa@ufpa.br) on 2014-01-16T15:16:01Z (GMT) No. of bitstreams: 2 license_rdf: 23898 bytes, checksum: e363e809996cf46ada20da1accfcd9c7 (MD5) Dissertacao_DesenvolvimentoMetodologiasAutomaticas.pdf: 1143947 bytes, checksum: 8fc7b7409ff57fceb1ecd680a1020795 (MD5) / Made available in DSpace on 2014-01-16T15:16:01Z (GMT). No. of bitstreams: 2 license_rdf: 23898 bytes, checksum: e363e809996cf46ada20da1accfcd9c7 (MD5) Dissertacao_DesenvolvimentoMetodologiasAutomaticas.pdf: 1143947 bytes, checksum: 8fc7b7409ff57fceb1ecd680a1020795 (MD5) Previous issue date: 2012 / Neste trabalho, são propostas metodologias para otimização do parâmetro de forma local c do método RPIM (Radial Point Interpolation Method). Com as técnicas apresentadas, é possível reduzir problemas com inversão de matrizes comuns em métodos sem malha e, também, garantir um maior grau de liberdade e precisão para a utilização da técnica, já que se torna possível uma definição semi-automática dos fatores de forma mais adequados para cada domínio de suporte. Além disso, é apresentado um algoritmo baseado no Line Sweep para a geração eficiente dos domínios de suporte. / In this thesis, a methodology is proposed for automatically (and locally) obtaining the shape factor c for the Gaussian basis functions, for each support domain, in order to increase numerical precision and mainly to avoid matrix inversion impossibilities. The concept of calibration function is introduced, which is used for obtaining c. The methodology developed was applied for a 2-D numerical experiment, which results are compared to analytical solution. This comparison revels that the results associated to the developed methodology are very close to the analytical solution for the entire bandwidth of the excitation pulse. The proposed methodology is called in this work Local Shape Factor Calibration Method (LSFCM).

[pt] Pesquisas na área de estrutura de dados são fundamentais para aumentar a generalidade e eficiência computacional da representacão de modelos geometricos. Neste trabalho, apresentamos duas estruturas de dados topológicas escalonáveis, uma para superfícies triânguladas, chamada CHE (Compact Half--Edge), e outra para malhas de tetraedros, chamada CHF (Compact Half--Face). Tais estruturas são compostas de diferentes níveis, que nos possibilitam alterar a quantidade de dados armazenados com objetivo de melhorar sua eficiência computacional. O uso de APIs baseadas no conceito de objeto, e de haran»ca de classes, possibilitam uma interface única para cada função em todos os níveis das estruturas. A CHE e a CHF requerem pouca memória e são simples de implementar já que substituem o uso de ponteiros pelo de contêineres genéricos e regras aritméticas. / [en] Research in data structure area are essential to increase the generality and computational effciency of geometric models` representation. In this work, we present two new scalable topological data structures, one for triangulated surfaces, called CHE (Compact Half { Edge ), and the another for tetrahedral meshes, called CHF (Compact Half { Face ). Such structures are composed of different levels, that enable us to modify the amount of data stored with the objective to improve its computational effciency. The use of APIs based in the object concept and class inheritance, makes possible an unique interface for each function at any level. CHE and CHF requires very few memory and are simple to implement since they substitute the use of pointers by generic containeres and arithmetical rules.

Orientador: Jorge Stolfi [Orientador] / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação. / Made available in DSpace on 2018-08-10T07:43:58Z (GMT). No. of bitstreams: 1 Montagner_ArnaldoJovanini_D.pdf: 2204093 bytes, checksum: 4c9c86ca0312f3b5507e1daa8c6553db (MD5) Previous issue date: 2007 / Resumo: Mapas são subdivisões de espaços topológicos em regiões simples, e triangulações são um tipo específico de mapa em que cada elemento é um simplexo (aresta, triângulo, tetraedro, etc). Neste trabalho, tratamos o problema de representação da topologia de triangulações e mapas de dimensão arbitrária. Estudamos a utilização de uma representação baseada em grafos de arestas coloridas, já utilizada como ferramenta teórica, mas nunca empregada em aplicações práticas. A principal limitação desta representação é a relativa inflexibilidade imposta sobre a manipulação da topologia. Há porém grandes vantagens em sua utilização, como a simplicidade de representação e a generalidade. Este trabalho consiste na especificação teórica de uma estrutura de dados baseada nestes grafos coloridos e de operações topológicas para construção e manipulação da estrutura. A utilização desta estrutura é ilustrada através de algoritmos para resolução de problemas em geometria computacional / Abstract: Maps are subdivisions of topological spaces into simple regions, and triangulations are a specific kind of map wherein each element is a simplex (edge, triangle, tetrahedron, etc). In this work, we analyze the problem of representing the topology of triangulations and maps with arbitrary dimension. We study a representation based on edge-colored graphs, already used as theoretical tool, but never employed in practical applications. The main limitation of this representation is the relative inexibility imposed on the manipulation of topology. There are, though, great advantages in its use, as its simplicity and generality. This work consists in the theoretic specification of a data structure based on these colored graphs and of topological operators to build and manipulate the structure.The use of this structure is illustrated by algorithms for computational geometry problems / Doutorado / Computação Grafica / Mestre em Ciência da Computação

Orientador: Wu Shin-Ting / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-13T23:55:20Z (GMT). No. of bitstreams: 1 Silva_AdlerCardosoGomesda_M.pdf: 2672358 bytes, checksum: 8e9b303b8bebb1d3e1aee1e46e01b4c9 (MD5) Previous issue date: 2007 / Resumo: A simplificação de linha é a operação da generalização cartográfica que remove os detalhes desnecessários de uma linha, preservando os principais aspectos da sua forma. A simplificação consistente de linha preocupa-se tanto em remover estes detalhes, quanto em gerar um mapa que seja consistente.ao original. Um mapa é dito consistente ao original se possuir a mesma topologia que este e conservar espaçamentos entre os seus objetos. Os trabalhos em simplificação consistente presentes na literatura ainda apresentam diversas limitações, das quais se destacam a aplicabilidade restrita a determinados tipos de objetos, a ineficácia na preservação da topologia em certos casos, a ausência da conservação de espaçamentos e o alto custo computacional. Este trabalho propõe uma nova solução para o problema dá simplificação consistente, procurando contornar estas limitações. Do ponto de vista teórico, ele determina um conjunto de condições que se aplicam a todos os tipos de objetos e garantem a consistência do mapa resultante. Do ponto de vista prático, ele apresenta um algoritmo que, com base nestas condições, é capaz de simplificar consistente e eficientemente as linhas de um mapa. O algoritmo proposto tambem apresenta outras características importantes para a simplificação consistente, tais como a capacidade de produzir de mapas independentes de escala e a invariância do mapa resultante em relação à ordem de processamento dos dados de entrada. / Abstract: Line simplification is the cartographic generalization operation that reduces the complexity of a line, while preserving its main shape features. Consistent line simplification involves not only the reduction of the line complexity, but also the consistency between the original and the simplified maps. A map is said to be consistent to the original one, if it preserves the topology and keeps the same proximity relation of the objects. Current works in consistent simplification still present drawbacks, such as the applicability to just certain types of objects, the failure while preserving topology in particular cases, the lack of proximity handling and the high computational cost. To overcome these drawbacks, this work proposes a new way for handling the consistent simplification problem. From the theoretical point of view, it presents a set of conditions applicable to all typesof objects, which guarantees the consistency between the original and simplified maps. From the practical point of view, it presents an algorithm that, based on these conditions, can consistently and efficiently simplify the lines of the original map. The algorithm also presents other important properties to the consistent simplification, such as the capacity of producing scale-independent maps and the ability of yielding the same simplified map for different data arrangements in the original map. / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica