Re: [obm-l] Funcao distancia

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

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
=========================================================================