Terry P wrote: > In a triangle ABC, the sides a,b,c are given, then a point D on side BC is > taken and length AD is given, Now i have to choose E and F on AB and AC such > that triangle DEF has got minimum perimeter. > > The problem > > You are given a triangle *ABC*, specified by the sides *BC*, *CA*, and > *AB*and a point > *D* on *BC*, specified by the length *AD* (if 2 such points are possible, > dont worry, they both give the same answer). You are to find the smallest > perimeter of a triangle *DEF* such that *E* lies on *AB* and *F* lies on *AC > *.
I do not know if there is a direct geometric solution to this problem. Giving this problem a cursory glance I was not able to find one. However, analytically, the problem appears to be simply some vectors and calculus. If x and y are free running variables, the distance can be seen as is: d(x,y) = | A-D + x*BA | + | A-D + y*CA | + | x*BA - y*CA | with the length of a vector being the square root of the dot product of the vector with itself (here E is A+x*BA and F is A+y*CA). So we can take the derivative of d(x,y) with respect to x then y and set it to 0 as usual. I haven't gone through the details but this will get you two equations that express x and y in terms of each other. So it will boil down to trying to solve those. (I have not gone through the math myself, but I know they have a lot of reciprocal square roots in them.) If it turns out that such equations cannot be solved directly, then you can use it to form an iterative solution. I.e., pick random x and y's (perhaps starting each at 0.5) then iteratively pick new x and y's which result from solving each of the two derivative equations one at a time. This will have the effect of always decreasing the perimeter with each new x and y chosen, and you can hand wave about convergence. If it turns out that solving for x and y in *each* derivative is too difficult, you can use Newton's method to approximate the solution -- in fact since this is just an iterative approximation method in the first place, you only need to run the Newton's iteration method once. Its work, and its annoying, but it certainly seems doable. -- Paul Hsieh http://www.pobox.com/~qed/ http://bstring.sf.net/ --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
