In this work, we focus on two kinds of problems involving the proximity of geometric objects. The first part revolves around intersection detection problems. In this setting, we are given two (or more) geometric objects and we are allowed to preprocess them. Then, the objects are translated and rotated within a geometric space, and we need to efficiently test if they intersect in these new positions. We develop representations of convex polytopes in any (constant) dimension that allow us to perform this intersection test in logarithmic time.In the second part of this work, we turn our attention to facility location problems. In this setting, we are given a set of sites in a geometric space and we want to place a facility at a specific place in such a way that the distance between the facility and its farthest site is minimized. We study first the constrained version of the problem, in which the facility can only be place within a given geometric domain. We then study the facility location problem under the geodesic metric. In this setting, we consider a different way to measure distances: Given a simple polygon, we say that the distance between two points is the length of the shortest path that connects them while staying within the given polygon. In both cases, we present algorithms to find the optimal location of the facility.In the process of solving facility location problems, we rely heavily on geometric structures called Voronoi diagrams. These structures summarize the proximity information of a set of ``simple'' geometric objects in the plane and encode it as a decomposition of the plane into interior disjoint regions whose boundaries define a plane graph. We study the problem of constructing Voronoi diagrams incrementally by analyzing the number of edge insertions and deletions needed to maintain its combinatorial structure as new sites are added. / Option Informatique du Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Submitted by Filipe dos Santos (fsantos@pucsp.br) on 2017-01-16T12:35:28Z No. of bitstreams: 1 Amarildo Aparecido dos Santos.pdf: 9999509 bytes, checksum: 9b5820ce340fffab20cf08990a404b53 (MD5) / Made available in DSpace on 2017-01-16T12:35:28Z (GMT). No. of bitstreams: 1 Amarildo Aparecido dos Santos.pdf: 9999509 bytes, checksum: 9b5820ce340fffab20cf08990a404b53 (MD5) Previous issue date: 2016-11-25 / Secretaria da Educação do Estado de São Paulo - SEE / This research aims to explore the construction of regular convex polyhedra in Cabri-3D as a possible didactic transposition on the construction of polyhedral surfaces developed by Euclid (300 BC), transformed to a current language, and verifying if this construction presents the necessary relations for the development of formulas for the volume measure calculation of these polyhedra. We oriented ourselves by the following question of research: Does the construction of regular polyhedra by Euclid method propitiate the measure calculation of their volumes as well as the composition and decomposition of dodecahedron and the icosahedron? The theorical referencial is based on the notion of Didatic Transposition and the Ecological Problematic of Yves Chevallard and the Registry of Durval’s Semiotics Representation specifically on the sequential, perceptive, operative and discursive apprehensions, in addition to the four ways of seeing (to look) the pictures in function of the roles that they perform in the activities of geometry: the botanical, the topographer geometer, the constructor and inventor-woodworker. The research is of qualitative nature of documental type because it is based on the reading, analysis and interpretation of Book XIII, the Elements of Euclid, that approach the construction of the regular tetrahedron, regular hexahedron, regular octahedron, regular dodecahedron and the regular icosahedron. The procedures are developed in three parts. On the first part we explored the constructions proposed by Euclid and we adapted them so that they could be constructed with the tools in the environment of Cabri-3D dynamic representation, and we noted that every regular convex polyedra can be constructed in this environment. On the second part we explored the constructions accomplished and search relations and measures that allow to deduce formulas for the volume measure calculation of these polyhedra, in function of the measure of their edges, as much as in function of spheres diameter measure that circumscribe them. The dynamism of the software favoured the visualization of these relations and measures. On the third part we searched the necessary conditions to determine if the pentagon based pyramid can or cannot be part of a regular dodecahedron, as well as the conditions for a tetrahedron can or cannot compound a regular icosahedron. From the determination of these conditions we could propose the construction of these two polyhedron by composition in Cabri-3D and deduct a formula for the volume measure calculation by the volume measure of one of the pyramids that compose it. Thus, we believe that our question was answered and the hypothesis raised during the research were validated, conducting ourselves to develop, futurely, a sequel for its education / Esta pesquisa tem por objetivo explorar a construção dos poliedros regulares convexos, no Cabri-3D como uma possível transposição didática interna da construção de superfícies poliédricas desenvolvidas por Euclides (300 a.C), transformado suas orientações para uma linguagem atual, e verificando se essa construção apresenta as relações necessárias para o desenvolvimento de fórmulas para o cálculo da medida do volume desses poliedros. Nos orientamos pela seguinte questão de pesquisa: a construção de poliedros regulares pelo método de Euclides propicia o cálculo da medida de seus volumes bem como a composição e decomposição do dodecaedro e do icosaedro? O referencial teórico está baseado na noção de Transposição Didática e a Problemática Ecológica de Yves Chevallard e nos Registro de Representação Semiótica de Duval especificamente nas apreensões sequencial, perceptiva, operatória e discursiva, além das quatro maneiras de ver (olhar) as figuras em função do papel que elas desempenham nas atividades de geometria: o botânico, o topógrafo geômetra, o construtor e o inventor-marceneiro. A pesquisa é de natureza qualitativa do tipo documental porque está baseada na leitura, análise e interpretação do livro XIII, de Elementos de Euclides que aborda as construções do tetraedro regular, hexaedro regular, octaedro regular, dodecaedro regular e do icosaedro regular. Os procedimentos são desenvolvidos em três partes. Na primeira parte exploramos as construções propostas por Euclides e as adaptamos para que pudessem ser construídas com as ferramentas do ambiente de representação dinâmica Cabri-3D, e constatamos que todos os poliedros regulares convexos podem ser construídos nesse ambiente. Na segunda parte exploramos as construções realizadas e buscamos relações e medidas que permitiram deduzir fórmulas para o cálculo da medida do volume desses poliedros, tanto em função da medida de suas arestas, quanto em função da medida do diâmetro das esferas que os circunscrevem. O dinamismo do software favoreceu a visualização dessas relações e medidas. Na terceira parte buscamos as condições necessárias para determinar se uma pirâmide de base regular pentagonal pode ou não fazer parte de um dodecaedro regular, bem como as condições para que um tetraedro possa compor ou não um icosaedro regular. A partir da determinação dessas condições pudemos propor a construção desses dois poliedros, por composição no Cabri-3D e deduzir uma fórmula para o cálculo da medida de seu volume a partir da medida do volume de uma das pirâmides que o compõe. Assim, consideramos que nossa questão foi respondida e as hipóteses levantadas durante o trabalho foram validadas nos conduzindo a desenvolver, futuramente, uma sequência para seu ensino

Made available in DSpace on 2015-03-03T15:36:13Z (GMT). No. of bitstreams: 1 OdilonJS_DISSERT.pdf: 1624865 bytes, checksum: f08c3087f93d38a7f0eca20c25b43940 (MD5) Previous issue date: 2014-03-31 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / In this paper we analyze the Euler Relation generally using as a means to visualize the fundamental idea presented manipulation of concrete materials, so that there is greater ease of understanding of the content, expanding learning for secondary students and even fundamental. The study is an introduction to the topic and leads the reader to understand that the notorious Euler Relation if inadequately presented, is not sufficient to establish the existence of a polyhedron. For analyzing some examples, the text inserts the idea of doubt, showing cases where it is not fit enough numbers to validate the Euler Relation. The research also highlights a theorem certainly unfamiliar to many students and teachers to research the polyhedra, presenting some very simple inequalities relating the amounts of edges, vertices and faces of any convex polyhedron, which clearly specifies the conditions and sufficient necessary for us to see, without the need of viewing the existence of the solid screen. And so we can see various polyhedra and facilitate understanding of what we are exposed, we will use Geogebra, dynamic application that combines mathematical concepts of algebra and geometry and can be found through the link http://www.geogebra.org / Neste trabalho, analisamos a Rela??o de Euler de uma maneira geral, utilizando, como meios de visualiza??o, a manipula??o de materiais concretos, a fifim de que haja maior facilidade na percep??o do conte?do, expandindo a aprendizagem aos alunos de n?vel m?dio e at? fundamental. O estudo faz uma introdu??o ao tema e leva o leitor a entender que a Rela??o de Euler, se apresentada de maneira inadequada, n?o ? sufificiente para determinar a exist?ncia de um poliedro. Pois, analisando alguns exemplos, o texto insere a id?ia de d?vida, mostrando casos onde n?o ? sufificiente encaixar n?meros que validem a Rela??o de Euler. A pesquisa destaca ainda um teorema, certamente desconhecido de muitos alunos e professores que pesquisam sobre os poliedros, apresentando algumas inequa??es muito simples, relacionando as quantidades de arestas, v?rtices e faces de qualquer poliedro convexo, as quais definem de forma precisa as condi??es sufificientes e necess?rias para que possamos constatar, sem a necessidade da visualiza??o, a exist?ncia do s?lido em tela. E para que possamos visualizar v?rios poliedros e facilitar a compreens?o do que estamos expondo, utilizaremos o Geogebra, aplicativo de matematica din?mica que combina conceitos de geometria e alg?bra e pode ser encontrado por meio do link http://www.geogebra.org