On Wed, Jan 21, 2004 at 07:48:46PM -0200, Eduardo Lourenco Apolinario wrote: > Oi pra todos dessa honrosa lista, > estava resolvendo um problema proposto por um amigo > que dizia o seguinte: dada uma sequencia de n pontos > nalgum plano, ache qual o ponto cuja soma das distancias > para os pontos dados eh minima. > > Nao consegui chegar a algum resultado muito > 'matematico' (com esse sentido quero dizer q n cheguei a > uma formula fechada). > E gostaria d pedir ajuda a vcs na mesma.
Eu não vou dar uma fórmula para o seu problema, mas observe que mesmo para n=3 há dois casos bem diferentes: Se os três pontos p1, p2, p3 formam um triângulo com todos os ângulos internos menores do que 120 graus, o ponto desejado q é o único ponto no interior do triângulo para o qual os ângulos p1-q-p2, p2-q-p3 e p3-q-p1 são todos iguais a +- 120 graus, onde o sinal depende da orientação do triângulo. Se os pontos p1, p2, p3 formam um um triângulo com o ângulo em p1 maior do que 120 graus, q será o próprio p1. Uma maneira "física" de resolver o problema (e de verificar o que eu falei acima) é a seguinte. Tome uma mesa e faça furos nos pontos p1, p2, ..., pn. Passe por cada furo um barbante e amarre na ponta do barbante que fica abaixo da mesa um peso de 1 kg. Amarre todos os n barbantes que ficam acima da mesa em um único ponto, o nó. Agora solte o nó: ele buscará a posição em que a energia potencial dos pesos é mínima, logo aquela em que a soma das distâncias é mínima. Ou seja, o nó acabará parando no ponto que você procura. Mas o ponto de vista matemático é antes de mais nada perguntar se a solução existe e é única. Mais precisamente, seja f: R^2 -> R a função dada por f(q) = f1(q) + ... + fn(q) onde fi(q) = d(q,pi). Eu afirmo que a função f tem um único ponto de mínimo local (logo global) *exceto* se n for par e todos os ponto pi estiverem sobre uma linha reta. Neste caso muito especial, supondo os pontos indexados em ordem de p1 até pn com n = 2m, qualquer ponto no segmento de pm até p(m+1) é um mínimo. Para verificar isso, observe que cada função fi é convexa logo f também é. Assim, f assume seu valor mínimo em um subconjunto convexo Q de R^2. Por outro lado cada fi é estritamente convexa sobre qq segmento que não estiver alinhado com pi. Assim, se o conjunto Q for mais do que um ponto ele contem um segmento e este segmento deve estar alinhado com todos os pontos pi, donde estamos no caso especial que descrevi acima. []s, N. ========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =========================================================================