Sobre a Construção de Árvores Geradoras Mínimas em Espaços k-Dimensionais e Problemas Relacionados

O problema de encontrar uma árvore geradora mínima conectando n pontos em um espaço k-dimensional é discutido sob três métricas de distância comuns: Euclidiana, reticulada e L_. Ao empregar uma sub-rotina que resolve o problema do correio, mostramos que, para k fixo 3, tal árvore geradora mínima pode ser encontrada em tempo O (n^2 - a (k) (n) ^1 - a (k) ), onde a (k) = 2^ - (k + 1). O limite pode ser melhorado para O ( (n n) ^1. 8) para pontos em espaço Euclidiano tridimensional. Também obtemos algoritmos o (n²) para encontrar um par mais distante em um conjunto de n pontos e para outros problemas relacionados.