Re: [obm-l] Re: Funcao Distancia
On Sat, Jan 24, 2004 at 05:54:11PM -0200, [EMAIL PROTECTED] wrote: Nicolau escreveu: 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. Atentando, para as considerações físicas sobre o problema feitas por Nicolau em e-mail anterior (fazer vários furos em uma cartolina, amarrar os barbantes que passam pelos furo entre si em um nó sobre a cartolina, a um peso abaixo da cartolina e soltar o peso) começei a pensar em uma outra maneira de resolver. O nó fica em uma posição de equilíbrio estável que é um atrator, isto é, se mexermos no nó ele volta para o equilíbrio. Isto é verdade quando existe um único mínimo local (que também é global) e já mostrei na outra mensagem que isto ocorre *exceto* no caso de todos os furos estarem em uma linha reta. Intuitivamente, parece que no equilíbrio as trações no fio são todas iguais (não verifiquei ainda). Claro, todas são iguais ao peso (mg, não é massa) dos pesos pendurados. Isto supondo que o nó não está justo acima de um furo. Se for verdade então os ângulos devem ser todos iguais também (senão a soma das forças no ponto não dá zero). No caso de três furos isto está correto. Ou melhor, está certo no caso de três furos se os ângulos internos forem menores do que 120 graus. No caso de mais de de três furos não está certo. Ora! Isso acontece no triângulo equilátero (os ângulos são todos 120 graus) a menos que um dos ângulos seja 120 graus. Daí várias idéias novas surgem pra tentar a solução. Se tivermos quatro furos nos vértices de um retângulo (não quadrado), o ponto desejado é o centro do retângulo. É fácil ver que as forças somam zero mas os quatro ângulos não são iguais. Uma delas, meio geométrica, é procurar para cada segmento o lugar geométrico dos ângulos de 360/n que tem dois pontos no segmento (um círculo) e achar a intersecção de todos tais círculos para todos os segmentos. Tem que ser um ponto só! Senão tem falha no raciocínio e isso só iria funcionar para triângulos. []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 =
RE: [obm-l] Re: Funcao Distancia
Este problema eh mesmo um tanto complicado para se achar uma solucao analitica. Mas eh facil de programar para usar um algoritmo de otimizacao. Dah para resolver numa planilha Excvel. Interessante que o problema fica simples se quisermos achar o ponto do plano, ou do espaco tridimensional, ou mesmo de um espaco de n3 dimensoes que minimize a soma dos quadrados das distancias a m pontos fixos. Neste caso, cada uma das coordenadas do ponto solucao eh simplesmente a media aritmetica das coordenadas dos pontos fixos. Uma mudanca que aparentemente complicaria, torna o problema bem mais simples. Artur = 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 =
Re: [obm-l] Re: Funcao Distancia
Nicolau escreveu: 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. Atentando, para as considerações físicas sobre o problema feitas por Nicolau em e-mail anterior (fazer vários furos em uma cartolina, amarrar os barbantes que passam pelos furo entre si em um nó sobre a cartolina, a um peso abaixo da cartolina e soltar o peso) começei a pensar em uma outra maneira de resolver. O nó fica em uma posição de equilíbrio estável que é um atrator, isto é, se mexermos no nó ele volta para o equilíbrio. Intuitivamente, parece que no equilíbrio as trações no fio são todas iguais (não verifiquei ainda). Se for verdade então os ângulos devem ser todos iguais também (senão a soma das forças no ponto não dá zero). Ora! Isso acontece no triângulo equilátero (os ângulos são todos 120 graus) a menos que um dos ângulos seja 120 graus. Daí várias idéias novas surgem pra tentar a solução. Uma delas, meio geométrica, é procurar para cada segmento o lugar geométrico dos ângulos de 360/n que tem dois pontos no segmento (um círculo) e achar a intersecção de todos tais círculos para todos os segmentos. Tem que ser um ponto só! Senão tem falha no raciocínio e isso só iria funcionar para triângulos. To tentando provar as considerações acima. alguém quiser contribuir fique a vontade :) -- Ronaldo L. Alonso _ Voce quer um iGMail protegido contra vírus e spams? Clique aqui: http://www.igmailseguro.ig.com.br Ofertas imperdíveis! Link: http://www.americanas.com.br/ig/ = 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 =
Re: [obm-l] Re: Funcao Distancia
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 =
Re: [obm-l] Re: Funcao Distancia
On Thu, Jan 22, 2004 at 06:12:09PM -0200, Nicolau C. Saldanha wrote: 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. Desculpem, cometi um erro tipográfico aqui. Deveria, é claro, ser 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. []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 =
