Re: [obm-l] Re: Funcao Distancia

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

On Thu, Jan 22, 2004 at 05:17:20PM -0200, ronaldogandhi@ig.com.br wrote:
>    Ontem a noite estava raciocinando sobre o problema citado, isto 
> é, dados n pontos no plano, p1=(x1,y1),p2=(x2,y2),...,pn=(x3,y3) 
>  achar um ponto p cuja soma das distâncias aos 
> pontos dados seja mínima. 
> 
>    Comecei a tentar uma solucão da seguinte forma: 
> 
>     Podemos sem perda de generalidade, 
> considerar que todas as distâncias consideradas são >= 1 
> (Porque se forem menores que 1 podemos aplicar 
> uma homotetia na figura e obter uma figura semelhante e após achar 
> p=(x,y) aplicar a homotetia inversa). 
>     Neste caso, seja d1 a distancia de p a p1, d2 a distancia de p a p2 
> e assim por diante.  A questão que  coloco é: 
> 
>     Temos que minimizar a funcão d(x,y) = 
> d1+d2+...+dn.  Como as distâncias são 
> todas maiores que 1 minimizar d seria equivalente a minimizar 
> d*d = d1*d1 + d2*d2 +...+dn*dn ? 

Não é equivalente. Como você verificou abaixo o ponto que minimiza
a soma dos quadrados das distâncias é o baricentro, que não tem
muito a ver com o ponto pedido. Se você quer um exemplo que deixe isto
totalmente claro tome p1 = (0,0), p2 = (8,0), p3 = (10,0).
Defina f1(x,y) = d((x,y),p1) + d((x,y),p2) + d((x,y),p3) e
f2(x,y) = d^2(...) + d^2(...) + d^2(...).
Depois de algumas simplificações você pode escrever
f2(x,y) = 3(x-6)^2 + 3y^2 + 56
que obviamente assume seu valor mínimo em (6,0).
f2(6,0) = 6^2 + 2^2 + 4^2 = 56 > f2(8,0) = 8^2 + 0^2 + 2^2 = 68 mas
f1(6,0) = 6 + 2 + 4 = 12 > f1(8,0) = 8 + 0 + 2 = 10.

> (estou no linux e não consigo o acento circunflexo..) 

Não sei em que o linux pode atrapalhar em escrever ^.
Você usa xmodmap? Mas podemos discutir isto fora da lista...

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