Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/306809
Type: TESE
Title: Geometria de distâncias euclidianas e aplicações
Title Alternative: Euclidean distance geometry and applications
Author: Lima, Jorge Ferreira Alencar, 1986-
Advisor: Lavor, Carlile Campos, 1968-
Abstract: Resumo: Geometria de Distâncias Euclidianas (GDE) é o estudo da geometria euclidiana baseado no conceito de distância. É uma teoria útil em diversas aplicações, onde os dados consistem em um conjunto de distâncias e as possíveis soluções são pontos em algum espaço euclidiano que realizam as distâncias dadas. O problema chave em GDE é conhecido como Problema de Geometria de Distâncias (PGD), em que é dado um inteiro K>0 e um grafo simples, não direcionado, ponderado G=(V,E,d), cujas arestas são ponderadas por uma função não negativa d, e 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. Consideramos tanto problemas teóricos quanto aplicações da GDE. Em termos teóricos, demonstramos a quantidade exata de soluções de uma classe de PGDs muito importante para problemas de conformação molecular e, além disso, conseguimos condições necessárias e suficientes para determinar quando um grafo completo associado a um PGD é realizável e qual o espaço euclidiano com dimensão mínima para tal realização. Em termos práticos, desenvolvemos um algoritmo que calcula tal realização em dimensão mínima com resultados superiores a um algoritmo clássico da literatura. Finalmente, mostramos uma aplicação direta do PGD em problemas de escalonamento multidimensional

Abstract: Euclidean distance geometry (EDG) is the study of Euclidean geometry based on the concept of distance. This is useful in several applications, where the input data consists of an incomplete set of distances and the output is a set of points in some Euclidean space realizing the given distances. The key problem in EDG is known as the Distance Geometry Problem (DGP), where an integer K>0 is given, as well as a simple undirected weighted graph G=(V,E,d), whose edges are weighted by a non-negative function d. The problem consists in determining whether or not there is a (realization) function that associates the vertices of V with coordinates of the K-dimensional Euclidean space, in such a way that those coordinates satisfy all distances given by d. We considered both theoretical issues and applications of EDG. In theoretical terms, we proved the exact number of solutions of a subclass of DGP that is very important in the molecular conformation problems. Moreover, we described necessary and sufficient conditions for determining whether a complete graph associated to a DGP is realizable and the minimum dimension of such realization. In practical terms, we developed an algorithm that computes such realization, which outperforms a classical algorithm from the literature. Finally, we showed a direct application of DGP to multidimensional scaling
Subject: Geometria de distâncias
Matrizes de distâncias euclidianas
Escalonamento multidimensional
Language: Multilíngua
Editor: [s.n.]
Date Issue: 2015
Appears in Collections:IMECC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Lima_JorgeFerreiraAlencar_D.pdf1.08 MBAdobe PDFView/Open


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