MATRIZES DE DISTÂNCIAS EUCLIDIANAS

Abstract

O problema de geometria de distâncias (PGD) consiste emdeterminar a posição de um conjunto de objetos em um dado espaço euclidiano, com base nas distâncias conhecidas entre alguns pares desses objetos. Este problema, que encontra aplicações em bioquímica, robótica, estatística e telecomunicações, está intimamente relacionado ao conceito de matrizes de distâncias euclidianas. Este trabalho apresenta um algoritmo de reconstrução sequencial que, explorando submatrizes de distâncias euclidianas de uma matriz de distâncias possivelmente incompleta, é capaz de resolver uma classe particular de PGDs que satisfazem certas hipóteses. Também estuda-se um algoritmo de reordenação do conjunto de objetos capaz de encontrar, quando existente, uma ordem que satisfaça as hipóteses necessárias ao algoritmo de reconstrução. Experimentos numéricos mostram que os algoritmos propostos são eficientes e apresentam boa precisão na reconstrução de conjuntos com milhares de pontos com base em uma lista incompleta de distâncias.