Orientador: Pedro Jussieu de Rezende / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-19T10:53:17Z (GMT). No. of bitstreams: 1 Fileto_Renato_M.pdf: 3121262 bytes, checksum: a6037b4da4c9e84f67c253e598cf0cce (MD5) Previous issue date: 1994 / Resumo: o tema central deste trabalho é a pesquisa de soluções para problemas de busca em subespaços (range search), sob o enfoque de projeto de algoritmos eficientes e geometria computacional, considerando objetos de dados em forma de pontos dispersos num espaço multidimensional e explorando diversos formatos de subespaços de busca encontrados na literatura. O objetivo é reunir diversas formulações e métodos de solução em um compêndio, onde estes são descritos sob uma mesma ótica, com notação uniforme e de forma mais simples que nos textos originais, de modo a facilitar um estudo mais detalhado e comparações, no que diz respeito à natureza e ao funcionamento das soluções. Pretende-se com isso tornar as idéias provenientes da pesquisa atualmente em processo na área de algoritmos acessíveis de forma mais integrada e simples, tanto aos interessados na pesquisa de métodos mais eficientes e adequados para problemas em teoria da computação, quanto àqueles mais interessados na aplicação dessas idéias. Um estudo abrangente das soluções encontradas na literatura permite perceber diversas semelhanças de concepção nos métodos empregados. Freqüentemente, pode-se observar a ocorrência de abordagens e técnicas comuns em diversas situações. A estas abordagens e técnicas de aplicação geral atribuímos o nome de paradigmas de algoritmos. O estudo e a utilização de paradigmas de algoritmos possibilitam um certo grau de sistematização das soluções de problemas de busca em subespaços, uma vez que eles permitem encarar diversas soluções distintas, de diversas variações do problema como manifestações de um mesmo fundamento racional. Alem disso, o estudo de paradigmas é instrutivo, pois promove o desenvolvimento de raciocínios sistemáticos, aplicáveis na resolução de diversos problemas em computação. A divisão do conteúdo é efetuada de maneira a fornecer primeiro o fundamento: teórico, necessário à compreensão dos métodos de solução, que são tratados posteriormente. No capítulo 1, são fornecidos os conceitos e classificações básicos, relativos a problemas de busca em geral e particularmente busca em subespaços, a fim de prover uma fundamentação teórica e situar a área de estudo.. No capítulo 2, são descritos alguns paradigmas de algoritmos aplicados a problemas de busca em subespaços, com o intuito de prover ao leitor maneiras alternativaS de relacionar as soluções apresentadas posteriormente, induzindo-o a desenvolver raciocínios que lhe habilitem a perceber os fundamentos e técnicas em comum. Nos capítulos 3 a 6, são abordados os sub.problemas caracterizados pelos formatos clássicos de subespaços de busca encontrados na literatura, ordenados da maneira que parece mais conveniente e que reflete a complexidade das soluções, a natureza das mesmas e sua evolução histórica. Em cada um destes capítulos, os sub-problemas são discutidos em detalhes, algumas soluções e limites inferiores são descritos superficialmente e há uma seção de notas bibliográficas, com referências para assuntos específicos. Finalmente, no capítulo 7, são sintetizadas as contribuições do trabalho e relacionados alguns assuntos para possíveis extensões no futuro. / Abstract: The main, objective of this work is the study of solutions found in the literature to range search, from the view point of algorithm design and computational geometry, considering only data objects; in the form of points embedded1 in a multidimensional space, and investigating various shapes of ranges. Several formulations and solutions to range search problems are surveyed. These are described under one abstract view, with uniform notation and in a form hopefully clearer than, the original sources, in such way that comparisons of the nature and functionality of the solutions and more detailed studies may be facilitated. Our purpose is to make the ideas deriving from the research on range search available in a more integrated and simpler way, to people interested in the discovery of more suitable and. efficient methods for problems in theoretical computer science as well as to those interested in the applications of these ideas. A wide study of the solutions found in the literature shows many conceptual similarities in the employed methods. Frequently, the same approaches and' techniques are seen in distinct situations. These general purpose approaches and techniques are called "algorithm paradigms". The study and application of these paradigms allow a certain level of generalization of the solutions to range search problems, because they allow one to perceive several solutions of vario1ls instances of a general problem as the manifestation of the same rationale. The study of algorithm paradigms is instructive in its own right, since it propitiates the development of systematic reasoning, useful in the solution of many problems in computer science. The contents herein are arranged so as to first give the theoretical basis necessary to understanding the methods given later. In chapter 1, we provide the basic concepts and classifications related to search problems in general and to range search in particular, and establish the scope of our research. In chapter 2, we describe some algorithm paradigms applied to range search problems, with the purpose of supplying the reader with alternative ways of establishing connections among the solutions presented later leading him to develop a reasoning that allows the identification of the fundamentals and techniques shared by tile sol1itions. In, chapters 3 to 6, we deal with the variations of' the range search problem characterized by the classical shapes of ranges considered in the literature. These chapters are arranged in a convenient way in order to reflect the complexity ofthe discussed solutions, their nature and the historical evolution. In each one of these chapters the problems are discussed in detail, some solutions and lower bounds are briefly described and bibliographic notes containing references to specific subjects are presented. Finally, in chapter 7, we summarize the contributions of this work and extensions that can be undertaken in the future. / Mestrado / Mestre em Ciência da Computação

Orientador: Pedro Jussieu de Rezende / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-23T09:53:10Z (GMT). No. of bitstreams: 1 Pinto_GuilhermeAlbuquerque_M.pdf: 5255697 bytes, checksum: 2472502cd1a3a5e723109ff1ab4c7029 (MD5) Previous issue date: 1998 / Resumo: Esta dissertação discute diagramas de Voronoi no plano projetivo orientado, um espaço geométrico que propicia vantagens computacionais tanto na representação quanto na construção dos diagramas. Esses diagramas, resumidamente, agregam informação de proximidade para um conjunto de objetos no espaço e estão entre as estruturas mais estudadas na Geometria Computacional com aplicações em diversas ciências. Apresentamos um algoritmo incremental simples, baseado somente no conceito de orientação, para construir o diagrama de pontos e, também, o de pontos com peso aditivo. Esse último e algumas outras generalizações do diagrama de Voronoi possuem arcos de cônicas entre suas arestas. Para obter a visualização dos diagramas, estudamos as cônicas naquele espaço e propomos uma representação para arcos que unifica as três classes de cônicas afins no plano. O trabalho se. completa com a implementação do algoritmo e o aprimoramento de dois visualizadores para os modelos plano e esférico do plano projetivo orientado, com a inclusão de cônicas, que permite a completa visualização dos diagramas / Abstract: This dissertation discusses Voronoi diagrams on the oriented projective plane, a geometric space which gives computational advantages in the representation as well as in the construction of the diagrams. These diagrams, in short, aggregate proximity information for a set of objects in the space and are among the best studied structures in Computational Geometry with applications in several sciences. We present a simple incremental algorithm, based only on the concept of orientation, to construct the diagram of points and, also, the additively weighted diagram. The latter and some other generalizations of the Voronoi diagram include conic arcs among their edges. To achieve the visualization of the diagrams, we study the conics in that space and propose a representation for arcs that unifies the three classes of affine conics in the plane. The work also includes the implementation of the algorithm and the update of two visualizers for the planar and spherical models of the oriented projective 'plane, in order to include conics, that allow for the complete visualization of the diagrams and the advantages of this geometric space / Mestrado / Mestre em Ciência da Computação

Orientador: Pedro J. de Rezende / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-27T11:37:24Z (GMT). No. of bitstreams: 1 Harada_MarioMassato_D.pdf: 3022260 bytes, checksum: d986f7b618ffda2df880a2454f96cc07 (MD5) Previous issue date: 2000 / Doutorado / Doutor em Ciência da Computação

Orientador: Wu Shin Ting / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica / Made available in DSpace on 2018-07-29T05:45:43Z (GMT). No. of bitstreams: 1 Bernardes_MarceloCordeiro_M.pdf: 2722326 bytes, checksum: 223fb6c7c79bbbe255f4fd138107e7d2 (MD5) Previous issue date: 1996 / Resumo: Buscando a melhor ia do desempenho do projetista e qualidade das curvas geradas, propõe-se que seja inserida uma camada de abstração e interface com o projetista - Interface Esperta. Esta Interface Esperta permite que o projetista trabalhe no nível semântico (geométrico ou subjetivo) das curvas, sem preocupar-se com o nível sintático (valores de parâmetros de ajuste). Para tanto, conceitos geométricos como curvatura e evoluta são utilizados para propor uma nova spline - C-spline. Na modelagem da subjetividade os conjuntos nebulosos são a palavra chave / Abstract: In searching for the improvement of the designer's efficiency and the quality of the generated curves, it is proposed to introduce an interface between the users and the underlying system - a Smart Layer. This layer allows that the designer works with the semantics of the curves (geometric or imprecise) without worrying on its syntaxe (their parameter values). To achieve it, we suggest a new class of curves based on geometric concepts such as curvature and evolute. We name it as C-splines. In order to model the subjectivity the fuzzy sets are employed. / Mestrado / Mestre em Engenharia Elétrica

Orientador: Siome Klein Goldenstein / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-14T02:23:56Z (GMT). No. of bitstreams: 1 Goes_FernandoFerraride_M.pdf: 31957234 bytes, checksum: c369081bcbbb5f360184a1f8467839ea (MD5) Previous issue date: 2009 / Resumo: Em computação gráfica, diversos problemas consistem na análise e manipulação da geometria de superfícies. O operador Laplace-Beltrami apresenta autovalores e autofunções que caracterizam a geometria de variedades, proporcionando poderosas ferramentas para o processamento geométrico. Nesta dissertação, revisamos as propriedades espectrais do operador Laplace-Beltrami e propomos sua aplicação em computação gráfica. Em especial, introduzimos novas abordagens para os problemas de segmentação semântica e geração de atlas em superfícies / Abstract: Many applications in computer graphics consist of the analysis and manipulation of the geometry of surfaces. The Laplace-Beltrami operator presents eigenvalues and eigenfuncitons which caracterize the geometry of manifolds, supporting powerful tools for geometry processing. In this dissertation, we revisit the spectral properties of the Laplace-Beltrami operator and apply them in computer graphics. In particular, we introduce new approaches for the problems of semantic segmentation and atlas generation on surfaces / Mestrado / Computação Grafica / Mestre em Ciência da Computação