Geometria de distâncias: Explorando com álgebra linear

Abstract

Neste trabalho, analisamos a solução do Molecular Distance Geometry Problem (MDGP) com distâncias exatas usando a Decomposição de Valores Singulares (SVD, do inglês Singular Value Decomposition). O MDGP consiste em determinar as posições dos átomos de uma molécula, no espaço tridimensional, a partir de um conjunto de distâncias entre eles. Quando todas as distâncias são conhecidas, o problema pode ser resolvido em tempo polinomial. Caso contrário, é um problema NP-difícil.

In this work, we analyse the solution to the Molecular Distance Geometry Problem (MDGP), with exact distances, using the Singular Value Decomposition (SVD). The MGDP consists in estimating the positions of atoms in a molecule, given their pairwise distances. When all such distances are known, the problem can be solved in polynomial time. Otherwise, it is an NP-Hard problem.