On Thu, Jan 22, 2004 at 05:17:20PM -0200, [EMAIL PROTECTED] 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 =========================================================================
