Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/306801
Type: TESE
Title: Explorando a dualidade em geometria de distâncias
Title Alternative: Exploring the duality on distance geometry
Author: Rezende, Germano Abud de, 1977-
Advisor: Lavor, Carlile Campos, 1968-
Abstract: 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
Subject: Geometria de distâncias
Estrutura molecular
Distância euclidiana
Algoritmos branch-and-prune
Editor: [s.n.]
Date Issue: 2014
Appears in Collections:IMECC - Dissertação e Tese

Files in This Item:
File SizeFormat 
Rezende_GermanoAbudde_D.pdf1.38 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.