[pt] Apresenta-se nesta dissertação um novo algoritmo para o cálculo de algumas funções distância entre polígonos convexos, no caso geral em que os polígonos podem se interseptar, cuja complexidade linear de pior caso é melhor do que a dos algoritmos até então conhecidos na literatura. O algoritmo é baseado em um algoritmo de complexidade linear originalmente proposto para determinação da distância de Hausdorff entre polígonos convexos disjuntos e utiliza como sua principal componente um algoritmo linear para o cálculo da interseção entre polígonos convexos. A motivação para o estudo de algoritmos eficientes para este problema de cálculo de distâncias decorre de aplicações em reconhecimento de formas e superposição ótima de contornos. Resultados computacionais também são apresentados. / [en] We present in this dissertation a new algorithm for the computation of some distance functions between convex polygons, in the general case where they can intersect, whose worst case time complexity is better than of the previously known algorithms. The algorthm is based on an algorithm originally proposed for the computation of the Hausdorff distance between disjoint polygons and uses as its main component a linear time algorithm for finding the intersection of convex polygons. The motivation for the study of efficient algorithms for this distance computation problem comes from applications in pattern recognition and contour fitting. Computatioal results are also presented.

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.

No description available.

No description available.

No description available.

By studying self-avoiding polygons (SAPs) in (L, M )-tubes (a tubular sublattice of the simple cubic lattice) as a sequence of 2-spans, transfer matrices can be used to obtain theoretical and numerical results for these SAPs. As a result, asymptotic properties of these SAPs, such as pattern densities in a random SAP and the expected span of a random SAP, can be calculated directly from these transfer matrices. These same results can also be obtained for compact polygons, as well as SAPs under the influence of an external force (called compressed or stretched polygons). These results can act as tools for examining the entanglement complexity of SAPs in (L, M )-tubes. In this thesis, it is examined how transfer matrices can be used to develop these tools. The transfer matrix method is reviewed, and previous transfer matrix results for SAPs in (L, M )-tubes, as well as SAPs subjected to an external force, are presented. The transfer matrix method is then similarly applied to compact polygons, where new results regarding compact polygons are obtained, including proofs for a compact concatenation theorem and for a compact pattern theorem. Also in this thesis, transfer matrices are actually generated (via the computer) for relatively small tube sizes. This is done for the general case of SAPs in (L, M )-tubes, as well as for the compact and external force cases. New numerical results are obtained directly from these transfer matrices, and a new algorithm for generating polygons is also developed from these transfer matrices. Compact polygons are actually generated (via the computer) for relatively small tube sizes and spans by using the developed polygon generation algorithm, and new numerical results for pattern densities and limiting free energies are obtained for stretched and compressed polygons.

The purpose of this study was to increase the student's understanding of the measures of area and perimeter of polygons. The goal of the project was to create a supplemental geometry unit to develop the concept of the area and perimeter of a polygon without the use of formulas and numbers and to measure the effectiveness of this unit on student understanding. Two high school geometry classes with under 28 students each participated in this study.

Made available in DSpace on 2015-03-26T13:45:34Z (GMT). No. of bitstreams: 1 texto completo.pdf: 1893968 bytes, checksum: ce37a1814e775a74aa222b17583fdc19 (MD5) Previous issue date: 2012-02-28 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This dissertation aims to study two topics related to modern topology and geometry. The first of these themes is dedicated to the study of packaging and record covering spheres in the hyperbolic plane, in which we treat the study results due to Bavard (1996) [3]. The second issue that was addressed refers to the study of edges pairing for irregular polygons. In this part we try to expose an example, created during our studies, for a pairing that generates a tiling of the hyperbolic plane by an irregular polygon. Also use the techniques developed by Mercio Botelho Faria, Catarina Mendes de Jesus and Panteleón D. R. Sanchez in [14] to obtain matching of edges of regular polygons through surgeries in surfaces associated with trivalent graphs. / Esta dissertação tem como objetivo o estudo de dois temas ligados a topologia e a geometria moderna. O primeiro destes temas é dedicado ao estudo de empacotamento e coberturas de discos do plano hiperbólico, no qual tratamos de estudar resultados devidos a Bavard (1996) [3]. Já o segundo tema que foi abordado se refere ao estudo de emparelhamento de arestas para polígonos irregulares. Nesta parte tratamos de expor um exemplo, criado durante nossos estudos, para um emparelhamento que gera um ladrilhamento do plano hiperbólico por um polígono irregular. Além disso utilizamos as técnicas desenvolvidas por Mercio Botelho Faria, Catarina Mendes de Jesus e Panteleón D. R. Sanchez em [14] para obtermos emparelhamentos de arestas de polígonos regulares por meio de cirurgias em superfícies associadas a grafos trivalentes.

No description available.

Wireless devices and applications have been an unavoidable part of human lives in the past decade. In the past few years, the global mobile data traffic has grown considerably and is expected to grow even faster in future. Given the fact that the number of wireless nodes has significantly increased, the contention and interference on the license-free industrial, scientific, and medical band has become severer than ever. Cognitive radio nodes were introduced in the past decade to mitigate the issues related to spectrum scarcity. In this dissertation, we focus on the interference and performance analysis of networks coexisting with cognitive radio networks and address the design and analysis of spectrum allocation and routing for cognitive radio networks. Spectrum allocation enables nodes to construct a link on a common channel at the same time so they can start communicating with each other. We introduce a new approach for the modeling and analysis of interference and spectrum allocation schemes for cognitive radio networks with arbitrarily-shaped network regions. First, for the first time in the literature, we propose a simple and efficient approach that can derive the distribution of the distance between an arbitrary interior/exterior reference point and a random point within an arbitrary convex/concave irregular polygon. This tool is essential in analyzing important distance-related performance metrics in wireless communication networks. Second, considering the importance of interference analysis in cognitive radio networks and its important role in designing spectrum allocation schemes, we model and analyze a heterogeneous cellular network consisting of several cognitive femto cells and a coexisting multi-cell network. Besides the cumulative interference, important distance-related performance metrics have been investigated, such as the signal-to-interference ratio and outage probability. Finally, the spectrum allocation and routing problems in cognitive radio networks have been discussed. Considering a wireless cognitive radio network coexisting with a cellular network with irregular polygon-shaped cells, we have used the tools developed in this dissertation and proposed a joint spectrum allocation and routing scheme. / Graduate