Orientador: Carlile Campos Lavor / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-25T18:42:28Z (GMT). No. of bitstreams: 1
Rezende_GermanoAbudde_D.pdf: 1418033 bytes, checksum: 61d29b02274278ede5ffca797e26371a (MD5)
Previous issue date: 2014 / Resumo: A geometria de distâncias é o estudo da geometria baseado no conceito de distância. Ela é útil em várias aplicações, onde os dados de entrada consistem de um conjunto incompleto de distâncias, e a saída é um conjunto de pontos no espaço euclidiano, que realiza as distâncias dadas. No Problema de Geometria de Distâncias (DGP), é dado um inteiro K > 0 e um grafo simples, não direcionado, G = (V,E,d), cujas arestas são ponderadas por uma função não negativa d. Queremos determinar se existe uma função (realização) que leva os vértices de V em coordenadas no espaço euclidiano K-dimensional, satisfazendo todas as restrições de distâncias dadas por d. Um DGPk (com K fixado) está fortemente relacionado a um outro tipo de problema, que trata dos possíveis completamentos de uma certa matriz de distâncias euclidianas. Este último pode ser visto, em um certo sentido, como o "dual do primeiro problema". Neste trabalho, exploramos essa dualidade com a finalidade de propor melhorias no método Branch-and-Prune aplicado a uma versão discreta do DGPk / Abstract: Distance Geometry is the study of geometry based on the concept of distance. It is useful in many applications where the input data consists of an incomplete set of distances, and the output is a set of points in some Euclidean space which realizes the given distances. In the Distance Geometry Problem (DGP), it is given an integer K > 0 and a simple undirected weighted graph G = (V,E,d), whose edges are weighted by a non-negative function d. We want to determine if there is a (realization) function that associates the vertices of V with coordinates of the K-dimensional Euclidean space satisfying all distance constraints given by d. A DGPk (with K fixed) is closely related to another type of problem, which treats the possible completions of a certain Euclidean distance matrix. In some sense, this is the "dual" of the first problem. We explore this duality in order to improve the Branch-and-Prune method applied to a discrete version of the DGPk / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.unicamp.br:REPOSIP/306801 |
| Date | 25 August 2018 |
| Creators | Rezende, Germano Abud de, 1977- |
| Contributors | UNIVERSIDADE ESTADUAL DE CAMPINAS, Lavor, Carlile Campos, 1968-, Martínez Pérez, José Mario, Tomei, Carlos, Lodwick, Weldon Alexandre, Mucherino, Antonio |
| Publisher | [s.n.], Universidade Estadual de Campinas. Instituto de Matemática, Estatística e Computação Científica, Programa de Pós-Graduação em Matemática Aplicada |
| Source Sets | IBICT Brazilian ETDs |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Format | 85 p. : il., application/pdf |
| Source | reponame:Repositório Institucional da Unicamp, instname:Universidade Estadual de Campinas, instacron:UNICAMP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0024 seconds