Algoritmos Distribuı́dos
UFMG/ICEx/DCC
2a Lista de Exercı́cios
Pós-Graduação em Ciência da Computação
2o Semestre de 2009
Observações:
• Data de entrega: 4/11/2009
• Qualquer linguagem de programação pode ser usada.
• Na documentação a ser entregue, descreva o que foi feito e os conceitos utilizados.
Algoritmo distribuı́do para o “Par de Pontos mais Próximo”
The closest pair of points problem or closest pair problem is a problem of computational
geometry: given n points in the d-dimensional metric space, find a pair of points with the smallest
distance between them. Its two-dimensional version, for points in the plane, was among the first
geometric problems which were treated at the origins of the systematic study of the computational
complexity of geometric algorithms. (Fonte: Wikipedia, http://en.wikipedia.org/wiki/Closest_
pair_of_points_problem)
A figura 1 mostra um exemplo de um conjunto de pontos no plano e o par mais próximo.
Figura 1: Par de pontos mais próximo
Proponha um algoritmo distribuı́do assı́ncrono para ao final da execução todos os nós saberem qual é o par de
pontos mais próximos. Um exemplo de aplicação desse algoritmo é quando num ambiente distribuı́do, dois nós
devem ser escolhidos para fazerem uma tarefa de acordo com um critério, que neste caso é a proximidade, mas
que poderia ser um outro qualquer.
O que fazer:
1. Implemente na sua linguagem de programação favorita, considerando que existem n pontos (n ≤ 100) no
plano numa região quadrada L delimitada pelas coordenadas (0, 0) e (1000, 1000). As coordenadas devem
ser fornecidas de um arquivo a partir da entrada padrão, onde a primeira linha tem o valor de n e as n
linhas seguintes as coordenadas de cada ponto.
2. Visualize a saı́da do seu programa na forma de um conjunto de pontos e o par mais próximo de forma
destacada, como na figura 1.